Extremal optimization
Encyclopedia
Extremal Optimization 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 glass
es, although the technique has been demonstrated to function in optimization domains.
(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.
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.
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.
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.
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.
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 glass
es.
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.
Optimization (mathematics)
In mathematics, computational science, or management science, mathematical optimization refers to the selection of a best element from some set of available alternatives....
heuristic inspired by the Bak-Sneppen model
Bak-Sneppen model
The Bak-Sneppen model is a simple model of co-evolution between interacting species. It was developed to show how self-organized criticality may explain key features of the fossil record, such as the distribution of sizes of extinction events and the phenomenon of punctuated equilibrium...
of self-organized criticality
Self-organized criticality
In physics, self-organized criticality is a property of dynamical systems which have a critical point as an attractor. Their macroscopic behaviour thus displays the spatial and/or temporal scale-invariance characteristic of the critical point of a phase transition, but without the need to tune...
from the field of statistical physics. This heuristic was designed initially to address combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problems such as the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
and spin glass
Spin glass
A spin glass is a magnet with frustrated interactions, augmented by stochastic disorder, where usually ferromagnetic and antiferromagnetic bonds are randomly distributed...
es, although the technique has been demonstrated to function in optimization domains.
Relation to self-organized criticality
Self-organized criticalitySelf-organized criticality
In physics, self-organized criticality is a property of dynamical systems which have a critical point as an attractor. Their macroscopic behaviour thus displays the spatial and/or temporal scale-invariance characteristic of the critical point of a phase transition, but without the need to tune...
(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
Bak-Sneppen model
The Bak-Sneppen model is a simple model of co-evolution between interacting species. It was developed to show how self-organized criticality may explain key features of the fossil record, such as the distribution of sizes of extinction events and the phenomenon of punctuated equilibrium...
of SOC, which is able to describe evolution via punctuated equilibrium
Punctuated equilibrium
Punctuated equilibrium is a theory in evolutionary biology which proposes that most species will exhibit little net evolutionary change for most of their geological history, remaining in an extended state called stasis...
(extinction events) - thus modelling evolution as a self-organised critical process.
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-completeNP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
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
Bak-Sneppen model
The Bak-Sneppen model is a simple model of co-evolution between interacting species. It was developed to show how self-organized criticality may explain key features of the fossil record, such as the distribution of sizes of extinction events and the phenomenon of punctuated equilibrium...
and the observation of critical points in combinatorial optimisation problems that lead to the development of Extremal Optimization by Stefan Boettcher and Allon Percus.
The technique
EO was designed as a local searchLocal search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
algorithm for combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
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
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
and evolutionary computation
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
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.
The technique is a fine-grained search, and superficially resembles a hill climbing
Hill climbing
In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution...
(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
Evolutionary computation
In computer science, evolutionary computation is a subfield of artificial intelligence that involves combinatorial optimization problems....
and artificial immune system
Artificial immune system
In computer science, Artificial immune systems are a class of computationally intelligent systems inspired by the principles and processes of the vertebrate 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.
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
Punctuated equilibrium
Punctuated equilibrium is a theory in evolutionary biology which proposes that most species will exhibit little net evolutionary change for most of their geological history, remaining in an extended state called stasis...
. 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.
EO has primarily been applied to combinatorial problems such as graph partitioning and the travelling salesman problem
Travelling salesman problem
The travelling salesman problem is an NP-hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find the shortest possible tour that visits each city exactly once...
, as well as problems from statistical physics such as spin glass
Spin glass
A spin glass is a magnet with frustrated interactions, augmented by stochastic disorder, where usually ferromagnetic and antiferromagnetic bonds are randomly distributed...
es.
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
Ant colony optimization
In computer science and operations research, the ant colony optimization algorithm ' is a probabilistic technique for solving computational problems which can be reduced to finding good paths through graphs....
. 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.
Web Resources
- http://www.physics.emory.edu/faculty/boettcher Stefan Boettcher's home page which includes an excellent explanation of the technique and demonstration applets
- http://wwwc3.lanl.gov/%7Epercus/ Allon Percus home page
- http://pensive-pondering.blogspot.com/2006/03/extremal-optimization-eo.html A good introduction to EO with lots of linked references
- http://www.it-weise.de/projects/book.pdf a general summary on global optimization, including a short introduction to EO