자연 진화 전략

다음 시리즈의 일부
진화 알고리즘
인공발달성 인공생명체 세포진화 알고리즘 문화 알고리즘 미분진화 효과적인 피트니스 진화 연산 진화전략 가우스 적응 진화적 다중모드 최적화 입자 군집 최적화 메미틱 알고리즘 자연 진화 전략 신경진화 프로모터 기반 유전 알고리즘 나선 최적화 알고리즘 자체수정코드 다형 코드
유전 알고리즘
염색체 클론 선택 알고리즘 크로스오버 돌연변이 유전적 기억력 유전 퍼지 시스템 선택 플라이 알고리즘
유전자 프로그래밍
데카르트 유전 프로그래밍 선형유전자프로그래밍 문법적 진화 다중 표현식 프로그래밍 유전적 개선 스키마 유리스코 패리티 벤치마크
v t

이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 보다 정확한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2015년 3월) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

NES(Natural Evolution Strategy)는 블랙박스 문제에 대한 수치 최적화 알고리즘의 계열이다. 진화 전략과 유사하게, 그들은 더 기대되는 적합성을 향한 자연적인 구배를 따라 검색 분포의 (연속) 매개변수를 반복적으로 업데이트한다.

방법

일반적인 절차는 다음과 같다: 매개변수화된 검색 분포를 사용하여 검색 지점을 일괄적으로 생성하며, 각 지점에서 피트니스 기능을 평가한다. 분포의 매개변수(전략 매개변수 포함)를 사용하면 알고리즘이 적합성 함수의 (로컬) 구조를 적응적으로 캡처할 수 있다. 예를 들어 가우스 분포의 경우 평균과 공분산 행렬로 구성된다. 표본으로부터, NES는 더 높은 기대 적합성을 향한 매개변수의 검색 구배를 추정한다. 그런 다음 NES는 자연 그라데이션에 따라 그라데이션 상승 단계를 수행하는데, 이는 일반 그라데이션과 달리 업데이트의 불확실성(.r.t. 불확실성)을 리노믹스하는 두 번째 순서 방법이다. 이 단계는 진동, 조기 수렴 및 주어진 매개변수화에 따른 원치 않는 영향을 방지하기 때문에 중요하다. 정지 기준이 충족될 때까지 전체 과정이 반복된다.

NES 계열의 모든 구성원은 동일한 원칙에 따라 운영된다. 확률 분포의 유형과 사용된 구배 근사치 방법이 다르다. 서로 다른 검색 공간은 서로 다른 검색 분포를 필요로 한다. 예를 들어, 낮은 차원에서는 완전한 공분산 행렬을 모형화하는 것이 매우 유익할 수 있다. 반면에 높은 차원에서는 공분산을 대각선으로만 제한하는 것이 보다 확장 가능한 대안이다. 또한, 고도로 다중모드 검색 공간은 더 무거운 꼬리 분포의 혜택을 받을 수 있다(가우스와는 반대로, 카우치 같은). 자연 경사를 분석적으로 계산할 수 있는 분포와 표본에서 추정할 필요가 있는 더 일반적인 분포 사이에 마지막 구분이 발생한다.

그라데이션 검색

$\theta {\displaystyle }$ ${\displaystyle \theta}$은(는) 검색 분포 $\pi {\displaystyle }$( x $){\displaystyle \pi (x\,$\$theta$ $)}$ $및{\displaystyle }$ f$$${\displaystyle }$( ${\displaystyle x}$$){\displaystystyle$ $f$$($x$)}$의 매개변수를$$ 나타내도록$$ 한다$.$ 그런 다음, NES는 검색 분포에서 예상 적합성을 최대화하는 목표를 추구한다.

${\displaystyle J(\theta )=\operatorname {E} _{\theta }[f(x)]=\int f(x)\;\pi(x\, \theta )\;dx}$

경사 등반을 통하여 그라데이션은 다음과 같이 다시 쓸 수 있다.

${\displaystyle \nabla _{\theta }J(\theta )=\nabla _{\theta }\int f(x)\;\pi(x\, \theta )\;dx}$

${\displaystyle =\int f(x)\;\dxla _{\theta }\pi(x\, \\theta )\;dx}$

${\displaystyle =\int f(x)\;\dxla _{\theta }\pi(x\, \,\theta )\;{\pi(x\, \,\theta )}{\pi(x\, \,\theta )}$

${\displaystyle =\Big [}f(x)\;\nabla _{\theta }\log \pi(x\, \\theta ){\Big ]\;\pi(x\, \,\theta )\;dx}$

${\displaystyle =\operatorname {E} _{\theta }왼쪽[f(x)\;\nabla _{\theta }\log \pi(x\, \theta )\right]}$

즉, $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle f(x)}$의 기대값은 $x{\displaystyle }$ ${\displaystyle x}$에서 로그-파생물의 배수를$$ 곱한 값이다$.$ 실제로 유한 $수의{\displaystyle }$ finite ${\displaystyle \lambda }$ 샘플에$$ 기반한 몬테카를로 근사치를 사용할 수 있다.

