Analyzing probabilistic models in hierarchical BOA on traps and spin glasses

ABSTRACT

The hierarchical Bayesian optimization algorithm (hBOA) can solve nearly decomposable and hierarchical problems of bounded difficulty in a robust and scalable manner by building and sampling probabilistic models of promising solutions. This paper analyzes probabilistic models in hBOA on two common test problems: concatenated traps and 2D Ising spin glasses with periodic boundary conditions. We argue that although Bayesian networks with local structures can encode complex probability distributions, analyzing these models in hBOA is relatively straightforward and the results of such analyses may provide practitioners with useful information about their problems. The results show that the probabilistic models in hBOA closely correspond to the structure of the underlying optimization problem, the models do not change significantly in subsequent iterations of BOA, and creating adequate probabilistic models by hand is not straightforward even with complete knowledge of the optimization problem.

REFERENCES

• 1: D. H. Ackley. An empirical study of bit vector function optimization. Genetic Algorithms and Simulated Annealing, pages 170--204, 1987.
• 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: K. Binder and A. Young. Spinglasses: Experimental facts, theoretical concepts and open questions. Rev. Mod. Phys., 58:801, 1986.
• 5: P. A. N. Bosman and D. Thierens. Continuous iterated density estimation evolutionary algorithms within the IDEA framework. Workshop Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2000), pages 197--200, 2000.
• 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: P. Dayal, S. Trebst, S. Wessel, D. Würtz, M. Troyer, S. Sabhapandit, and S. Coppersmith. Performance limitations of flat histogram methods and optimality of Wang-Langdau sampling. Physical Review Letters, 92(9):097201, 2004.
• 8: K. Deb and D. E. Goldberg. Analyzing deception in trap functions. IlliGAL Report No. 91009, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1991.
• 9: K. Fischer and J. Hertz. Spin Glasses. Cambridge University Press, Cambridge, 1991.
• 10: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 11: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 12: 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
• 13: R. A. Howard and J. E. Matheson. Influence diagrams. In R. A. Howard and J. E. Matheson, editors, Readings on the principles and applications of decision analysis, volume II, pages 721--762. Strategic Decisions Group, Menlo Park, CA, 1981.
• 14: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
• 15: C. F. Lima et al. Structural accuracy of probabilistic models in BOA. Technical report, University of Algarve, 2007.
• 16: C. F. Lima, M. Pelikan, K. Sastry, M. V. Butz, D. E. Goldberg, and F. G. Lobo. Substructural neighborhoods for local search in the Bayesian optimization algorithm. Parallel Problem Solving from Nature, pages 232--241, 2006.
• 17: M. Mezard, G. Parisi, and M. Virasoro. Spin glass theory and beyond. World Scientific, Singapore, 1987.
• 18: Heinz Mühlenbein , Thilo Mahnig , Alberto Ochoa Rodriguez, Schemata, Distributions and Graphical Models in Evolutionary Optimization, Journal of Heuristics, v.5 n.2, p.215-247, July 1999 [doi>10.1023/A:1009689913453]
• 19: 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
• 20: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 21: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer-Verlag, 2005.
• 22: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Genetic and Evolutionary Computation Conference (GECCO2001), pages 511--518, 2001.
• 23: M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and MAXSAT. Genetic and Evolutionary Computation Conference (GECCO2003), II:1275--1286, 2003.
• 24: 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]
• 25: M. Pelikan and D. E. Goldberg. Hierarchical Bayesian optimization algorithm. In M. Pelikan, K. Sastry, and E. Cant'u-Paz, editors, Scalable optimization via probabilistic modeling: From algorithms to applications, pages 63--90. Springer, 2006.
• 26: M. Pelikan, D. E. Goldberg, and E. CantúPaz. BOA: The Bayesian optimization algorithm. Genetic and Evolutionary Computation Conference (GECCO99), I:525--532, 1999.
• 27: 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]
• 28: M. Pelikan and A. K. Hartmann. Searching for ground states of Ising spin glasses with hierarchical BOA and cluster exact approximation. In M. Pelikan, K. Sastry, and E. CantúPaz, editors, Scalable optimization via probabilistic modeling: From algorithms to applications, pages 333--349. Springer, 2006.
• 29: M. Pelikan and K. Sastry. Fitness inheritance in the Bayesian optimization algorithm. Genetic and Evolutionary Computation Conference (GECCO2004), 2:48--59, 2004.
• 30: M. Pelikan, K. Sastry, M. V. Butz, and D. E. Goldberg. Performance of evolutionary algorithms on random decomposable problems. Parallel Problem Solving from Nature (PPSN IX), pages 788--797, 2006.
• 31: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning, 31(3):221--258, 2002.
• 32: M. Pelikan, K. Sastry, and D. E. Goldberg. Sporadic model building for e#ciency enhancement of hierarchical BOA. pages 405--412, 2006.
• 33: K. Sastry. Evaluationrelaxation schemes for genetic and evolutionary algorithms. Master's thesis, University of Illinois at UrbanaChampaign, Department of General Engineering, Urbana, IL, 2001.
• 34: K. Sastry and D. E. Goldberg. Designing competent mutation operators via probabilistic model building of neighborhoods. Genetic and Evolutionary Computation Conference (GECCO2004), pages 114--125, 2630 2004.
• 35: K. Sastry, D. E. Goldberg, and M. Pelikan. Don't evaluate, inherit. Genetic and Evolutionary Computation Conference (GECCO2001), pages 551--558, 2001.
• 36: K. Sastry, M. Pelikan, and D. E. Goldberg. Efficiency enhancement of estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cant'uPaz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, pages 161--185. Springer, 2006.
• 37: Herbert A. Simon, The sciences of the artificial (3rd ed.), MIT Press, Cambridge, MA, 1996
• 38: Spin Glass Ground State Server. http://www.informatik.uni-koeln.de/ls_juenger/research/sgs/sgs.html, 2004. University of Küoln, Germany.
• 39: Dirk Thierens , David E. Goldberg, Mixing in Genetic Algorithms, Proceedings of the 5th International Conference on Genetic Algorithms, p.38-47, June 01, 1993
• 40: H. Wu and J. L. Shapiro. Does overfitting affect performance in estimation of distribution algorithms. pages 433--434, 2006.
• 41: A. Young, editor. Spin glasses and random fields. World Scientific, Singapore, 1998.
• 42: T.L. Yu. A Matrix Approach for Finding Extreme: Problems with Modularity, Hierarchy, and Overlap. PhD thesis, University of Illinois at UrbanaChampaign, Urbana, IL, 2006.

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:
bayesian optimization algorithm, estimation of distribution algorithms, hierarchical BOA, model accuracy