CMA-ES

공분산 행렬 적응 진화 전략(CMA-ES)은 수치 최적화를 위한 특정한 종류의 전략이다. 진화 전략(ES)은 비선형 또는 비콘벡스 연속 최적화 문제의 수치 최적화를 위한 확률적이고 파생적이지 않은 방법이다. 그것들은 진화 알고리즘과 진화 계산의 등급에 속한다. 진화 알고리즘은 생물학적 진화의 원리, 즉 (재조합과 돌연변이를 통한) 변동의 반복적인 상호연극과 선택: 각 세대(반복)에서 새로운 개인(pandidate solution, $x{\displaystyle }$ ${\displaystyle x$이 보통 확률적인 방식으로 변동에 의해 생성된다. 현재 부모의 개인 그 후, 어떤 개인은 자신의 적합성이나 객관적인 기능 $값{\displaystyle }$ f $){\displaystyle$ f$(x)}}$을 기준으로 다음 세대의 부모가 되는 것으로 선택된다$.$ 이와 같이 세대 순서에 따라 $더{\displaystyle }$ 나은 f$[\displaystyle$ f$} -값$을 가진$$ 개인은 생성된다.

진화 전략에서, 새로운 후보 솔루션은 다변량 정규 분포에 따라 ${\displaystyle {}^{}}$ ${\$에 따라 샘플링된다$.$ 재결합은 분포에 대한 새로운 평균값을 선택하는 데 해당된다. 돌연변이는 평균이 0인 동요인 무작위 벡터를 추가하는 것이다. 분포의 변수들 사이의 쌍방향 종속성은 공분산 행렬로 표현된다. 공분산 행렬 적응법(CMA)은 이 분포의 공분산 행렬을 업데이트하는 방법이다. 이것은 $기능{\displaystyle }$ f ${\displaystyle f}$이(가) 잘못된 조건일 경우 특히 유용하다.

공분산 행렬의 적응은 고전적 최적화의 준뉴턴 방법에서 헤시안 행렬의 역행렬의 근사치와 유사한 기초 목적함수의 두 번째 순서 모델을 배우는 것에 해당한다. 대부분의 고전적인 방법과 대조적으로, 기본 목표 기능에 대한 가정은 더 적다. 후보 솔루션의 순위(또는 동등하게 정렬)만 활용되기 때문에 파생상품도, 심지어 (명확한) 객관적 기능도 이 방법에 의해 요구되지 않는다. 예를 들어, 순위는 스위스-시스템 토너먼트에서 후보 솔루션 간의 쌍끌이 시합에서 나올 수 있다.

원칙

단순한 2차원 문제에 공분산 행렬 적응을 사용한 실제 최적화 실행 그림. 구형 최적화 조경은 동일한 $f{\displaystyle }$ ${\displaystyle f}$ -값의$$ 실선으로 표시된다. 모집단(점)은 필요한 것보다 훨씬 크지만, 최적화하는 동안 모집단(점선)의 분포가 어떻게 변하는지 명확하게 보여준다. 이 간단한 문제에 대해, 인구는 몇 세대 안에 세계 최적화에 집중한다.

검색 분포의 매개변수 적응을 위한 두 가지 주요 원칙은 CMA-ES 알고리즘에서 활용된다.

첫째, 합격자 해법과 검색 단계의 확률을 높이기 위한 아이디어에 근거한 최대 우도 원칙이다. 분포의 평균은 이전에 성공한 후보 솔루션의 가능성이 최대화되도록 업데이트된다. 분포의 공분산 행렬은 이전에 성공한 검색 단계의 가능성이 증가하도록 업데이트된다(증분). 두 업데이트 모두 자연스러운 그라데이션 강하로 해석할 수 있다. 또한 CMA는 모든 주축을 유지하면서 성공적인 검색 단계에 대한 반복된 주성분 분석을 수행한다. 분포 알고리즘 추정과 교차-엔트로피 방법은 매우 유사한 아이디어에 기초하지만 성공적인 검색 단계 대신 성공적인 솔루션 포인트의 가능성을 극대화하여 공분산 행렬을 추정(비증분)한다.

둘째, 전략의 분포 평균의 시간 진화의 두 가지 경로를 검색 또는 진화 경로라고 한다. 이러한 경로에는 연속적인 단계 간의 상관관계에 대한 중요한 정보가 포함되어 있다. 구체적으로는 유사한 방향으로 연속적인 조치를 취하면 진화 경로가 길어진다. 진화의 길은 두 가지 방법으로 이용된다. 하나의 경로는 성공적인 단일 검색 단계 대신 공분산 행렬 적응 절차에 사용되며 유리한 방향의 분산을 훨씬 빠르게 증가시킬 수 있다. 다른 경로는 추가 단계 크기 제어를 수행하는 데 사용된다. 이 단계적 크기 제어는 기대에서 직교하는 분포 평균의 연속적인 이동을 목표로 한다. 단계적 크기 제어는 조기 수렴을 효과적으로 방지하면서도 빠른 수렴을 최적으로 허용한다.

알고리즘.

다음은 가장 일반적으로 사용되는 (μ/μ_w, μ)-CMA-ES의 개요를 설명하며, 각 반복 단계에서는 μ 중에서 가장 좋은 μ의 가중 조합이 분포 매개변수를 업데이트하는 데 사용된다. 메인 루프는 1) 새 솔루션의 샘플링, 2) 적합성에 기반한 샘플링 솔루션의 재주문, 3) 재주문된 샘플에 기반한 내부 상태 변수의 업데이트 등 3가지 주요 부분으로 구성된다. 알고리즘의 유사코드는 다음과 같다.

