GA(유전자 알고리즘) - 시작

유전자 알고리즘이란 생물의 진화과정을 프로그램에 응용한 것입니다. 즉 진화의 과정인 변이와 자연선택을 흉내내는 프로그램기법입니다.
이를테면, 장애물을 피해 움직여야 하는 자동차를 상상해 봅시다.

1. 초기상태
다음과 같은 10대의 자동차를 만들었습니다. 각각의 자동차들은 장애물의 위치에 따라 다음 표와 같은 행동을 합니다.

차량	왼쪽장애물	앞쪽장애물	오른쪽장애물
가	직진	직진	오른쪽이동
나	왼쪽이동	직진	왼쪽이동
다	왼쪽이동	직진	오른쪽이동
라	오른쪽이동	직진	직진
마	왼쪽이동	왼쪽이동	오른쪽이동
...	...	...	...

2. 자연선택
그 다음에는 이 차들을 실제 장애물이 있는 도로에서 달리게 합니다. 물론 저들중 제대로 도로를 통과하는 차들은 없을 것입니다. (가)의 경우 오른쪽이나 정면에 장애물이 나타난다면 그대로 장애물을 들이받을 테니까 말입니다. 하지만 (다) 같은 경우 모든 장애물을 들이받겠지만 (가)는 왼쪽에 장애물이 나타난 경우, (나)는 왼쪽에 장애물이 나타난 경우는 제대로 피할 수 있습니다. 이런 식으로 각 자동차들의 성능을 점수를 매길 수 있습니다.

3. 재생산
2번 과정에서 점수를 가장 많이 얻은 자동차들을 모아 재생산을 합니다. 자연상태에서 한쌍의 어미가 유전자를 섞어 자손을 만들듯 높은 점수를 얻은 두 자동차의 특성을 섞어 새로운 자동차를 만드는 것입니다.
위의 경우 (가)와 (나)가 (그중에) 높은 점수를 얻어 재생산하게 되었다면

차량	왼쪽장애물	앞쪽장애물	오른쪽장애물
가	직진	직진	오른쪽이동
나	왼쪽이동	직진	왼쪽이동

으로부터

차량	왼쪽장애물	앞쪽장애물	오른쪽장애물
가'	직진	직진	왼쪽이동
나'	왼쪽이동	직진	오른쪽이동

인 새로운 두 자동차가 만들어집니다.
이때 (가')는 부모인 (가), (나)의 장점만을 받아 더 향상된 성능을 가지게 됩니다. 아, 물론 (나')는 오히려 (가)와 (나)의 단점만을 물려받아 성능이 더 나빠졌죠.

4. 자연선택
3번 단계에서 재생산된 자동차들을 가지고 다시한번 도로에서 테스트를 합니다.

5. 재생산
4의 결과를 가지고 다시 재생산을 합니다. 이 경우에 (가')는 확실히 (가)나 (나)보다 높은 점수를 받을 테니 다음번 재생산 대상이 될 수 있을 것입니다. 반면에 (나')는 점수가 형편없어질 테니 재생산대상이 될 수 없겠죠.

이런 식으로 반복해 나간다면 결국은 모든 경우에 장애물을 피할 수 있는 자동차가 나타날 것입니다. 이것이 유전자 알고리즘의 원리입니다.