research-article

Finding ground states of Sherrington-Kirkpatrick spin glasses with hierarchical boa and genetic algorithms

Authors:

Martin Pelikan,

Katzgraber G. Helmut,

Sigismund KobeAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 447 - 454

https://doi.org/10.1145/1389095.1389176

Published: 12 July 2008 Publication History

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 approximately 90 spins. We describe several approaches based on the hierarchical Bayesian optimization algorithm (hBOA) to reliably identify 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 can be used with many other evolutionary algorithms. Performance of hBOA is compared to that of the genetic algorithm with two common crossover operators.

References

[1]

T. Aspelmeier, M. A. Moore, and A. P. Young. Interface energies in Ising spin glasses. Phys. Rev. Lett., 90:127202, 2003.

[2]

S. Baluja. Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning. Tech. Rep. No. CMU-CS-94-163, Carnegie Mellon University, Pittsburgh, PA, 1994.

Digital Library

[3]

F. Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical, Nuclear and General, 15(10):3241--3253, 1982.

[4]

A. Billoire. Some aspects of infinite range models of spin glasses: theory and numerical simulations. (arXiv:cond-mat/0709.1552), 2007.

[5]

K. Binder and A. P. Young. Spin glasses: Experimental facts, theoretical concepts and open questions. Rev. Mod. Phys., 58:801, 1986.

[6]

S. Boettcher. Extremal optimization for Sherrington-Kirkpatrick spin glasses. Eur. Phys. J. B, 46:501--505, 2005.

[7]

J.--P. Bouchaud, F. Krzakala, and O. C. Martin. Energy exponents and corrections to scaling in Ising spin glasses. Phys. Rev. B, 68:224404, 2003.

[8]

D. M. Chickering, D. Heckerman, and C. Meek. A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSR-TR-97-07, Microsoft Research, Redmond, WA, 1997.

[9]

G. F. Cooper and E. H. Herskovits. A Bayesian method for the induction of probabilistic networks from data. Machine Learning, 9:309--347, 1992.

[10]

A. Crisanti, G. Paladin, and H.-J. S. A. Vulpiani. Replica trick and fluctuations in disordered systems. J. Phys. I, 2:1325--1332, 1992.

[11]

N. Friedman and M. Goldszmidt. Learning Bayesian networks with local structure. In M. I. Jordan, editor, Graphical models, pages 421--459. MIT Press, Cambridge, MA, 1999.

Digital Library

[12]

D. E. Goldberg. Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, MA, 1989.

Digital Library

[13]

G. Harik and F. Lobo. A parameter-less genetic algorithm. Proc. of the Genetic and Evolutionary Computation Conference (GECCO-99), I:258--265, 1999.

[14]

G. R. Harik. Finding multimodal solutions using restricted tournament selection. Proc. of the Int. Conference on Genetic Algorithms (ICGA-95), pages 24--31, 1995.

Digital Library

[15]

A. Hartwig, F. Daske, and S. Kobe. A recursive branch-and-bound algorithm for the exact ground state of Ising spin-glass models. Computer Physics Communications, 32:133--138, 1984.

[16]

J. H. Holland. Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor, MI, 1975.

Digital Library

[17]

R. Höns. Estimation of Distribution Algorithms and Minimum Relative Entropy. PhD thesis, University of Bonn, Germany, 2005.

[18]

K. Hukushima and K. Nemoto. Exchange Monte Carlo method and application to spin glass simulations. J. Phys. Soc. Jpn., 65:1604, 1996.

[19]

H. G. Katzgraber. Spin glasses and algorithm benchmarks: A one-dimensional view. In Proc. of the International Workshop on Statistical-Mechanical Informatics, 2007.

[20]

H. G. Katzgraber, M. Körner, F. Liers, M. Jünger, and A. K. Hartmann. Universality-class dependence of energy distributions in spin glasses. Phys. Rev. B, 72:094421, 2005.

[21]

N. Kawashima and H. Rieger. Recent Progress in Spin Glasses. 2003. (cond-mat/0312432).

[22]

S. Kirkpatrick and D. Sherrington. Infinite-ranged models of spin-glasses. Phys. Rev. B, 17(11):4384--4403, Jun 1978.

[23]

S. Kobe. Ground-state energy and frustration of the Sherrington-Kirkpatrick model and related models. ArXiv Condensed Matter e-print cond-mat/03116570, University of Dresden, 2003.

