Optimization with Extremal Dynamics

Stefan Boettcher; Allon G. Percus

doi:10.1103/PhysRevLett.86.5211

Optimization with Extremal Dynamics

Stefan Boettcher and Allon G. Percus

Phys. Rev. Lett. 86, 5211 – Published 4 June 2001

Abstract

We explore a new general-purpose heuristic for finding high-quality solutions to hard discrete 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 updates extremely undesirable variables of a single suboptimal solution, assigning them new, random values. Large fluctuations ensue, efficiently exploring many local optima. 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 $\pm J$ spin glasses in $d = 3$ and $4$ .

Received 23 October 2000

DOI:https://doi.org/10.1103/PhysRevLett.86.5211

Authors & Affiliations

Stefan Boettcher^1,* and Allon G. Percus^2,†

¹Physics Department, Emory University, Atlanta, Georgia 30322
²Computer & Computational Sciences Division, Los Alamos National Laboratory, Los Alamos, New Mexico 87545

^*Electronic address: sboettc@emory.edu
^†Electronic address: percus@lanl.gov