이부분은 자세한 알고리즘은 생략하겠습니다. 단지 먼저 1000점을 주고, 임의로 만들어진 도로를 앞에서 설계한 유전자에 따라 일정거리(100칸) 이동시키면서 장애물을 들이받을 때마다 10점씩 감점시키는 것입니다. 다만 만약 앞 3칸이 다 장애물로 채워진 경우, 자동차는 장애물을 들이받을 수밖에 없기에 이런 장애물은 미리 제거하였습니다.
4. 재생산할 꼬마자동차 찾기
높은 점수를 받은 꼬마자동차를 찾아 재생산해야 '더 우수한 꼬마자동차'가 만들어질 수 있습니다. 재생산할 꼬마자동차를 찾는 가장 기본적인 방법은 룰렛법입니다. 룰렛법에 의하면 각자의 꼬마자동차가 선택될 확률은 그 꼬마자동차의 점수와 비례합니다.
function SelectParent()
.. // 모든 꼬마자동차의 점수 합 계산
.. totalscore := 0
.. for i := 0, 128 do
..... totalscore := totalscore + car[i].score
.. end
.. // 점수비율로 선택
.. rnd := Random(0:totalscore - 1)
.. for i := 0, 128 do
..... if car[i].score > rnd then
........ return car[i]
..... end
..... rnd := rnd - car[i].score
.. end
.. error Not Selected
end
5. 교차
선택된 두 꼬마자동차를 복제하는 것만으로는 더 우수한 꼬마자동차를 얻을 수 없습니다. 꼬마자동차의 유전자를 섞어야 선택된 두 부모의 장점을 이어받은 꼬마자동차를 얻을수 있죠.실제 생물계에서도 오른쪽 그림과 같이 DNA가닥의 교차가 일어납니다.
여기서는 가장 간단한 1점교차를 사용해 유전자를 혼합하기로 하겠습니다. 즉, 임의의 한 점을 골라 그 점을 중심으로 유전자를 바꾸는 것입니다.
이를테면
A : 02101001
B : 11022120
였던 유전자가 3번 위치에서 교차가 일어났을 경우
A : 11001001
B : 02122120
가 되는 것입니다.
procedure CrossOver(Car A, car B)
.. // 교차가 일어날 위치 결정
.. crosspoint = Random(1, 7)
.. // 실제 교차
.. for k = 0, crosspoint do
..... tmp = A.gene[k]
..... A.gene[k] = B.gene[k]
..... B.gene[k] = tmp
.. end
end
한편 교차에는 위와 같은 일점교차뿐 아니라 2점교차 및 n점교차도 존재합니다. n점교차란 n개의 점을 선택해 자른 후 각각의 조각을 서로 바꾸는 교차입니다.
다음 유전자를
A : 02101001
B : 11022120
다음 유전 2, 5, 7점에서 3점교차를 한다면
A : 11101121
B : 02022000
와 같은 두 유전자가 만들어집니다.
마지막으로 랜덤교차는, 각각의 유전자 하나하나마다 일정확률을 적용시켜 교환할지 말지를 결정하는 교차방법입니다.
A : 02101001
B : 11022120
이것을 랜덤교차시킨다면
A : 11121021
B : 02002100
같이 보다 많이 뒤섞이게 됩니다.
6. 돌연변이
돌연변이는 임의의 비트를 전혀 다른 값으로 바꾸어버림으로써 새로운 정보를 만들고 유전자의 다양성을 증가시키기 위한 기본적인 방법입니다.
돌연변이 없이는 완전히 새로운 정보를 만들어낼 수도 없습니다(이 꼬마자동차는 처음 만들었을때 모든 유전자가 '직진'으로만 채워져 있기에 돌연변이 없이는 옆으로 이동이 불가능하죠). 그러나 돌연변이는 자칫하면 이미 잘 만들어진 유전자를 흐트러뜨릴 수도 있습니다(장애물을 잘 피해가던 꼬마자동차가 돌연변이에 의해 장애물을 들이받을 수도 있습니다). 그러므로 유전자알고리즘에서는, 돌연변이를 적용하더라도그 비율은 매우 낮게 적용합니다.
이 꼬마자동차의 경우에는 각 유전자 비트가 0.1%확률로 돌연변이를 일으키도록 설정했습니다.
procedure Mutantation(Car a)
.. for k = 0, 8 do
..... if Random(0, 999) == 0 then
........ a.gene[k] := Random(0, 2)
..... end
.. end
end
이렇게 새롭게 만든 128개의 꼬마자동차들을 원래의 배열로 옮기면 한 세대가 끝납니다. 이 새로운 세대를 대상으로 적응도테스트를 반복하면 점차 적응성이 높아지는 모습을 볼 수 있습니다.
다음은 실제로 유전자알고리즘을 돌린 결과입니다. 각 세대당 최고, 최저, 평균점수를 표시했습니다.
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 6 MaxScore:900 MinScore:710 AverageScore:804
............
Generation 999 MaxScore:1000 MinScore:830 AverageScore:935
Generation 1000 MaxScore:1000 MinScore:790 AverageScore:930
Generation 1001 MaxScore:980 MinScore:830 AverageScore:934
Generation 1002 MaxScore:990 MinScore:870 AverageScore:935
Generation 1003 MaxScore:990 MinScore:850 AverageScore:939
Generation 1004 MaxScore:1000 MinScore:840 AverageScore:935
Generation 1005 MaxScore:990 MinScore:840 AverageScore:934
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
Generation 1011 MaxScore:1000 MinScore:860 AverageScore:935
Generation 1012 MaxScore:990 MinScore:850 AverageScore:935
Generation 1013 MaxScore:980 MinScore:860 AverageScore:929
......
1000세대 이상 지난 상태입니다. 1000점짜리(모든 장애물을 완전하게 피한) 꼬마자동차가 나타났군요. 하지만 만점 꼬마자동차가 계속 유지되지 않습니다. 만점 꼬마자동차가 도태되었다가 다시 만들어지는 현상의 반복이군요.
다음번엔 이것을 한번 고쳐봅시다.
댓글 없음:
댓글 쓰기