Order or not: does parallelization of model building in hBOA affect its scalability?

ABSTRACT

It has been shown that model building in the hierarchical Bayesian optimization algorithm (hBOA) can be efficiently parallelized by randomly generating an ancestral ordering of the nodes of the network prior to learning the network structure and allowing only dependencies consistent with the generated ordering. However, it has not been thoroughly shown that this approach to restricting probabilistic models does not affect scalability of hBOA on important classes of problems. This paper demonstrates that although the use of a random ancestral ordering restricts the structure of considered models to allow efficient parallelization of model building, its effects on hBOA performance and scalability are negligible.

REFERENCES

• 1: D. H. Ackley. An empirical study of bit vector function optimization. Genetic Algorithms and Simulated Annealing pages 170--204, 1987.
• 2: P. A. N. Bosman and D. Thierens. Linkage information processing in distribution estimation algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99) I:60--67, 1999.
• 3: 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.
• 4: Gregory F. Cooper , Edward Herskovits, A Bayesian Method for the Induction of Probabilistic Networks from Data, Machine Learning, v.9 n.4, p.309-347, Oct. 1992 [doi>10.1023/A:1022649401552]
• 5: 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.
• 6: 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.
• 7: K. Deb and D. E. Goldberg. Sufficient conditions for deceptive and easy binary functions. Annals of Mathematics and Artificial Intelligence 10:385--408, 1994.
• 8: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 9: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 10: G. Harik. Linkage learning via probabilistic modeling in the ECGA. IlliGAL Report No. 99010, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 1999.
• 11: 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
• 12: A. K. Hartmann. Ground-state clusters of two, three and four-dimensional +/-J Ising spin glasses. Phys. Rev. E 63:016106, 2001.
• 13: 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.
• 14: M. Henrion. Propagating uncertainty in Bayesian networks by probabilistic logic sampling. In J. F. Lemmer and L. N. Kanal, editors, Uncertainty in Artificial Intelligence pages 149--163. Elsevier, Amsterdam, London, New York, 1988.
• 15: 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.
• 16: P. Larrañaga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation Kluwer, Boston, MA, 2002.
• 17: A. Mendiburu, J. A. Lozano, and J. Miguel-Alonso. Parallel estimation of distribution algorithms:New approaches. Technical Report Technical Report EHU-KAT-IK-1-3, Department of Computer Architecture and Technology, The University of the Basque Country, 2003.
• 18: A. Mendiburu , J. Miguel-Alonso , J. A. Lozano , M. Ostra , C. Ubide, Parallel EDAs to create multivariate calibration models for quantitative chemical applications, Journal of Parallel and Distributed Computing, v.66 n.8, p.1002-1013, August 2006 [doi>10.1016/j.jpdc.2006.03.001]
• 19: J. Ocenasek. Parallel Estimation of Distribution Algorithms PhD thesis, Faculty of Information Technology, Brno University of Technology, Brno, 2002.
• 20: J. Ocenasek, E. Cantú-Paz, M. Pelikan, and J. Schwarz. Design of parallel estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications Springer, 2006.
• 21: J. Ocenasek and J. Schwarz. The parallel Bayesian optimization algorithm. In Proceedings of the European Symposium on Computational Inteligence pages 61--67. Physica-Verlag, 2000.
• 22: J. Ocenasek, J. Schwarz, andM. Pelikan. Designof multithreaded estimation of distribution algorithms. Proceedings of the Genetic and Evol utionary Computation Conference (GECCO-2003)pages 1247--1258, 2003.
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: Martin Pelikan , David E. Goldberg, Bayesian optimization algorithm: from single level to hierarchy, University of Illinois at Urbana-Champaign, Champaign, IL, 2002
• 25: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms Springer-Verlag, 2005.
• 26: M. Pelikan and D. E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)pages 511--518, 2001. Also IlliGAL Report No. 2000020.
• 27: M. Pelikan and D. E. Goldberg. Hierarchical BOA solves Ising spin glasses and MAXSAT. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003)II:1275--1286, 2003. Also IlliGAL Report No. 2003001.
• 28: M. Pelikan and D. E. Goldberg. Hierarchical bayesian optimization algorithm. In E. Cantú-Paz, M. Pelikan, and K. Sastry, editors, Scalable optimization via probabilistic modeling: From algorithms to applications pages 63--90. Springer, 2006.
• 29: M. Pelikan, D. E. Goldberg, and E. Cantú-Paz. BOA: The Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-99)I:525--532, 1999. Also IlliGAL Report No. 99003.
• 30: 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]
• 31: M. Pelikan, D. E. Goldberg, and K. Sastry. Bayesian optimization algorithm, decision graphs, and Occam's razor. Proceedings of the Genetic and Evol utionary Computation Conference (GECCO-2001)pages 519--526, 2001. Also IlliGAL Report No. 2000020.
• 32: M. Pelikan and A. K. Hartmann. Searching for ground states of Ising spin glasses with hierarchical BOA and cluster exact approximation. In E. Cantú-Paz, M. Pelikan, and K. Sastry, editors, Scalable optimization via probabilistic modeling: From algorithms to applications pages 333--349. Springer, 2006.
• 33: M. Pelikan and K. Sastry. Fitness inheritance in the Bayesian optimization algorithm. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2004)2:48--59, 2004.
• 34: 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
• 35: Martin Pelikan , Kumara Sastry , David E. Goldberg, Sporadic model building for efficiency enhancement of hierarchical BOA, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144072]
• 36: 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. Also IlliGAL Report No. 2002004.
• 37: K. Sastry and D. E. Goldberg. On extended compact genetic algorithm. IlliGAL Report No. 2000026, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2000.
• 38: K. Sastry, D. E. Goldberg, and M. Pelikan. Don't evaluate, inherit. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001)pages 551--558, 2001. Also IlliGAL Report No. 2001013.
• 39: K. Sastry, M. Pelikan, and D. E. Goldberg. Efficiency enhancement of estimation of distribution algorithms. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications pages 161--185. Springer, 2006.
• 40: D. Thierens. Analysis and design of genetic algorithms PhD thesis, Katholieke Universiteit Leuven, Leuven, Belgium, 1995.

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 networks, decomposable problems, efficiency enhancement, evolutionary algorithms, hierarchical Bayesian optimization algorithm, parallelization, probabilistic models