GA - CNNC를 실은 꼬마자동차[3] - 결과

11. 결과 1
우선 앞과 같은 방식으로 돌길과 꼬마자동차를 공진화시켰습니다. 100세대 후 최고 적응도를 얻은 꼬마자동차의 성적표입니다.

Generation:99 MaxScore:-2440 Collision:254 MinScore:-2561 Move:264

최고성적의 꼬마자동차도 64개의 돌길을 지나며 264(평균 4.125)칸만을 이동할 수 있었습니다. 그동안 254번이나 장애물과 충돌했군요.

꼬마자동차와 함께 진화된 돌길을 살펴보겠습니다. 다음은 돌길의 앞부분만을 그린 것입니다.

오른쪽 끝의 푸른 점이 꼬마자동차의 출발점입니다. 저 위치로부터 꼬마자동차는 앞쪽, 왼쪽앞, 오른쪽앞으로 이동할 수 있습니다. 그런데 보시다시피 자동차가 갈 수 있는 곳은 모두 장애물로 덮여 있습니다. 꼬마자동차가 장애물을 통과할때 기름 5씩 들어가므로 4칸만 움직이면 기름이 떨어져 버리죠.
이런 돌길을 통과할 수 있는 꼬마자동차가 진화될 수 없습니다. 돌길에 대해 약간의 제한이 필요하겠군요.

12. 결과 2
꼬마자동차는 앞의 세 칸들 중 하나로 이동할 수 있습니다. 앞의 세 칸 중 하나가 장애물이 아니면 앞으로 이동할 수 있는 것입니다. 그러므로 돌길을 만들때 장애물 세개가 연이어 놓이는 것을 방지했습니다.
그 결과는 다음과 같습니다.

Generation:99 MaxScore:12798 Collision:0 MinScore:-2561 Move:1280

확실히 아까보다는 성적이 좋아졌군요. 그런데 64개 돌길을 지나면서 1280(평균 20)칸을 움직였습니다. 결국 초기 가지고 있던 기름만 다 사용한 것이군요. 이유가 무엇일까요.


위에서 보다시피 꼬마자동차의 앞을 모두 막진 않았지만, 기름통으로 갈 수 있는 길은 철저히 막혀 있습니다. 최소한 한개의 장애물을 밟지 않고는 기름을 얻을 수 없는 구조가 되어 버렸습니다.
조금 더 돌길에 제한이 필요하겠군요.

13. 결과 3
이번에는 각 연료통으로 갈 수 있는 길을 확보해 주었습니다. 100턴 이후 꼬마자동차의 성적표입니다.

Generation:99 MaxScore:63998 Collision:0 MinScore:-2551 Move:6400

보시다시피 길이 100인 돌길 64개, 6400칸을 장애물과 충돌 없이 움직이는데 성공했습니다.

100턴이 지날 때까지 각 세대 최고 적응도의 꼬마자동차가 장애물과 충돌한 횟수를 그래프로 그렸습니다. 이것이 공진화의 전형적인 패턴입니다.
처음 돌길의 진화로 꼬마자동차들이 피할수 없는 장애물패턴을 만듧니다(충돌횟수가 증가합니다). 그 후에는 꼬마자동차의 진화로 그 장애물을 피합니다(충돌횟수가 감소합니다). 다시 돌길의 새로운 패턴 발견(충돌증가), 꼬마자동차의 패턴 돌파(충돌감소)가 반복되며 꼬마자동차와 돌길의 적응도가 증가합니다. 다만 여기서는 꼬마자동차가 중심이기에 돌길에 약간의 제한을 주어 꼬마자동차의 진화를 돕는 쪽으로 유도했습니다.

GA - CNNC를 실은 꼬마자동차[2] - 입력과 출력, 교차

5. 꼬마자동차의 신경망 입력
꼬마자동차가 알아야 할 정보는, 바로 앞의 블럭정보, 그리고 연료가 어디 있는지에 대한 정보입니다.
꼬마자동차 CNNC의 입력노드 중 3개는 앞쪽에 어떤 장애물이 있는지(있으면 1, 없으면 -1), 마지막 하나는 연료의 위치를 -1~+1 사이의 float값으로 입력합니다.

procedure Detect(Car car, StoneRoad road)
.. cl := car.Locate.Len
.. cw := car.Locate.Wid

.. // 앞쪽 3칸 블럭정보
.. if road[cl - 1][cw - 1] == ROCK then
..... SetCharge(car.CNNC, 0, 1) // 0번셀에 입력
.. else
..... SetCharge(car.CNNC, 0, -1)
.. end
.. if road[cl - 1][cw + 0] == ROCK then
..... SetCharge(car.CNNC, 1, 1) // 1번셀에 입력
.. else
..... SetCharge(car.CNNC, 1, -1)
.. end
.. if road[cl - 1][cw + 1] == ROCK then
..... SetCharge(car.CNNC, 2, 1) // 2번셀에 입력
.. else
..... SetCharge(car.CNNC, 2, -1)
.. end