설정 반복당 샘플의 λ{\lambda\displaystyle}//번호, 적어도 두개, 일반적으로입니다.;4initialize m{m\displaystyle},σ{\displaystyle \sigma}, C)나는, pσ)}0{\displaystyle p_{\sigma}=0{C=I\displaystyle}, c)0{\displaystyle p_{c}=0}//initialize 상태 변수 반면 n.고르terminate do  // iterate     for ${\displaystyle i}$ in ${\displaystyle \{1\ldots \lambda \}}$ do  // sample ${\displaystyle \lambda }$ new solutions and evaluate them         ${\displaystyle x_{i}={}}$sample_multivariate_normal(mean${\displaystyle {}=m}$, covariance_matrix${\displaystyle ={\sigma }^2}$${\displaystyle {}=\sigma ^{2}C}$)         ${\displaystyle f_{i}=\operatorname {fitness} (x_{i})}$ ${\displaystyle x_{1\ldots \lambda }}$ ← ${\displaystyle x_{s(1)\ldots s(\lambda )}}$ with ${\displaystyle s(i)=\o$$peratorname {argsort} (f_{1\ldots \lambda },i)}$ // sort solutions     ${\displaystyle m'=m}$  // we need later ${\displaystyle m-m'}$ and ${\displaystyle x_{i}-m'}$ ${\displaystyle m}$ ← update_m${\displaystyle (x_{1},\ldots ,x_{\lambda })}$  // move mean to better solutions      ${\displaystyle p_{\sigma }}$ ← update_ps${\displaystyle (p_{\sigma },\sigma ^{-1}C^{-1/2}(m-m'))}$  // update isotropic evolution path     ${\displaystyle p_{c}}$ ← update_pc${\$$displaystyle (p_{c},\sigma ^{-1}(m-m'),\ p_{\sigma }\ )}$  // update anisotropic evolution path     ${\displaystyle C}$ ← update_C${\displaystyle (C,p_{c},(x_{1}-m')/\sigma ,\ldots ,(x_{\lambda }-m')/\sigma )}$  // update covariance matrix     ${\displ$$aystyle \chostma }$$$←$$ update_sigma${\displaystyle }$($$ ${\displaystyle \Vert }$ ${\displaystyle p_{}}$ ${\displaystyle {}_{}}$ $displaystyle ,\p_{\pma }\}$ //$$ 등방성 경로 길이 $리턴{\displaystyle }$ m ${\displaystym m}$ $또는$ ${\displaystyle {x\mathrm{}}_{}}$ 1 ${\$}을 사용하여 단계 크기 업데이트 

