Improved extremal optimization for the Ising spin glass

2004/02/29 by A. Alan Middleton
Computer Science · Economics, Econometrics and Finance · Physics and Astronomy · #Complex Systems and Time Series Analysis #Neural Networks and Applications #Theoretical and Computational Physics #cond-mat.dis-nn

paper · pdf · doi:10.1103/physreve.69.055701

published as Physical Review E 69, 055701 (R) (2004) · 4 pages, 3 color figs; minor text changes and new data point in v. 2

arxiv created 2004/03/15 · openalex publication_date 2004/05/14 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A version of the extremal optimization (EO) algorithm introduced by Boettcher and Percus is tested on two- and three-dimensional spin glasses with Gaussian disorder. EO preferentially flips spins that are locally ``unfit''; the variant introduced here reduces the probability of flipping previously selected spins. Relative to EO, this adaptive algorithm finds exact ground states with a speedup of order 10⁴\phantom\rule0.3em0ex(10²) for 16²\penalty1000-\hskip0pt\phantom\rule0.3em0ex(8³\penalty1000-\hskip0pt)spin samples. This speedup increases rapidly with system size, making this heuristic a useful tool in the study of materials with quenched disorder.

Related

• Probing spin glasses with heuristic optimization algorithms
• Computational complexity and simulation of rare events of Ising spin\n glasses
• Simulated annealing, optimization, searching for ground states
• A Set of Annealing Protocols for Optimized System Dynamics and Classification of Fully Connected Spin Glass Problems
• Optimization of random high-dimensional functions: Structure and algorithms