Extremal Optimization: Methods derived from Co-Evolution

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.

arXiv comment8 pages, Latex, 5 ps-figures included. To appear in ``GECCO-99: Proceedings of the Genetic and Evolutionary Computation Conference,'' (Morgan Kaufmann, San Francisco, 1999)

References in corpus (1)

• Aging in a Model of Self-Organized Criticality

Cited by in corpus (7)

• Random Geometric Graphs
• Nature's Way of Optimizing
• Comprehensive Taxonomies of Nature- and Bio-inspired Optimization: Inspiration versus Algorithmic Behavior, Critical Analysis and Recommendations (from 2020 to 2024)
• Adaptive learning by extremal dynamics and negative feedback
• A Game-Theoretic Approach for Detection of Overlapping Communities in Dynamic Complex Networks
• Critical control of a genetic algorithm
• Experimental performance of graph neural networks on random instances of max-cut