다섯 $가지{\displaystyle }$ 업데이트 할당의 순서는 다음과 같다: $m{\displaystyle }$ ${\displaystyle m}$이(가) 먼저 업데이트되어야 하고$$, $p{\displaystyle {}_{}}$ ${\displaystyle {\sigma }_{}}$ ${\$$sigma$$},$$$${\displaystyle p_{}}$ ${\displaystyle$$p_$${c}$이$($가$)$ $마지막$으로 업데이트되어야 한다$$$$. 다음에서는 5개 상태 변수에 대한 업데이트 방정식을 지정한다.

검색 공간 차원 $n{\displaystyle }$ ${\displaystyle n}$ 및$$ 반복 단계 $k{\displaystyle }$ ${\displaystyle k}$이$($가) 제공됨. 다섯 가지 국가 변수는

${\displaystyle m_{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}^{}}$ ${\$ 최적화 문제에 대한 분포 평균 및 현재 즐겨찾는 솔루션,

> ${\displaystyle \sigma _{k}>0$ 스텝 사이즈,

${\displaystyle C_{}}$ ${\displaystyle k_{}}$ ${\$ C ${\displaystyle {0\mathrm{}}_{}}$= ${\displaystyle I}$ ${\displaystyle C_{0}=I}$을(를) 갖는$$ 대칭적이고 확실한 $n{\displaystyle }$ ${\displaystyle \times }$ ${\displaystyle n}${\$displaystyle n\\times$ n$}$ 공분산$$ 행렬 및

${\displaystyle p_{}}$ ${\displaystyle {\sigma }_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathbb{}}^{}}$ ${\displaystyle {}^{}}$, p ${\displaystyle c_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {\mathbb{}}^{}}$ n ${\$mathb {R$}\in \mathb$ {$R}^{$n$\}\}\}\},$ 초기에는 0 벡터로 설정된 두 개의 진화 경로가 있다.

그 반복 λ를 견본 추출과 함께, 나는 갈1{\displaystyle \lambda 1}후보 솔루션 나는}은 다변량 정규 분포에서 N(mk, kσ 2Ckm그리고 4.9초 만){\displaystyle \textstyle{{\mathcal N}}(m_{k},\sigma_{k}^{2}C_{k})}Rn{\displaystyle x_{나는}\in \mathbb{R}^{n}∈, 즉 x 시작한다.1, …${\displaystyle i=1,\ldots,\\da }$

${\displaystyle {\begin}x_{i}\\\sim \{\mathcal{N}(m_{k},\sigma _{k}^{k}}}\\\sim \m_{k}+}\c}\time {\n}}{{{{N}}}}}}}}}}}}}}}}}:{n}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

