Covariance matrix adaptation evolution strategy (CMA-ES) is a particular kind of strategy fornumerical optimization.Evolution strategies (ES) arestochastic,derivative-free methods fornumerical optimization of non-linear or non-convexcontinuous optimization problems. They belong to the class ofevolutionary algorithms andevolutionary computation. Anevolutionary algorithm is broadly based on the principle ofbiological evolution, namely the repeated interplay of variation (viarecombination andmutation) and selection: in each generation (iteration) new individuals (candidate solutions, denoted as${\displaystyle x}$) are generated by variation of the current parental individuals, usually in a stochastic way. Then, some individuals are selected to become the parents in the next generation based on their fitness orobjective function value${\displaystyle f(x)}$. Like this, individuals with better and better${\displaystyle f}$-values are generated over the generation sequence.

In anevolution strategy, new candidate solutions are usually sampled according to amultivariate normal distribution in${\displaystyle {\mathbb{R}}^n}$. Recombination amounts to selecting a new mean value for the distribution. Mutation amounts to adding a random vector, a perturbation with zero mean. Pairwise dependencies between the variables in the distribution are represented by acovariance matrix. The covariance matrix adaptation (CMA) is a method to update thecovariance matrix of this distribution. This is particularly useful if the function${\displaystyle f}$ isill-conditioned.

Adaptation of thecovariance matrix amounts to learning a second order model of the underlyingobjective function similar to the approximation of the inverseHessian matrix in thequasi-Newton method in classicaloptimization. In contrast to most classical methods, fewer assumptions on the underlying objective function are made. Because only a ranking (or, equivalently, sorting) of candidate solutions is exploited, neither derivatives nor even an (explicit) objective function is required by the method. For example, the ranking could come about from pairwise competitions between the candidate solutions in aSwiss-system tournament.

Two main principles for the adaptation of parameters of the search distribution are exploited in the CMA-ES algorithm.

First, amaximum-likelihood principle predicated on the idea that increasing (though not necessarily maximizing) the sample probability ofsuccessful candidate solutions or search directions is beneficial. The mean of the distribution is updated such that thelikelihood of previously successful candidate solutions is maximized. Thecovariance matrix of the distribution is updated (incrementally) such that the likelihood of previously successful search steps is increased. Both updates can be interpreted as anatural gradient descent. Also, in consequence, the CMA conducts an iteratedprincipal components analysis of successful search steps while retainingall principal axes.Estimation of distribution algorithms and theCross-Entropy Method are based on very similar ideas, but generally estimate (non-incrementally) the covariance matrix by maximizing the likelihood of successful solutionpoints rather than successful searchsteps.

Second, two paths of the time evolution of the distribution mean of the strategy are recorded, called search or evolution paths. These paths contain significant information about the correlation between consecutive steps. Specifically, if consecutive steps are taken in a similar direction, the evolution paths become long. The evolution paths are exploited in two ways. One path is used for the covariance matrix adaptation procedure in place of single successful search steps and facilitates a possibly much faster variance increase of favorable directions. The other 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 preventspremature convergence yet allowing fast convergence to an optimum.

In the following the most commonly used (μ/μ_w, λ)-CMA-ES is outlined, where in each iteration step a weighted combination of theμ best out ofλ new candidate solutions is used to update the distribution parameters. The main loop consists of three main parts: 1) sampling of new solutions, 2) re-ordering of the sampled solutions based on their fitness, 3) update of the internal state variables based on the re-ordered samples. Apseudocode of the algorithm looks as follows.

