# 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