두 번째 선은 현재 선호하는 용액 벡터 ${\displaystyle m_{}}$ k ${\$분포 평균 벡터)의 섭동(혼합)으로 해석을 제시한다. 후보 솔루션 $x{\displaystyle {}_{}}$ ${\displaystyle i_{}}$ ${\$은(는) 최소화할$$ 목표 $함수{\displaystyle }$ f${\displaystyle }$: ${\displaystyle {}^{}}$ ${\displaystyle n\mathbb{}{}^{}}$→ R ${\$에 대해 평가한다$$. $f{\displaystyle }$ ${\displaystyle f}$ - 다양한$$ 후보 솔루션을 다음과 같이 표시

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

새로운 평균 값은 다음과 같이 계산된다.

${\displaystyle {\begin{aligned}m_{k+1}&=\sum _{i=1}^{\mu }w_{i}\,x_{i:\lambda }\\&=m_{k}+\sum _{i=1}^{\mu }w_{i}\,(x_{i:\lambda }-m_{k})\end{aligned}}}$

서 1 w w > {\$displaystyle w_{$1}\$geq w_{2}\geq \geq$ \$geq \{\mu }}}}}$의 양이 1에 해당한다. Typically, ${\displaystyle \mu \leq \lambda /2}$ and the weights are chosen such that ${\displaystyle \textstyle \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 지수 $i{\displaystyle }$:${\displaystyle \lambda }$ ${\displaystyle i:\lambda }$ 때문에 후보 솔루션을 샘플링했다$.$

스텝사이즈 $\sigma {\displaystyle {}_{}}$ ${\displaystyle k_{}}${\$displaystyle \sigma _{k}$는 누적 스텝사이즈 적응(CSA)을 사용하여 업데이트되며$$, 때로는 경로 길이 조절로도 알려져 있다. 진화경로(또는 검색경로) $p{\displaystyle {}_{}}$ ${\$p_{\$sigma$}}}이(가) 먼저 업데이트된다$$.

$_{\displaystyle p_{\buffma }\buffer \underbrace {(1-c_{\buffma }}} _{\!\!\!\!\!{\text{factor}\!\!\!\!\!}\,p_{\p_{\pma }+\overbrace {\sqrt {1-(1-c_{\probma }}^{2}} ^{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{datability}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu_{w}\,C_{k}^{\\;-1/2}}\,{\frac {\overbrace {m_{k+1}-m_{k}}} ^{\!\!{\text{{}m\!\!}{\\ma _{k}}} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text}{{}}}{\mathcal{N}(0,I){\text{중립선택시)}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}$

${\displaystyle \sigma _{k+1}=\sigma _{k}\times \exp {\bigg (}{\frac {c_{\sigma }}{d_{\sigma }}}\underbrace {\left({\frac {\ p_{\sigma }\ }{\operatorname {E} \ {\mathcal {N}}(0,I)\ }}-1\right)} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{national selection}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}{\bigg )}}}}}$

어디에

${\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 an exponential 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\leq \mu _{w}\leq \mu }$ by definition of ${\displaystyle w_{i}}$,

${\displaystyle C_{k}^{\;-1/2}={\sqrt {C_{k}}}^{\;-1}={\sqrt {C_{k}^{\;-1}}}}$ is the unique symmetric square root of the inverse of ${\displaystyle C_{k}}$, and

${\displaystyle d_{}}$ ${\$는 보통 1에 가까운 댐핑 매개변수다. $d{\displaystyle {}_{}}$ ${\displaystyle {\sigma }_{}}$= $∞$ = $display$ {\$displaystyle d_${\sigma }=\$put }$ 또는$$ $c{\displaystyle {}_{}}$ ${\displaystyle {\sigma }_{}}$= ${\displaystyle 0}$ ${\displaystyle c_{\sigma }=0}$의 경우 단계 크기는 변경되지 않은 상태로 유지된다.

스텝 사이즈 ${\$는 $\Vert {\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle {\sigma }_{}}$ {\$displaystyle \p_{\sigma }\}}$이(가) 예상값보다 큰 경우에만 증가한다$$.

${\displaystyle {\begin{aligned}\operatorname {E} \ {\mathcal {N}}(0,I)\ &={\sqrt {2}}\,\Gamma ((n+1)/2)/\Gamma (n/2)\\&\approx {\sqrt {n}}\,(1-1/(4\,n)+1/(21\,n^{2}))\end{aligned}}}$

그리고 더 작으면 줄어들었다. 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 \textstyle \left({\frac {m_{k+2}-m_$${k+1}{\probma _{k+1}}\오른쪽)^{$$T}\!C_{k}^{-1}{\frac {m_{k+1}-m_{k}}{\sigma _{k}}\약$ 0$\}.$^[1]

마지막으로 공분산 행렬이 업데이트되고, 여기서 다시 각 진화 경로가 먼저 업데이트된다.

${\displaystyle p_{c}\desc \underbrace {(1-c_{c}) _{\!\!\!\!\!{\text{factor}\!\!\!\!\!}\,p_{c}+\underbrace {1} _{[0,\propert{n}}}}(\p_{\sqrt{n}})}}(\p_{\text{nma }\}}}}}}}}}\오버브레이스{1-(1-c_{c}^2}}!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{datability}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\underbrace {{\sqrt {\mu _{w}\,{\frac {m_{k+1}-m_{k}}{\ma _{k}}}}}{\\\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!{\text{data.}\}\\text{data.}\\\mathcal{N}(0,C_{k!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}}$

${\displaystyle C_{k+1}=\underbrace {(-1-c_{1}-c_{\mu }+c_{s}) _{\!\!\!\!\!{\text{factor}\!\!\!\!\!}\,C_{k}+C_{1}}\underbrace {p_{c}p_{c}^{{c}^T} _{\!\!\!\!\!\!\!\!\!\!\!\!\!\!\\!{\text{list one matrix}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}+\,c_{\mu }\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} _{\operatorname {rank} \min(\mu ,n){\text{ 매트릭스}}}}}}$

$여기$서 T ${\displaystyle T}$은 전치 및

${\displaystyle c_{}^{}}$- ${\displaystyle 1_{}^{}}$ ${\displaystyle {}_{}^{}n}$/ ${\displaystyle 4\mathrm{}}$ ${\displaystyle c_{c}^{-1}\$약$n/4}$은(는) ${\displaystyle 1_{}}$보다 큰 진화의 $경로{\displaystyle {}_{}}$ p ${\$에 대한 후진 시간 지평이다.

${\displaystyle \alpha \approx 1.5}$ and the indicator function ${\displaystyle \mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\ p_{\sigma }\ )}$ evaluates to one iff ${\displaystyle \ p_{\sigma }\ \in [0,\alpha {\sqrt {n}}]}$ or, in other words, ${\displaystyle \Vert p_{\sigma }\Vert }$${\displaystyle \le }$ ${\displaystyle \alpha n\sqrt{}}$ ${\${\$sqrt{n$ 보통은 다음과 같다.

${\displaystyle c_{s}=(1-\mathbf {1} _{[0,\alpha {\sqrt {n}}]}(\ p_{\sigma }\ )^{2})\,c_{1}c_{c}(2-c_{c})}$ makes partly up for the small variance loss in case the indicator is zero,

${\displaystyle {}_{}\mathrm{c}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\displaystyle {}_{}}$ 2${\displaystyle }$/ ${\displaystyle {n\mathrm{}}^{}}$ ${\displaystyle 2{}^{}}$ ${\$ 약 $2/n^{2}}:$ 공분산 행렬의 순위 1 업데이트에 대한 학습 속도

${\displaystyle c_{}{}_{}}$ ${\displaystyle w_{}}$/ ${\displaystyle n{}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\$}}은$$ 공분산 행렬의 순위 ${\displaystyle }$ ${\displaystyle \mu }$ 업데이트에$$ 대한 학습률이며 $1{\displaystyle \mathrm{}}$ -${\displaystyle {c\mathrm{}}_{}}$ ${\$를 초과해서는 안 된다$.$

The covariance matrix update tends to increase the likelihood 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})}$. 이렇게 하면 반복 단계가 완료된다.

$반복당{\displaystyle }$ 후보 표본 수 , ${\displaystyle \lambda }$은$($는) priori로 결정되지 않으며 광범위한 범위에서 달라질 수 있다. $예$를 들어${\displaystyle 10}$ =$$10 {\$displaystyle \lambda$ =$10}$과 같은 값이 작을수록 로컬 검색 동작이 많아진다$.$ $예$를 들어, 기본값 ${\displaystyle {\mu }_{}}$가 w μ w ${\displaystyle \mu }$ w ${\displaystyle {}_{}}$/ ${\displaystyle 4\mathrm{}}${\$displaystyle \mu _{w}\약 \lambda /4$인 ${\displaystyle =}$ $= 10n}$ 값이 클수록 검색이 보다 글로벌하게 된다. 때때로 알고리즘은 각 재시작에 대해 $two{\displaystyle }$ ${\displaystyle \lambda }$을(를) 2배씩 증가시키면서 반복적으로 재시작된다.^[2] $\lambda {\displaystyle }$ ${\displaystyle \lambda }($또는$$ $\mu s{\displaystyle }$ ${\displaystyle \lambda }$이($$가) 사용 가능한 프로세서 수로 미리 결정된$$ 경우)를 설정하는 것 외에, 위에서 소개한 파라미터는 주어진 목표 기능에 한정되지 않으므로 사용자가 수정할 수 없다.

MATLAB/Octave의 예 코드

function xmin=purecmaes   % (mu/mu_w, lambda)-CMA-ES  % --------------------  Initialization --------------------------------    % User defined input parameters (need to be edited)  strfitnessfct = 'frosenbrock'; % name of objective/fitness function  N = 20; % number of objective variables/problem dimension  xmean = rand(N,1); % objective variables 초기 점 시그마 = 0.3, % 좌표현 표준 편차(단계 크기) 스톱피트 = 1e-10, 피트니스 < 스톱피트니스(미니메이션) 스톱피트 = 1e3*N^2; 함수 평가의 스톱볼 수 후 % 스톱스톱, % 전략 매개변수 설정: Selection    lambda = 4+floor(3*log(N)); % population size, offspring number  mu = lambda/2; % number of parents/points for recombination  weights = log(mu+1/2)-log(1:mu)'; % muXone array for weighted recombination  mu = floor(mu);   weights = weights/sum(weights); % normalize recombination weights array  mueff=sum(weights)^2/sum(weights.^2); w_i x_i % 전략 매개변수 설정: Adaptation  cc = (4+mueff/N) / (N+4 + 2*mueff/N); % time constant for cumulation for C  cs = (mueff+2) / (N+mueff+5); % t-const for cumulation for sigma control  c1 = 2 / ((N+1.3)^2+mueff); % learning rate for rank-one update of C  cmu = min(1-c1, 2 * (mueff-2+1/mueff) / ((N+2)^2+mueff)); % and for rank-mu update  damps = 1 + 2*max(0, sqrt((mueff-1)/(N+1))-1) + cs; % damping for sigma   % usually close to 1  % Initialize dynamic (internal) strategy parameters and constants  pc = zeros(N,1); ps = zeros(N,1); % evolution paths for C and sigma  B = eye(N,N); % B defines the coordinate system  D = ones(N,1); % diagonal D defines the scaling  C = B * diag(D.^2) * B'; % covariance matrix C  invsqrtC = B * diag(D.^-1) * B'; % C^-1/2   eigeneval = 0; % track update of B and D  chiN=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 interest잉 코드는 동안counteval<>stopeval%생성하고 평가 lambda 자식을 점지 k=1:람다 arx(:,k))xmean+시그마*B((D.* randn(N,1));%m+sig*Normal(0,C)arfitness(k))feval(strfitnessfct, arx(:,k).%객관적인 함수 호출 counteval)counteval+1, end%정렬 기준 건강과 컴퓨팅 가중 평균으로xmean[arfitnes.sarindex] = 정렬(능률), % 최소화 xold = xmean, xmean = arx(:,arindex(1:mu))*중량, % 재결합, 새 평균 값 % 누적: Update evolution paths  ps = (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 C  artmp = (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(가중치) * artmp'; % 더하기 mu update % Adapt step size sigma = sigma * exp(cs/damps)*(norm(ps)/chiN - 1); C를 B*diag(D)로 분해.^2)*B의(대각선화)만약counteval-eigeneval>lambda(c1+cmu)/N/10%O(N^2)eigeneval=counteval을 이루기 위해;C)triu(C)+triu(C,1)'이다;%)eig(C).%고유 분해, B==normalized 값 D)sqrt(diag(D). 표준 편차의%D는 벡터 지금)B*diag(D.^-1)*invsqrtC 대칭[B,D]를 숙정하다 B'이다;끝%을 깨트린 경우.하이 파이tness가 충분하거나 조건이 1e14를 초과하며, artfitty(1) <= stopfitty max(D) > 1e7 * min(D) break; end %, end generation loop xmin = arx(:, arindex(1); 마지막 반복의 Returning best point.% xmean이 훨씬 더 좋을 것으로 예상됨. %. 끝 % ------------------------------------------------------------------------------------------------------- 크기(x,1) < 2 에러 ('dimension가 더 커야 한다'; 끝 f = 100*sum(x(1:end-1))^2 - x(2:end)).^2) + 합(x(1:end-1)-1).^2); 끝 