set${\displaystyle \lambda }$  // number of samples per iteration, at least two, generally > 4initialize${\displaystyle m}$,${\displaystyle \sigma }$,${\displaystyle C=I}$,${\displaystyle p_{\sigma }=0}$,${\displaystyle p_c=0}$  // initialize state variableswhilenot terminatedo  // iteratefor${\displaystyle i}$in${\displaystyle \{1\dots \lambda \}}$do  // sample${\displaystyle \lambda }$ new solutions and evaluate them${\displaystyle x_i=}$sample_multivariate_normal(mean${\displaystyle =m}$, covariance_matrix${\displaystyle ={\sigma }^{2}C}$)${\displaystyle f_i=\mathrm{fitness}(x_i)}$${\displaystyle x_{1\dots \lambda }}$ ←${\displaystyle x_{s(1)\dots s(\lambda )}}$ with${\displaystyle s(i)=\mathrm{argsort}(f_{1\dots \lambda },i)}$ // sort solutions${\displaystyle m^{\prime }=m}$  // we need later${\displaystyle m-m^{\prime }}$ and${\displaystyle x_i-m^{\prime }}$${\displaystyle m}$ ← update_m${\displaystyle (x_1,\dots ,x_{\lambda })}$  // move mean to better solutions${\displaystyle p_{\sigma }}$ ← update_ps${\displaystyle (p_{\sigma },{\sigma }^{-1}{C}^{-1/2}(m-m^{\prime }))}$  // update isotropic evolution path${\displaystyle p_c}$ ← update_pc${\displaystyle (p_c,{\sigma }^{-1}(m-m^{\prime }),\Vert p_{\sigma }\Vert )}$  // update anisotropic evolution path${\displaystyle C}$ ← update_C${\displaystyle (C,p_c,(x_1-m^{\prime })/\sigma ,\dots ,(x_{\lambda }-m^{\prime })/\sigma )}$  // update covariance matrix${\displaystyle \sigma }$ ← update_sigma${\displaystyle (\sigma ,\Vert p_{\sigma }\Vert )}$  // update step-size using isotropic path lengthreturn${\displaystyle m}$ or${\displaystyle x_1}$

The order of the five update assignments is relevant:${\displaystyle m}$ must be updated first,${\displaystyle p_{\sigma }}$ and${\displaystyle p_c}$ must be updated before${\displaystyle C}$, and${\displaystyle \sigma }$ must be updated last. The update equations for the five state variables are specified in the following.

Given are the search space dimension${\displaystyle n}$ and the iteration step${\displaystyle k}$. The five state variables are

• ${\displaystyle m_k\in {\mathbb{R}}^n}$, the distribution mean and current favorite solution to the optimization problem,
• ${\displaystyle {\sigma }_k>0}$, the step-size,
• ${\displaystyle C_k}$, a symmetric andpositive-definite${\displaystyle n\times n}$covariance matrix with${\displaystyle C_0=I}$ and
• ${\displaystyle p_{\sigma }\in {\mathbb{R}}^n,p_c\in {\mathbb{R}}^n}$, two evolution paths, initially set to the zero vector.

The iteration starts with sampling${\displaystyle \lambda >1}$ candidate solutions${\displaystyle x_i\in {\mathbb{R}}^n}$ from amultivariate normal distribution${\displaystyle \mathcal{N}(m_k,{\sigma }_k^2{C}_k)}$, i.e. for${\displaystyle i=1,\dots ,\lambda }$

The second line suggests the interpretation as unbiased perturbation (mutation) of the current favorite solution vector${\displaystyle m_k}$ (the distribution mean vector). The candidate solutions${\displaystyle x_i}$ are evaluated on the objective function${\displaystyle f:{\mathbb{R}}^n\to \mathbb{R}}$ to be minimized. Denoting the${\displaystyle f}$-sorted candidate solutions as

$${\displaystyle \{x_{i:\lambda }\mid i=1\dots \lambda \}=\{x_i\mid i=1\dots \lambda \}\text{ and }f(x_{1:\lambda })\le \cdots \le f(x_{\mu :\lambda })\le f(x_{\mu +1:\lambda })\le \cdots ,}$$

the new mean value is computed as

where the positive (recombination) weights${\displaystyle w_1\ge w_2\ge \cdots \ge w_{\mu }>0}$ sum to one. Typically,${\displaystyle \mu \le \lambda /2}$ and the weights are chosen such that${\displaystyle {\mu }_w:=1/\sum _{i=1}^{\mu }{w}_i^2\approx \lambda /4}$. The only feedback used from the objective function here and in the following is an ordering of the sampled candidate solutions due to the indices${\displaystyle i:\lambda }$.

The step-size${\displaystyle {\sigma }_k}$ is updated usingcumulative step-size adaptation (CSA), sometimes also denoted aspath length control. The evolution path (or search path)${\displaystyle p_{\sigma }}$ is updated first.

$${\displaystyle p_{\sigma }\leftarrow \underset{\text{discount factor}}{\underbrace{(1-c_{\sigma })}}{p}_{\sigma }+\stackrel{\text{complements for discounted variance}}{\overbrace{\sqrt{1-(1-c_{\sigma }{)}^2}}}\underset{\text{distributed as }\mathcal{N}(0,I)\text{ under neutral selection}}{\underbrace{\sqrt{{\mu }_w}{C}_k^{-1/2}\frac{\stackrel{\text{displacement of }m}{\overbrace{m_{k+1}-m_k}}}{{\sigma }_k}}}}$$$${\displaystyle {\sigma }_{k+1}={\sigma }_k\times \exp (\frac{c_{\sigma }}{d_{\sigma }}\underset{\text{unbiased about 0 under neutral selection}}{\underbrace{\left(\frac{\Vert p_{\sigma }\Vert }{\mathrm{E}\Vert \mathcal{N}(0,I)\Vert }-1\right)}})}$$

