MEDAL




Home
Curriculum Vitae
Current Research
Publications
Books
Software
Presentations
Photos
Contact

MEDAL
MEDAL Blogging

BOA
hBOA



External links:
   hBOATM
   IlliGAL
   ACM SIGEVO
   www.arxiv.org
   more...

Bayesian optimization algorithm (BOA)
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 two operators:
  1. selection, and
  2. 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 model-related processes in BOA:
  • 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.
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.



Reading
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).



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 Urbana-Champaign, Urbana, IL.

Last update: Mon Aug 6 21:08:13 CDT 2012 by Martin Pelikan