preprint · arXiv (Cornell University) · 2000

Optimization with Extremal Dynamics

Boettcher, S., Percus, A. G.

Cited by 0Open access

Abstract

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.

Cite this paper

APA 7

Boettcher, S., & Percus, A. G. (2000). Optimization with Extremal Dynamics. arXiv (Cornell University). https://doi.org/10.48550/arxiv.cond-mat/0010337

MLA 9

Boettcher, S., and A. G. Percus. “Optimization with Extremal Dynamics.” arXiv (Cornell University), 2000, https://doi.org/10.48550/arxiv.cond-mat/0010337.

Chicago

Boettcher, S., and A. G. Percus. 2000. “Optimization with Extremal Dynamics.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.cond-mat/0010337.

Harvard

Boettcher, S. and Percus, A.G. (2000) ‘Optimization with Extremal Dynamics’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.cond-mat/0010337.

BibTeX

@misc{boettcher2000optimization,
  title = {{Optimization with Extremal Dynamics}},
  author = {Boettcher, S. and Percus, A. G.},
  journal = {arXiv (Cornell University)},
  year = {2000},
  doi = {10.48550/arxiv.cond-mat/0010337}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.