Finding Ground States of Sherrington-Kirkpatrick Spin Glasses with Hierarchical BOA and Genetic Algorithms

Abstract

This study focuses on the problem of finding ground states of random instances of the Sherrington-Kirkpatrick (SK) spin-glass model with Gaussian couplings. While the ground states of SK spin-glass instances can be obtained with branch and bound, the computational complexity of branch and bound yields instances of not more than about 90 spins. We describe several approaches based on the hierarchical Bayesian optimization algorithm (hBOA) to reliably identifying ground states of SK instances intractable with branch and bound, and present a broad range of empirical results on such problem instances. We argue that the proposed methodology holds a big promise for reliably solving large SK spin-glass instances to optimality with practical time complexity. The proposed approaches to identifying global optima reliably can also be applied to other problems and they can be used with many other evolutionary algorithms. Performance of hBOA is compared to that of the genetic algorithm with two common crossover operators.

Also available at the MEDAL web site, http://medal.cs.umsl.edu/

References in corpus (4)

• Finding Low-Temperature States with Parallel Tempering, Simulated Annealing and Simple Monte Carlo
• Universality-class dependence of energy distributions in spin glasses
• Ground-state energy and frustration of the Sherrington-Kirkpatrick model and related models
• Some aspects of infinite range models of spin glasses: theory and numerical simulations

Cited by in corpus (2)

• Analysis of Evolutionary Algorithms on the One-Dimensional Spin Glass with Power-Law Interactions
• On the Workings of Genetic Algorithms: The Genoclique Fixing Hypothesis