이론적 기초

분포 모수(평균, 분산 및 공분산)를 고려할 때, 새로운 후보 솔루션을 샘플링하기 위한 정규 확률 분포는 ${\displaystyle {}^{}}$ ${\$ 즉 분포에 내장된 최소한의 사전 정보를 가진 표본 분포다. CMA-ES의 업데이트 방정식에 대한 추가 고려사항은 다음과 같다.

가변 미터법

CMA-ES는 확률적 변수-금속 방법을 구현한다. 볼록한 2차 목표 함수의 매우 특별한 경우

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

공분산 행렬 $C{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$은(는) 스칼라 인자와 작은 랜덤 변동까지 Hesian $행렬{\displaystyle }$ H$${\$displaystyle$H$\}$의 역에 적응한다$$. $보다{\displaystyle }$ 일반적이며$,$ $g{\displaystyle }$ ${\displaystyle$ g}이$($$가)$ 엄격히 증가하여$$ 보존 순서를$정하고$ f ${\displaystyle f}$이(가) 볼록한 양수인$$ 경우 공분산 행렬 ${\displaystyle C_{}}$ $k{\displaystyle {}_{}}$ ${\$는 스칼라 $인자$에${\displaystyle {\mathrm{따라}}^{}}$ H$$- 1 {\$displaystyle$ H$^{-$1$\}$에 적응한다$$. 그리고 작은 무작위 변동. 역-헤시안을 반영하는 공분산 행렬을 적응시키기 위한 일반화된 진화 전략 능력이 2차 근사치에 의존하는 정적 모델에 대해 입증되었다는 점에 유의한다.^[3]

최대 우도 업데이트

평균 및 공분산 행렬에 대한 업데이트 방정식은 기대 최대화 알고리즘과 유사하면서 가능성을 최대화한다. 평균 벡터 $m{\displaystyle }$ ${\displaystyle m}$의 업데이트는 로그 우도를 최대화하며$$, 다음과 같다.

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

어디에

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

$평균{\displaystyle {}_{}}$ $m{\displaystyle }$ ${\displaystyle m$$}$과(와) 모든 양의 한정된 $공분산{\displaystyle }$행렬 C {\$displaystyle$ m_${$k+1}이(가) 있는$$ $다변량{\displaystyle }$정규 $분포$에서 x {\$displaystyle$ x}의 로그 우도를 나타냄$.$$먼저$ m k + 1 {\$displaystylem$ $m_$${k+$1}이 C$}$에 대해 독립적이라는$$ 것을$$ 확인하십시오. 좌표-현상 최대화자가 스케일링 계수와 독립적이기 때문에 임의의 $대각{\displaystyle }$ 행렬$$C {\$displaystyle$C$.$ 그런 다음 데이터 점을 회전하거나 $C{\displaystyle }$ ${\displaystyle C}$ 비대각형을$$ 선택하는 것이 동일하다.

공분산 행렬의 순위 ${\displaystyle }$ ${\displaystyle \mu }$ 업데이트$$, 즉 $C{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$의 업데이트 방정식에서 가장 적절한 요약으로 로그 우도를 최대화한다$.$

${\displaystyle \sum \sum _{i=1}^{\w_{i}{x_{i:}-m_{k}}{\frac {x_{k}}}{x_{i}}}}{x_}}}{\i_ma _{k}}}}}}}{\i}}오른쪽)^{{{{{\frac }}}}}}}}}}}}}}}}}}}}}}}^{{{{{{{{{{{prexfrcT}=\arg \max _{C}\sum _{i=1}^{\mu }w_{i}\log p_{{\mathcal {N}\왼쪽(\왼쪽){\frac {x_{i:\lambda }-m_{k}{\sigma _{k}\오른쪽 C\오른쪽)}$

${\displaystyle \mu \geq$ n$}$의 경우($$그렇지 $않은{\displaystyle }$ 경우$$C {\$displaystyle$C}은(는$$) 단수지만 실질적으로 동일한 가 μ< ${\displaystyle \mu <n})$에 대해 유지된다. 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 }$${\displaystyle C_{}}$ ${\displaystyle k_{}}$+ ${\displaystyle 1_{}}$ ${\$}은$($는) 위의 최대 우도 추정기다. 파생에 대한 자세한 내용은 공분산 행렬 추정을 참조하십시오.

표본 분포 공간의 자연 그라데이션 강하

아키모토 외 ^[4]연구진 및 글라스머러스 외 연구진은 ^[5]독립적으로 분포 매개변수의 업데이트가 예상 목적 함수 값 ${\displaystyle \mathrm{Ef}}$ $){\displaystyle Ef(x)}($최소화 예정)의 샘플링된 자연 경사 방향으로 하강하는 것과 유사하다는 것을 발견했으며, 여기서 샘플 배분에 따른 기대치가 취해진다. c ${\displaystyle {\sigma }_{}}$= ${\displaystyle 0}$ ${\displaystyle c_{\sigma }=0}$ 및$$ ${\displaystyle {c\mathrm{}}_{}}$ ${\displaystyle 1{}_{}}$= 0 ${\displaystyle c_{1}=0$ 즉 단계적 크기 제어 및 순위 1 업데이트 없이 CMA-ES는 NES(Natural Evolution Strategies)의 인스턴스화라고 볼 수 있다.^[4][5] 자연 경사도는 분포의 매개변수화와 무관하다. 표본 분포의 매개변수에 대해, ${\displaystyle \mathrm{Ef}}$( ${\displaystyle x}$) ${\displaystyle Ef(x)}$의 구배는 다음과 같이 표현할$$ 수 있다.

${\displaystyle {\progressed}{\displayla }_{\!\theta }E(f(x)\mid \theta )&=\nabla _{\!\theta }\int _{\mathb {R} ^{n}f(x)p(x)\,\mathrm {d}x\&=\int _{\mathb {R} ^{n}f(x)\nabla _{\\!\theta }p(x)\,\mathrm {d}x\&=\int _{\mathb {R} ^{n}f(x)p(x)\nabla _{\!\theta }\ln p(x)\\\mathrm {d} x\\&=\operatorname {E}(f(x)\nabla _{\!\theta }\ln p(x\mid \theta )\ended{aigned}}}$

여기서 $p{\displaystyle }$( ${\displaystyle x}$)${\displaystyle }$= ${\displaystyle p}$( x ${\displaystyle \mid }$ ${\displaystyle \theta }$)$$= p ($x)=p(x\mid \theta )}$는 매개 변수 벡터 $\theta {\displaystyle }${\$displaystyle \theta$}에 따라$$ 달라진다$.$ 이른바 점수 함수인 ∇ $\nabla {\displaystyle {\mathrm{}}_{}}$ ${\displaystyle \ln }$ ${\displaystyle \backslash }$ ${\displaystyle p}$(${\displaystyle \frac{x}{}}$)${\displaystyle }$=$∇$ ${\displaystyle \frac{}{}}$( ${\displaystyle \frac{x}{}}$ )$displaystyp \nabla$\$nabla$ \!$\theta }\ln p(x\mid \theta )={\frac {\fla _{\!$$\teta }p(x)}{p(x)}}}$은$($는) w.r.t의 상대적 민감도를 나타내며, 분포에 대해 기대치를 취한다. 이제 Fisher 정보 메트릭(확률 분포와 상대 엔트로피의 곡률 사이의 정보 거리 측정$)$을 $준수$하는 ${\displaystyle \mathrm{Ef}}$(${\displaystyle x}$ ${\displaystyle )}${\$displaystyle Ef(x)}$의 자연 경사가 판독된다.

${\displaystyle {\begin{aigned}{\tilde {\nabla }}\opername {E}(f(x)\mid \theta )&=F_}^{-1}\nabla _{\\\nabla!\theta }\operatorname {E}(f(x)\mid \theta )\end{aigned}}}$

여기서 피셔 정보 매트릭스 F ${\displaystyle {\theta }_{}}$ ${\$은(는p) -ln의 헤시안 기대값이며$$ 선택된 파라미터화와 무관하게 식을 렌더링한다. 이전의 동등성을 결합하여

${\displaystyle {\begin{aigned}{\tilde {\nabla }}\operatorname {E}(f(x)\mid \theta )&=F_{\1}^{-1}\operatorname {E}(f(x)\nabla _{\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\!\theta }\ln p(x\mid \theta )\&=\operatorname {E}(f(x)F_{\theta }^{-1}\nabla _{\\\\\\\!\theta }\ln p(x\mid \theta )\ended{aigned}}}$

몬테카를로(Monte Carlo)의 근사치는 다음의 표본에 대한 평균을 취한다.

${\displaystyle {\tilde {\nabla }{\widehat{E}_{\theta }(f):=-\sum _{i=1}^{\lambda }\overbrace {w_{i}} ^{\!\!\!{\text{weight}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!\!}\언더브레이스 {F_{\theta }^{-1}\nabla _{\!\theta }\ln p(x_{i:\lambda }\mid \theta )} _{\!\!\!\!\!{\text{{direction from }}x_{i:\}da }\!\!\\}\cHB {\text{{w_{i}=-f(x_{i:\ida }}/\cHBDA }}$

여기서 위의 $표기법$ i :${\displaystyle \lambda }$ ${\displaystyle i:\lambda }$이(가) 사용되므로 w ${\displaystyle i_{}}$ ${\$는 단조롭게 $i{\displaystyle }$ ${\displaysty i}$에서 감소한다$.$

올리비에 외 ^[6]연구진은 마침내 CMA-ES에 정의된 바와 같이 ${\displaystyle {보다}_{}}$ 견고한 중량 w${\$에 대한 엄격한 파생법을 발견했다. (중량은 >의 경우 0인 경우가 많다.) $그것들$은 고정된 ${\displaystyle \mathrm{단조}}$로운 감소 ${\displaystyle \mathrm{변환}}$으로 구성된${\displaystyle }$f ( X${\displaystyle }$)${\displaystyle }$, ${\displaystyle X}$~ p$$ . ${\displaystyle \theta }$ ) {\$displaystyle f(X), X\sim$ p$(.$ \$theta )}$의 CDF에 대한 일관성 있는 추정기로 공식화된다$.$ $이$ ${\displaystyle {값}_{}}$은${\displaysty$ w} 입니다.

${\displaystyle w_{i}=w\left({\frac {{\mathsf {rank}(f(x_{i:\\da })-1/2}}{\messda }}오른쪽)}$

따라서 알고리즘이 특정 $f{\displaystyle }$ ${\displaystyle f}$ - 값에$$ 무감각하게 된다. 좀 더 간결하게, $f{\displaystyle }$ ${\displaystyle f}$ 그 자체$$ 대신$$ $f{\displaystyle }$ ${\displaystyle f}$의 CDF 추정기를 사용하면 알고리즘은 $f{\displaystyle }$ ${\displaystyle f$} -값의$$ 순위에만 의존할 뿐 기본 분포에는 의존하지 않는다. 그것은 알고리즘을 단조로운 $f{\displaystyle }$ ${\displaystyle f}$ -변환에$$ 불변하게 한다. 내버려두다

${\displaystyle \teta =[m_{k}^{T}\operatorname {vec}(C_{k})^{{{}}^{T}\sigma _{k}^{T}\in \mathb {R} ^{n+n^{2}+1}$

such that ${\displaystyle p(\cdot \mid \theta )}$ is the density of the multivariate 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 ${\displaystyl$$e \sigma _{k}}$ 고정$$

${\displaystyle F_{k}\theta \sigma _{k}^{-1}=\왼쪽[{\begin{array}}\sigma _{k}{c_{2}C_{k}}\otimes C_{k}\end}}}}}}:{k}}}}}\end{array\rigreight]}}}}}}}}}}}}}}}}}}}오른쪽]}}}}}}}}$

그리고 위하여

${\displaystyle \ln p(x\mid \theta )=\ln p(x\mid m_{k},\sigma _{k}^{k}}=-{\frac {1}{1}{1}{1}{1}:{1}:{k}^{l}}}}}^{n.T}\sigma _{k}^{-2}C_{k}^{-1}(x-m_{k})-{\frac {1}{2}}\ln \det(2\pi \sigma _{k}^{2}C_{k}}}}}}}$

몇 가지 계산 결과 CMA-ES의 업데이트 내용은^[4]