Learning hard problems: CMA-ES
The covariance matrix adaptation evolution strategy is black-box optimization algorithm. That performs well in practice [source].
We have a function $f: \R^n → \R$ that we want to minimize.
The algorithm iterates three steps:
- Generate new solutions $\vec x_i \in \R^n$.
- Sort solutions by fitness $f(x_i) ≤ f(x_{i+1})$.
- Update the internal state using re-ordered samples.
Since $f$ is only used to order the candidate solutions, very few assumptions on $f$ are made.
The state of the algorithm is:
- The mean $\vec m ∈ \R^n$.
- The covariance matrix $C ∈ \R^{n^2}$.
- The step-size $σ ∈ \R_{> 0}$.
- The isotropic path $\vec p ∈ \R^n$.
- The anisotropic path $\vec q ∈ \R^n$.
The initial values are $C = I$, $\vec p = \vec q = \vec 0$.
The parameters of the algoritm are:
- $λ ∈ \N_{>0}$ the number of candidate solutions to try.
- $\vec w ∈ \R^n$ the recombination weights.
Generating new solutions
A total of $λ$ new solutions $\vec x_0, \dots, \vec x_{λ -1}$ are drawn from the multinomial distribution
$$ \vec x_i ∼ \mathcal N (\vec m, σ^2 ⋅ C) $$
This is the same as $\vec m + σ ⋅ \mathcal N (\vec 0, C)$, the solutions are all pertubations of the mean $\vec m$, which represents the current best estimate.
Sorting solutions
Sort the solutions by $f$ such that
$$ f(\vec x_0) ≤ f(\vec x_1) ≤ \cdots ≤ f(\vec x_{λ - 1}) $$
Update the mean
$$ \vec m' = \sum_i w_i ⋅ \vec x_i $$
Where $w_i$ are the recombination weights such that $\sum_i w_i = 1$ and $w_i \geq w_{i+1}$. Typically there is a $0 < μ ≤ λ/2$ such that $w_i = \frac{1}{μ}$ for $i < μ$ and zero otherwise.
$$ μ = \left\lfloor \frac{λ}{2} \right\rfloor $$
$$ w_i = \frac{1}{\Sigma} \ln(μ + 2) - \ln i $$
Update the step-size
First the isotropic path is updated
$$ \vec p' = (1 - c_p) \vec p + $$
Update the covariance matrix
First the anisotropic path is updated
References
- https://en.wikipedia.org/wiki/CMA-ES
- BIPOP-CMA-ES. Benchmarking a BI-Population CMA-ES on theBBOB-2009 Function Testbed https://hal.inria.fr/inria-00382093/document
- Comparing Results of 31 Algorithms from the Black-Box Optimization Benchmarking BBOB-2009 https://dl.acm.org/doi/pdf/10.1145/1830761.1830790