# Estimation of distribution algorithm

Estimation of distribution algorithm

Estimation of Distribution Algorithms (EDA), sometimes called Probabilistic Model-Building Genetic Algorithms (PMBGA), are an outgrowth of genetic algorithms. In a genetic algorithm, a population of candidate solutions to a problem is maintained as part of the search for an optimum solution. This population is typically represented explicitly as an array of objects. Depending on the specifics of the GA, the objects might be bit strings, vectors of real numbers, LISP style S expressions or some custom representation. In an EDA, this explicit representation of the population is replaced with a probability distribution over the choices available at each position in the vector that represents a population member.

For example, if the population is represented by bit strings of length 4, the EDA for the populations would be a single vector of four probablities (p1, p2, p3, p4) where each p is the probability of that position being a 1. Using this probability vector it is possible to create an arbitrary number of candidate solutions.

In evolutionary computation new candidate solutions are often generated by combining and modifying existing solutions in a stochastic way. The underlying probability distribution of new solutions over the space of possible solutions is usually not explicitly specified. In EDAs a population may be approximated with a probability distribution and new candidate solutions can be obtained by sampling this distribution. This may have several advantages, including avoiding premature convergence and being a more compact representation.

Better-known EDAs include the Compact Genetic Algorithm, Population-based incremental learning, the Univariate Marginal Distribution Algorithm, and the Estimation of Multivariate Normal Algorithm.

The model may be found to fit an existing population or take on the role of the population entirely. Once the model is obtained, it can be sampled to produce more candidate solutions which are then used to adapt or regenerate the model. EDAs are typically classified according to the level of variable interaction that their probabilistic model includes - they can be classed as univariate (no interactions), bivariate (interactions between pairs of variables) or multivariate (interactions between more than two variables) (Pelikan, 1999).

References

*Larrañga, Pedro; & Lozano, Jose A. (Eds.). Estimation of distribution algorithms: A new tool for evolutionary computation. Kluwer Academic Publishers, Boston, 2002.
*Lozano, J. A.; Larrañga, P.; Inza, I.; & Bengoetxea, E. (Eds.). Towards a new evolutionary computation. Advances in estimation of distribution algorithms. Springer, 2006.
*Citation | last1=Pelikan | first1=Martin | last2=Goldberg | first2=David | last3=Lobo | first3=Fernando | publication-date=1999 | title = A Survey of Optimization by Building and Using Probabilistic Models | publication-place = Illinois | publisher = Illinois Genetic Algorithms Laboratory (IlliGAL), University of Illinois at Urbana-Champaign.
*Pelikan, Martin. Hierarchical Bayesian optimization algorithm: Toward a new generation of evolutionary algorithms. Springer, 2005.
*Pelikan, Martin; Sastry, Kumara; & Cantu-Paz, Erick (Eds.). Scalable optimization via probabilistic modeling: From algorithms to applications. Springer, 2006.

Wikimedia Foundation. 2010.

### Look at other dictionaries:

• Algorithme a estimation de distribution — Algorithme à estimation de distribution Les algorithmes à estimation de distribution résolvent des problèmes d optimisation en échantillonnant un modèle de distribution, dont les paramètres évoluent via des opérateurs de sélection. Ici, un AED à… …   Wikipédia en Français

• Algorithme À Estimation De Distribution — Les algorithmes à estimation de distribution résolvent des problèmes d optimisation en échantillonnant un modèle de distribution, dont les paramètres évoluent via des opérateurs de sélection. Ici, un AED à distribution normale mono variante… …   Wikipédia en Français

• Algorithmes à estimation de distribution — Algorithme à estimation de distribution Les algorithmes à estimation de distribution résolvent des problèmes d optimisation en échantillonnant un modèle de distribution, dont les paramètres évoluent via des opérateurs de sélection. Ici, un AED à… …   Wikipédia en Français

• Algorithme à estimation de distribution — Les algorithmes à estimation de distribution résolvent des problèmes d optimisation en échantillonnant un modèle de distribution, dont les paramètres évoluent via des opérateurs de sélection. Ici, un AED à distribution normale mono variante… …   Wikipédia en Français

• Estimation theory — is a branch of statistics and signal processing that deals with estimating the values of parameters based on measured/empirical data. The parameters describe an underlying physical setting in such a way that the value of the parameters affects… …   Wikipedia

• Distribution mangagement system — SCADA systems have been a part of utility automation for at least 15 years and contributing to the decision making process of the control rooms. However, majority of the existing solutions are closely related to distribution network data… …   Wikipedia

• Expectation-maximization algorithm — An expectation maximization (EM) algorithm is used in statistics for finding maximum likelihood estimates of parameters in probabilistic models, where the model depends on unobserved latent variables. EM alternates between performing an… …   Wikipedia

• Normal distribution — This article is about the univariate normal distribution. For normally distributed vectors, see Multivariate normal distribution. Probability density function The red line is the standard normal distribution Cumulative distribution function …   Wikipedia

• Maximum a posteriori estimation — In Bayesian statistics, a maximum a posteriori probability (MAP) estimate is a mode of the posterior distribution. The MAP can be used to obtain a point estimate of an unobserved quantity on the basis of empirical data. It is closely related to… …   Wikipedia

• k-nearest neighbor algorithm — KNN redirects here. For other uses, see KNN (disambiguation). In pattern recognition, the k nearest neighbor algorithm (k NN) is a method for classifying objects based on closest training examples in the feature space. k NN is a type of instance… …   Wikipedia