where

• ${\displaystyle c_{\sigma }^{-1}\approx n/3}$ is the backward time horizon for the evolution path${\displaystyle p_{\sigma }}$ and larger than one (${\displaystyle c_{\sigma }\ll 1}$ is reminiscent of anexponential decay constant as${\displaystyle (1-c_{\sigma }{)}^k\approx \exp (-c_{\sigma }k)}$ where${\displaystyle c_{\sigma }^{-1}}$ is the associated lifetime and${\displaystyle c_{\sigma }^{-1}\ln (2)\approx 0.7c_{\sigma }^{-1}}$ the half-life),
• ${\displaystyle {\mu }_w={\left(\sum _{i=1}^{\mu }{w}_i^2\right)}^{-1}}$ is the variance effective selection mass and${\displaystyle 1\le {\mu }_w\le \mu }$ by definition of${\displaystyle w_i}$,
• ${\displaystyle C_k^{-1/2}={\sqrt{C_k}}^{-1}=\sqrt{C_k^{-1}}}$ is the unique symmetricsquare root of theinverse of${\displaystyle C_k}$, and
• ${\displaystyle d_{\sigma }}$ is the damping parameter usually close to one. For${\displaystyle d_{\sigma }=\mathrm{\infty }}$ or${\displaystyle c_{\sigma }=0}$ the step-size remains unchanged.

The step-size${\displaystyle {\sigma }_k}$ is increased if and only if${\displaystyle \Vert p_{\sigma }\Vert }$ is larger than theexpected value

and decreased if it is smaller. For this reason, the step-size update tends to make consecutive steps${\displaystyle C_k^{-1}}$-conjugate, in that after the adaptation has been successful${\displaystyle {\left(\frac{m_{k+2}-m_{k+1}}{{\sigma }_{k+1}}\right)}^T{C}_k^{-1}\frac{m_{k+1}-m_k}{{\sigma }_k}\approx 0}$.^[1]

Finally, thecovariance matrix is updated, where again the respective evolution path is updated first.

$${\displaystyle p_c\leftarrow \underset{\text{discount factor}}{\underbrace{(1-c_c)}}{p}_c+\underset{\text{indicator function}}{\underbrace{{\mathbf{1}}_{[0,\alpha \sqrt{n}]}(\Vert p_{\sigma }\Vert )}}\stackrel{\text{complements for discounted variance}}{\overbrace{\sqrt{1-(1-c_c{)}^2}}}\underset{\text{distributed as}\mathcal{N}(0,C_k)\text{under neutral selection}}{\underbrace{\sqrt{{\mu }_w}\frac{m_{k+1}-m_k}{{\sigma }_k}}}}$$

$${\displaystyle C_{k+1}=\underset{\text{discount factor}}{\underbrace{(1-c_1-c_{\mu }+c_s)}}{C}_k+c_1\underset{\text{rank one matrix}}{\underbrace{p_c{p}_c^T}}+c_{\mu }\underset{\mathrm{rank}min(\mu ,n)\text{ matrix}}{\underbrace{\sum _{i=1}^{\mu }{w}_i\frac{x_{i:\lambda }-m_k}{{\sigma }_k}{\left(\frac{x_{i:\lambda }-m_k}{{\sigma }_k}\right)}^T}}}$$

where${\displaystyle T}$ denotes the transpose and

• ${\displaystyle c_c^{-1}\approx n/4}$ is the backward time horizon for the evolution path${\displaystyle p_c}$ and larger than one,
• ${\displaystyle \alpha \approx 1.5}$ and theindicator function${\displaystyle {\mathbf{1}}_{[0,\alpha \sqrt{n}]}(\Vert p_{\sigma }\Vert )}$ evaluates to oneif and only if${\displaystyle \Vert p_{\sigma }\Vert \in [0,\alpha \sqrt{n}]}$ or, in other words,${\displaystyle \Vert p_{\sigma }\Vert \le \alpha \sqrt{n}}$, which is usually the case,
• ${\displaystyle c_s=(1-{\mathbf{1}}_{[0,\alpha \sqrt{n}]}(\Vert p_{\sigma }\Vert {)}^2)c_1{c}_c(2-c_c)}$ makes partly up for the small variance loss in case the indicator is zero,
• ${\displaystyle c_1\approx 2/n^2}$ is the learning rate for the rank-one update of thecovariance matrix and
• ${\displaystyle c_{\mu }\approx {\mu }_w/n^2}$ is the learning rate for the rank-${\displaystyle \mu }$ update of thecovariance matrix and must not exceed${\displaystyle 1-c_1}$.

