Combining Local Search with Co-Evolution in a Remarkably Simple Way
Stefan Boettcher, Allon G. Percus · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2000
Abstract- We explore a new general-purpose heuristic for finding high-quality solutions to hard optimization problems. The method, called extremal optimization, is inspired by “self-organized criticality”, a concept introduced to describe emergent complexity in physical systems. In contrast to genetic algorithms, which operate on an entire “gene-pool ” of possible solutions, extremal optimization successively replaces extremely undesirable elements of a single sub-optimal solution with new, random ones. Large fluctuations, or “avalanches”, ensue that efficiently explore many local optima. Drawing upon models used to simulate far-from-equilibrium dynamics, extremal optimization complements heuristics inspired by equilibrium statistical physics, such as simulated annealing. With only one adjustable parameter, its performance