.. // 기름통 위치정보(차에서 가장 가까운)
.. fl := road.Fuel(car).Locate.Len
.. fw := road.Fuel(car).Locate.Wid
.. SetCharge(car.CNNC, 3, (fw - cw) / (fl - cl)) // 3번셀에 입력
end

6. 꼬마자동차의 신경망 출력
신경망 출력을 꼬마자동차의 움직임으로 바꾸기 위해 3개의 출력노드를 사용합니다. 그리고 각 출력노드의 출력양에 따라 직진할지 왼쪽이나 오른쪽으로 움직일지 결정하는 것입니다.
그러나 신경망의 특성상 가능하면 노드수를 줄이는 것이 최적화시키는데 도움이 됩니다. 여기서는 출력노드를 두개로 만들어, 더 강한 출력을 보이는 쪽으로 이동시키도록 하겠습니다. 즉,

procedure Action(Car car, StoneRoad road)
.. left = 0
.. right = 0
.. l := GetCharge(car.CNNC, 0);
.. r := GetCharge(car.CNNC, 1);
.. if l > 0 then // 왼쪽으로 움직이려는 경향
..... left := left + l
.. else // -왼쪽(즉 오른쪽)으로 움직이려는 경향
..... right := right - l
.. end .. if r > 0 then // 오른쪽으로 움직이려는 경향
..... right := right + r
.. else // -오른쪽(즉 왼쪽)으로 움직이려는 경향
..... left := left - r
.. end
.. // 출력이 강한 쪽으로 이동
.. rnd := Random(0, 2)
.. if left > rnd then
..... if right > rnd then
........ MoveForwar(car)
..... else
........ MoveLeft(car)
..... end
... else
..... if right > rnd then
........ MoveRight(car)
..... else
........ MoveForwar(car)
..... end
.. end
end

출력노드를 하나로 해 놓고, +1에 가까울수록 왼쪽으로, -1에 가까울수록 오른쪽으로 움직이도록 할 수도 있지만, 생각만큼 수렴이 잘 되지 않더군요. 우선은 출력노드 두개짜리로 실행해 봤습니다.

7. 적응도 계산
위와 같은 식으로 256개의 꼬마자동차와 64개의 돌길 개체를 만듧니다. 이 256개의 꼬마자동차 각각은 64개의 돌길을 통과하고 각 꼬마자동차와 돌길의 적응도를 결정합니다.
① 꼬마자동차의 적응도 : 평지로 진입할 때마다 10점추가, 장애물을 통과할때 10점감점
② 돌길의 적응도 : 자동차가 기름을 먹으면 5점감점, 장애물로 진입하면 10점추가

8. 교차
꼬마자동차의 경우는 앞의 XOR회로와 같은 일반적인 CNNC식 교차를 사용했습니다.
돌길의 경우는 길 전체를 길이 100의 선형유전자로 간주하고 일반적인 일점교차를 사용했습니다.

procedure CrossOver(StoneRoad a, StoneRoad b)
.. cut := Random(1, 99)
.. for l := 0, cut do
..... for w := 0, 11 do
........ tmp := a[l][w]
........ a[l][w] := b[l][w]
........ b[l][w] := tmp
..... end
.. end
end

9. 돌연변이
돌연변이 역시 꼬마자동차의 경우에는 CNNC의 돌연변이 루틴을 사용합니다.
돌길의 돌연변이는 두 단계로 이루어집니다. 첫째, 일정한 확률로 장애물을 만들기(또는 장애물을 없애기), 둘째, 기름통 위치 바꾸기입니다.

procedure Mutantation(StoneRoad gene)
.. for l := 0, 99 do
..... for w := 1, 10 do // 가장자리는 장애물로 유지
........ if MutantRate then
........... if gene[l][w] == ROCK then
.............. gene[l][w] := ROAD
........... else if gene[l][w] == ROAD then
.............. gene[l][w] := ROCK
........... end
..... end
.. end

.. for l := 0, 99 do
..... for w := 1, 10 do // 가장자리는 장애물로 유지
........ if gene[l][w] == FUEL then
........... if MutantRate then
.............. gene[l][w] := ROAD
.............. gene[l][Random(1, 10)] := FUEL
.............. break // w 루프 탈춮
........... end
........ end
..... end
.. end
end

