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 소개
|
| 재생산(reproduction) | |
|
작성 |
정현철 (lifegear@hanmail.net) |
|
작성 날짜 |
2001.12.4 |
|
개요 |
유전자 알고리즘에서 개체의 재생산(reproduction)에 대해 알아보자. |
|
|
|
유전자 알고리즘은 기본적으로 세 가지의 연산자(operator)로 구성된다.
[1] 재생산(reproduction)
[2] 교배(Crossover)
[3] 돌연변이(Mutation)
이번 내용에서는 재생산이라는 연산자(operator)에 대해 알아보자. 근데 operator를 연산자라고 번역하니까 좀 이상하군요.(^_^)
|
내용 |
|
|
개요
유전자 알고리즘에서 재생산(reproduction)이란 적합함수(fitness function)에 따라서 개체들을 복사하는 과정이다. 쉽게 말해서 개체들이 속해 있는 군에서 잘난 넘(nom?)은 다음 세대를 더 많이 생산할 수 있는 기회를 주고, 물론 못난 놈은 자기와 닮은 개체를 생산할 수가 없어 그 형질이 다음 세대에 전달되지 않는다.
그렇다면 과연, 우수 형질의 개체를 어느 정도 개체를 생산할 수 있고, 열등 형질은 무조건 없어져야 하는가? 그렇지만은 않다. 왜냐면 열등 형질도 부분적으로는 우수 형질의 기질을 가지고 있기 때문이다. 따라서 유전자 알고리즘에서는 어떤 개체에게 어느 정도의 우수성을 부여하고 어떤 방식으로 재생산이 행해지느냐는 중요한 요소이다. 무작정 우수 형질의 개체를 재생산하다보면 전체 해(global point)를 찾지 못할 가능성도 커진다.
결론적으로 우수 형질의 개체 생산과 열등 형질의 개체 생산비율을 적절히 설정할 필요가 있다. 이를 실현하는 데 있어 유전자 알고리즘에서 기본적으로 roulette wheel이라는 확률개념을 사용한다. 지금은 많이 사라졌지만, roulette wheel을 돌려서 뽑기하는 장사를 기억할 것이다. 원판(roulette wheel을 원판이라 번역, ^_^)에서 할당된 영역이 넓으면 그만큼 걸릴 확률이 많은 것이다. 우수 형질은 그만큼 원판에서의 면적 할당이 넓게 함으로써 다음 세대의 개체 생산의 가능성을 크게 하는 것이다. 아래 그림을 보면 이해가 될 것이다. 군(pool)에 개체들이 있고, 그 개체들은 우수 정도에 따라 영역을 할당받는다. 우수 개체는 아래 그림에서 (2) 영역을 할당받을 것이고, 열등 형질은 (1) 영역을 할당받을 것이다. 이제 재생산의 남은 과정은 원판을 돌리고 화살만 쏘면 되는 것이다. 걸리면 살아남는 개체가 되는 것이다. 냉혹함이 숨겨져 있는 알고리즘이다.
그림. 유전자 알고리즘에서의 재생산(Reproduction)
예제(example)
f(x) = x2이라는 환경에서 살아가는 개체가 시간 t일 때
01101
11000
01000
10011
와 같이 네 개체만이 있다면 개체들의 적합도(fitness)와 전체에 대한 우수성의 비율을 아래 표에 나타내었다.
|
No. |
개체 |
Fitness |
% of Total |
|
1 |
01101 |
169 |
14.4 |
|
2 |
11000 |
576 |
49.2 |
|
3 |
01000 |
64 |
5.5 |
|
4 |
10011 |
361 |
30.9 |
|
Total |
|
1170 |
100.0 |
표. f(x) = x2에서의 개체와 적합함수(fitness function)
원판위에 적합함수(fitness function)에 따라 다음 세대에서의 생존 가능성을 그리면 앞의 원판 그림이다. No. 2라는 개체가 f(x) = x2이라는 환경에서는 가장 잘 적응되고 원판에서도 가장 넓은 영역을 차지하고 있다. 따라서 다음 세대를 재생산(reproduction) 하기 위해 화살을 네 번 쏜다면, No. 2라는 개체는 살아남아서 다음 단계인 교배(crossover)를 할 가능성이 가장 높다.
이상으로 roulette wheel이라는 확률 기반의 재생산(reporduction) 방법에 대해 알아보았다. 다음은 교배(crossover)에 대해 알아볼 차례다. 교배는 실제 재생산된 개체들끼리의 연산으로 좀 더 나은 개체를 발생시키고자 하는 데 목적이 있다. 유전자 알고리즘은 재생산(reproduction), 교배(crossover), 돌연변이(mutation)에 대해서 확실히 알면 그 다음은 그것들의 응용이다.
|
참조 |
|
|
Genetic Algorithms in Search, Optimization & Machine Learning by David E.
Goldberg, ISBN 0-201-15767-5
|
Downloads |
|
|
|
Reference |
|
|
||
|
|
||
|