Thecovariance matrix update tends to increase thelikelihood for${\displaystyle p_c}$ and for${\displaystyle (x_{i:\lambda }-m_k)/{\sigma }_k}$ to be sampled from${\displaystyle \mathcal{N}(0,C_{k+1})}$. This completes the iteration step.

The number of candidate samples per iteration,${\displaystyle \lambda }$, is not determined a priori and can vary in a wide range. Smaller values, for example${\displaystyle \lambda =10}$, lead to more local search behavior. Larger values, for example${\displaystyle \lambda =10n}$ with default value${\displaystyle {\mu }_w\approx \lambda /4}$, render the search more global. Sometimes the algorithm is repeatedly restarted with increasing${\displaystyle \lambda }$ by a factor of two for each restart.^[2] Besides of setting${\displaystyle \lambda }$ (or possibly${\displaystyle \mu }$ instead, if for example${\displaystyle \lambda }$ is predetermined by the number of available processors), the above introduced parameters are not specific to the given objective function and therefore not meant to be modified by the user.

functionxmin=purecmaes   %(mu/mu_w, lambda)-CMA-ES% --------------------  Initialization --------------------------------% User defined input parameters (need to be edited)strfitnessfct='frosenbrock';% name of objective/fitness functionN=20;% number of objective variables/problem dimensionxmean=rand(N,1);% objective variables initial pointsigma=0.3;% coordinate wise standard deviation (step size)stopfitness=1e-10;% stop if fitness < stopfitness (minimization)stopeval=1e3*N^2;% stop after stopeval number of function evaluations% Strategy parameter setting: Selectionlambda=4+floor(3*log(N));% population size, offspring numbermu=lambda/2;% number of parents/points for recombinationweights=log(mu+1/2)-log(1:mu)';% muXone array for weighted recombinationmu=floor(mu);weights=weights/sum(weights);% normalize recombination weights arraymueff=sum(weights)^2/sum(weights.^2);% variance-effectiveness of sum w_i x_i% Strategy parameter setting: Adaptationcc=(4+mueff/N)/(N+4+2*mueff/N);% time constant for cumulation for Ccs=(mueff+2)/(N+mueff+5);% t-const for cumulation for sigma controlc1=2/((N+1.3)^2+mueff);% learning rate for rank-one update of Ccmu=min(1-c1,2*(mueff-2+1/mueff)/((N+2)^2+mueff));% and for rank-mu updatedamps=1+2*max(0,sqrt((mueff-1)/(N+1))-1)+cs;% damping for sigma% usually close to 1% Initialize dynamic (internal) strategy parameters and constantspc=zeros(N,1);ps=zeros(N,1);% evolution paths for C and sigmaB=eye(N,N);% B defines the coordinate systemD=ones(N,1);% diagonal D defines the scalingC=B*diag(D.^2)*B';% covariance matrix CinvsqrtC=B*diag(D.^-1)*B';% C^-1/2eigeneval=0;% track update of B and DchiN=N^0.5*(1-1/(4*N)+1/(21*N^2));% expectation of%   ||N(0,I)|| == norm(randn(N,1))% -------------------- Generation Loop --------------------------------counteval=0;% the next 40 lines contain the 20 lines of interesting codewhilecounteval<stopeval% Generate and evaluate lambda offspringfork=1:lambdaarx(:,k)=xmean+sigma*B*(D.*randn(N,1));% m + sig * Normal(0,C)arfitness(k)=feval(strfitnessfct,arx(:,k));% objective function callcounteval=counteval+1;end% Sort by fitness and compute weighted mean into xmean[arfitness,arindex]=sort(arfitness);% minimizationxold=xmean;xmean=arx(:,arindex(1:mu))*weights;% recombination, new mean value% Cumulation: Update evolution pathsps=(1-cs)*ps...+sqrt(cs*(2-cs)*mueff)*invsqrtC*(xmean-xold)/sigma;hsig=norm(ps)/sqrt(1-(1-cs)^(2*counteval/lambda))/chiN<1.4+2/(N+1);pc=(1-cc)*pc...+hsig*sqrt(cc*(2-cc)*mueff)*(xmean-xold)/sigma;% Adapt covariance matrix Cartmp=(1/sigma)*(arx(:,arindex(1:mu))-repmat(xold,1,mu));C=(1-c1-cmu)*C...                  % regard old matrix+c1*(pc*pc'...                 % plus rank one update+(1-hsig)*cc*(2-cc)*C)... % minor correction if hsig==0+cmu*artmp*diag(weights)*artmp';% plus rank mu update% Adapt step size sigmasigma=sigma*exp((cs/damps)*(norm(ps)/chiN-1));% Decomposition of C into B*diag(D.^2)*B' (diagonalization)ifcounteval-eigeneval>lambda/(c1+cmu)/N/10% to achieve O(N^2)eigeneval=counteval;C=triu(C)+triu(C,1)';% enforce symmetry[B,D]=eig(C);% eigen decomposition, B==normalized eigenvectorsD=sqrt(diag(D));% D is a vector of standard deviations nowinvsqrtC=B*diag(D.^-1)*B';end% Break, if fitness is good enough or condition exceeds 1e14, better termination methods are advisableifarfitness(1)<=stopfitness||max(D)>1e7*min(D)break;endend% while, end generation loopxmin=arx(:,arindex(1));% Return best point of last iteration.% Notice that xmean is expected to be even% better.end% ---------------------------------------------------------------functionf=frosenbrock(x)ifsize(x,1)<2error('dimension must be greater one');endf=100*sum((x(1:end-1).^2-x(2:end)).^2)+sum((x(1:end-1)-1).^2);end

