Choosing Search Algorithms in Bayesian Optimization Algorithm

Authors: Hao Wu, Jonathan L. Shapiro

Abstract:

The Bayesian Optimization Algorithm (BOA) is an algorithm based on the estimation of distributions. It uses techniques from modeling data by Bayesian networks to estimating the joint distribution of promising solutions. To obtain the structure of Bayesian network, different search algorithms can be used. The key point that BOA addresses is whether the constructed Bayesian network could generate new and useful solutions (strings), which could lead the algorithm in the right direction to solve the problem. Undoubtedly, this ability is a crucial factor of the efficiency of BOA. Varied search algorithms can be used in BOA, but their performances are different. For choosing better ones, certain suitable method to present their ability difference is needed. In this paper, a greedy search algorithm and a stochastic search algorithm are used in BOA to solve certain optimization problem. A method using Kullback-Leibler (KL) Divergence to reflect their difference is described.

Keywords: Bayesian optimization algorithm, greedy search, KL divergence, stochastic search.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1058941

References:

[1] T. M. Cover, Elements of information theory, Wiley series in telecommunications, New York, 1991.
[2] Martin Pelikan, David E. Goldberg and Erick Cantu-Paz, "BOA: The Bayesian Optimization Algorithm," IlliGAL Report No. 99003. Illinois Genetic Algorithms Laboratory 1999.
[3] Martin Pelikan, David E. Goldberg, Kumara Sastry, Bayesian "Optimization Algorithm, Decision Graphs and Occam-s Razor," IlliGAL Report No.2000020 Illinois Genetic Algorithms Laboratory, 2000.
[4] Judea Pearl, Probabilistic Reasoning in Intelligence Systems, Morgan Kaufmann, San Mateo, CA, 1988.
[5] R. W. Robinson, Counting Unlabeled Acyclic digraphs. In C. H. C. Little, Ed., Combinatorial Mathematics V, volume 622 of Lecture Notes in Mathematics, Berlin, 1977.
[6] Martin Pelikan, David E. Goldberg, Erick Cantu-Paz, "Linkage Problem, Distribution Estimation and Bayesian Networks," Evolutionary Computation (2000) 8(3): 311-340.
[7] Peter Grunwald, "A Tutorial Introduction to Minimum Description Length Principle," Centrum voor Wiskunde en Informatica, 2004
[8] Pedro Larranaga, Jose A. Lozano, Estimation of Distribution Algorithms. University of the Basque Country, 2002.