Estimation of distribution algorithms (EDAs), sometimes called probabilistic model-building genetic algorithms (PMBGAs),^[1] are stochastic optimization methods that guide the search for the optimum by building and sampling explicit probabilistic models of promising candidate solutions. Optimization is viewed as a series of incremental updates of a probabilistic model, starting with the model encoding an uninformative prior over admissible solutions and ending with the model that generates only the global optima.^[2][3][4]

EDAs belong to the class of evolutionary algorithms. The main difference between EDAs and most conventional evolutionary algorithms is that evolutionary algorithms generate new candidate solutions using an implicit distribution defined by one or more variation operators, whereas EDAs use an explicit probability distribution encoded by a Bayesian network, a multivariate normal distribution, or another model class. Similarly as other evolutionary algorithms, EDAs can be used to solve optimization problems defined over a number of representations from vectors to LISP style S expressions, and the quality of candidate solutions is often evaluated using one or more objective functions.

The general procedure of an EDA is outlined in the following:

t := 0
initialize model M(0) to represent uniform distribution over admissible solutions
while (termination criteria not met) do
    P := generate N>0 candidate solutions by sampling M(t)
    F := evaluate all candidate solutions in P
    M(t + 1) := adjust_model(P, F, M(t))
    t := t + 1

Using explicit probabilistic models in optimization allowed EDAs to feasibly solve optimization problems that were notoriously difficult for most conventional evolutionary algorithms and traditional optimization techniques, such as problems with high levels of epistasis^{[citation needed]}. Nonetheless, the advantage of EDAs is also that these algorithms provide an optimization practitioner with a series of probabilistic models that reveal a lot of information about the problem being solved. This information can in turn be used to design problem-specific neighborhood operators for local search, to bias future runs of EDAs on a similar problem, or to create an efficient computational model of the problem.

For example, if the population is represented by bit strings of length 4, the EDA can represent the population of promising solution using a single vector of four probabilities (p1, p2, p3, p4) where each component of p defines the probability of that position being a 1. Using this probability vector it is possible to create an arbitrary number of candidate solutions.

Estimation of distribution algorithms (EDAs)

This section describes the models built by some well known EDAs of different levels of complexity. It is always assumed a population ${\displaystyle P(t)}$ at the generation ${\displaystyle t}$, a selection operator ${\displaystyle S}$, a model-building operator ${\displaystyle \alpha }$ and a sampling operator ${\displaystyle \beta }$.

Univariate factorizations

The most simple EDAs assume that decision variables are independent, i.e. ${\displaystyle p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})}$. Therefore, univariate EDAs rely only on univariate statistics and multivariate distributions must be factorized as the product of ${\displaystyle N}$ univariate probability distributions,

${\displaystyle D_{\text{Univariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}).}$

Such factorizations are used in many different EDAs, next we describe some of them.

Univariate marginal distribution algorithm (UMDA)

The UMDA^[5] is a simple EDA that uses an operator ${\displaystyle \alpha _{UMDA}}$ to estimate marginal probabilities from a selected population ${\displaystyle S(P(t))}$. By assuming ${\displaystyle S(P(t))}$ contain ${\displaystyle \lambda }$ elements, ${\displaystyle \alpha _{UMDA}}$ produces probabilities:

${\displaystyle p_{t+1}(X_{i})={\dfrac {1}{\lambda }}\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N.}$

Every UMDA step can be described as follows

${\displaystyle D(t+1)=\alpha _{\text{UMDA}}\circ S\circ \beta _{\lambda }(D(t)).}$

Population-based incremental learning (PBIL)

The PBIL,^[6] represents the population implicitly by its model, from which it samples new solutions and updates the model. At each generation, ${\displaystyle \mu }$ individuals are sampled and ${\displaystyle \lambda \leq \mu }$ are selected. Such individuals are then used to update the model as follows

${\displaystyle p_{t+1}(X_{i})=(1-\gamma )p_{t}(X_{i})+(\gamma /\lambda )\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N,}$

where ${\displaystyle \gamma \in (0,1}$ is a parameter defining the learning rate, a small value determines that the previous model ${\displaystyle p_{t}(X_{i})}$ should be only slightly modified by the new solutions sampled. PBIL can be described as

${\displaystyle D(t+1)=\alpha _{\text{PIBIL}}\circ S\circ \beta _{\mu }(D(t))}$

Compact genetic algorithm (cGA)

The CGA,^[7] also relies on the implicit populations defined by univariate distributions. At each generation ${\displaystyle t}$, two individuals ${\displaystyle x,y}$ are sampled, ${\displaystyle P(t)=\beta _{2}(D(t))}$. The population ${\displaystyle P(t)}$ is then sorted in decreasing order of fitness, ${\displaystyle S_{{\text{Sort}}(f)}(P(t))}$, with ${\displaystyle u}$ being the best and ${\displaystyle v}$ being the worst solution. The CGA estimates univariate probabilities as follows

${\displaystyle p_{t+1}(X_{i})=p_{t}(X_{i})+\gamma (u_{i}-v_{i}),\quad \forall i\in 1,2,\dots ,N,}$

where, ${\displaystyle \gamma \in (0,1}$ is a constant defining the learning rate, usually set to ${\displaystyle \gamma =1/N}$. The CGA can be defined as

${\displaystyle D(t+1)={\mathrm{\alpha <!--\; \alpha \; -->}}_{\text{CGA}}\circ <!--\; \circ \; -->S_{\text{Sort}(f}}$Zdroj:https://en.wikipedia.org?pojem=Estimation_of_distribution_algorithm
>Text je dostupný pod licencí Creative Commons Uveďte autora – Zachovejte licenci, případně za dalších podmínek. Podrobnosti naleznete na stránce Podmínky užití.