Extremal Optimization: Methods Derived from Co-Evolution

摘要

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