Analysis of evolutionary algorithms on the one-dimensional spin glass with power-law interactions

ABSTRACT

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 interactions, what makes the problem interesting as an algorithm benchmark. As algorithms, the paper considers the genetic algorithm (GA) with twopoint and uniform crossover, and the hierarchical Bayesian optimization algorithm (hBOA). hBOA is shown to outperform both variants of GA, whereas GA with uniform crossover is shown to perform worst. The differences between the compared algorithms become more significant as the problem size grows and as the range of interactions decreases. Unlike for GA with uniform crossover, for hBOA and GA with twopoint crossover, instances with short-range interactions are shown to be easier. The paper also points out interesting avenues for future research.

REFERENCES

• 1: Shummet Baluja, Population-Based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Learning, Carnegie Mellon University, Pittsburgh, PA, 1994
• 2: F. Barahona. On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical, Nuclear and General, 15(10):3241--3253, 1982.
• 3: J. W. Barnes, B. Dimova, S. P. Dokov, and A. Solomon. The theory of elementary landscapes. Appl. Math. Lett., 16(3):337--343, 2003.
• 4: S. Boettcher. Extremal optimization for Sherrington-Kirkpatrick spin glasses. Eur. Phys. J. B, 46:501--505, 2005.
• 5: S. Boettcher, H. G. Katzgraber, and D. Sherrington. Local field distributions in spin glasses. Journal of Physics A: Mathematical and Theoretical, 41(32):324007, 2008.
• 6: 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.
• 7: S. Fischer and I. Wegener. The ising model on the ring: Mutation versus recombination. Genetic and Evolutionary Computation Conf. (GECCO-2004), pages 1113--1124, 2004.
• 8: D. S. Fisher and D. A. Huse. Equilibrium behavior of the spin--glass ordered phase. Phys. Rev. B, 38:386, 1988.
• 9: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 10: David E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 11: D. E. Goldberg, K. Deb, and J. H. Clark. Genetic algorithms, noise, and the sizing of populations. Complex Systems, 6:333--362, 1992.
• 12: D. E. Goldberg and M. Rudnick. Genetic algorithms and the variance of fitness. Complex Systems, 5(3):265--278, 1991.
• 13: 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
• 14: G. R. Harik, E. Cantú-Paz, D. E. Goldberg, and B. L. Miller. The gambler's ruin problem, genetic algorithms, and the sizing of populations. International Conf. on Evolutionary Computation (ICEC-97), pages 7--12, 1997.
• 15: S. Boettcher, H. G. Katzgraber, and D. Sherrington. Local A. K. Hartmann. Ground-state clusters of two, three and four-dimensional +/-J Ising spin glasses. Phys. Rev. E 63:016106, 2001.
• 16: 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. .
• 17: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 18: L. Kallel , B. Naudts , C. R. Reeves, Properties of fitness functions and search landscapes, Theoretical aspects of evolutionary computing, Springer-Verlag, London, 2001
• 19: H. G. Katzgraber. Spin glasses and algorithm benchmarks: A one-dimensional view. Journal of Physics: Conf. Series 95:012004, 2008.
• 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: H. G. Katzgraber and A. P. Young. Monte Carlo studies of the one-dimensional Ising spin glass with power-law interactions. Phys. Rev. B 67:134410, 2003.
• 22: S. Kirkpatrick and D. Sherrington. In finite-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: G. Kotliar, P. W. Anderson, and D. L. Stein. One-dimensional spin-glass model with long-range random interactions. Phys. Rev. B 27:R602, 1983.
• 25: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation Kluwer, Boston, MA, 2002.
• 26: Jose A. Lozano , Pedro Larrañaga , Iñaki Inza , Endika Bengoetxea, Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 27: H. Mühlenbein and T. Mahnig. Convergence theory and applications of the factorized distribution algorithm. Journal of Computing and Information Technology 7(1):19--32, 1998.
• 28: Heinz Mühlenbein , Thilo Mahnig, Fda -a scalable evolutionary algorithm for the optimization of additively decomposed functions, Evolutionary Computation, v.7 n.4, p.353-376, Winter 1999 [doi>10.1162/evco.1999.7.4.353]
• 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: Heinz Mühlenbein , Dirk Schlierkamp-Voosen, Predictive models for the breeder genetic algorithm i. continuous parameter optimization, Evolutionary Computation, v.1 n.1, p.25-49, Spring 1993 [doi>10.1162/evco.1993.1.1.25]
• 31: Bart Naudts , Jan Naudts, The Effect of Spin-Flip Symmetry on the Performance of the Simple GA, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.67-76, September 27-30, 1998
• 32: B. Naudts, D. Suys, and A. Verschoren. Epistasis as a basic concept in formal landscape analysis. International Conf. on Genetic Algorithms (ICGA-97)pages 65--72, 1997.
• 33: 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.
• 34: K. F. Pál. Hysteretic optimization for the Sherrington Kirkpatrick spin glass. Physica A 367:261--268, 2006.
• 35: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms Springer, 2005.
• 36: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Genetic and Evolutionary Computation Conf.(GECCO-2001) pages 511--518, 2001.
• 37: M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and maxsat. Genetic and Evolutionary Computation Conf.(GECCO-2003) II:1275--1286, 2003.
• 38: Martin Pelikan , David E. Goldberg, A hierarchy machine: learning to optimize from nature and humans, Complexity, v.8 n.5, p.36-45, May/June 2003 [doi>10.1002/cplx.10103]
• 39: 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]
• 40: M. Pelikan and A. K. Hartmann. Hierarchical BOA, cluster exact approximation, and Ising spin glasses. Parallel Problem Solving from Nature pages 122--131, 2006.
• 41: Martin Pelikan , Katzgraber G. Helmut , Sigismund Kobe, Finding ground states of Sherrington-Kirkpatrick spin glasses with hierarchical boa and genetic algorithms, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389176]
• 42: Martin Pelikan , Kumara Sastry , Erick Cantú-Paz, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications (Studies in Computational Intelligence), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 43: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning 31(3):221--258, 2002.
• 44: Franz Rothlauf , David E. Goldberg, Representations for Genetic and Evolutionary Algorithms, Physica-Verlag, 2002
• 45: 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.
• 46: D. Thierens, D. E. Goldberg, andA. G. Pereira. Domino convergence, drift, and the temporal-salience structure of problems. International Conf. on Evolutionary Computation (ICEC-98) pages 535--540, 1998.
• 47: C. Van Hoyweghen, Detecting spin-flip symmetry in optimization problems, Theoretical aspects of evolutionary computing, Springer-Verlag, London, 2001
• 48: Tian-Li Yu , Kumara Sastry , David E. Goldberg , Martin Pelikan, Population sizing for entropy-based model building in discrete estimation of distribution algorithms, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277080]
• 49: Q. Zhang. On stability of fixed points of limit models of univariate marginal distribution algorithm and factorized distribution algorithm. IEEE Transactions on Evolutionary Computation 8:80--93, 2004.
• 50: Q. Zhang and H. Muhlenbein. On the convergence of a class of estimation of distribution algorithms. IEEE Transactions on Evolutionary Computation 8:127--136, 2004.

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

General Terms:
Algorithms, Performance

Keywords:
crossover, estimation of distribution algorithms, evolutionary computation, ga, genetic algorithm, hboa, hierarchical boa, hybridization, physics, power-law interactions, sherrington-kirkpatrick spin glass, spin glass