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 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: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 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: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 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: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 12: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 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: Georges R. Harik, Finding Multimodal Solutions Using Restricted Tournament Selection, Proceedings of the 6th International Conference on Genetic Algorithms, p.24-31, July 15-19, 1995
• 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: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 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: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 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: Heinz Mühlenbein , Gerhard Paass, From Recombination of Genes to the Estimation of Distributions I. Binary Parameters, Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, p.178-187, September 22-26, 1996
• 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: Martin Pelikan , David E. Goldberg , Fernando G. Lobo, A Survey of Optimization by Building and Using Probabilistic Models, Computational Optimization and Applications, v.21 n.1, p.5-20, January 2002 [doi>10.1023/A:1013500812258]
• 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: Martin Pelikan , Kumara Sastry , David E. Goldberg, Sporadic model building for efficiency enhancement of hierarchical BOA, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144072]
• 41: Roberto Santana, Estimation of Distribution Algorithms with Kikuchi Approximations, Evolutionary Computation, v.13 n.1, p.67-97, January 2005 [doi>10.1162/1063656053583496]
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Physics

General Terms:
Algorithms, Performance

Keywords:
EDA, branch and bound, estimation of distribution algorithms, evolutionary computation, genetic algorithm, hBOA, hierarchical boa, sherrington-kirkpatrick spin glass, sk spin glass