Given the distribution parameters—mean, variances and covariances—thenormal probability distribution for sampling new candidate solutions is themaximum entropy probability distribution over${\displaystyle {\mathbb{R}}^n}$, that is, the sample distribution with the minimal amount of prior information built into the distribution. More considerations on the update equations of CMA-ES are made in the following.

The CMA-ES implements a stochasticvariable-metric method. In the very particular case of a convex-quadratic objective function

$${\displaystyle f(x)=\frac{1}{2}(x-x^{\ast }{)}^{T}H(x-x^{\ast })}$$

the covariance matrix${\displaystyle C_k}$ adapts to the inverse of theHessian matrix${\displaystyle H}$,up to a scalar factor and small random fluctuations. More general, also on the function${\displaystyle g\circ f}$, where${\displaystyle g}$ is strictly increasing and therefore order preserving, the covariance matrix${\displaystyle C_k}$ adapts to${\displaystyle H^{-1}}$,up to a scalar factor and small random fluctuations. For selection ratio${\displaystyle \lambda /\mu \to \mathrm{\infty }}$ (and hence population size${\displaystyle \lambda \to \mathrm{\infty }}$), the${\displaystyle \mu }$ selected solutions yield an empirical covariance matrix reflective of the inverse-Hessian even in evolution strategies without adaptation of the covariance matrix. This result has been proven for${\displaystyle \mu =1}$ on a static model, relying on the quadratic approximation.^[3]

The update equations for mean and covariance matrix maximize alikelihood while resembling anexpectation–maximization algorithm. The update of the mean vector${\displaystyle m}$ maximizes a log-likelihood, such that

$${\displaystyle m_{k+1}=\arg \underset{m}{max}\sum _{i=1}^{\mu }{w}_i\log p_{\mathcal{N}}(x_{i:\lambda }\mid m)}$$

where

$${\displaystyle \log p_{\mathcal{N}}(x)=-\frac{1}{2}\log det(2\pi C)-\frac{1}{2}(x-m{)}^T{C}^{-1}(x-m)}$$

denotes the log-likelihood of${\displaystyle x}$ from a multivariate normal distribution with mean${\displaystyle m}$ and any positive definite covariance matrix${\displaystyle C}$. To see that${\displaystyle m_{k+1}}$ is independent of${\displaystyle C}$ remark first that this is the case for any diagonal matrix${\displaystyle C}$, because the coordinate-wise maximizer is independent of a scaling factor. Then, rotation of the data points or choosing${\displaystyle C}$ non-diagonal are equivalent.

The rank-${\displaystyle \mu }$ update of the covariance matrix, that is, the right most summand in the update equation of${\displaystyle C_k}$, maximizes a log-likelihood in that

$${\displaystyle \sum _{i=1}^{\mu }{w}_i\frac{x_{i:\lambda }-m_k}{{\sigma }_k}{\left(\frac{x_{i:\lambda }-m_k}{{\sigma }_k}\right)}^T=\arg \underset{C}{max}\sum _{i=1}^{\mu }{w}_i\log p_{\mathcal{N}}\left(\frac{x_{i:\lambda }-m_k}{{\sigma }_k}|C\right)}$$