[24]

S. Kobe and A. Hartwig. Exact ground state of finite amorphous Ising systems. Computer Physics Communications, 16:1--4, 1978.

[25]

M. Körner, H. G. Katzgraber, and A. K. Hartmann. Probing tails of energy distributions using importance-sampling in the disorder with a guiding function. J. Stat. Mech., P04005, 2006.

[26]

P. Larranaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.

Digital Library

[27]

M. Mézard, G. Parisi, and M. A. Virasoro. Spin Glass Theory and Beyond. World Scientific, Singapore, 1987.

[28]

J. J. Moreno, H. G. Katzgraber, and A. K. Hartmann. Finding low-temperature states with parallel tempering, simulated annealing and simple Monte Carlo. Int. J. Mod. Phys. C, 14:285, 2003.

[29]

H. Mühlenbein and G. Paaß. From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature, pages 178--187, 1996.

Digital Library

[30]

K. F. Pál. The ground state energy of the Edwards-Anderson Ising spin glass with a hybrid genetic algorithm. Physica A, 223(3-4):283--292, 1996.

[31]

K. F. Pál. Hysteretic optimization for the Sherrington Kirkpatrick spin glass. Physica A, 367:261--268, 2006.

[32]

M. Palassini. Ground-state energy fluctuations in the Sherrington-Kirkpatrick model. 2003. (cond-mat/0307713).

[33]

G. Parisi. Infinite number of order parameters for spin-glasses. Phys. Rev. Lett., 43:1754, 1979.

[34]

M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.

[35]

M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proc. of the Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, 2001.

[36]

M. Pelikan, D. E. Goldberg, and F. Lobo. A survey of optimization by building and using probabilistic models. Computational Optimization and Applications, 21(1):5--20, 2002.

Digital Library

[37]

M. Pelikan, D. E. Goldberg, and K. Sastry. Bayesian optimization algorithm, decision graphs, and Occam’s razor. Proc. of the Genetic and Evolutionary Computation Conference (GECCO--2001), pages 519--526, 2001.

[38]

M. Pelikan and A. K. Hartmann. Searching for ground states of Ising spin glasses with hierarchical BOA and cluster exact approximation. In E. Cantú-Paz, M. Pelikan, and K. Sastry, editors, Scalable optimization via probabilistic modeling: From algorithms to applications, pages 333--349. Springer, 2006.

[39]

M. Pelikan, J. Ocenasek, S. Trebst, M. Troyer, and F. Alet. Computational complexity and simulation of rare events of ising spin glasses. Proc. of the Genetic and Evolutionary Computation Conference (GECCO-2004), 2:36--47, 2004.

[40]

M. Pelikan, K. Sastry, and D. E. Goldberg. Sporadic model building for efficiency enhancement of hBOA. Proc. of the Genetic and Evolutionary Computation Conference (GECCO-2006), 2006.

Digital Library

[41]

R. Santana. Estimation of distribution algorithms with Kikuchi approximations. Evolutionary Computation, 13(1):67--97, 2005.

Digital Library

[42]

K. Sastry. Evaluation-relaxation schemes for genetic and evolutionary algorithms. Master’s thesis, University of Illinois at Urbana--Champaign, Department of General Engineering, Urbana, IL, 2001.

[43]

K. Sastry, M. Pelikan, and D. E. Goldberg. Efficiency enhancement of estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pages 161--185. Springer, 2006.

[44]

S. K. Shakya, J. A. McCall, and D. F. Brown. Solving the Ising spin glass problem using a bivariate EDA based on Markov random fields. Proc. of the IEEE Congress on Evolutionary Computation (CEC 2006), pages 908--915, 2006.

[45]

E. A. Smorodkina and D. R. Tauritz. Greedy population sizing for evolutionary algorithms. IEEE Congress on Evolutionary Computation (CEC 2007), pages 2181--2187, 2007.

[46]

M. Talagrand. The Parisi formula. Ann. of Math., 163:221, 2006.

[47]

D. Thierens, D. E. Goldberg, and A. G. Pereira. Domino convergence, drift, and the temporal-salience structure of problems. Proc. of the Int. Conference on Evolutionary Computation (ICEC-98), pages 535--540, 1998.

Cited By

