CMA-ES is a continuous optimisation metaheuristic known for its powerful global optimisation capabilities.

## Problem

Let's consider the following simple problem:
$$\min \qquad f= x^2_{1} + x^2_{2}$$
The solution is obviously $$x_1 = 0$$ and $$x_2 = 0$$. Let's use CMA-ES to find this.

## Run CMAES

$$x_1^* =$$
$$x_2^* =$$
$$f_{min} =$$
$$gen =$$

## Instructions

1. Click on "Run 1 generation" or "Keep running" buttons to see CMAES in action.
2. Click "Reset" to initiate from the beginning.

## How CMA-ES works?

1. CMA-ES is a population-based heuristic strategy that improves a population of candidate solutions through an evolutionary process to reach a near-optimal solution.
2. It uses a multi-variate Gaussian to represent the current population in a generation.
3. Then, in each generation,
• CMA-ES generates sample points using the mean $$\mathbf{x}^{mean}$$ and the covariance matrix $$\begin{bmatrix} \sigma^2_{x_1} &\sigma^2_{x_1,x_2}\\ \sigma^2_{x_2,x_1}& \sigma^2_{x_2} \end{bmatrix}$$ of the multi-variate Gaussian.
• Updates the covariance matrix using the fitness values ($$f$$) obtained at the sampled points.
• Updates the mean value of the sampling distribution toward the direction of improvement.
4. The process is repeated until a satisfactory result is achieved.
5. In the above example problem, the initial guess is set to be $$\mathbf{x}^{mean} = [1, 1]^T$$ with an initial standard deviation of $$0.3$$ for both $$x_1$$ and $$x_2$$ and no covariance.

## Understanding the covariance matrix

Change the covariance matrix using the sliders to see how the sampled distribution changes.

Mean:
$$x^{mean}_1$$
$$x^{mean}_2$$

Covariance Matrix:
$$C_{11}$$
$$C_{12}$$
$$C_{21}$$
$$C_{22}$$

Number of sampled points:
$$N$$

1. Changing the mean values will move the region where the points are sampled.
2. Changing the variances $$C_{11}$$ and $$C_{22}$$ will adjust the spread of the sampled points in the corresponding directions
3. Changing the covariances $$C_{12}$$ or $$C_{21}$$ will adjust the interdependence of the variables

Note that the scale for covariances $$C_{12}$$ and $$C_{21}$$ is updated such that the range corresponds to a correlation between $$-1$$ to $$1$$. This is because, there exists an upper limit for covariance of two variables given by $$\lceil C_{12} \rceil = \sqrt{C_{11} C_{22}}$$.

By using the fitness values at the sampled points, the CMA-ES algorithm makes clever adaptations to the covariance matrix and mean values, and thereby performs effective optimisation. For more details on the adaptation procedures, one may refer to the following resources.