Optimization with Extremal Dynamics
Physical Review LettersPublished 4 June 2001Open access
Stefan Boettcher, Allon G. Percus
Citations341
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This work uses extremal optimization to elucidate the phase transition in the 3-coloring problem, and provides independent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.
Abstract
We explore a new general-purpose heuristic for finding high-quality solutions to hard discrete optimization problems. The method, called extremal optimization, is inspired by self-organized criticality, a concept introduced to describe emergent complexity in physical systems. Extremal optimization successively updates extremely undesirable variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, efficiently exploring many local optima. We use extremal optimization to elucidate the phase transition in the 3-coloring problem, and we provide independent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.
Keywords
MathematicsPhysics and Astronomy
ScienceOptimization by Simulated Annealing
44,600 Citations1983Scott Kirkpatrick, C. D. Gelatt +1 more
A detailed analogy with annealing in solids provides a framework for optimization of the properties of very large and complex systems.
The MIT Press eBooksAdaptation in Natural and Artificial Systems
35,568 Citations1992John H. Holland
Initially applying his concepts to simply defined artificial systems with limited numbers of parameters, Holland goes on to explore their use in the study of a wide range of complex, naturally occuring processes, concentrating on systems having multiple factors that interact in nonlinear ways.
Physical Review LettersSelf-organized criticality: An explanation of the 1/<i>f</i>noise
7,645 Citations1987Per Bak, Chao Tang +1 more
How Nature Works
2,812 Citations1996Per Bak
Physical Review LettersPunctuated equilibrium and criticality in a simple model of evolution
1,524 Citations1993Per Bak, Kim Sneppen
A simple and robust model of biological evolution of an ecology of interacting species that self-organizes into a critical steady state with intermittent coevolutionary avalanches of all sizes and exhibits ``punctuated equilibrium'' behavior.
Journal of Physics A Mathematical and GeneralOn the computational complexity of Ising spin glass models
1,308 Citations1982Francisco Barahona
In a spin glass with Ising spins, the problems of computing the magnetic partition function and finding a ground state are studied and are shown to belong to the class of NP-hard problems, both in the two-dimensional case within a magnetic field, and in the three-dimensional cases.
Where the really hard problems are
1,021 Citations1991Peter Cheeseman, Bob Kanefsky +1 more
It is shown that NP-complete problems can be summarized by at least one "order parameter", and that the hard problems occur at a critical value of such a parameter.
NatureDetermining computational complexity from characteristic ‘phase transitions’
803 Citations1999Rémi Monasson, Riccardo Zecchina +3 more
An analytic solution and experimental investigation of the phase transition in K -satisfiability, an archetypal NP-complete problem, is reported and the nature of these transitions may explain the differing computational costs, and suggests directions for improving the efficiency of search algorithms.
ScienceCritical Behavior in the Satisfiability of Random Boolean Expressions
598 Citations1994Scott Kirkpatrick, Bart Selman
Finite-size scaling, a method from statistical physics, can be used to characterize size-dependent effects near the threshold and a relationship can be drawn between thresholds and computational complexity.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsAvalanche dynamics in evolution, growth, and depinning models
572 Citations1996Maya Paczuski, Sergei Maslov +1 more
A scaling theory is developed that relates many of the critical exponents in this broad category of extremal models, representing different universality classes, to two basic exponents characterizing the fractal attractor.
Artificial IntelligenceNature's way of optimizing
286 Citations2000Stefan Boettcher, Allon G. Percus
The method, called Extremal Optimization, successively eliminates extremely undesirable components of sub-optimal solutions in a manner that proves competitive with, and often superior to, more elaborate stochastic optimization procedures.
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsExtremal optimization for graph partitioning
138 Citations2001Stefan Boettcher, Allon G. Percus
Numerical results demonstrate that extremal optimization maintains consistent accuracy for increasing system sizes, with an approximation error decreasing over run time roughly as a power law t(-0.4).
Theoretical Computer ScienceFrozen development in graph coloring
117 Citations2001Joseph Culberson, Ian P. Gent
The 'frozen development' of coloring random graphs is defined, and theoretical and empirical evidence is given to show that the size of the smallest uncolorable subgraphs of threshold graphs becomes large as the number of nodes in graphs increases.
Physica A Statistical Mechanics and its ApplicationsThe ground state energy of the Edwards-Anderson Ising spin glass with a hybrid genetic algorithm
80 Citations1996Károly F. Pál
Computing in Science & EngineeringExtremal optimization: heuristics via coevolutionary avalanches
64 Citations2000Stefan Boettcher
The extremal dynamics of the Bak-Sneppen model can be converted into an optimization algorithm called extremal optimization, which achieves almost all species have a much better than random fitness and most species preserve a good fitness for long times.
Journal of Statistical PhysicsModels of Fractal River Basins
59 Citations1998Marek Cieplak, Achille Giacometti +4 more
Physical Review LettersOptimization by Thermal Cycling
56 Citations1997A. Möbius, A. Neklioudov +4 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsCalculation of ground states of four-dimensional<mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" display="inline"><mml:mo>±</mml:mo><mml:mi>J</mml:mi></mml:math>Ising spin glasses
50 Citations1999Alexander K. Hartmann
Ground states of four-dimensional (d=4) Edwards-Anderson Ising spin glasses are calculated using a combination of a genetic algorithm and cluster-exact approximation to confirm that the d=4 model has an equilibrium spin-glass-paramagnet transition for nonzero T(c).
Physical Review LettersRenormalization for Discrete Optimization
49 Citations1999J. Houdayer, Olivier Martin
The heart of the method uses renormalization and recursion, and these processes are embedded in a genetic algorithm that is self-consistently optimized on all scales, leading to a high probability of finding the ground state configuration.
Journal of Physics A Mathematical and GeneralExtremal optimization of graph partitioning at the percolation threshold
45 Citations1999Stefan Boettcher
The benefits of a recently proposed method to approximate hard optimization problems are demonstrated on the graph partitioning problem and this new method, called extremal optimization (EO), is compared with simulated annealing (SA) in extensive numerical simulations.
Physical Review LettersOptimization on Rugged Landscapes: A New General Purpose Monte Carlo Approach
38 Citations1996Frank-Michael Dittes
Europhysics Letters (EPL)Evidence for nontrivial ground-state structure of 3d ± J spin glasses
38 Citations1997Alexander K. Hartmann
Journal of Physics A Mathematical and GeneralPower-law distribution of landslides in an experiment on the erosion of a granular pile
29 Citations1994Ellák Somfai, András Czirók +1 more
Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topicsUltrametricity and memory in a solvable model of self-organized criticality
29 Citations1996Stefan Boettcher, Maya Paczuski
A self-organized critical model of punctuated equilibrium behavior in the context of biological evolution is presented, and an exact equation of motion for the avalanche dynamics from the microscopic rules are derived.
Lecture notes in computer scienceOptimizing through Co-evolutionary Avalanches
15 Citations2000Stefan Boettcher, Allon G. Percus +1 more
It is believed that extremal optimization will be a useful tool in the investigation of phase transitions in combinatorial optimization problems, hence valuable in elucidating the origin of computational complexity.