Covariance Matrix Adaptive Evolution Strategy

The Covariance Matrix Adaptive Evolution Strategy (CMA-ES) is a black bock optimization method proposed by Hansen and Ostermeier (1996). Their method has earned its good name in various fields of applications and has proven to be an efficient method for a wide class of objective functions.

The power of the CMA-ES algorithm lies in its ability to adapt the size of the covariance matrix it draws its samples from, at each iteration. It allows increasing the size of the sampling distribution to cover more ground when needed, and shrink the covariance down when it is confident in the located solution.

In the above animation, we can observe the path taken by successive cycles of CMA-ES, through various random gaussian fields. Even though these random fields have no definite trend (they are all constructed out of 0 mean Gaussian processes) and possess several local minima, the CMA-ES is capable of navigating the misfit adequately to find the optimal solution denoted by the white triangle.

Word of caution!

CMA-ES can be trapped in local minima, depending on the length scale of the misfit roughness, if the initial covariance is not set up properly.


Simplified algorithm

Here is the very simplified description of the algorithm depicted in the animation above:

  • Generate and evaluate n offspring
  • Sort by fitness and compute new weighted mean
  • Compute mean of 50% best fitting offsprings
  • Adapt covariance matrix
  • Adapt step size

The key point in the CMA-ES algorithm, is that we work with only the 50% best fitting samples to compute the next population mean. Then the new covariance is computed with the same best fitting points, but with respect to the previous mean. The covariance size and orientation are thus defined by the repartition of the best fitting samples, and from how much and where the mean is moving.