진화전략
Evolution strategy컴퓨터 과학에서 진화 전략(ES)은 진화의 아이디어를 바탕으로 한 최적화 기법이다. 진화 연산이나 인공 진화 방법론의 일반 등급에 속한다.
역사
'진화 전략' 최적화 기법은 1960년대 초반에 만들어졌고 1970년대 이후 인고 레첸베르크, 한스폴 슈웨펠, 그리고 그들의 동료들에 의해 더욱 발전했다.
방법들
진화 전략은 자연적인 문제 의존적 표현, 그리고 주로 돌연변이와 선택을 검색 운영자로 사용한다. 진화 알고리즘과 공통적으로 운용자는 루프 방식으로 적용된다. 고리의 반복을 세대라고 한다. 세대 순서는 종료 기준이 충족될 때까지 계속된다.
실제 값 검색 공간의 경우 정규 분포 랜덤 벡터를 추가하여 돌연변이를 수행한다. 단계 크기 또는 돌연변이 강도(즉, 정규 분포의 표준 편차)는 종종 자가 적응에 의해 제어된다(진화 창 참조). 기본 공분산 행렬에 의해 본질적으로 정의되는 각 좌표에 대한 개별 단계 크기 또는 좌표 간 상관관계는 실제로 자가 적응 또는 공분산 행렬 적응(CMA-ES)에 의해 제어된다. 진화하는 공분산 행렬을 사용하여 다변량 정규 분포에서 돌연변이 단계를 도출할 때, 이 적응된 행렬이 검색 경관의 역헤시안 행렬에 근접한 것으로 가정되었다. 이 가설은 2차 근사치에 의존하는 정적 모델에 대해 입증되었다.[1]
진화 전략에서 (환경) 선택은 결정론적이며 실제 피트니스 가치에 기초하지 않고 피트니스 순위에 기초해야 한다. 따라서 결과 알고리즘은 목표 함수의 단조적 변환에 대해 불변한다. 가장 간단한 진화 전략은 두 번째 크기의 모집단에서 작동한다: 현재 지점(부모)과 그 돌연변이의 결과. 돌연변이의 체력이 적어도 부모만큼 좋아야 다음 세대의 부모가 된다. 그렇지 않으면 돌연변이는 무시된다. 이것은 (1 + 1)-ES이다. 보다 일반적으로 λ 돌연변이를 발생시킬 수 있으며 (1 + ))-ES라고 하는 모체와 경쟁할 수 있다. (1, λ)-ES에서 최고의 돌연변이는 다음 세대의 부모가 되는 반면 현재의 부모는 항상 무시된다. 이러한 변종들 중 일부의 경우, ( 확률적 의미에서의) 선형 수렴의 증거가 단일한 객관적 함수에 대해 도출되었다.[2][3]
현대의 진화 전략의 파생상품은 흔히 μ 부모 모집단을 사용하고, (μ/μ+, μ)-ES라고 불리는 추가 연산자로 재조합한다. 이것은 그들이 지역적 최적지에 정착하는 것을 덜 어렵게 만든다.[4]
참고 항목
참조
- ^ Shir, O.M.; A. Yehudayoff (2020). "On the covariance-Hessian relation in evolution strategies". Theoretical Computer Science. Elsevier. 801: 157–174. arXiv:1806.03674. doi:10.1016/j.tcs.2019.09.002.
- ^ Auger, A. (2005). "Convergence results for the (1,λ)-SA-ES using the theory of φ-irreducible Markov chains". Theoretical Computer Science. Elsevier. 334 (1–3): 35–69. doi:10.1016/j.tcs.2004.11.017.
- ^ Jägersküpper, J. (2006). "How the (1+1) ES using isotropic mutations minimizes positive definite quadratic forms". Theoretical Computer Science. Elsevier. 361 (1): 38–56. doi:10.1016/j.tcs.2006.04.004.
- ^ Hansen, N.; S. Kern (2004). "Evaluating the CMA Evolution Strategy on Multimodal Test Functions". Parallel Problem Solving from Nature - PPSN VIII. Springer. pp. 282–291. doi:10.1007/978-3-540-30217-9_29.
참고 문헌 목록
- Ingo Rechenberg(1971년): Evolutions strategy – Optimierung Technischer Systeme nach Prinzipien der Biologicalischen Evolution(PhD 논문) Frommann-Holzboog(1973년)에 의해 다시 인쇄됨.
- 한스폴 슈웨펠(1974년): 오미슈 옵티미에룽 폰 컴퓨터-모델렌(PhD 논문). Birkhauser(1977년)에 의해 다시 인쇄됨.
- H.G.비어,H.P. 슈베펠 진화 전략: 포괄적인 도입. Journal Natural Computing, 1:1:3-52, 2002.
- 한스-조그 바이어: 진화론: 2001년 4월 27일 봄.
- 한스폴 슈웨펠: 진화 및 최적의 추구: 뉴욕: Wiley & Sons 1995.
- Ingo Rechenberg: Evolutions strategy'94. 슈투트가르트: Frommann-Holzboog 1994.
- J. 클록게터와 H. P. 슈베펠(1970). 2상 노즐 및 중공 코어 제트 실험. AEG-Forschungsinstitut. MDH Stostrahlrohr 프로젝트 그룹. 독일 베를린. 제11회 자석-유체역학 공학 측면에 관한 심포지엄의 진행, Caltech, Pasadena, Cal, 24.–26.3. 1970.
- M. 에메리히, O.M. Shir, H. Wang: Evolutholution Strategies. 내: 휴리스틱스 핸드북, 1-31. 스프링거 인터내셔널 퍼블리싱(2018).
