  We explore a new general-purpose heuristic for finding high-quality solutions
to hard optimization problems. The method, called extremal optimization, is
inspired by self-organized criticality, a concept introduced to describe
emergent complexity in physical systems. Extremal optimization successively
replaces extremely undesirable variables of a single sub-optimal solution with
new, random ones. Large fluctuations ensue, that efficiently explore many local
optima. With only one adjustable parameter, the heuristic's performance has
proven competitive with more elaborate methods, especially near phase
transitions which are believed to coincide with the hardest instances. We use
extremal optimization to elucidate the phase transition in the 3-coloring
problem, and we provide independent confirmation of previously reported
extrapolations for the ground-state energy of +-J spin glasses in d=3 and 4.

Statistical Mechanics;Neural and Evolutionary Computing;Optimization and Control