Simulated annealing and greedy search for multi-objective optimisation
Everson, Richard M.; Fieldsend, Jonathan E.; Smith, Kevin I.
Date: 2009
Publisher
University of Exeter
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 ...
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.
Computer Science
Faculty of Environment, Science and Economy
Item views 0
Full item downloads 0