10. 재생산
256개 꼬마자동차들이 모두 64개 돌길에서 달려 본 후 꼬마자동차와 돌길을 재생산합니다. 역시 꼬마자동차의 경우는 CNNC의 재생산 루틴을 사용했으며(이 경우 상위 8개의 꼬마자동차를 다음 세대에 그대로 복사하는 Elitism을 사용했습니다.)
돌길의 경우에는 T==0.95, Round==4인 토너먼트법(임의로 2⁴=16개의 돌길을 고른 후 95%의 확률로 적응도 높은 쪽이 이기는 토너먼트를 4회 반복)으로 재생산시켰습니다.

GA - CNNC를 실은 꼬마자동차[1] - 공진화와 유전자설계

1. 개요
장애물을 피해 움직이는 꼬마자동차는 이미 앞에서 진화시켜본 적이 있습니다. 8개의 유전자를 가진 자동차들이었죠.
이번에는 8개의 유전자를 가진 꼬마자동차가 아니라 CNNC를 탑재한 꼬마자동차를 진화시키도록 하겠습니다. 기본적으로 바로 앞 3칸의 블럭정보를 받아들여 CNNC에 기초한 신경망을 돌려 다음 행동을 결정하는 것이죠.
하지만 이번 문제에서는 한가지 요인을 더 넣었습니다. '연료'란 개념을 넣었죠.
꼬마자동차는 최대크기 20의 기름통을 가지고 있습니다. 한칸 이동할 때마다 1씩, 그리고 장애물 위를 통과하기 위해서는 5의 기름을 소모합니다.
물론 자동차가 통과해야 할 거리는 100입니다. 그러므로 길 위에는 10칸마다 하나씩 기름통을 10만큼 채울 수 있는 기름이 존재합니다. 그리고 각 자동차들은 다음 기름통의 위치를 감지할 수 있는 감지기를 추가합니다.

2. 공진화
개인의 발전을 위해 라이벌이 필요하듯, 천적들이 서로가 서로의 선택압으로 작용하여 적응도가 높아지는 경우가 있습니다. 이러한 현상을 공진화라고 합니다.
그렇다면 이 꼬마자동차의 천적은 무엇일까요? 이 꼬마자동차가 극복해야 할 대상, 즉 장애물이 깔려있는 돌길 자체가 천적이 되겠죠.
꼬마자동차의 적응도는 '돌길을 얼마나 멀리 갔는가'에 따라 결정됩니다. 반대로 돌길의 적응도는 '자동차들을 얼마나 방해했는가'로 결정할 수 있습니다. '특정한 장애물 패턴'을 가지고 있는 돌길에 많은 자동차들이 발목을 잡힌다면, 그 돌길은 높은 적응도를 갖고 진화적 우위를 차지해서 결국 그러한 '특정한 장애물 패턴'은 점점 많아집니다. 다시 그 '특정한 장애물 패턴'을 돌파할 수 있는 자동차들이 진화적 우위를 차지합니다.

3. 유전자설계 - 꼬마자동차
꼬마자동차의 유전자는 앞의 XOR회로를 진화시키기 위해 사용했던 신경망 그대로입니다. 다만 여기서는 (뒤에서 나올 이유로) 신경세포의 전하량을 0~1이 아니라 -1~+1 사이로 정의했습니다. 이것은 시그모이드함수를 다음과 같이 수정함으로써 간단히 구현됩니다.


4. 유전자설계 - 돌길
돌길의 유전자는, 다음 그림과 같이 설계됩니다. 돌(장애물)과 기름통이 놓여있는 길이 100인 길이죠.



갈색은 장애물, 녹색은 기름통입니다. 그 외의 흰 부분은 장애물 없는 빈 공간입니다.

procedure InitGene(StoneRoad gene)
.. for length := 0, 99 do
..... gene[length][0] := ROCK
..... for width := 1, 10 do
........ gene[length][width] := ROAD
..... end
..... gene[length][11] := ROCK
..... if length % 10 == 5 then
........ gene[length][Random(1, 10)] := FUEL
..... end
.. end
end

코드를 보면 아시겠지만, 최초의 돌길은 양쪽 가장자리를 막고 있는 장애물 외에는 아무런 장애물도 없이 일정 거리마다 연료통만이 흩어져 있는 '가장 쉬운 돌길'들입니다.

미리 말씀드리지만, 유전자알고리즘을 사용하다 보면 유전자알고리즘으로 만들어진 녀석들이 상당히 '얍삽'하다고 느낄 때가 있습니다. 이 문제에서도 알 수 있지만, 결국 '규칙'을 잘 만들지 않으면 이상한 행동을 할 때가 있습니다(사실 그 녀석들도 주어진 규칙 안에서 최대 적응도를 찾은 것이니 뭐라고 할 수도 없죠).

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

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


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

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

GA - 자동차[2] 재생산

