Bayesian optimization algorithm (BOA)
Bayesian optimization algorithm (BOA) (Pelikan, Goldberg, & Cantu-paz, 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
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:
- selection, and
Another way to view BOA is to focus on two model-related processes in BOA:
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 boundedly-difficult 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 black-box optimization problems where candidate solutions are represented by fixed-length vectors over a finite alphabet.
- Model learning.
A model of high-quality solutions is adapted capable of generating increasingly good solutions.
- Model sampling.
The model is repeatedly sampled to generate new candidate solutions.
Best reading for a description of BOA and some BOA theory is my PhD thesis. Here's a short paper on BOA from GECCO-99
(please note that there's a typo in the equation for BDe metric in the short paper).
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.
- 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 Urbana-Champaign, Urbana, IL.
Last update: Mon Aug 6 21:08:13 CDT 2012
by Martin Pelikan