CNS
Meeting
Monday Oct 20, 11:00 AM, W505 Howey
Optimization with Extremal Dynamics
Stefan Boettcher
A local-search heuristic for finding high-quality solutions for
many hard optimization problems is explored. The method is inspired by
recent progress in understanding far-from-equilibrium phenomena in
terms of self-organized criticality, a concept introduced to
describe emergent complexity in physical systems. This method, called
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 simulated
annealing . This method is very general
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 spin glasses. This
heuristic is particularly successful near phase transitions, found in
the parameter space of many optimization problems, which are deemed to
be the origin of the hardest instances in terms of computational
complexity. Analysis of a model problem predicts the only free
parameter of the method in accordance with all experimental
results. For (p)reprints, see
http://www.physics.emory.edu/faculty/boettcher/.