Using previous models to bias structural learning in the hierarchical BOA

ABSTRACT

Estimation of distribution algorithms (EDAs) are stochastic optimization techniques that explore the space of potential solutions by building and sampling probabilistic models of promising candidate solutions. While the primary goal of applying EDAs is to discover the global optimum (or an accurate approximation), any EDA also provides us with a sequence of probabilistic models, which hold a great deal of information about the problem. Although using problem-specific knowledge has been shown to significantly improve performance of EDAs and other evolutionary algorithms, this readily available source of information has been largely ignored by the EDA community. This paper takes the first step towards the use of probabilistic models obtained by EDAs to speed up the solution of similar problems in the future. More specifically, we propose two approaches to biasing model building in the hierarchical Bayesian optimization algorithm (hBOA) based on knowledge automatically learned from previous runs on similar problems. We show that the methods lead to substantial speedups and argue that they should work well in other applications that require solving a large number of problems with similar structure.

REFERENCES

• 1: 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.
• 2: D. Boughaci and H. Drias. A performance comparison of evolutionary meta-heuristics and solving MAX-SAT problems. In A. Okatan, editor, International Conference on Computational Intelligence, pages 379--383. International Computational Intelligence Society, 2004.
• 3: Alexander E. I. Brownlee , John A. W. McCall , Deryck F. Brown, Solving the MAXSAT problem using a multivariate EDA based on Markov networks, Proceedings of the 2007 GECCO conference companion on Genetic and evolutionary computation, July 07-11, 2007, London, United Kingdom [doi>10.1145/1274000.1274005]
• 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. W¨urtz, 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: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 7: Ian P. Gent , Holger H. Hoos , Patrick Prosser , Toby Walsh, Morphing: combining structure and randomness, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.654-660, July 18-22, 1999, Orlando, Florida, United States
• 8: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 9: Jens Gottlieb , Elena Marchiori , Claudio Rossi, Evolutionary algorithms for the satisfiability problem, Evolutionary Computation, v.10 n.1, p.35-50, Spring 2002 [doi>10.1162/106365602317301763]
• 10: 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
• 11: 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]
• 12: H. H. Hoos and T. Stutzle. Satlib: An online resource for research on sat. SAT 2000, pages 283--292, 2000. SATLIB is available online at www.satlib.org.
• 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Ünaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
• 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: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 17: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer-Verlag, 2005.
• 18: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Genetic and Evolutionary Computation Conference (GECCO-2001), pages 511--518, 2001.
• 19: M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and MAXSAT. Genetic and Evolutionary Computation Conference (GECCO-2003), II:1275--1286, 2003.
• 20: 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]
• 21: 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
• 22: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning, 31(3):221--258, 2002.
• 23: Soraya B. Rana , L. Darrell Whitley, Genetic Algorithm Behavior in the MAXSAT Domain, Proceedings of the 5th International Conference on Parallel Problem Solving from Nature, p.785-794, September 27-30, 1998
• 24: 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.
• 25: 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.
• 26: 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
• 27: J. Schwarz and J. Ocenasek. A problem-knowledge based evolutionary algorithm KBOA for hypergraph partitioning, 2000. Personal communication.
• 28: Spin Glass Ground State Server. http://www.informatik.uni-koeln.de/ls_juenger/research/sgs/sgs.html, 2004. University of Koln, Germany.

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:
estimation of distribution algorithms, hierarchical boa, learning from experience, model complexity, prior knowledge, probabilistic model