Ancliff MSachnev V(2023)Numerical estimation of the ground states of frustrated antiferromagnet gadolinium gallium garnetJournal of the Korean Physical Society10.1007/s40042-023-00754-582:7(699-706)Online publication date: 20-Feb-2023
https://doi.org/10.1007/s40042-023-00754-5
Burjorjee KNeumann FDe Jong K(2013)Explaining optimization in genetic algorithms with uniform crossoverProceedings of the twelfth workshop on Foundations of genetic algorithms XII10.1145/2460239.2460244(37-50)Online publication date: 16-Jan-2013
https://dl.acm.org/doi/10.1145/2460239.2460244
Burjorjee KMoore J(2012)Explaining adaptation in genetic algorithms with uniform crossoverProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330991(1461-1462)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330991
Show More Cited By

Index Terms

Finding ground states of Sherrington-Kirkpatrick spin glasses with hierarchical boa and genetic algorithms

Recommendations

Analysis of evolutionary algorithms on the one-dimensional spin glass with power-law interactions
GECCO '09: Proceedings of the 11th Annual conference on Genetic and evolutionary computation

This paper provides an in-depth empirical analysis of several hybrid evolutionary algorithms on the one-dimensional spin glass model with power-law interactions. The considered spin glass model provides a mechanism for tuning the effective range of ...
Hierarchical BOA, Cluster Exact Approximation, and Ising Spin Glasses
Parallel Problem Solving from Nature - PPSN IX
Abstract
This paper analyzes the hierarchical Bayesian optimization algorithm (hBOA) on the problem of finding ground states of Ising spin glasses with ±J couplings in two and three dimensions. The performance of hBOA is compared to that of the simple ...
Analysis of estimation of distribution algorithms and genetic algorithms on NK landscapes
GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

This study analyzes performance of several genetic and evolutionary algorithms on randomly generated NK fitness landscapes with various values of n and k. A large number of NK problem instances are first generated for each n and k, and the global ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
247
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ancliff MSachnev V(2023)Numerical estimation of the ground states of frustrated antiferromagnet gadolinium gallium garnetJournal of the Korean Physical Society10.1007/s40042-023-00754-582:7(699-706)Online publication date: 20-Feb-2023
https://doi.org/10.1007/s40042-023-00754-5
Burjorjee KNeumann FDe Jong K(2013)Explaining optimization in genetic algorithms with uniform crossoverProceedings of the twelfth workshop on Foundations of genetic algorithms XII10.1145/2460239.2460244(37-50)Online publication date: 16-Jan-2013
https://dl.acm.org/doi/10.1145/2460239.2460244
Burjorjee KMoore J(2012)Explaining adaptation in genetic algorithms with uniform crossoverProceedings of the 14th annual conference companion on Genetic and evolutionary computation10.1145/2330784.2330991(1461-1462)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330784.2330991
Chen WShao CHsu PYu TMoore J(2012)A test problem with adjustable degrees of overlap and conflict among subproblemsProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330201(257-264)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330201
Malago LMatteucci MValentini G(2011)Introducing ℓ1-regularized logistic regression in Markov Networks based EDAs2011 IEEE Congress of Evolutionary Computation (CEC)10.1109/CEC.2011.5949804(1581-1588)Online publication date: Jun-2011
https://doi.org/10.1109/CEC.2011.5949804
Hauschild MPelikan M(2010)Performance of network crossover on NK landscapes and spin glassesProceedings of the 11th international conference on Parallel problem solving from nature: Part II10.5555/1887255.1887306(462-471)Online publication date: 11-Sep-2010
https://dl.acm.org/doi/10.5555/1887255.1887306
Zeng GLu YMao W(2010)Finding Ground States of Sherrington-Kirkpatrick Spin Glass by Modified Extremal Optimization2010 International Conference on Computational Intelligence and Software Engineering10.1109/CISE.2010.5677137(1-5)Online publication date: Dec-2010
https://doi.org/10.1109/CISE.2010.5677137
Hauschild MPelikan M(2010)Performance of Network Crossover on NK Landscapes and Spin GlassesParallel Problem Solving from Nature, PPSN XI10.1007/978-3-642-15871-1_47(462-471)Online publication date: 2010
https://doi.org/10.1007/978-3-642-15871-1_47
Pelikan MKatzgraber HRothlauf F(2009)Analysis of evolutionary algorithms on the one-dimensional spin glass with power-law interactionsProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570017(843-850)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570017

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten