Intelligent bias of network structures in the hierarchical BOA

ABSTRACT

One of the primary advantages of estimation of distribution algorithms (EDAs) over many other stochastic optimization techniques is that they supply us with a roadmap of how they solve a problem. This roadmap consists of a sequence of probabilistic models of candidate solutions of increasing quality. The first model in this sequence would typically encode the uniform distribution over all admissible solutions whereas the last model would encode a distribution that generates at least one global optimum with high probability. It has been argued that exploiting this knowledge should improve EDA performance when solving similar problems. This paper presents an approach to bias the building of Bayesian network models in the hierarchical Bayesian optimization algorithm (hBOA) using information gathered from models generated during previous hBOA runs on similar problems. The approach is evaluated on trap-5 and 2D spin glass problems.

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: S. Baluja. Incorporating a priori knowledge in probabilistic-model based optimization. In M. Pelikan, K. Sastry, and E. Cantu-Paz, editors, Scalable optimization via probabilistic modeling: From algorithms to applications, pages 205--219. Springer, 2006.
• 4: 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.
• 5: P. Dayal, S. Trebst, S. Wessel, D. Wurtz, 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.
• 6: K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence, 10:385--408, 1994.
• 7: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 8: 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
• 9: Mark Hauschild , Martin Pelikan , Claudio F. Lima , Kumara Sastry, Analyzing probabilistic models in hierarchical BOA on traps and spin glasses, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277070]
• 10: Mark W. Hauschild , Martin Pelikan , Kumara Sastry , David E. Goldberg, Using previous models to bias structural learning in the hierarchical BOA, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389172]
• 11: D. Heckerman, D. Geiger, and D. M. Chickering. Learning Bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research, Redmond, WA, 1994.
• 12: 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.
• 13: Pedro Larraanaga , Jose A. Lozano, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation, Kluwer Academic Publishers, Norwell, MA, 2001
• 14: Claudio F. Lima , Fernando G. Lobo , Martin Pelikan, From mating pool distributions to model overfitting, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389174]
• 15: H. Muhlenbein and T. Mahnig. Evolutionary optimization and the estimation of search distributions with applications to graph bipartitioning. International Journal on Approximate Reasoning, 31(3):157--192, 2002.
• 16: H. Muhlenbein, T. Mahnig, and A. O. Rodriguez. Schemata, distributions and graphical models in evolutionary optimization. Submitted for publication, 1998.
• 17: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 18: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer-Verlag, 2005.
• 19: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Genetic and Evolutionary Computation Conf. (GECCO-2001), pages 511--518, 2001.
• 20: 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.
• 21: M. Pelikan and D. E. Goldberg. Hierarchical Bayesian optimization algorithm. In M. Pelikan, K. Sastry, and E. Cantu-Paz, editors, Scalable optimization via probabilistic modeling: From algorithms to applications, pages 63--90. Springer, 2006.
• 22: 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]
• 23: 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
• 24: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. Int. Journal of Approximate Reasoning, 31(3):221--258, 2002.
• 25: R. Santana, P. Larranaga, and J. A. Lozano. The role of a priori information in the minimization of contact potentials by means of estimation of distribution algorithms. In E. Marchiori, J. H. Moore, and J. C. Rajapakse, editors, Proc. of the 5th European Conf. on Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics, volume 4447 of Lecture Notes in Computer Science, pages 247--257. Springer, 2007.
• 26: K. Sastry. Efficient atomic cluster optimization using a hybrid extended compact genetic algorithm with seeded population. IlliGAL Report No. 2001018, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2001.
• 27: 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.
• 28: J. Schwarz and J. Ocenasek. A problem-knowledge based evolutionary algorithm KBOA for hypergraph partitioning, 2000. Personal communication.
• 29: Spin Glass Ground State Server. http://www.informatik.uni-koeln.de/ls_juenger/research/sgs/sgs.html, 2004. University of Koln, Germany.
• 30: Dirk Thierens, Scalability problems of simple genetic algorithms, Evolutionary Computation, v.7 n.4, p.331-352, Winter 1999 [doi>10.1162/evco.1999.7.4.331]

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, efficiency enhancement, estimation of distribution algorithms, hierarchical BOA, learning from experience, model complexity