${\displaystyle \nabla _{\theta }J(\theta )\approx {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }f(x_{k})\;\nabla _{\theta }\log \pi (x_{k}\, \,\theta )}$.

마지막으로, 검색 분포의 매개변수를 반복적으로 업데이트할 수 있다.

$\displaystyle \theta \leftarrow \theta +\eta \nabla _{\theta }J(\theta )}$

자연 그라데이션 상승

NES는 업데이트에 일반 확률적 그라데이션 대신 자연적인 그라데이션에 따르며, 다음과 같은 일반(바닐라) 그라데이션에 비해 많은 장점을 가지고 있는 것으로 나타났다.

• 그라데이션 방향이 검색 분포의 매개 변수화와 무관함
• 업데이트 크기는 불확실성에 기반하여 자동으로 조정되며, 고지와 능선의 수렴 속도가 빨라진다.

따라서 NES 업데이트는

${\displaystyle \theta }$ ${\displaystyle \leftarrow }$ +${\displaystyle \eta }$ ${\displaystyle {}^{}}$- ${\displaystyle 1^{}{\mathrm{}}_{}}$∇ ${\displaystyle {}_{}}$ (${\displaystyle }$) )${\displaystyle }$\$displaystyle \theta \leftarrow \theta +\eta \mathbf {F}$^{-1$}\nabla _{\theta }J(\ta$ $)\},$

여기서 $F{\displaystyle \mathbf{}}$ ${\$은$($는) Fisher 정보 매트릭스다. 때때로 피셔 매트릭스는 정확하게 계산될 수 있으며, 그렇지 않으면 샘플로부터 추정되며, 로그-파생성 atives ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$(${\displaystyle x}$ \$){\displaystyle \nabla _{\theta }\log \pi ($x$\teta )}$를 재사용한다$.$

피트니스 쉐이핑

NES는 순위 기반 피트니스 쉐이핑을 활용하여 알고리즘을 보다 견고하게 하고, 단조롭게 증가하는 피트니스 기능의 변환 하에서 불변성을 구현한다. 이를 위해 모집단의 적합성은 $u{\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}\ge }$ u u u ${\displaystyle {}_{}}$ u u ${\displaystyle {\lambda }_{}}$ { { ${\$${\lambda$$\}\}\}\}\}\}\}\}\}\}\}\}$ let ${\displaystyle x_{}}$ i ${\$ individual$$ individual individual individual individual individual i^th individual individual i individual individual individual $individual$ individual i i i u u individual? 피트니스를 유틸리티로 대체하면 구배 추정치는

${\displaystyle \nabla _{\theta }J(\theta )=\sum _{k=1}^{\lambda }u_{k}\;\nabla _{\theta }\log \pi (x_{k}\, \,\theta )}$.

효용 함수의 선택은 알고리즘의 자유 매개변수다.

가성음

input: ${\displaystyle f,\;\;\theta _{init}}$  1  repeat     2     for  ${\displaystyle k=1\ldots \lambda }$ do // λ is the population size         3         draw sample ${\displaystyle x_{k}\sim \pi (\cdot  \theta )}$         4         evaluate fitness ${\di$$splaystyle f(x_{k})}$         5         calculate log-derivatives ${\displaystyle \nabla _{\theta }\log \pi (x_{k} \theta )}$         6     end     7     assign the utilities ${\displaystyle u_{k}}$ // based on rank     8     estimate the gradient ${\displaystyle {\mathrm{\nabla }}_{\theta }J\leftarrow \frac{1}{\lambda }\sum _{k=1}^{\lambda }{u}_k}$${\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k} \theta )}$     9     estimate ${\displaystyle \mathbf {F} \leftarrow {$$\frac {1}{\lambda }}\sum _{k=1}^{\lambda }\nabla _{\theta }\log \pi (x_{k} \theta )\nabla _{\theta }\log \pi (x_{k} \theta )^{\top }}$ // or compute it exactly      10    update parameters ${\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J}$ // η is the learning rate  11 정지 기준이 충족될 때까지 

참고 항목

• 진화 연산
• 공분산 행렬 적응 진화 전략(CMA-ES)

참고 문헌 목록

• D. Wierstra, T. Schaul, J. Peters 및 J. Schmidhuber(2008). 자연 진화 전략. IEEE CEC(Involutional Computing) 회의.
• Y. Sun, D. Wierstra, T. Schaul 및 J. Schmidhuber(2009). 자연 그라데이션(Natural Gradient)을 이용한 확률적 탐색. 기계학습 국제회의(ICML).
• T. 글라스머, T. Schaul, Y. Sun, D. 비에스트라와 J. 슈미두버(2010년). 지수 자연 진화 전략. 유전자 및 진화 연산 회의(GECCO).
• T. Schaul, T. Glasmurs and J. Schmidhuber(2011년). 자연 진화 전략을 위한 높은 치수와 무거운 꼬리. 유전자 및 진화 연산 회의(GECCO).
• T. Schaul(2012). 자연 진화 전략은 구체 기능에 수렴한다. 유전자 및 진화 연산 회의(GECCO).

외부 링크

• 여러 언어로 된 NES 구현 모음