Extremal Optimization: Methods derived from Co-Evolution

arXivmath/9904056MaRDI QIDQ6501273FDOQ6501273

Authors: Stefan Boettcher, Allon G. Percus 

Abstract: We describe a general-purpose method for finding high-quality solutions to hard optimization problems, inspired by self-organized critical models of co-evolution such as the Bak-Sneppen model. The method, called Extremal Optimization, successively eliminates extremely undesirable components of sub-optimal solutions, rather than ``breeding better components. In contrast to Genetic Algorithms which operate on an entire ``gene-pool of possible solutions, Extremal Optimization improves on a single candidate solution by treating each of its components as species co-evolving according to Darwinian principles. Unlike Simulated Annealing, its non-equilibrium approach effects an algorithm requiring few parameters to tune. With only one adjustable parameter, its performance proves competitive with, and often superior to, more elaborate stochastic optimization procedures. We demonstrate it here on two classic hard optimization problems: graph partitioning and the traveling salesman problem.

This page was built for publication: Extremal Optimization: Methods derived from Co-Evolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6501273)