CMA-ES
From Wikipedia, the free encyclopedia
CMA-ES stands for Covariance Matrix Adaptation Evolution Strategy. An evolution strategy (ES) is a stochastic, population-based, iterative optimization method belonging to the class of evolutionary algorithms. The covariance matrix adaptation (CMA) is a method to update the covariance matrix of the multivariate normal mutation distribution in the evolution strategy. New candidate solutions are sampled according to the mutation distribution and the covariance matrix describes the pairwise dependencies between the variables in the distribution. Adaptation of the covariance matrix amounts to 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.
[edit] Principle
Two adaptation principles are exploited in the CMA-ES algorithm. First, a maximum likelihood principle, based on the idea to increase the probability of a successful mutation step. The covariance matrix of the distribution is updated such that the likelihood of previously realized successful steps to appear again is increased. Consequently the CMA conducts an iterated principal components analysis of successful mutation steps while retaining all principle axes.
Second, a path of the time evolution of the distribution mean of the strategy is recorded, called evolution path. Such a path contains significant information of the correlation between consecutive steps. The evolution path is exploited in two ways. It is used for the covariance matrix adaptation procedure in place of single successful mutation steps. Also, the evolution path is used to conduct an additional step-size control. This step-size control aims to make consecutive movements of the distribution mean orthogonal in expectation. The step-size control effectively prevents premature convergence.
[edit] Bibliography
- 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]
