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 genetic algorithm (GA) and the univariate marginal distribution algorithm (UMDA). The performance of all tested algorithms is improved by incorporating a deterministic hill climber (DHC) based on single-bit flips and cluster exact approximation (CEA). The results show that hBOA significantly outperforms GA and UMDA with both types of local search and that CEA enables all tested algorithms to solve larger spin-glass instances than DHC. Using advanced hybrid methods created by combining competent genetic and evolutionary algorithms with advanced local searchers thus proves advantageous in this challenging class of problems.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Binder, K., Young, A.: Spin-glasses: Experimental facts, theoretical concepts and open questions. Rev. Mod. Phys. 58, 801 (1986)
Mezard, M., Parisi, G., Virasoro, M.: Spin glass theory and beyond. World Scientific, Singapore (1987)
Fischer, K., Hertz, J.: Spin Glasses. Cambridge University Press, Cambridge (1991)
Young, A. (ed.): Spin glasses and random fields. World Scientific, Singapore (1998)
Hartmann, A.K., Rieger, H.: Optimization Algorithms in Physics. Wiley-VCH, Weinheim (2001)
Hartmann, A.K., Rieger, H. (eds.): New Optimization Algorithms in Physics. Wiley-VCH, Weinheim (2004)
Hartmann, A.K., Weigt, M.: Phase Transitions in Combinatorial Optimization Problems. Wiley-VCH, Weinheim (2005)
Mühlenbein, H., Mahnig, T.: Convergence theory and applications of the factorized distribution algorithm. Journal of Computing and Information Technology 7(1), 19–32 (1999)
Naudts, B., Naudts, J.: The effect of spin-flip symmetry on the performance of the simple GA. Parallel Problem Solving from Nature, 67–76 (1998)
Hartmann, A.K.: Ground-state clusters of two, three and four-dimensional +/-J Ising spin glasses. Phys. Rev. E 63, 016106 (2001)
Van Hoyweghen, C.: Detecting spin-flip symmetry in optimization problems. In: Kallel, L., et al. (eds.) Theoretical Aspects of Evolutionary Computing, pp. 423–437. Springer, Berlin (2001)
Pelikan, M., Goldberg, D.E.: Hierarchical BOA solves Ising spin glasses and MAXSAT. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2003), vol. II, pp. 1275–1286 (2003)
Fischer, S., Wegener, I.: The Ising model on the ring: Mutation versus recombination. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 1113–1124. Springer, Heidelberg (2004)
Dayal, P., Trebst, S., Wessel, S., ürtz, D., Troyer, M., Sabhapandit, S., Coppersmith, S.: Performance limitations of flat histogram methods and optimality of Wang-Langdau sampling. Physical Review Letters 92(9), 097201 (2004)
Pelikan, M., Goldberg, D.E.: Escaping hierarchical traps with competent genetic algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2001), pp. 511–518 (2001)
Pelikan, M.: Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, Heidelberg (2005)
Hartmann, A.K.: Cluster-exact approximation of spin glass ground states. Physica A 224, 480 (1996)
Wang, F., Landau, D.P.: Efficient, multiple-range random walk algorithm to calculate the density of states. Physical Review Letters 86(10), 2050–2053 (2001)
Mühlenbein, H., Paaß, G.: From recombination of genes to the estimation of distributions I. Binary parameters. Parallel Problem Solving from Nature, 178–187 (1996)
Larrañaga, P., Lozano, J.A. (eds.): Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston (2002)
Pelikan, M., Goldberg, D.E., Lobo, F.: A survey of optimization by building and using probabilistic models. Computational Optimization and Applications 21(1), 5–20 (2002)
Chickering, D.M., Heckerman, D., Meek, C.: A Bayesian approach to learning Bayesian networks with local structure. Technical Report MSR-TR-97-07, Microsoft Research, Redmond, WA (1997)
Friedman, N., Goldszmidt, M.: Learning Bayesian networks with local structure. In: Jordan, M.I. (ed.) Graphical models, pp. 421–459. MIT Press, Cambridge (1999)
Harik, G.R.: Finding multimodal solutions using restricted tournament selection. In: Proceedings of the International Conference on Genetic Algorithms (ICGA 1995), pp. 24–31 (1995)
Holland, J.H.: Adaptation in natural and artificial systems. University of Michigan Press, Ann Arbor (1975)
Goldberg, D.E.: Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading (1989)
Claiborne, J.: Mathematical Preliminaries for Computer Networking. Wiley, New York (1990)
Swamy, M., Thulasiraman, K.: Graphs, Networks and Algorithms. Wiley, New York (1991)
Picard, J.C., Ratliff, H.: Minimum cuts and related problems. Networks 5, 357 (1975)
Träff, J.: A heuristic for blocking flow algorithms. Eur. J. Oper. Res. 89, 564 (1996)
Tarjan, R.: Data Structures and Network Algorithms. Society for industrial and applied mathematics, Philadelphia (1983)
Spin Glass Ground State Server. University of Köln, Germany (2004), http://www.informatik.unikoeln.de/ls_juenger/research/sgs/sgs.html
Thierens, D., Goldberg, D.E., Pereira, A.G.: Domino convergence, drift, and the temporal-salience structure of problems. In: Proceedings of the International Conference on Evolutionary Computation (ICEC 1998), pp. 535–540 (1998)
Mühlenbein, H., Schlierkamp-Voosen, D.: Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evol. Comp. 1(1), 25–49 (1993)
Sastry, K., Goldberg, D.E.: Analysis of mixing in genetic algorithms: A survey. IlliGAL Report No. 2002012, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL (2002)
Middleton, A., Fisher, D.S.: The three-dimensional random field Ising magnet: Interfaces, scaling, and the nature of states. Phys. Rev. B 65, 134–411 (2002)
Galluccio, A., Loebl, M.: A theory of Pfaffian orientations. I. Perfect matchings and permanents. Electr. J. of Combinatorics 6(1) Research Paper 6 (1999)
Galluccio, A., Loebl, M.: A theory of Pfaffian orientations. II. T-joins, k-cuts, and duality of enumeration. Electronic Journal of Combinatorics 6(1) Research Paper 7 (1999)
Pelikan, M., Ocenasek, J., Trebst, S., Troyer, M., Alet, F.: Computational complexity and simulation of rare events of Ising spin glasses. In: Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), vol. 2, pp. 36–47 (2004)
Barahona, F.: On the computational complexity of Ising spin glass models. Journal of Physics A: Mathematical, Nuclear and General 15(10), 3241–3253 (1982)
Höns, R.: Estimation of Distribution Algorithms and Minimum Relative Entropy. PhD thesis, University of Bonn, Bonn, Germany (2006)
Shakya, S., McCall, J., Brown, D.: Solving the ising spin glass problem using a bivariate eda based on markov random fields. In: Proceedings of IEEE Congress on Evolutionary Computation (CEC 2006) (to appear, 2006)
Santana, R.: Estimation of distribution algorithms with Kikuchi approximations. Evolutionary Computation 13(1), 67–97 (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pelikan, M., Hartmann, A.K., Sastry, K. (2006). Hierarchical BOA, Cluster Exact Approximation, and Ising Spin Glasses. In: Runarsson, T.P., Beyer, HG., Burke, E., Merelo-Guervós, J.J., Whitley, L.D., Yao, X. (eds) Parallel Problem Solving from Nature - PPSN IX. PPSN 2006. Lecture Notes in Computer Science, vol 4193. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11844297_13
Download citation
DOI: https://doi.org/10.1007/11844297_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-38990-3
Online ISBN: 978-3-540-38991-0
eBook Packages: Computer ScienceComputer Science (R0)