Extremal Optimization (EO) is an optimization heuristic inspired by the Bak-Sneppen model of self-organized criticality from the field of statistical physics. This heuristic was designed initially to address combinatorial optimization problems such as the travelling salesman problem and spin glasses, although the technique has been demonstrated to function in optimization domains. In mathematics, optimization is the discipline which is concerned with finding the maxima and minima of functions, possibly subject to constraints. ... In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ... The Bak-Sneppen model is a simple model of co-evolution between interacting species. ... The theory of self-organized criticality (SOC) claims that whenever a self-organizing dynamical system is open or dissipative, it exhibits critical (scale-invariant) behaviour similar to that displayed by static systems undergoing a second-order phase transition. ... In computer science, besides the common use as rule of thumb (see heuristic), the term heuristic has two well-defined technical meanings. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ... If a salesman starts at point A, and if the distances between any two points is known, what is the shortest round-trip the salesman can make which will visit all points once and return to point A? The travelling salesman problem[1] [2](TSP) is a problem in discrete... A spin glass is a disordered material exhibiting high magnetic frustration. ...

Relation to self-organized criticality

Self-organized criticality (SOC) is a statistical physics concept to describe a class of dynamical systems that have a critical point as an attractor. Specifically, these are non-equilibrium systems that evolve through avalanches of change and dissipations that reach up to the highest scales of the system. SOC is said to govern the dynamics behind some natural systems that have these burst-like phenomena including landscape formation, earthquakes, evolution, and the granular dynamics of rice and sand piles. Of special interest here is the Bak-Sneppen model of SOC, which is able to describe evolution via punctuated equilibrium (extinction events) - thus modelling evolution as a self-organised critical process. The theory of self-organized criticality (SOC) claims that whenever a self-organizing dynamical system is open or dissipative, it exhibits critical (scale-invariant) behaviour similar to that displayed by static systems undergoing a second-order phase transition. ... The Bak-Sneppen model is a simple model of co-evolution between interacting species. ... Punctuated equilibrium (or punctuated equilibria) is a theory in evolutionary biology which states that most sexually reproducing species will show little to no evolutionary change throughout their history. ...

Relation to computational complexity

Another piece in the puzzle is work on computational complexity, specifically that critical points have been shown to exist in NP-complete problems, where near-optimum solutions are widely dispersed and separated by barriers in the search space causing local search algorithms to get stuck or severely hampered. It was the evolutionary self-organised criticality model by Bak and Sneppen and the observation of critical points in combinatorial optimisation problems that lead to the development of Extremal Optimization by Stefan Boettcher and Allon Percus. In complexity theory, the NP-complete problems are the most difficult problems in NP, in the sense that they are the ones most likely not to be in P. The reason is that if you could find a way to solve an NP-complete problem quickly, then you could use... The Bak-Sneppen model is a simple model of co-evolution between interacting species. ...

The technique

EO was designed as a local search algorithm for combinatorial optimization problems. Unlike genetic algorithms, which work with a population of candidate solutions, EO evolves a single solution and makes local modifications to the worst components. This requires that a suitable representation be selected which permits individual solution components to be assigned a quality measure ("fitness"). This differs from holistic approaches such as ant colony optimization and evolutionary computation that assign equal-fitness to all components of a solution based upon their collective evaluation against an objective function. The algorithm is initialized with an initial solution, which can be constructed randomly, or derived from another search process. Local search is a metaheuristic for solving computationally hard optimization problems. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ... A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ... The ant colony optimization algorithm (ACO), introduced by Moyson and Manderick [MoMa88] and widely developped by Marco Dorigo [CMD91,Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ... In computer science evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) involving combinatorial optimization problems. ...

The technique is a fine-grained search, and superficially resembles a hill climbing (local search) technique. A more detailed examination reveals some interesting principles, which may have applicability and even some similarity to broader population-based approaches (evolutionary computation and artificial immune system). The governing principle behind this algorithm is that of improvement through selectively removing low-quality components and replacing them with a randomly selected component. This is obviously at odds with genetic algorithms, the quintessential evolutionary computation algorithm that selects good solutions in an attempt to make better solutions. Hill climbing is a graph search algorithm where the current path is extended with a successor node which is closer to the solution than the end of the current path. ... In computer science evolutionary computation is a subfield of artificial intelligence (more particularly computational intelligence) involving combinatorial optimization problems. ... Artificial Immune Systems (AIS) are computer algorithms inspired by the principles and processes of the vertebrates immune system. ... A genetic algorithm (GA) is an algorithm used to find approximate solutions to difficult-to-solve problems through application of the principles of evolutionary biology to computer science. ...

The resulting dynamics of this simple principle is firstly a robust hill climbing search behaviour, and secondly a diversity mechanism that resembles that of multiple-restart search. Graphing holistic solution quality over time (algorithm iterations) shows periods of improvement followed by quality crashes (avalanche) very much in the manner as described by punctuated equilibrium. It is these crashes or dramatic jumps in the search space that permit the algorithm to escape local optima and differentiate this approach from other local search procedures. Although such punctuated-equilibrium behaviour can be "designed" or "hard-coded", it should be stressed that this is an emergent effect of the negative-component-selection principle fundamental to the algorithm. Punctuated equilibrium (or punctuated equilibria) is a theory in evolutionary biology which states that most sexually reproducing species will show little to no evolutionary change throughout their history. ...

