Clever Algorithms: Nature-Inspired Programming Recipes

A book by Jason Brownlee

Probabilistic Algorithms

Overview

This chapter describes Probabilistic Algorithms

Probabilistic Algorithms are those algorithms that model a problem or search a problem space using an probabilistic model of candidate solutions. Many Metaheuristics and Computational Intelligence algorithms may be considered probabilistic, although the difference with algorithms is the explicit (rather than implicit) use of the tools of probability in problem solving. The majority of the algorithms described in this Chapter are referred to as Estimation of Distribution Algorithms.

Estimation of Distribution Algorithms

Estimation of Distribution Algorithms (EDA) also called Probabilistic Model-Building Genetic Algorithms (PMBGA) are an extension of the field of Evolutionary Computation that model a population of candidate solutions as a probabilistic model. They generally involve iterations that alternate between creating candidate solutions in the problem space from a probabilistic model, and reducing a collection of generated candidate solutions into a probabilistic model.

The model at the heart of an EDA typically provides the probabilistic expectation of a component or component configuration comprising part of an optimal solution. This estimation is typically based on the observed frequency of use of the component in better than average candidate solutions. The probabilistic model is used to generate candidate solutions in the problem space, typically in a component-wise or step-wise manner using a domain specific construction method to ensure validity.

Pelikan et al. provide a comprehensive summary of the field of probabilistic optimization algorithms, summarizing the core approaches and their differences [Pelikan2002b]. The edited volume by Pelikan, Sastry, and Cantu-Paz provides a collection of studies on the popular Estimation of Distribution algorithms as well as methodology for designing algorithms and application demonstration studies [Pelikan2006]. An edited volume on studies of EDAs by Larranaga and Lozano [Larranaga2002] and the follow-up volume by Lozano et al. [Lozano2006] provide an applied foundation for the field.

Algorithms

Extensions

There are many other algorithms and classes of algorithm that were not described from the field of Estimation of Distribution Algorithm, not limited to:

Extensions to UMDA: Extensions to the Univariate Marginal Distribution Algorithm such as the Bivariate Marginal Distribution Algorithm (BMDA) [Pelikan1998] [Pelikan1999] and the Factorized Distribution Algorithm (FDA) [Muhlenbein1999].
Extensions to cGA: Extensions to the Compact Genetic Algorithm such as the Extended Compact Genetic Algorithm (ECGA) [Harik1999a] [Harik2006].
Extensions to BOA: Extensions to the Bayesian Optimization Algorithm such as the Hierarchal Bayesian Optimization Algorithm (hBOA) [Pelikan2000] [Pelikan2001b] and the Incremental Bayesian Optimization Algorithm (iBOA) [Pelikan2008].
Bayesian Network Algorithms: Other Bayesian network algorithms such as The Estimation of Bayesian Network Algorithm [Etxeberria1999], and the Learning Factorized Distribution Algorithm (LFDA) [Muehlenbein1999].
PIPE: The Probabilistic Incremental Program Evolution that uses EDA methods for constructing programs [Salustowicz1997].
SHCLVND: The Stochastic Hill-Climbing with Learning by Vectors of Normal Distributions algorithm [Rudlof1996].

Bibliography

[Etxeberria1999]	R. Etxeberria and P. Larranaga, "Global optimization using Bayesian networks", in Proceedings of the Second Symposium on Artificial Intelligence (CIMAF-99), 1999.
[Harik1999a]	G. R. Harik, "Linkage Learning via Probabilistic Modeling in the Extended Compact\n\tGenetic Algorithm (ECGA)", Technical Report 99010, Illinois Genetic Algorithms Laboratory, Department of General Engineering,\n\tUniversity of Illinois, 1999.
[Harik2006]	G. R. Harik and F. G. Lobo and K. Sastry, "Linkage Learning via Probabilistic Modeling in the Extended Compact\n\tGenetic Algorithm (ECGA)", in Scalable Optimization via Probabilistic Modeling, pages 39–61, Springer, 2006.
[Larranaga2002]	P. Larranaga and J. A. Lozano, "Estimation of distribution algorithms: A new tool for evolutionary\n\tcomputation", Springer, 2002.
[Lozano2006]	J. A. Lozano and P. Larranaga and I. Inza and E. Bengoetxea, "Towards a new evolutionary computation. Advances in estimation of\n\tdistribution algorithms", Springer, 2006.
[Muehlenbein1999]	H. M\ühlenbein and T. Mahnig, "FDA–A Scalable Evolutionary Algorithm for the Optimization of\n\tAdditively Decomposed Discrete Functions", Evolutionary Compilation, 1999.
[Muhlenbein1999]	H. M\ühlenbein and T. Mahnig and A. O. Rodriguez, "Schemata, Distributions and Graphical Models in Evolutionary Optimization", Journal of Heuristics, 1999.
[Pelikan1998]	M. Pelikan and H. M\ühlenbein, "Marginal distributions in evolutionary algorithms", in Proceedings of the International Conference on Genetic Algorithms\n\tMendel, 1998.
[Pelikan1999]	M. Pelikan and H. M\ühlenbein, "The Bivariate Marginal Distribution Algorithm", in Advances in Soft Computing: Engineering Design and Manufacturing, pages 521–535, Springer, 1999.
[Pelikan2000]	M. Pelikan and D. E. Goldberg, "Hierarchical Problem Solving and the Bayesian Optimization Algorithms", in Genetic and Evolutionary Computation Conference 2000 (GECCO-2000), 2000.
[Pelikan2001b]	M. Pelikan and D. E. Goldberg, "Escaping hierarchical traps with competent genetic algorithms", in Proceedings of the Genetic and Evolutionary Computation Conference\n\t(GECCO-2001), 2001.
[Pelikan2002b]	M. Pelikan and D. E. Goldberg and F. G. Lobo, "A Survey of Optimization by Building and Using Probabilistic Models", Computational Optimization and Applications, 2002.
[Pelikan2006]	M. Pelikan and K. Sastry and E. Cantú–Paz (editors), "Scalable Optimization via Probabilistic Modeling: From Algorithms\n\tto Applications", Springer, 2006.
[Pelikan2008]	M. Pelikan and K. Sastry and D. E. Goldberg, "iBOA: The Incremental Bayesian Optimization Algorithms", in Proceedings of the Genetic and Evolutionary Computation Conference\n\t(GECCO-2008), 2008.
[Rudlof1996]	S. Rudlof and M. Koppen, "Stochastic hill climbing with learning by vectors of normal distributions", in First On-line Workshop on Soft Computing, 1996.
[Salustowicz1997]	R. Salustowicz and J. Schmidhuber, "Probabilistic Incremental Program Evolution: Stochastic search through\n\tprogram space", in Proceedings of the 9th European Conference on Machine Learning Prague, 1997.

Please Note: This content was automatically generated from the book content and may contain minor differences.