Optimization with extremal dynamics

We explore a new general-purpose heuristic for finding high-quality solutio ns to hard discrete optimization problems. The method, called extremal opti mization, is inspired by self-organized criticality, a concept introduced t o describe emergent complexity in physical systems. Extremal optimization s uccessively updates extremely undesirable Variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, effi ciently exploring many local optima. We use extremal optimization to elucid ate the phase transition in the 3-coloring problem, and we provide independ ent confirmation of previously reported extrapolations for the ground-state energy of +/-J spin glasses in d = 3 and 4.