" /> 진화 전략 : Evolution Strategy

 

Evolution  Strategy

 

Google : 진화전략    Google : Evolution Strategy

진화전략 : 황희수 : 1963 년에 독일 베를린기술대학 (TUB) 의 두 학생이 공기저항을 최소화하는 물체의 형상을 찾기 위해 풍동 실험을 하였다. 기존의 경사법에 의한 탐색이 실패하였을 때, 두 학생 가운데 한명이었던 레켄베르그 (Ingo Rechenberg) 는 형상을 정의하는 파라메타를 돌연변이와 같이 랜덤하게 변화시킬 생각을 하였다. 이것이 바로 진화전략이 탄생하게 된 계기다. 1973 년에 레켄베르그는 2 개의 개체로 된 진화전략을 발표하였고 이를 다수의 개체로 확장할 것을 제안하였다.

진화전략을 발전시킨 또 다른 사람인 쉬베펠 (Hans Paul Schwefel) 은 1977 년에 진화전략과 수치 최적화라는 논문을 발표하였다. 진화전략은 목적함수를 해석적 형태로 만들 수 없어서 기존의 최적화 방법을 사용할 수 없었던 기술적인 최적화 문제를 해결하기 위해 고안되었다. 두개의 개체로 구성되는 초기의 (1 + 1) 진화전략에서는, 매 세대마다 하나의 부모 개체에 표준 정규분포를 이용한 돌연변이를 적용해서 부모보다 우수한 자식 개체가 발생하면, 이것으로 부모 개체를 대체한다.

이처럼 단순한 구조를 갖는 초기의 진화전략에 대해서는 돌연변이 양의 제어와 수렴속도와 같은 이론적인 연구가 수행되었다. 이 연구에 따르면, 모든 돌연변이 가운데 성공적인 돌연변이 비율은 1/5 이다. 이를 흔히 1/5 성공 규칙이라 부른다. 돌연변이만을 사용하는 초기의 진화전략은 μ 개의 부모 개체를 사용함으로써 재결합 과정을 포함할 수 있는 (μ + λ) 진화전략으로 발전하게 되었다. 돌연변이 체계와 그 크기를 제어하는 방식은 (1 + 1) 진화전략과 차이가 없다. 쉬베펠은 다수 개체를 갖는 진화전략을 (μ + λ) 진화전략과 (μ, λ) 진화전략으로 일반화시켰다. 여기서 μ 는 집단의 크기를 말하며 λ 는 매 세대에서 발생하는 자식 개체의 수이다.

이 일반화된 진화전략은 다수 개체로 구성된 집단이라는 개념을 도입함으로써 랜덤 교배, 돌연변이와 선택이라는 자연계진화 원리를 모방할 수 있게 되었다. 진화전략은 많은 시험 사례에서 반복적인 다른 방법에 비해 성공적임이 입증되엇다. 진화전략은 개체의 평가 방법 외에는 문제에 대한 정보를 거의 필요로 하지 않기 때문에, 거의 모든 종류의 최적화 문제에 적용될 수 있다. 진화전략은 선형 및 비선형 제약조건을 갖는 고차원, 멀티모달의 비선형 문제를 해결할 수 있다. 목적함수는 해석적 형태일 필요는 없으며, 시뮬레이션 결과가 목적함수로 사용될 수도 있다. 이는 제약조건의 경우도 마찬가지이다 .......

 진화전략과 유전알고리즘의 특성 비교

 

진화전략

유전알고리즘

표현방식

실수

보통 이진 문자열 (실수형도 가능)

자기-적응성

표준편차와 상호분산

없음

적합도

목적함수 값

비율 조정된 목적함수 값

돌연변이

유일한 연산자

보조 연산자

교배

없음

주요 연산자

선택

종의 수준에서 진화를 모방한 것으로 교배 과정이 없음.

확률적이며 보존성이 있음

 

진화전략 : 중앙대 인공생명 및 지능정보 시스템 연구실 : 진화전략(ES)은 자연계의 진화현상에 기반한 계산 모델로서 국소해가 많은 최적화 문제의 해를 구하는 것을 목적으로 Rechenberg와 Schwefel에 의하여 1960년대에 개발된 알고리즘이다. 주 연산자로는 돌연변이를 사용하고 가끔 교배를 사용하기도 한다 ........ ES의 각 개체는 (x,σ)와 같이 한쌍의 실수벡터로서 표현된다. 이것의 x는 탐색공간내의 위치 벡터이며 σ는 표준편차 벡터가 된다. 이때 돌연변이에 의한 다음 세대의 개체는 다음과 같이 표현된다.

단, N(0,σ)는 평균이, 0 표준편차가 σ인 가우스 분포를 따르는 임의의 난수이다. 여기서, σ의 원소가 모두 같을 때, 즉 σ = (σ,σ,…,σ)일 때를 특별히 identical problem 이라고 한다.

초기의 ES에는 하나의 개체로부터 집단의 탐색을 행하였다. 이런 경우 돌연변이에 의해 만들어진 자손(위 식의 xt+1)은 부모(xt) 보다 적합도가 좋게 될 때 부모로서 집단의 일원으로 채용하였다.(결국, 다음세대의 부모가 된다). 그 후 ES는 복수개체의 집단에 의한 탐색수법으로서 여러 가지 형태로 발전되어져 왔다 .....