Computer Science – Neural and Evolutionary Computing
Scientific paper
2002-09-26
Computer Science
Neural and Evolutionary Computing
Latex, 17 pages, to appear in the {\it Proceedings of the 8th INFORMS Computing Society Conference,} (2003)
Scientific paper
A recently introduced general-purpose heuristic for finding high-quality solutions for many hard optimization problems is reviewed. The method is inspired by recent progress in understanding far-from-equilibrium phenomena in terms of {\em self-organized criticality,} a concept introduced to describe emergent complexity in physical systems. This method, called {\em extremal optimization,} successively replaces the value of extremely undesirable variables in a sub-optimal solution with new, random ones. Large, avalanche-like fluctuations in the cost function self-organize from this dynamics, effectively scaling barriers to explore local optima in distant neighborhoods of the configuration space while eliminating the need to tune parameters. Drawing upon models used to simulate the dynamics of granular media, evolution, or geology, extremal optimization complements approximation methods inspired by equilibrium statistical physics, such as {\em simulated annealing}. It may be but one example of applying new insights into {\em non-equilibrium phenomena} systematically to hard optimization problems. This method is widely applicable and so far has proved competitive with -- and even superior to -- more elaborate general-purpose heuristics on testbeds of constrained optimization problems with up to $10^5$ variables, such as bipartitioning, coloring, and satisfiability. Analysis of a suitable model predicts the only free parameter of the method in accordance with all experimental results.
Boettcher Stefan
Percus Allon G.
No associations
LandOfFree
Extremal Optimization: an Evolutionary Local-Search Algorithm does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Extremal Optimization: an Evolutionary Local-Search Algorithm, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Extremal Optimization: an Evolutionary Local-Search Algorithm will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-523491