Estimation of distribution algorithm

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)).}$

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))}$

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)=\alpha _{\text{CGA}}\circ S_{{\text{Sort}}(f)}\circ \beta _{2}(D(t))}$

The MIMIC[8] factorizes the joint probability distribution in a chain-like model representing successive dependencies between variables. It finds a permutation of the decision variables, ${\displaystyle r:i\mapsto j}$, such that ${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$ minimizes the Kullback-Leibler divergence in relation to the true probability distribution, i.e. ${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$. MIMIC models a distribution

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=p_{t}(X_{r(N)})\prod _{i=1}^{N-1}p_{t}(X_{r(i)}|X_{r(i+1)}).}$

New solutions are sampled from the leftmost to the rightmost variable, the first is generated independently and the others according to conditional probabilities. Since the estimated distribution must be recomputed each generation, MIMIC uses concrete populations in the following way

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{MIMIC}}\circ S(P(t)).}$

The BMDA[9] factorizes the joint probability distribution in bivariate distributions. First, a randomly chosen variable is added as a node in a graph, the most dependent variable to one of those in the graph is chosen among those not yet in the graph, this procedure is repeated until no remaining variable depends on any variable in the graph (verified according to a threshold value).

The resulting model is a forest with multiple trees rooted at nodes ${\displaystyle \Upsilon _{t}}$. Considering ${\displaystyle I_{t}}$ the non-root variables, BMDA estimates a factorized distribution in which the root variables can be sampled independently, whereas all the others must be conditioned to the parent variable ${\displaystyle \pi _{i}}$.

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=\prod _{X_{i}\in \Upsilon _{t}}p_{t}(X_{i})\cdot \prod _{X_{i}\in I_{t}}p_{t}(X_{i}|\pi _{i}).}$

Each step of BMDA is defined as follows

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BMDA}}\circ S(P(t)).}$

The ECGA[10] was one of the first EDA to employ multivariate factorizations, in which high-order dependencies among decision variables can be modeled. Its approach factorizes the joint probability distribution in the product of multivariate marginal distributions. Assume ${\displaystyle T_{\text{eCGA}}=\{\tau _{1},\dots ,\tau _{\Psi }\}}$ is a set of subsets, in which every ${\displaystyle \tau \in T_{\text{eCGA}}}$ is a linkage set, containing ${\displaystyle |\tau |\leq K}$ variables. The factorized joint probability distribution is represented as follows

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{\tau \in T_{\text{eCGA}}}p(\tau ).}$

The ECGA popularized the term "linkage-learning" as denoting procedures that identify linkage sets. Its linkage-learning procedure relies on two measures: (1) the Model Complexity (MC) and (2) the Compressed Population Complexity (CPC). The MC quantifies the model representation size in terms of number of bits required to store all the marginal probabilities

${\displaystyle MC=\log _{2}(\lambda +1)\sum _{\tau \in T_{\text{eCGA}}}(2^{|\tau |-1}),}$

The CPC, on the other hand, quantifies the data compression in terms of entropy of the marginal distribution over all partitions, where ${\displaystyle \lambda }$ is the selected population size, ${\displaystyle |\tau |}$ is the number of decision variables in the linkage set ${\displaystyle \tau }$ and ${\displaystyle H(\tau )}$ is the joint entropy of the variables in ${\displaystyle \tau }$

${\displaystyle CPC=\lambda \sum _{\tau \in T_{\text{eCGA}}}H(\tau ).}$

The linkage-learning in ECGA works as follows: (1) Insert each variable in a cluster, (2) compute CCC = MC + CPC of the current linkage sets, (3) verify the increase on CCC provided by joining pairs of clusters, (4) effectively joins those clusters with highest CCC improvement. This procedure is repeated until no CCC improvements are possible and produces a linkage model ${\displaystyle T_{\text{eCGA}}}$. The ECGA works with concrete populations, therefore, using the factorized distribution modeled by ECGA, it can be described as

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

The BOA[11][12][13] uses Bayesian networks to model and sample promising solutions. Bayesian networks are directed acyclic graphs, with nodes representing variables and edges representing conditional probabilities between pair of variables. The value of a variable ${\displaystyle x_{i}}$ can be conditioned on a maximum of ${\displaystyle K}$ other variables, defined in ${\displaystyle \pi _{i}}$. BOA builds a PGM encoding a factorized joint distribution, in which the parameters of the network, i.e. the conditional probabilities, are estimated from the selected population using the maximum likelihood estimator.

${\displaystyle p(X_{1},X_{2},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).}$

The Bayesian network structure, on the other hand, must be built iteratively (linkage-learning). It starts with a network without edges and, at each step, adds the edge which better improves some scoring metric (e.g. Bayesian information criterion (BIC) or Bayesian-Dirichlet metric with likelihood equivalence (BDe)).[14] The scoring metric evaluates the network structure according to its accuracy in modeling the selected population. From the built network, BOA samples new promising solutions as follows: (1) it computes the ancestral ordering for each variable, each node being preceded by its parents; (2) each variable is sampled conditionally to its parents. Given such scenario, every BOA step can be defined as

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

The LTGA[15] differs from most EDA in the sense it does not explicitly model a probability distribution but only a linkage model, called linkage-tree. A linkage ${\displaystyle T}$ is a set of linkage sets with no probability distribution associated, therefore, there is no way to sample new solutions directly from ${\displaystyle T}$. The linkage model is a linkage-tree produced stored as a Family of sets (FOS).

${\displaystyle T_{\text{LT}}=\{\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\},\{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.}$

The linkage-tree learning procedure is a hierarchical clustering algorithm, which work as follows. At each step the two closest clusters ${\displaystyle i}$ and ${\displaystyle j}$ are merged, this procedure repeats until only one cluster remains, each subtree is stored as a subset ${\displaystyle \tau \in T_{\text{LT}}}$.

The LTGA uses ${\displaystyle T_{\text{LT}}}$ to guide an "optimal mixing" procedure which resembles a recombination operator but only accepts improving moves. We denote it as ${\displaystyle R_{\text{LTGA}}}$, where the notation ${\displaystyle x[\tau ]\gets y[\tau ]}$ indicates the transfer of the genetic material indexed by ${\displaystyle \tau }$ from ${\displaystyle y}$ to ${\displaystyle x}$.

Algorithm Gene-pool optimal mixing
   Input: A family of subsets ${\displaystyle T_{\text{LT}}}$ and a population ${\displaystyle P(t)}$
   Output: A population ${\displaystyle P(t+1)}$.
   for each ${\displaystyle x_{i}}$ in ${\displaystyle P(t)}$ do
       for each ${\displaystyle \tau }$ in ${\displaystyle T_{\text{LT}}}$ do
           choose a random ${\displaystyle x_{j}\in P(t):x_{i}\neq x_{j}}$
           ${\displaystyle f_{x_{i}}}$ := ${\displaystyle f(x_{i})}$
           ${\displaystyle x_{i}[\tau ]}$:= ${\displaystyle x_{j}[\tau ]}$
           if ${\displaystyle f(x_{i})\leq f_{x_{i}}}$ then
               ${\displaystyle x_{i}[\tau ]:=x_{j}[\tau ]}$ 
   return ${\displaystyle P(t)}$

The LTGA does not implement typical selection operators, instead, selection is performed during recombination. Similar ideas have been usually applied into local-search heuristics and, in this sense, the LTGA can be seen as an hybrid method. In summary, one step of the LTGA is defined as

${\displaystyle P(t+1)=R_{\text{LTGA}}(P(t))\circ \alpha _{\text{LTGA}}(P(t))}$