3. 가상환경에서의 적응도 테스트
이부분은 자세한 알고리즘은 생략하겠습니다. 단지 먼저 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점짜리(모든 장애물을 완전하게 피한) 꼬마자동차가 나타났군요. 하지만 만점 꼬마자동차가 계속 유지되지 않습니다. 만점 꼬마자동차가 도태되었다가 다시 만들어지는 현상의 반복이군요.
다음번엔 이것을 한번 고쳐봅시다.

GA - 자동차[1] 유전자설계 및 초기화

여러분은 오른쪽 그림과 같은 꼬마자동차를 만들었습니다. 그리고는 무선조종이 아니라 이 자동차가 스스로 장애물을 피해 움직이도록 하려고 합니다.
다만 센서가 약한 관계로 오른쪽 그림과 같이 단 세군데(바로 앞, 바로 앞의 왼쪽, 바로 앞의 오른쪽)만을 감지할 수 있습니다. 그리고 그 결과로 직진할지 왼쪽 앞으로 갈지 오른쪽 앞으로 갈지 결정해야 하는 것입니다.

물론 프로그래밍을 배운 사람은 초보자라도 간단하게 프로그램을 짤 수 있을 것입니다. 그러나 지금 이 자동차는 유전자 알고리즘을 공부하기 위한 샘플이니 직접 프로그래밍하는 것은 잠시 미뤄두시기 바랍니다.

1. 유전자 설계
유전자 프로그램을 할때 가장 첫단계는, 이 꼬마자동차의 '유전자를 설계'하는 일입니다. 보통 입력과 출력 사이의 상관관계를 유전자화시켜야 합니다.
이 꼬마자동차 문제에서 입력은 각 세 군데에서 장애물이 있는지 없는지 여부(장애물이 있으면 1, 없으면 0)로 나타낼 수 있습니다. 즉 8가지의 입력이 존재합니다.
출력은 각 상태일 경우 직진할지 왼쪽앞으로 갈지, 아니면 오른쪽 앞으로 갈지 결정해야 합니다.
그러므로 8개의 동작만으로 연결된 다음과 같은 유전자를 만들 수 있습니다.

차량	유전자(0:왼쪽앞으로 1:직진 2:오른쪽앞으로)
가	10212001
나	22120001
다	11220210
라	21010112
마	00211201
...	...

만약 꼬마자동차가 왼쪽과 같은 상황에 처했다면, 입력장치는 011, 즉 3이란 입력을 보냅니다. 각 꼬마자동차들은 자신의 유전자에서 3 위치를 검색, 다음에 어떤 행동을 할 것인지 결정합니다.
'가'의 경우 3 위치에 해당하는 것은 (첫 동작이 0이므로) <1-직진>입니다. 그러므로 '가'는 사람을 치고 지나가겠죠.
'다'의 경우 3위치의 동작은 <2-오른쪽앞>이므로 '다'는 나무를 향해 돌진할 것입니다.

이와같이 해서 꼬마자동차의 입력과 출력을 연결할 수 있는 유전자를 설계할 수 있습니다.

물론 다른 방식으로 유전자를 설계할 수도 있습니다. 그러나 이 꼬마자동차 문제는 유전자 알고리즘을 공부하기 위한 첫단계이므로 가장 간단하고 직관적인 유전자로 설계했습니다.

2. 최초 세대의 유전자 초기화(GeneInit)
이 프로그램에서는 한 세대의 꼬마자동차 수를 128대로 정의했습니다. 128개 꼬마자동차의 배열 또는 벡터를 만든 후 각 꼬마자동차의 유전자를 초기화하는 루틴을 만들어야 합니다.

사실 이 128이란 숫자는 유전자알고리즘에서 적당한 세대인구가 아닙니다. 보통 유전자알고리즘은 '수로 승부하는 방법'이라고 할 수 있습니다. 가능하면 많은 개체를 사용하여, 다양성을 증가시켜야 제대로된 결과가 나올 수 있습니다. 다만 이 꼬마자동차는 상당히 간단한 유전자 구조를 가지고 있기에 세대인구가 적더라도 비교적 빨리 원하는 결과를 얻을 수 있습니다. 보통 유전자알고리즘의 세대인구수는 최소 1000 이상, 대개 10000단위까지 올라갈 수 있습니다.

초기화루틴은 다음과 같이 정의합니다.

procedure GeneInit(KidCar car)
.. for i := 0,8 do
..... car.gene[i] := 1 // 모든 경우에 무조건 직진으로 세팅
end

일반적으로 유전자를 초기화하기 위해서는 유전자의 각 위치(bit)에 유전자가 허용하는 랜덤값을 넣는 것이 정도(正道)입니다. 즉 ..... car.gene[i] := Random(0:2) // 0, 1, 2중 임의 선택 가 되어야 합니다. 다만 이 꼬마자동차에서는 돌연변이 효과를 확인하기 위해 일부러 모든 경우 직진하는 코드를 넣었습니다.