Extremal optimization

Extremal optimization

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.

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.

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.

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.

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 glasses.

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.

References

* [http://prola.aps.org/abstract/PRL/v59/i4/p381_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)
* [http://prola.aps.org/abstract/PRL/v71/i24/p4083_1] Per Bak and Kim Sneppen, "Punctuated equilibrium and criticality in a simple model of evolution", Physical Review Letters 71, 4083–4086 (1993)
* [http://www.cs.usask.ca/grads/jiz194/References/cheeseman91where.ps] 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)
* [http://arxiv.org/abs/math/9904056] Stefan Boettcher, Allon G. Percus, "Extremal Optimization: Methods derived from Co-Evolution", Proceedings of the Genetic and Evolutionary Computation Conference (1999)
* [http://www.iop.org/EJ/abstract/0305-4470/32/28/302] Stefan Boettcher, "Extremal optimization of graph partitioning at the percolation threshold", J. Phys. A: Math. Gen. 32, 5201-5211 (1999)
* [http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6TYF-40XGW6J-9&_user=10&_coverDate=05%2F31%2F2000&_rdoc=9&_fmt=summary&_orig=browse&_srch=%23toc%235617%232000%23998809998%23205975!&_cdi=5617&_sort=d&_docanchor=&_acct=C000050221&_version=1&_urlVersion=0&_userid=10&md5=83eeb321ed5935b0dedda16f87ab1788] S Boettcher, A Percus, "Nature’s Way of Optimizing", Artif. Intel. 119, (2000) 275
* [http://ieeexplore.ieee.org/iel5/5992/19077/00881710.pdf] S Boettcher, "Extremal Optimization - Heuristics via Co-Evolutionary Avalanches", Computing in Science & Engineering 2, pp. 75-82, 2000
* [http://prola.aps.org/abstract/PRL/v86/i23/p5211_1] Stefan Boettcher and Allon G. Percus, "Optimization with Extremal Dynamics", Phys. Rev. Lett. 86, 5211–5214 (2001)
* [http://arxiv.org/abs/cond-mat/0107475] Jesper Dall and Paolo Sibani, "Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method", Computer Physics Communication 141 (2001) 260-267
* [http://www.iop.org/EJ/abstract/0305-4470/35/5/301] Stefan Boettcher and Michelangelo Grigni, "Jamming Model for the Extremal Optimization Heuristic", J. Phys. A: Math. Gen. 35, 1109-1123 (2002)
* [http://www.springerlink.com/(24ia1q55gtqkcy45pgzuxm45)/app/home/contribution.asp?referrer=parent&backto=issue,40,74;journal,1497,3835;linkingpublicationresults,1:105633,1] 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)
* [http://arxiv.org/abs/q-bio.PE/0410007] Roberto N. Onody and Paulo A. de Castro, "Self-Organized Criticality, Optimization and Biodiversity", Int. J. Mod. Phys. C 14, 911-916 (2002)
* [http://link.aps.org/abstract/PRE/v69/e066703] Stefan Boettcher and Allon G. Percus, "Extremal Optimization at the Phase Transition of the 3-Coloring Problem", Phys. Rev. E 69, 066703 (2004)
* [http://link.aps.org/abstract/PRE/v69/e055701] A. Alan Middleton, "Improved extremal optimization for the Ising spin glass", Phys. Rev. E 69, 055701 (2004)
* [http://www.edpsciences.org/10.1209/epl/i2004-10011-3] F. Heilmann, K. H. Hoffmann and P. Salamon, "Best possible probability distribution over extremal optimization ranks", Europhys. Lett. 66, pp. 305-310 (2004)
* [http://arxiv.org/abs/cs.AI/0411072] Pontus Svenson, "Extremal optimization for sensor report pre-processing", Proc SPIE 5429, 162-171 (2004)
* [http://link.aps.org/abstract/PRE/v72/e016702] Tao Zhou, Wen-Jie Bai, Long-Jiu Cheng, Bing-Hong Wang, "Continuous extremal optimization for Lennard-Jones Clusters", Phys. Rev. E 72, 016702 (2004)
* [http://link.aps.org/abstract/PRE/v72/e027104] Jordi Duch and Alex Arenas, "Community detection in complex networks using extremal optimization", Phys. Rev. E 72, 027104 (2005)
* [http://dx.doi.org/10.1016/j.amc.2005.01.122] E. Ahmed and M.F. Elettreby, "On combinatorial optimization motivated by biology", Applied Mathematics and Computation, Volume 172, Issue 1, 1 January 2006, Pages 40-48

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

See also

* Simulated Annealing
* Genetic Algorithm


Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

  • Category:Optimization algorithms — An optimization algorithm is an algorithm for finding a value x such that f(x) is as small (or as large) as possible, for a given function f, possibly with some constraints on x. Here, x can be a scalar or vector of continuous or discrete values …   Wikipedia

  • Ant colony optimization algorithms — Ant behavior was the inspiration for the metaheuristic optimization technique. In computer science and operations research, the ant colony optimization algorithm (ACO) is a probabilistic technique for solving computational problems which can be… …   Wikipedia

  • Genetic algorithm — A genetic algorithm (GA) is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems. Genetic algorithms belong to the larger class of… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Metaheuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Méta-heuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Métaheuristique — Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence artificielle) pour lesquels on ne… …   Wikipédia en Français

  • Métaheuristiques — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… …   Wikipédia en Français

  • Cross-entropy method — The cross entropy (CE) method attributed to Reuven Rubinstein is a general Monte Carlo approach to combinatorial and continuous multi extremal optimization and importance sampling. The method originated from the field of rare event simulation,… …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”