Warning: main(/home/gurugail/header.php) [function.main]: failed to open stream: No such file or directory in /home/gurugail/GeneticAlgo/page.html on line 23
Warning: main(/home/gurugail/header.php) [function.main]: failed to open stream: No such file or directory in /home/gurugail/GeneticAlgo/page.html on line 23
Warning: main() [function.include]: Failed opening '/home/gurugail/header.php' for inclusion (include_path='.:/usr/local/lib/php') in /home/gurugail/GeneticAlgo/page.html on line 23
|
커뮤니티 게시판 |
|
A.I Section
자연어 처리 |
|
GGOP
GGOP 소개
|
| 스키마 이론(Schema theorem) | |
|
작성 |
정현철 (lifegear@hanmail.net) |
|
작성 날짜 |
2002.01.08 |
|
개요 |
유전자 알고리즘의 수학적 배경에 대해 알아보자. |
|
|
|
|
내용 |
|
|
스키마 이론(schema theorem)
유전자 알고리즘의 세 연산자(operator)인 재생산(reproduction), 교배(crossover), 돌연변이(mutation)은 너무나 간단하다. 결국 n개의 문자열(strings, 개체)로 구성되어 있는 개체군(population)에서 적합 함수(fitness function)에 따라 몇 개의 개체를 선택하고, 몇 개의 부분 문자열을 바꿈으로써 교배를 시키고, 확률에 따라서 돌연변이를 발생함으로써 환경에 진화하는 것이다. 간단하지만 수학적 근거가 없었다면 끝났다면, 아마도 유전자 알고리즘이 이처럼 유용한 알고리즘이 되지는 못하였을 것이다. 위의 방법론은 누구나가 제시할 수 있지만, 수학적 근거를 제시하기는 쉽지만은 않다.
이런 점에서 스키마 이론은 유전자 알고리즘의 수학적 배경을 제시한다는 점에서 유전자 알고리즘의 근본되는 이론이라 할 수 있다. 원서(참조)에서는 스키마 이론을 'The fundamental theorem'이라고 말하고 있다. 먼저 스키마가 무엇인지를 언급하고, 그 스키마가 환경에 적응하는 정도를 제시함으로써, 그 스키마에 속하는 개체들의 적응력(?)도 그 스키마의 적응력과 결국 같은 것이기 때문에, 유전자 알고리즘이 무작위 탐색과는 다르다라는 것을 말하고자 한다.
f(x) = x2이라는 환경에서 아래와 같은 개체군이 존재한다고 가정하자.
01101
11000
01000
10011
이 예제에서는 0**** 보다는 1**** (* = 0 or 1)의 형태를 띠는 개체들이 더 높은 적합 함수값을 가진다. 일반적으로 환경을 모르더라도 개체들의 유전자 구성에 따른 일정한 법칙이나 배열규칙에 따라 적합 함수값이 비슷한 값들을 알 수 있다. 다시 말해, 개체의 특정한 유전자 배열 규칙이 개체의 우수성을 지니게 하는 하는 것이다. 스키마는 0****, 또는 1****처럼 표현한 것을 말하고 스키마의 복수가 스키마타이다.
0**** = 01101, 01000
1**** = 11000, 10011
을 각각 표현하는 것이다. 예제처럼 개체군내에서 부분 개체 집단의 일반적 적합성을 표현하는 데 있어 *(0 or 1) 이란 기호를 사용하여 스키마타(schemata)를 사용한다. 스키마타의 적합 함수값은 그 스키마타로 표현되는 개체들의 평균 적합함수값으로 표현된다.
개체군에 대단히 많은 개체들이 존재한다고 가정하자. 각각의 개체들은 유전자 알고리즘의 연산자에 따라 선택되고, 교배되고, 돌연변이 하면서 적응을 하겠지만, 겉으로 드러나지 않은 어떤 법칙에 따라 유전자 배열이 주어진 개체들만이 적응을 하게 되고, 그 드러나지 않는 공통적 법칙이 스키마타로 표현이 될지도 모른다. 스키마타는 개체들의 부분군을 대표하며, 또한 개체들의 병렬적 처리라고 생각하면 된다. 이해가 되었으리라 생각되지만 또 하나의 인간군을 예를 들어보자. 스키마타는 집단의 대표자라고 할 수 있다. 집단의 대표자는 그 집단의 평균적 우수성을 지니고 있다고 가정하자. 집단 A와 집단 B가 있을 경우, 집단 A의 대표자가 집단 B의 대표자보다 우수하면 집단 A는 적응하고, 집단 B는 도퇴하는 것이다. 각각의 개체 각각의 적합성보다는 집단 대표자의 적합성을 보고 그 개체들의 적합성을 추측하는 것이다. 그만큼 처리속도(적응하는 데 소요되는 시간)가 빨라 질 수 있다.
스키마타를 이용한 환경에 대한 개체 적응은
[1] 처리 속도를 올릴 수 있지만
[2] 반면, 열등 부분
집합에 속해있는 우수 개체를 도퇴시킬 수 있다는 부작용(side effect)도 존재한다.
Order, Length의 개념
먼저 정의부터 확인해보자. order라는 것을 우리말로 번역하면 이상할 것 같아 원어 그대로 사용한다. 스키마 H에 대하여 order와 definig length의 정의는 아래와 같다.
|
정의 |
표기 |
설명 |
|
order |
ο(H) |
H의 유전자 구성에서 고정된 위치의 갯수 |
|
length |
δ(H) |
H의 고정된 위치에서 처음과 끝의 거리 |
예를 들어, 스키마 H = 011*1** 인 경우 ο(H) = 4, δ(H)= 5-1 = 4이다.
위와 같은 order와 length는 스키마에서 어떤 의미를 지니고 있는 것인가? 우선
'스키마타가 생존한다'라는 의미부터 정확히 알아야 될 것 같다. 특정 스키마 H가
교배나 돌연변이를 하여도 그 스키마가 생존한다는 의미는 소속집단(?)이 바뀌지
않는다는 말로 이해하면 될 것이다. 아래 그림을 보자.
그림. 스키마(schema) 생존의 의미
그림에서 스키마 H1과 H2 가 개체 A와 교배(crossover)를 하였다고 가정하면, 교배의 결과 스키마 H1C는 H1의 배열 규칙을 벗어나게 되고 H2C는 H2의 규칙에서 벗어나지 않고 다만 좀 더 한정적인 스키마가 될 뿐이다. 생존의 의미는 바로 규칙에서 벗어나지 않음을 의미한다.
그럼 스키마가 생존할 확률(survival probability, SP)은 어떻게 표현될 수 있을까? 바로 order와 length가 밀접한 관계가 있다. length가 짧을수록 그만큼 교배후에도 스키마가 생존할 확률이 크고, order가 작을수록 돌연변이 이후에도 스키마가 생존할 확률이 크다. 즉,
SP(H) ∝ (1 - c1 * ο(H) - c2 * δ(H))
단, c1 = f(pc, t) , c2 = f(pm),
pc : prob. of crossover, pm : prob. of mutation,
t : total length of schema (ex. 0**011 = 6)
위의 개념을 바탕으로 스키마 이론(schema theorem)을 적어보면
- Schema theorem is fundamental theorem
와 같다. 위의 식을 풀어쓰면, '주어진 환경에 적응하는 스키마는 기하급수적으로 증가하며, length가 짧을수록, order가 작을수록 더 빠르게 증가한다.' 라는 것을 말한다. 물론 적응하지 못하는 스키마는 기하급수적으로 감소한다라는 것도 뜻한다. 쉽게 말하면, 유전자 알고리즘의 탐색 능력은 단순한 무작위 탐색과는 비교가 안된다라는 것을 수학적으로 증명한 이론이 스키마 이론(schema theorem)이다.
|
참조 |
|
|
Genetic Algorithms in Search, Optimization & Machine Learning by David E.
Goldberg, ISBN 0-201-15767-5
|
Downloads |
|
|
|
Reference |
|
|
||
|
|
||
|
