Improved extremal optimization for the Ising spin glass

Abstract

A version of the extremal optimization (EO) algorithm introduced by Boettcher and Percus is tested on 2D and 3D spin glasses with Gaussian disorder. EO preferentially flips spins that are locally ``unfit''; the variant introduced here reduces the probability to flip previously selected spins. Relative to EO, this adaptive algorithm finds exact ground states with a speed-up of order $10^4$ ($10^2$) for $16^2$- ($8^3$-) spin samples. This speed-up increases rapidly with system size, making this heuristic a useful tool in the study of materials with quenched disorder.

4 pages, 3 color figs; minor text changes and new data point in v. 2

References in corpus (7)

• An efficient, multiple range random walk algorithm to calculate the density of states
• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• Simplest random K-satisfiability problem
• Calculation of ground states of four-dimensional +or- J Ising spin glasses
• Renormalization for Discrete Optimization
• Low Energy Excitations in Spin Glasses from Exact Ground States

Cited by in corpus (18)

• Extremal Optimization for Sherrington-Kirkpatrick Spin Glasses
• Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
• Comparing Monte Carlo methods for finding ground states of Ising spin glasses: population annealing, simulated annealing and parallel tempering
• Continuous extremal optimization for Lennard-Jones Clusters
• Hysteretic optimization for the Sherrington-Kirkpatrick spin glass
• A quantum speedup in machine learning: Finding a N-bit Boolean function for a classification
• Comparing extremal and thermal Explorations of Energy Landscapes
• Analysis of the Relation between Quadratic Unconstrained Binary Optimization (QUBO) and the Spin Glass Ground-State Problem
• Optimizing at the Ergodic Edge
• Novel disordering mechanism in ferromagnetic systems with competing interactions
• Extremal optimization for sensor report pre-processing
• Numerical Results for Spin Glass Ground States on Bethe Lattices: Gaussian Bonds
• Inference from Matrix Products: A Heuristic Spin Glass Algorithm
• Different Environmental Conditions in Genetic Algorithm
• Random-field-induced disordering mechanism in a disordered ferromagnet: Between the Imry-Ma and the standard disordering mechanism
• Obtaining Stiffness Exponents from Bond-diluted Lattice Spin Glasses
• Charge avalanches and depinning in the Coulomb glass: The role of long-range interactions
• Ground states of 2d +-J Ising spin glasses via stationary Fokker-Planck sampling