Evolution of Distribution Algorithms (EDAs)

EDAs are mathematically principled evolutionary algorithm which do away with the biological analogy. As the name suggests EDAs are based on an unsupervised learning topic: density estimation, which will be reviewed thoroughly in the machine learning section. EDAs achieve state of the art performance in the black-box optimization setting where the goal is to optimize a function $f$ without any knowledge of how $f$ computes its values.

EDAs propose to represent individuals as samples from a probability distribution: the so called proposal distribution. A population is then a set of iid samples from this distribution. In the preceding section, we saw that the mutation and cross-over operators served to define small possible movements around a current population. The EDA approach has the advantage of transforming the problem of moving towards better populations in the input space (which may not be well behaved) to a proxy problem which is usually well behaved: moving towards better proposal distributions.

Formally the algorithm generates a new population by taking $\mu$ samples from a proposal distribution $P_{{\theta }^t}(\mathbf{x})$. These $\mu$ individuals are then ranked according to their $f$-values and the $\sigma$ best individuals are used to update the proposal distribution with a log-likelihood gradient ascent step, i.e.
$$P_{{\theta }^{t+1}}(\mathbf{x})=P_{{\theta }^t}(\mathbf{x})+\delta t\mathrm{\nabla }\log P_{{\theta }^t}(\mathbf{x})$$
where $\delta t$ is the step size of the gradient ascent update. The algorithm can then run for a number of steps, until a satisfactory solution is found. The figure below gives an example of EDA update for a Gaussian proposal distribution.

Although the purpose of the algorithm is to maximize $\mathbb{E}[f(\mathbf{x})]$, it consists in the maximization of a surrogate objective: $\mathbb{E}[w(\mathbf{x})]$, where the weight function $w(\mathbf{x})$ is equal to $1$ for the $\sigma$ best individuals, and $0$ otherwise. This has the advantage of making the approach invariant w.r.t. monotone transformations of the objective function $f$.

The maximization of the surrogate objective $\mathbb{E}[w(\mathbf{x})]$ is done with gradient ascent:
$$\mathrm{\nabla }\mathbb{E}[w(\mathbf{x})]=\mathrm{\nabla }{\int }_{\mathrm{dom}f}w(\mathbf{x})P_{{\theta }^t}(\mathbf{x})$$
$$={\int }_{\mathrm{dom}f}w(\mathbf{x})\mathrm{\nabla }{P}_{{\theta }^t}(\mathbf{x})$$
$$={\int }_{\mathrm{dom}f}\mathrm{\nabla }\log P_{{\theta }^t}(\mathbf{x})w(\mathbf{x})P_{{\theta }^t}(\mathbf{x})$$
where taking $\sigma$ samples from $w(\mathbf{x})P_{{\theta }^t}(\mathbf{x})$ can be done by taking samples from $P_{{\theta }^t}(\mathbf{x})$ and keeping only the $\sigma$ best according to $f$.

This general framework can be adapted to optimize functions in ${\mathbb{R}}^D$ e.g. with CMA-ES [Hansen2008], or in discrete spaces such as $\{0,1{\}}^D$ with PBIL [Baluja1994]. It has the advantage of allowing a move towards several proposal solutions at once, contrary to methods such as hill climbing. The PBIL algorithm for optimization over $\{0,1{\}}^D$ is given below.

Figure 5: The steps of an EDA given a fitness function (a) and a Gaussian proposal distribution at time $t$ (b). First, samples are drawn from the proposal distribution (c). The $\sigma$ best samples are then selected according to their $f$-values (d). Finally, the likelihood of the selected samples w.r.t. the parameters (e) can be increased with a step of log-likelihood gradient ascent leading to a new proposal distribution at time $t+1$ (f).

Next: Summary