for${\displaystyle \mu \ge n}$ (otherwise${\displaystyle C}$ is singular, but substantially the same result holds for). Here,${\displaystyle p_{\mathcal{N}}(x|C)}$ denotes the likelihood of${\displaystyle x}$ from a multivariate normal distribution with zero mean and covariance matrix${\displaystyle C}$. Therefore, for${\displaystyle c_1=0}$ and${\displaystyle c_{\mu }=1}$,${\displaystyle C_{k+1}}$ is the abovemaximum-likelihood estimator. Seeestimation of covariance matrices for details on the derivation.

Akimotoet al.^[4] and Glasmacherset al.^[5] discovered independently that the update of the distribution parameters resembles the descent in direction of a samplednatural gradient of the expected objective function value${\displaystyle Ef(x)}$ (to be minimized), where the expectation is taken under the sample distribution. With the parameter setting of${\displaystyle c_{\sigma }=0}$ and${\displaystyle c_1=0}$, i.e. without step-size control and rank-one update, CMA-ES can thus be viewed as an instantiation ofNatural Evolution Strategies (NES).^[4][5]Thenatural gradient is independent of the parameterization of the distribution. Taken with respect to the parametersθ of the sample distributionp, the gradient of${\displaystyle Ef(x)}$ can be expressed as

where${\displaystyle p(x)=p(x\mid \theta )}$ depends on the parameter vector${\displaystyle \theta }$. The so-calledscore function,${\displaystyle {\mathrm{\nabla }}_{\theta }\ln p(x\mid \theta )=\frac{{\mathrm{\nabla }}_{\theta }p(x)}{p(x)}}$, indicates the relative sensitivity ofp w.r.t.θ, and the expectation is taken with respect to the distributionp. Thenatural gradient of${\displaystyle Ef(x)}$, complying with theFisher information metric (an informational distance measure between probability distributions and the curvature of therelative entropy), now reads

where theFisher information matrix${\displaystyle F_{\theta }}$ is the expectation of theHessian of−lnp and renders the expression independent of the chosen parameterization. Combining the previous equalities we get

A Monte Carlo approximation of the latter expectation takes the average overλ samples fromp

$${\displaystyle \tilde{\mathrm{\nabla }}{\hat{E}}_{\theta }(f):=-\sum _{i=1}^{\lambda }\stackrel{\text{preference weight}}{\overbrace{w_i}}\underset{\text{candidate direction from }{x}_{i:\lambda }}{\underbrace{F_{\theta }^{-1}{\mathrm{\nabla }}_{\theta }\ln p(x_{i:\lambda }\mid \theta )}}\text{with }{w}_i=-f(x_{i:\lambda })/\lambda }$$

where the notation${\displaystyle i:\lambda }$ from above is used and therefore${\displaystyle w_i}$ are monotonically decreasing in${\displaystyle i}$.

Ollivieret al.^[6]finally found a rigorous derivation for the weights,${\displaystyle w_i}$, as they are defined in the CMA-ES. The weights are anasymptotically consistent estimator of theCDF of${\displaystyle f(X)}$ at the points of the${\displaystyle i}$thorder statistic${\displaystyle f(x_{i:\lambda })}$, as defined above, where${\displaystyle X\sim p(.|\theta )}$, composed with a fixed monotonically decreasing transformation${\displaystyle w}$, that is,

$${\displaystyle w_i=w\left(\frac{\mathsf{r}\mathsf{a}\mathsf{n}\mathsf{k}(f(x_{i:\lambda }))-1/2}{\lambda }\right).}$$

These weights make the algorithm insensitive to the specific${\displaystyle f}$-values. More concisely, using theCDF estimator of${\displaystyle f}$ instead of${\displaystyle f}$ itself let the algorithm only depend on the ranking of${\displaystyle f}$-values but not on their underlying distribution. This renders the algorithm invariant to strictly increasing${\displaystyle f}$-transformations. Now we define

$${\displaystyle \theta =[m_k^T\mathrm{vec}(C_k{)}^T{\sigma }_k{]}^T\in {\mathbb{R}}^{n+n^2+1}}$$

such that${\displaystyle p(\cdot \mid \theta )}$ is the density of themultivariate normal distribution${\displaystyle \mathcal{N}(m_k,{\sigma }_k^2{C}_k)}$. Then, we have an explicit expression for the inverse of the Fisher information matrix where${\displaystyle {\sigma }_k}$ is fixed

and for

