GA - 자동차[3] 선택압

유전자 알고리즘 시작 부분에서 나온 것처럼, 유전자알고리즘은 '우수한 개체'를 재생산함으로써 진행됩니다. 여기서 '우수한 개체가 선택될 가능성'을 선택압이라고 합니다.

앞의 꼬마자동차 문제로 돌아가 보죠.
1000세대가 지나면서 가끔씩 1000점짜리 꼬마자동차가 생기긴 했습니다만 번번히 번식기회(?)를 놓치고 도태되고 말았습니다. 그 이유가 무엇일까요?

어느 순간 1000점짜리 꼬마자동차가 하나 탄생했습니다. 나머지 127대는 평균 950점대에 분포되어 있습니다. 꼬마자동차에서 재생산대상을 선택하기 위한 Roulette법에 의한다면, 점수의 총합은 950 * 127 + 1000 = 121650입니다. 그러므로 1000점짜리 꼬마자동차가 선택될 가능성은 1000/121650 = 0.00822 = 0.822%, 즉 1% 이하가 됩니다. 전체 128개 꼬마자동차 중에서 1% 이하라면 다른 꼬마자동차들과 거의 동일한 확률로 재생산된다고 봐야 하겠죠.
그러므로 1000점짜리 꼬마자동차를 늘리기 위해서는 선택압을 높일 필요가 있겠습니다.

선택압을 높이기 위해서는 재생산을 위한 부모를 찾는 방식을 바꾸어야 합니다. 여기서는 다음과 같은 두가지 방법을 시도해 봤습니다.

1. 순위법
순위법은 1위부터 차례로 순서를 매긴 후 등수에 따라 점수를 다르게 다시 주는 방법입니다. 여기서는 1위에게는 1000점, 2위에게는 950점, 3위에게는 900점 등으로 점수를 다시 계산했습니다.

function SelectParent()
.. sort car[] // 자동차 리스트를 소트(car[0]에 최대값이 들어가도록)

.. curscore := car[0].score
.. newscore := 1000;
.. order := 0;
.. for k := 0, 128 do
..... order := order + 1
..... if car[k].score == curscore then // 동점자일때는 같은점수
........ car[k].score := newscore
..... else
........ curscore := car[k].score
........ newscore = 1000 - order * 50;
........ car[k].score := newscore
..... end
.. end
.. // 이후는 Roulette법과 동일
end

순위법으로 선택압을 높여 유전자 알고리즘을 진행시킨 결과는 다음과 같습니다.
Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
......
Generation 48 MaxScore:990 MinScore:850 AverageScore:928
Generation 49 MaxScore:1000 MinScore:830 AverageScore:919
Generation 50 MaxScore:980 MinScore:820 AverageScore:926
Generation 51 MaxScore:990 MinScore:830 AverageScore:922
......
Generation 225 MaxScore:990 MinScore:810 AverageScore:925
Generation 226 MaxScore:1000 MinScore:820 AverageScore:925
Generation 227 MaxScore:1000 MinScore:810 AverageScore:923
Generation 228 MaxScore:990 MinScore:810 AverageScore:928
Generation 229 MaxScore:990 MinScore:800 AverageScore:925
Generation 230 MaxScore:1000 MinScore:810 AverageScore:928
Generation 231 MaxScore:1000 MinScore:800 AverageScore:945
Generation 232 MaxScore:1000 MinScore:800 AverageScore:969
Generation 233 MaxScore:1000 MinScore:940 AverageScore:974
......
Generation 680 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 681 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 682 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 683 MaxScore:1000 MinScore:900 AverageScore:999
Generation 684 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 685 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 686 MaxScore:1000 MinScore:1000 AverageScore:1000

최초의 만점 꼬마자동차(이것을 영웅이라 부릅시다^^)는 49세대만에 나타났다가 도태되었습니다. 그러나 이 경우 영웅은 많은 재생산기회를 가지므로 영웅의 유전자는 교차에 의해 분리되어 많은 다음세대의 꼬마자동차들에 흩어져 들어갑니다. 이 영웅유전자를 일부라도 가진 꼬마자동차들은 비교적 높은 점수를 얻을 수 있고 다음 재생산 대상이 될 수 있으므로 영웅유전자는 자꾸만 늘어납니다. 결국 영웅유전자끼리 만날 가능성은 점점 커지고(230세대) 마침내는 모든 꼬마자동차가 영웅유전자를 가질 수 있는 것이죠(600세대 이후). 이 이후 가끔씩 보이는 감점은 돌연변이에 의한 결과입니다.

