Simulated annealing and greedy search for multi-objective optimisation

Abstract

Simulated annealing generalises greedy or elitist search methods by permitting states which are not an improvement over previous solutions, and for single-objective problems these exploratory moves permit escape from local minima. We examine two classes of multi-objective simulated annealing algorithm: those in which a single solution comprises the state and those in which a set of mutually non-dominating solutions form the state. We compare ways of determining the `energy' of the state in simulated annealing, including the dominated volume and we relate the greedy versions of these annealers (zero computational temperature) to well-established multi-objective optimisation algorithms. Empirical tests on the DTLZ test problems show that (a) a single solution state is often more efficient than a set-based state; and (b) that exploratory algorithms are out-performed by their greedy counterparts. These results lead to an examination of the role of local fronts. Problems for which the Pareto front cannot be located via a sequence of infinitesimal perturbations are defined to be noninfinitesimally greedy searchable. We present examples of non-infinitesimally greedy searchable test problems, which are nonetheless searchable using finite perturbations, but which may be adjusted to be arbitrarily hard even with large finite perturbations.