A comparison of extremal optimization with flat-histogram dynamics for finding spin-glass ground states

Abstract

We compare the performance of extremal optimization (EO), flat-histogram and equal-hit algorithms for finding spin-glass ground states. The first-passage-times to a ground state are computed. At optimal parameter of tau=1.15, EO outperforms other methods for small system sizes, but equal-hit algorithm is competitive to EO, particularly for large systems. Flat-histogram and equal-hit algorithms offer additional advantage that they can be used for equilibrium thermodynamic calculations. We also propose a method to turn EO into a useful algorithm for equilibrium calculations. Keywords: extremal optimization. flat-histogram algorithm, equal-hit algorithm, spin-glass model, ground state.

10 LaTeX pages, 2 figures

References in corpus (15)

• Exchange Monte Carlo Method and Application to Spin Glass Simulations
• Multicanonical Ensemble: A New Approach to Simulate First-order Phase Transitions
• Optimization with Extremal Dynamics
• Nature's Way of Optimizing
• Transition Matrix Monte Carlo Method
• Monte Carlo simulation and global optimization without parameters
• Multi-Overlap Simulations of the $3d$ Edwards-Anderson Ising Spin Glass
• Faster Monte Carlo Simulations at Low Temperatures. The Waiting Time Method
• Renormalization for Discrete Optimization
• Evidence for existence of many pure ground states in 3d $\pm J$ Spin Glasses
• Is the broad histogram random walk dynamics correct?
• Transition Matrix Monte Carlo
• Configuration Space for Random Walk Dynamics
• A new approach to the study of the ground-state properties of 2D Ising spin glass
• A general learning algorithm for solving optimization problems and its application to the spin glass problem

Cited by in corpus (1)

• Optimizing at the Ergodic Edge