Choosing Search Algorithms in Bayesian Optimization Algorithm

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.

• Hao Wu
• Jonathan L. Shapiro

• Bayesian optimization algorithm
• greedy search
• KL divergence
• stochastic search.

[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.