Schema Theory

FrontPage|FindPage|TitleIndex|RecentChanges| UserPreferences P RSS
SchemaTheory: GeneticAlgorithm의 이론적 배경이 되는 Theory.

이 이론은 일반적으로 최적의 조건을 갖춘 유전자값에 근접한 유전자일수록 점수가 높다는 가정 하에 성립한다. 점수가 높은 유전자일수록 살아남을 확률이 높기 때문에 GeneticAlgorithm 안에서의 유전자 풀은 결국 (통계적으로) 최적치에 수렴하게 된다.

GA-deceptive problem

SchemaTheory의 맹점은 바로 최적의 유전자값에 근접한 유전자일수록 점수가 일반적으로 높지 않는 문제가 존재한다는 것이다.
유추적으로 말하자면 어느 행성에서 가장 낮은 지점이 A지점에 있으나 A지점은 아주 높은 산맥에 둘러싸여 있는, 그런 행성이 존재한다는 말이다. (See SimulatedAnnealing.)

그 행성 안에서 탐사조들은 가장 낮은 지점을 찾는 것이 목적이기 때문에 높은 산맥을 넘어가야 하는 A지점 방향으로는 가지 않게 되는 법이다.
게다가 설령 누군가가 A지점을 발견했다고 해도 과반수가 A지점에 있지 않는 이상 (GeneticAlgorithm의 특성상) 그 사실은 매장된다.

이런 행성, 혹은 최적화 문제를 GA를 속일 수 있는 문제라고 해서 GA-deceptive problem이라고 한다.

류기정은 이 문제가, 진화연산이란 방법의 본질적인 특성이며, 또한 재미있는 유추를 준다고 생각한다. 수학적 증명이 아닌이상, 우리는 그 어떤 해도 최적의 해인지 알 수 없다. 진화연산의 결과로 만들어진 우리 인간은, 말하자면 최적의 해가 아니다. 우리는 가능한 최적의 생명체가 아닌 셈이다. 국소해에 빠져버린 일단의 유전자풀로서 인간을 보는 점은 서글프기도 하지만 재미있다.

PuzzletChung은 Michalewicz의 책에서 GA-deceptive problem에 대한 부분을 읽고 슬픈 기분이 들었던 경험이 있다. 실제 세상에서도 과반수의 뜻이 아니라는 이유로 매장되어 버린 진보적인 아이디어들이 얼마나 많은가... 어차피 결국에는 긴 시행착오 끝에 그 쪽으로 수렴하게 될 것이면서...



"; if (isset($options[timer])) print $menu.$banner."
".$options[timer]->Write()."
"; else print $menu.$banner."
".$timer; ?> # # ?>