and, after some calculations, the updates in the CMA-ES turn out as^[4]

where mat forms the proper matrix from the respective natural gradient sub-vector. That means, setting${\displaystyle c_1=c_{\sigma }=0}$, the CMA-ES updates descend in direction of the approximation${\displaystyle \tilde{\mathrm{\nabla }}{\hat{E}}_{\theta }(f)}$ of the natural gradient while using different step-sizes (learning rates 1 and${\displaystyle c_{\mu }}$) for theorthogonal parameters${\displaystyle m}$ and${\displaystyle C}$ respectively. More recent versions allow a different learning rate for the mean${\displaystyle m}$ as well.^[7] The most recent version of CMA-ES also use a different function${\displaystyle w}$ for${\displaystyle m}$ and${\displaystyle C}$ with negative values only for the latter (so-called active CMA).

It is comparatively easy to see that the update equations of CMA-ES satisfy some stationarity conditions, in that they are essentially unbiased. Under neutral selection, where${\displaystyle x_{i:\lambda }\sim \mathcal{N}(m_k,{\sigma }_k^2{C}_k)}$, we find that

$${\displaystyle \mathrm{E}(m_{k+1}\mid m_k)=m_k}$$

and under some mild additional assumptions on the initial conditions

$${\displaystyle \mathrm{E}(\log {\sigma }_{k+1}\mid {\sigma }_k)=\log {\sigma }_k}$$

and with an additional minor correction in the covariance matrix update for the case where the indicator function evaluates to zero, we find

$${\displaystyle \mathrm{E}(C_{k+1}\mid C_k)=C_k}$$

Invariance properties imply uniform performance on a class of objective functions. They have been argued to be an advantage, because they allow to generalize and predict the behavior of the algorithm and therefore strengthen the meaning of empirical results obtained on single functions. The following invariance properties have been established for CMA-ES.

• Invariance under order-preserving transformations of the objective function value${\displaystyle f}$, in that for any${\displaystyle h:{\mathbb{R}}^n\to \mathbb{R}}$ the behavior is identical on${\displaystyle f:x\mapsto g(h(x))}$ for all strictly increasing${\displaystyle g:\mathbb{R}\to \mathbb{R}}$. This invariance is easy to verify, because only the${\displaystyle f}$-ranking is used in the algorithm, which is invariant under the choice of${\displaystyle g}$.
• Scale-invariance, in that for any${\displaystyle h:{\mathbb{R}}^n\to \mathbb{R}}$ the behavior is independent of${\displaystyle \alpha >0}$ for the objective function${\displaystyle f:x\mapsto h(\alpha x)}$ given${\displaystyle {\sigma }_0\propto 1/\alpha }$ and${\displaystyle m_0\propto 1/\alpha }$.
• Invariance under rotation of the search space in that for any${\displaystyle h:{\mathbb{R}}^n\to \mathbb{R}}$ and any${\displaystyle z\in {\mathbb{R}}^n}$ the behavior on${\displaystyle f:x\mapsto h(Rx)}$ is independent of theorthogonal matrix${\displaystyle R}$, given${\displaystyle m_0=R^{-1}z}$. More general, the algorithm is also invariant under general linear transformations${\displaystyle R}$ when additionally the initial covariance matrix is chosen as${\displaystyle R^{-1}{R^{-1}}^T}$.

Any serious parameter optimization method should be translation invariant, but most methods do not exhibit all the above described invariance properties. A prominent example with the same invariance properties is theNelder–Mead method, where the initial simplex must be chosen respectively.

Conceptual considerations like the scale-invariance property of the algorithm, the analysis of simplerevolution strategies, and overwhelming empirical evidence suggest that the algorithm converges on a large class of functions fast to the global optimum, denoted as${\displaystyle x^{\ast }}$. On some functions, convergence occurs independently of the initial conditions with probability one. On some functions the probability is smaller than one and typically depends on the initial${\displaystyle m_0}$ and${\displaystyle {\sigma }_0}$. Empirically, the fastest possible convergence rate in${\displaystyle k}$ for rank-based direct search methods can often be observed (depending on the context denoted aslinear convergence orlog-linear orexponential convergence). Informally, we can write

$${\displaystyle \Vert m_k-x^{\ast }\Vert \approx \Vert m_0-x^{\ast }\Vert \times e^{-ck}}$$

for some${\displaystyle c>0}$, and more rigorously

or similarly,

