iBOA: the incremental bayesian optimization algorithm

ABSTRACT

This paper proposes the incremental Bayesian optimization algorithm (iBOA), which modifies standard BOA by removing the population of solutions and using incremental updates of the Bayesian network. iBOA is shown to be able to learn and exploit unrestricted Bayesian networks using incremental techniques for updating both the structure as well as the parameters of the probabilistic model. This represents an important step toward the design of competent incremental estimation of distribution algorithms that can solve difficult nearly decomposable problems scalably and reliably.

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: Shumeet Baluja , Scott Davies, Using Optimal Dependency-Trees for Combinational Optimization, Proceedings of the Fourteenth International Conference on Machine Learning, p.30-38, July 08-12, 1997
• 4: 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.
• 5: 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.
• 6: C. Chow and C. Liu. Approximating discrete probability distributions with dependence trees. IEEE Transactions on Information Theory, 14:462--467, 1968.
• 7: 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.
• 8: R. Etxeberria and P. Larra\ naga. Global optimization using Bayesian networks. In A. A. O. Rodriguez, M. R. S. Ortiz, and R. S. Hermida, editors, Second Symposium on Artificial Intelligence (CIMAF-99), pages 332--339, Habana, Cuba, 1999. Institude of Cybernetics, Mathematics, and Physics and Ministry of Science, Technology and Environment.
• 9: Nir Friedman , Moises Goldszmidt, Learning Bayesian networks with local structure, Learning in graphical models, MIT Press, Cambridge, MA, 1999
• 10: David E. Goldberg, The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 11: David E. Goldberg , Kumara Sastry , Xavier Llorà, Toward routine billion-variable optimization using genetic algorithms: Short Communication, Complexity, v.12 n.3, p.27-29, January 2007 [doi>10.1002/cplx.v12:3]
• 12: P. Grünwald. The Minimum Description Length Principle and Reasoning under Uncertainty. PhD thesis, University of Amsterdam, Amsterdam, Netherlands, 1998.
• 13: G. R. Harik, F. G. Lobo, and D. E. Goldberg. The compact genetic algorithm. Proceedings of the International Conference on Evolutionary Computation (ICEC-98), pages 523--528, 1998.
• 14: 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.
• 15: 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.
• 16: 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.
• 17: A. Juels, S. Baluja, and A. Sinclair. The equilibrium genetic algorithm and the role of crossover, 1993.
• 18: P. Larra\ naga and J. A. Lozano, editors. Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation. Kluwer, Boston, MA, 2002.
• 19: Jose A. Lozano , Pedro Larrañaga , Iñaki Inza , Endika Bengoetxea, Towards a New Evolutionary Computation: Advances on Estimation of Distribution Algorithms (Studies in Fuzziness and Soft Computing), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 20: Heinz Mühlenbein , Thilo Mahnig, Fda -a scalable evolutionary algorithm for the optimization of additively decomposed functions, Evolutionary Computation, v.7 n.4, p.353-376, Winter 1999 [doi>10.1162/evco.1999.7.4.353]
• 21: 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
• 22: H. Mühlenbein and D. Schlierkamp-Voosen. Predictive models for the breeder genetic algorithm: I. Continuous parameter optimization. Evolutionary Computation, 1(1):25--49, 1993.
• 23: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 24: M. Pelikan. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.
• 25: M. Pelikan and D. E. Goldberg. Hierarchical Bayesian optimization algorithm. In M. Pelikan, K. Sastry, and E. Cantú-Paz, editors, Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications. Springer, 2006.
• 26: 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.
• 27: 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
• 28: M. Pelikan, K. Sastry, and D. E. Goldberg. Scalability of the Bayesian optimization algorithm. International Journal of Approximate Reasoning, 31(3):221--258, 2002.
• 29: R. Prim. Shortest connection networks and some generalizations. Bell Systems Technical Journal, 36:1389--1401, 1957.
• 30: 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.
• 31: K. Sastry, D. E. Goldberg, and X. Llorà. Towards billion bit optimization via efficient genetic algorithms. IlliGAL Report No. 2007007, University of Illinois at Urbana-Champaign, Illinois Genetic Algorithms Laboratory, Urbana, IL, 2007.
• 32: G. Schwarz. Estimating the dimension of a model. The Annals of Statistics, 6:461--464, 1978.
• 33: 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]
• 34: D. Thierens, D. E. Goldberg, and A. G. Pereira. Domino convergence, drift, and the temporal-salience structure of problems. Proceedings of the International Conference on Evolutionary Computation (ICEC-98), pages 535--540, 1998.

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

Keywords:
BOA, EDA, bayesian optimization algorithm, estimation of distribution algorithms, evolutionary computation, iBOA, incremental boa, incremental model update