CMA-ES

CMA-ES stands for Covariance Matrix Adaptation Evolution Strategy. An Evolution Strategy is a stochastic optimization method belonging to the class of Evolutionary Algorithms. The covariance matrix adaptation (CMA) is a method to adapt the covariance matrix of the multivariate normal mutation distribution in the Evolution Strategy (ES). The covariance matrix describes the pairwise dependencies between the variables. Adaptation of the covariance matrix means learning a second order model of the underlying objective function similar to the approximation of the inverse Hessian matrix in the Quasi-Newton method in classical optimization.

Principle

The adaptation principle is based on the idea to increase the probability of a successful mutation step. The covariance matrix is updated such that the likelihood of the successful step(s) of the last generation to appear again is increased. Consequently the CMA conducts an iterated principle component analysis of successful mutation steps while retaining all principle axes. Besides the covariance matrix adaptation procedure, an additional step-size control is conducted in the CMA-ES. The step-size control effectively prevents premature convergence.

References

• Hansen N, Ostermeier A (2001). Completely derandomized self-adaptation in evolution strategies. Evolutionary Computation, 9(2) pp.159-195. [1]

• Hansen N, Müller SD, Koumoutsakos P (2003). Reducing the time complexity of the derandomized evolution strategy with covariance matrix adaptation (CMA-ES). Evolutionary Computation, 11(1) pp.1-18. [2]

• Hansen N, Kern S (2004). Evaluating the CMA evolution strategy on multimodal test functions. In Xin Yao et al, editors, Parallel Problem Solving from Nature - PPSN VIII, pp.282-291, Springer. [3]

• Igel C, Hansen N, Roth S (2007). Covariance Matrix Adaptation for Multi-objective Optimization. Evolutionary Computation, 15(1) pp.1-28. [4]

External links

• The CMA Evolution Strategy, a short introduction and further references