A Simulated Annealing-Based Multiobjective Optimization Algorithm: AMOSA

Sanghamitra Bandyopadhyay, Sriparna Saha, Ujjwal Maulik, Kalyanmoy Deb

IEEE Transactions on Evolutionary Computation · 2008 · 835 citations · 32 references

Concepts

TL;DR

The authors propose a simulated annealing–based multiobjective optimization algorithm that uses an archive to generate a set of trade‑off solutions. The algorithm determines acceptance probability by evaluating the domination status of candidate solutions relative to the current solution and the archive, using a domination measure and includes a complexity analysis. Extensive experiments demonstrate that the proposed algorithm outperforms two well‑known MOEAs on five performance metrics across diverse test problems, achieving superior results on many‑objective instances and outperforming a recent real‑coded simulated annealing method.

Abstract

This paper describes a simulated annealing based multiobjective optimization algorithm that incorporates the concept of archive in order to provide a set of tradeoff solutions for the problem under consideration. To determine the acceptance probability of a new solution vis-a-vis the current solution, an elaborate procedure is followed that takes into account the domination status of the new solution with the current solution, as well as those in the archive. A measure of the amount of domination between two solutions is also used for this purpose. A complexity analysis of the proposed algorithm is provided. An extensive comparative study of the proposed algorithm with two other existing and well-known multiobjective evolutionary algorithms (MOEAs) demonstrate the effectiveness of the former with respect to five existing performance measures, and several test problems of varying degrees of difficulty. In particular, the proposed algorithm is found to be significantly superior for many objective test problems (e.g., 4, 5, 10, and 15 objective problems), while recent studies have indicated that the Pareto ranking-based MOEAs perform poorly for such problems. In a part of the investigation, comparison of the real-coded version of the proposed algorithm is conducted with a very recent multiobjective simulated annealing algorithm, where the performance of the former is found to be generally superior to that of the latter.

References

32