EO has primarily been applied to combinatorial problems such as graph partitioning and the travelling salesman problem, as well as problems from statistical physics such as spin glasses. If a salesman starts at point A, and if the distances between any two points is known, what is the shortest round-trip the salesman can make which will visit all points once and return to point A? The travelling salesman problem[1] [2](TSP) is a problem in discrete... A spin glass is a disordered material exhibiting high magnetic frustration. ...

Variations on the theme and applications

Generalised Extremal Optimization (GEO) was developed to operate on bit strings where component quality is determined by the absolute rate of change of the bit, or the bits contribution to holistic solution quality. This work includes application to standard function optimisation problems as well as engineering problem domains. Another similar extension to EO is Continuous Extremal Optimization (CEO).

EO has been applied to image rasterization as well as used as a local search after using ant colony optimization. EO has been used to identify structures in complex networks. EO has been used on a multiple target tracking problem. Finally, some work has been done on investigating the probability distribution used to control selection. The ant colony optimization algorithm (ACO), introduced by Moyson and Manderick [MoMa88] and widely developped by Marco Dorigo [CMD91,Dor92,DoSt04], is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs. ...

References

• [1] Per Bak, Chao Tang, and Kurt Wiesenfeld, "Self-organized criticality: An explanation of the 1/f noise", Physical Review Letters 59, 381–384 (1987)
• [2] Per Bak and Kim Sneppen, "Punctuated equilibrium and criticality in a simple model of evolution", Physical Review Letters 71, 4083–4086 (1993)
• [3] P Cheeseman, B Kanefsky, WM Taylor, "Where the really hard problems are", Proceedings of the 12th IJCAI, (1991)
• G Istrate, "Computational complexity and phase transitions", Proceedings. 15th Annual IEEE Conference on Computational Complexity, 104-115 (2000)
• [4] Stefan Boettcher, Allon G. Percus, "Extremal Optimization: Methods derived from Co-Evolution", Proceedings of the Genetic and Evolutionary Computation Conference (1999)
• [5] Stefan Boettcher, "Extremal optimization of graph partitioning at the percolation threshold", J. Phys. A: Math. Gen. 32, 5201-5211 (1999)
• [6] S Boettcher, A Percus, "Nature’s Way of Optimizing", Artif. Intel. 119, (2000) 275
• [7] S Boettcher, "Extremal Optimization - Heuristics via Co-Evolutionary Avalanches", Computing in Science & Engineering 2, pp. 75-82, 2000
• [8] Stefan Boettcher and Allon G. Percus, "Optimization with Extremal Dynamics", Phys. Rev. Lett. 86, 5211–5214 (2001)
• [9] Jesper Dall and Paolo Sibani, "Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method", Computer Physics Communication 141 (2001) 260-267
• [10] Stefan Boettcher and Michelangelo Grigni, "Jamming Model for the Extremal Optimization Heuristic", J. Phys. A: Math. Gen. 35, 1109-1123 (2002)
• [11] Souham Meshoul and Mohamed Batouche, "Robust Point Correspondence for Image Registration Using Optimization with Extremal Dynamics", Lecture Notes in Computer Science 2449, 330-337 (2002)
• [12] Roberto N. Onody and Paulo A. de Castro, "Self-Organized Criticality, Optimization and Biodiversity", Int. J. Mod. Phys. C 14, 911-916 (2002)
• [13] Stefan Boettcher and Allon G. Percus, "Extremal Optimization at the Phase Transition of the 3-Coloring Problem", Phys. Rev. E 69, 066703 (2004)
• [14] A. Alan Middleton, "Improved extremal optimization for the Ising spin glass", Phys. Rev. E 69, 055701 (2004)
• [15] F. Heilmann, K. H. Hoffmann and P. Salamon, "Best possible probability distribution over extremal optimization ranks", Europhys. Lett. 66, pp. 305-310 (2004)
• [16] Pontus Svenson, "Extremal optimization for sensor report pre-processing", Proc SPIE 5429, 162-171 (2004)
• [17] Tao Zhou, Wen-Jie Bai, Long-Jiu Cheng, Bing-Hong Wang, "Continuous extremal optimization for Lennard-Jones Clusters", Phys. Rev. E 72, 016702 (2004)
• [18] Jordi Duch and Alex Arenas, "Community detection in complex networks using extremal optimization", Phys. Rev. E 72, 027104 (2005)

Web Resources

• [19] Stefan Boettcher's home page which includes an excellent explanation of the technique and demonstration applets
• [20] Allon Percus home page
• [21] A good introduction to EO with lots of linked references

See also

• Simulated Annealing
• Genetic Algorithm

Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. ... A genetic algorithm (abbreviated as GA) is a search technique used in computing (with applications in computer science, engineering, economics, physics, mathematics and other fields) to find true or approximate solutions to optimization and search problems. ...

External Links

• VitaSCIENCES Web-platform of global optimization and metaheuristics.