2. 재계산법
재계산법은 꼬마자동차들 사이의 점수분포를 제한된 범위 안에 분포하도록 재계산하는 방식입니다. 룰렛방식 부모선택의 경우 1000세대 이후의 점수분포는 주로
Generation 1006 MaxScore:990 MinScore:840 AverageScore:938
Generation 1007 MaxScore:990 MinScore:850 AverageScore:935
Generation 1008 MaxScore:990 MinScore:860 AverageScore:937
Generation 1009 MaxScore:990 MinScore:810 AverageScore:938
Generation 1010 MaxScore:980 MinScore:870 AverageScore:933
810~990 사이였습니다. 이 범위를 꼬마자동차의 경우 10~1000 사이로 확대하여 재계산한 후 룰렛법과 같은 방식으로 계산합니다.

function SelectParent()
.. // 점수의 상한선과 하한선 찾기
.. minscore := 10000;
.. maxscore := 0;
.. for k := 0, 128 do
..... if minscore > car[k].score then
........ minscore := car[k].score
..... if car[k].score > maxscore then
........ maxscore := car[k].score
.. end

.. if maxscore != minscore then // 모든 자동차의 점수가 다 같은 경우는 적용할 수 없음
..... // max를 1000, min을 10으로 맞춤
..... newmax := 1000
..... newmin := 10
..... diff := maxscore - minscore; // 보정 전의 스코어 차이
..... for k := 0, 128 do
........ score := car[k].score
........ score := score - minscore
........ score := score * (newmax - newmin) / diff + newmin
........ car[k].score := score
..... end
.. end
.. // 이후는 Roulette법과 동일
end

재계산법으로 돌린 결과입니다.

Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
......
Generation 47 MaxScore:980 MinScore:700 AverageScore:898
Generation 48 MaxScore:990 MinScore:740 AverageScore:919
Generation 49 MaxScore:1000 MinScore:780 AverageScore:918
Generation 50 MaxScore:980 MinScore:820 AverageScore:926
Generation 51 MaxScore:990 MinScore:830 AverageScore:922
Generation 52 MaxScore:990 MinScore:850 AverageScore:928
......
Generation 492 MaxScore:990 MinScore:820 AverageScore:931
Generation 493 MaxScore:1000 MinScore:860 AverageScore:935
Generation 494 MaxScore:990 MinScore:870 AverageScore:937
Generation 495 MaxScore:990 MinScore:780 AverageScore:936
Generation 496 MaxScore:1000 MinScore:860 AverageScore:937
Generation 497 MaxScore:1000 MinScore:860 AverageScore:938
Generation 498 MaxScore:1000 MinScore:810 AverageScore:942
Generation 499 MaxScore:1000 MinScore:850 AverageScore:943

빠르고 늦고의 차이가 있을 뿐 전체적인 모습은 순위법일 경우와 동일합니다.


뱀발 :
그렇다면 유전자 알고리즘에서 선택압이 높을수록 좋은 것일까요? 그것은 아닙니다. 특히 초반에 지나치게 높은 선택압은 개체의 '다양성'을 해칠 수 있습니다. 말하자면 모든 꼬마자동차가 왼쪽에 있는 장애물만 못피하는데, 왼쪽 장애물을 피할 수 있는 유전자가 멸종해서 더이상의 개선이 불가능한 경우가 생길 수 있다는 것이죠.(물론 돌연변이가 있긴 하지만, 돌연변이에만 의존하는 유전자알고리즘은 비효율적입니다)

다양성에 대한 이야기는 다음 기회에 하도록 하겠습니다. 다만, 순위법이든 재계산법이든 후반에 선택압을 높이기 위해 사용할 수도 있지만 반대로 초반에 선택압을 줄여서 다양성을 유지하기 위해 사용할 수도 있습니다.