- 단순 유전 알고리즘에서 단속평형의 지속시간에 대한 연구
- ㆍ 저자명
- 오상엽,Oh. Sang-Yeop
- ㆍ 간행물명
- 정보과학회논문지. Journal of KIISE. 소프트웨어 및 응용
- ㆍ 권/호정보
- 2005년|32권 11호|pp.1059-1070 (12 pages)
- ㆍ 발행정보
- 한국정보과학회
- ㆍ 파일정보
- 정기간행물| PDF텍스트
- ㆍ 주제분야
- 기타
유전 알고리즘에서 개체군은 지역 최적치에 빠질 수 있지만 긴 지속시간이 지난 후에는 여기에서 빠져나을 수 있으며 이러한 현상을 단속평형 (punctuated equilibrium)이라고 한다. 자연계나 컴퓨터 생태계 (computational ecosystems) 에서 관찰되는 단속평형은 확산 방정식 (diffusion equation)으로 잘 설명된다. 본 연구에서는 단순 유전 알고리즘을 이론적으로 분석하여 개체군의 움직임이 확산 방정식으로 표현될 수 있다는 것을 보인다. 또한 적합도 (fitness) 함수를 단위화 (unitation) 함수로 국한하면 이 분석을 더 구체화하여 유전 알고리즘의 주요 변수들이 이 방정식에 나타나도록 할 수 있다. 이 경우 확산 방정식에 대한 이론적 결과를 이용하면 지역 최적치에서 빠져 나오기까지의 지속시간이 개체군의 크기, 1/(돌연변이 확률), 그리고 지역 최적치의 깊이에 대해 지수적으로 증가한다는 것을 알 수 있다. 이러한 이론적 결과는 이중안정 지형 (bistable landscapes)에서의 시뮬레이션 결과와 일치한다.
For genetic algorithms, the population may get stuck in a local optimum. The population can escape from this after a long duration. This phenomenon is called punctuated equilibrium. The punctuated equilibria observed in nature and computational ecosystems are known to be well described by diffusion equations. In this paper, simple genetic algorithms are theoretically analyzed to show that they can also be described by a diffusion equation. When fitness is the function of unitation, this analysis can be further refined to make the parameters of genetic algorithms appear in this equation. Using theoretical results on the diffusion equation, the duration of equilibrium is shown to be exponential of such parameters as population size, 1/(mutation probability), and potential barrier. This is corroborated by simulation results for bistable potential landscapes with one local optimum and one global optimum.