Bayesian optimization algorithm (BOA)
Bayesian optimization algorithm (BOA) (Pelikan, Goldberg, & Cantupaz, 1998) evolves a population of candidate solutions to the given optimization problem.
The initial population is generated at random. The population is then updated for a number of iterations using
two operators:
 selection, and
 variation.
Selection makes multiple copies of better solutions and eliminates
the worst ones. Variation starts by constructing a Bayesian network as a model of promising
solutions after selection. New candidate solutions are then generated by sampling the constructed Bayesian network.
Finally, new solutions are incorporated into the population, eliminating some old candidate solutions, and next iteration is
executed unless termination criteria are met. The following figure displays the main iteration of BOA:
Another way to view BOA is to focus on two modelrelated processes in BOA:
 Model learning.
A model of highquality solutions is adapted capable of generating increasingly good solutions.
 Model sampling.
The model is repeatedly sampled to generate new candidate solutions.
The search for the optimum can thus be viewed as a sequence of models leading to better and better solutions, until a model of global optima is constructed. Bayesian networks allow automated learning of decomposition that breaks up the given problem into boundedlydifficult subproblems. Exploitation of appropriate problem decomposition via sampling the built Bayesian network ensures efficient exploitation of decomposition for effective exploration. BOA can solve problems that can be decomposed into subproblems of bounded order in quadratic or subquadratic number of function evaluations. It can be applied to blackbox optimization problems where candidate solutions are represented by fixedlength vectors over a finite alphabet.
Reading
Best reading for a description of BOA and some BOA theory is my PhD thesis. Here's a short paper on BOA from GECCO99
(please note that there's a typo in the equation for BDe metric in the short paper).
Code
There C/C++ is code available for the basic BOA with BDe metric and for BOA with decision graphs (two versions), go to the software page to download the code. Updates are planned for all versions.
References
 Pelikan, M., Goldberg, D. E., & CantúPaz, E. (1998). Linkage problem, distribution estimation, and Bayesian networks. IlliGAL Report No. 98013: Illinois Genetic Algorithm Laboratory, University of Illinois at UrbanaChampaign, Urbana, IL.
Last update: Mon Aug 6 21:08:13 CDT 2012
by Martin Pelikan
