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