This means that on average the distance to the optimum decreases in each iteration by a "constant" factor, namely by${\displaystyle \exp (-c)}$. The convergence rate${\displaystyle c}$ is roughly${\displaystyle 0.1\lambda /n}$, given${\displaystyle \lambda }$ is not much larger than the dimension${\displaystyle n}$. Even with optimal${\displaystyle \sigma }$ and${\displaystyle C}$, the convergence rate${\displaystyle c}$ cannot largely exceed${\displaystyle 0.25\lambda /n}$, given the above recombination weights${\displaystyle w_i}$ are all non-negative. The actual linear dependencies in${\displaystyle \lambda }$ and${\displaystyle n}$ are remarkable and they are in both cases the best one can hope for in this kind of algorithm. Yet, a rigorous proof of convergence is missing.

Using a non-identity covariance matrix for themultivariate normal distribution inevolution strategies is equivalent to a coordinate system transformation of the solution vectors,^[8] mainly because the sampling equation

can be equivalently expressed in an "encoded space" as$${\displaystyle \underset{\text{represented in the encode space}}{\underbrace{C_k^{-1/2}{x}_i}}\sim \underbrace{C_k^{-1/2}{m}_k}+{\sigma }_k\times \mathcal{N}(0,I)}$$

The covariance matrix defines abijective transformation (encoding) for all solution vectors into a space, where the sampling takes place with identity covariance matrix. Because the update equations in the CMA-ES are invariant under linear coordinate system transformations, the CMA-ES can be re-written as an adaptive encoding procedure applied to a simpleevolution strategy with identity covariance matrix.^[8]This adaptive encoding procedure is not confined to algorithms that sample from a multivariate normal distribution (like evolution strategies), but can in principle be applied to any iterative search method.

In contrast to most otherevolutionary algorithms, the CMA-ES is, from the user's perspective, quasi-parameter-free. The user has to choose an initial solution point,${\displaystyle m_0\in {\mathbb{R}}^n}$, and the initial step-size,${\displaystyle {\sigma }_0>0}$. Optionally, the number of candidate samples λ (population size) can be modified by the user in order to change the characteristic search behavior (see above) and termination conditions can or should be adjusted to the problem at hand.

The CMA-ES has been empirically successful in various applications and is considered to be particularly useful on non-convex, non-separable, ill-conditioned, multi-modal or noisy objective functions.^[9] One survey of Black-Box optimizations found it outranked 31 other optimization algorithms, performing especially strongly on "difficult functions" or larger-dimensional search spaces.^[10]

The search space dimension ranges typically between two and a few hundred. Assuming a black-box optimization scenario, where gradients are not available (or not useful) and function evaluations are the only considered cost of search, the CMA-ES method is likely to be outperformed by other methods in the following conditions:

• on low-dimensional functions, say, for example by thedownhill simplex method or surrogate-based methods (likekriging with expected improvement);
• on separable functions without or with only negligible dependencies between the design variables in particular in the case of multi-modality or large dimension, for example bydifferential evolution;
• on (nearly)convex-quadratic functions with low or moderatecondition number of theHessian matrix, whereBFGS orNEWUOA or SLSQP are typically at least ten times faster;
• on functions that can already be solved with a comparatively small number of function evaluations, say no more than${\displaystyle 10n}$, where CMA-ES is often slower than, for example,NEWUOA orMultilevel Coordinate Search (MCS).

On separable functions, the performance disadvantage is likely to be most significant in that CMA-ES might not be able to find at all comparable solutions. On the other hand, on non-separable functions that are ill-conditioned or rugged or can only be solved with more than${\displaystyle 100n}$ function evaluations, the CMA-ES shows most often superior performance.

The (1+1)-CMA-ES^[11] generates only one candidate solution per iteration step which becomes the new distribution mean if it is better than the current mean. For${\displaystyle c_c=1}$ the (1+1)-CMA-ES is a close variant ofGaussian adaptation. SomeNatural Evolution Strategies are close variants of the CMA-ES with specific parameter settings. Natural Evolution Strategies do not utilize evolution paths (that means in CMA-ES setting${\displaystyle c_c=c_{\sigma }=1}$) and they formalize the update of variances and covariances on aCholesky factor instead of a covariance matrix. The CMA-ES has also been extended tomultiobjective optimization as MO-CMA-ES.^[12] Another remarkable extension has been the addition of a negative update of the covariance matrix with the so-called active CMA.^[13]Using the additional active CMA update is considered as the default variant nowadays.^[7]

• Global optimization – Branch of mathematics
• Stochastic optimization – Optimization method
• Derivative-free optimization – Mathematical discipline
• Estimation of distribution algorithm – Family of stochastic optimization methods

• 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]