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 - CNNC를 이용한 XOR 회로[6] - 결과

10. 결과
다음은 앞에서 설명한 대로 CNNC신경망을 XOR회로에 맞추어 진화시킨 결과입니다.

Generation : 0
Spec[0] Node[3] Pop[512] Min[198.476] Max[405.106]
Generation : 1
Spec[0] Node[3] Pop[512] Min[207.359] Max[639.097]
Generation : 2
Spec[0] Node[3] Pop[512] Min[170.006] Max[799.999]
......
Generation : 282
Spec[0] Node[3] Pop[512] Min[250] Max[880]
Generation : 283
Spec[0] Node[3] Pop[512] Min[410] Max[860]
Generation : 284
Spec[0] Node[3] Pop[511] Min[250] Max[860]
Spec[1] Node[4] Pop[1] Min[430] Max[430]
Generation : 285
Spec[0] Node[3] Pop[273] Min[320] Max[850]
Spec[1] Node[4] Pop[239] Min[330] Max[650]
Generation : 286
Spec[0] Node[3] Pop[204] Min[440] Max[880]
Spec[1] Node[4] Pop[308] Min[360] Max[780]
Generation : 287
Spec[0] Node[3] Pop[161] Min[400] Max[860]
Spec[1] Node[4] Pop[350] Min[270] Max[800]
Spec[2] Node[5] Pop[1] Min[590] Max[590]
Generation : 288
Spec[0] Node[3] Pop[124] Min[380] Max[850]
Spec[1] Node[4] Pop[265] Min[390] Max[770]
Spec[2] Node[5] Pop[123] Min[250] Max[810]
......
Generation : 307
Spec[0] Node[3] Pop[39] Min[390] Max[830]
Spec[1] Node[4] Pop[228] Min[210] Max[970]
Spec[2] Node[5] Pop[245] Min[200] Max[950]
Generation : 308
Spec[0] Node[3] Pop[36] Min[380] Max[800]
Spec[1] Node[4] Pop[235] Min[220] Max[900]
Spec[2] Node[5] Pop[241] Min[170] Max[1000]
Generation : 309
Spec[0] Node[3] Pop[29] Min[250] Max[800]
Spec[1] Node[4] Pop[228] Min[200] Max[940]
Spec[2] Node[5] Pop[255] Min[200] Max[1000]

각각 앞에서부터 종 ID, 노드 갯수, 각 종의 개체수, 각 세대,종에 따른 최소, 최대 적응도를 의미합니다. 308세대 이후에야 겨우 최고 적응도 1000을 달성했습니다.
그런데... 일반적으로 XOR게이트는 노드 4개로도 달성 가능합니다. 그런데 5개짜리가 만들어졌군요. 적응도에 노드 갯수가 포함되어 있지 않기 때문입니다. 최소한의 노드 수, 그리고 최소한의 연결 갯수를 알기 위해서는 노드 수와 연결 수도 적응도에 포함시켜야 합니다.

여기서 주의할 점은, 가장 작은 신경망을 만들기 위해 노드 수와 연결 수에 지나치게 큰 가중치를 준다면, 유전자알고리즘은 정답률을 희생하고 크기를 줄이는 경우도 생길 수 있다는 점입니다.
그러므로, 100회의 적응도 테스트가 끝난 후 (노드 수 + 연결 수)를 적응도에서 빼는 방식을 사용했습니다.
다음은 노드와 연결 갯수까지 적응도에 적용시켜 실행한 결과입니다. seed를 바꾸어 가며 여러번 실행시킨 결과 중 가장 빨리 수렴된 결과입니다.

Generation : 0
Spec[0] Node[3] Pop[512] Min[191.699] Max[446.516]
Generation : 1
Spec[0] Node[3] Pop[512] Min[203.907] Max[660.462]
Generation : 2
Spec[0] Node[3] Pop[512] Min[205] Max[790.834]
Generation : 3
Spec[0] Node[3] Pop[512] Min[105] Max[825]
Generation : 4
Spec[0] Node[3] Pop[512] Min[195] Max[825]
Generation : 5
Spec[0] Node[3] Pop[512] Min[145] Max[825]
Generation : 6
Spec[0] Node[3] Pop[512] Min[215] Max[855]
Generation : 7
Spec[0] Node[3] Pop[512] Min[155] Max[855]
Generation : 8
Spec[0] Node[3] Pop[512] Min[195] Max[825]
Generation : 9
Spec[0] Node[3] Pop[512] Min[135] Max[845]
Generation : 10
Spec[0] Node[3] Pop[512] Min[215] Max[835]
Generation : 11
Spec[0] Node[3] Pop[512] Min[195] Max[845]
Generation : 12
Spec[0] Node[3] Pop[512] Min[255] Max[855]
Generation : 13
Spec[0] Node[3] Pop[511] Min[265] Max[905]
Spec[1] Node[4] Pop[1] Min[372] Max[372]
Generation : 14
Spec[0] Node[3] Pop[361] Min[135] Max[835]
Spec[1] Node[4] Pop[151] Min[402] Max[812]
Generation : 15
Spec[0] Node[3] Pop[287] Min[215] Max[894]
Spec[1] Node[4] Pop[225] Min[370.891] Max[872]
Generation : 16
Spec[0] Node[3] Pop[252] Min[246.175] Max[845]
Spec[1] Node[4] Pop[260] Min[232.093] Max[862]
Generation : 17
Spec[0] Node[3] Pop[218] Min[336] Max[855]
Spec[1] Node[4] Pop[294] Min[192] Max[991]
Generation : 18
Spec[0] Node[3] Pop[210] Min[175] Max[855]
Spec[1] Node[4] Pop[302] Min[234.32] Max[991]
Generation : 19
Spec[0] Node[3] Pop[216] Min[263] Max[865]
Spec[1] Node[4] Pop[296] Min[260] Max[991]

불과 17세대만에 최적화된 XOR회로가 만들어졌군요. XOR회로는 4개의 노드(세포)와 5개의 연결이 필요하니, 1000 - (4 + 5) = 991이 가장 최적화된 적응도값입니다.
유전자를 분석해서 최적화된 신경망을 그려 보았습니다. 선에 달린 숫자는 각 연결선의 강도, 세포에 달린 숫자는 각각 Bias, SigmoidFactor값입니다.

GA - CNNC를 이용한 XOR 회로[5] - 종(種) 분류 및 보호, 재생산

7. 종 분류
다른 GA에서도 마찬가지지만, CNNC 역시 다양성 확보를 위해 종을 분류하여 관리하는 것이 좋습니다.
종 분류 방법이야 많이 있지만, 여기 CNNC에서는 노드 수(세포 수)를 기준으로 종을 관리하기로 했습니다. 앞의 교차부분에서 언급했던 것처럼 노드 수가 다를 경우에는 교배가 불가능하니까 말입니다.

8. 종 보호
다양성을 위해 종별로 나누고 다양성을 유지시키기 위해 소수종을 보호합니다. 그런데 약간의 문제가 생기는군요.
기존에 소수종을 보호하기 위한 방법은, 각 개체의 적응도에 그 개체가 소속된 종의 개체수에 따라 감소시키는 것이었습니다.
문제는 개체수가 줄어들었을때 그 개체의 적응도가 증가하고, 그 개체가 선택될 가능성이 늘어남에 따라, 한번 만들어진 종은 사라질 가능성이 줄어들게 된다는 점입니다.

Node[3] Pop[28]
Node[4] Pop[34]
Node[5] Pop[37]
Node[6] Pop[23]
Node[7] Pop[31]
Node[8] Pop[34]
Node[9] Pop[19]
Node[10] Pop[33]
Node[11] Pop[37]
Node[12] Pop[28]
Node[13] Pop[37]
Node[14] Pop[31]
Node[15] Pop[24]
Node[16] Pop[31]
Node[17] Pop[39]
Node[18] Pop[33]
Node[19] Pop[13]

과 같은 결과가 나올 수도 있습니다. 더구나 같은 종 안에서만 교배해야 하는 CNNC의 특성상20~40개의 개체수 안에서 유전자알고리즘을 돌려야 한다는 이야기가 되는 것입니다(한마디로 다양성이 너무 증가되었다는 말이 되는군요).
그러므로 CNNC에서는 '소수종의 보호'가 아니라 '각 종의 보호시간'을 도입하기로 했습니다. 돌연변이에 의해 하나의 새로운 종이 새로 나타났을 경우 30세대동안 보호(다음 세대 번식때 일정비율 그 종에서 번식시킴)시키는 개념입니다. 만약 30세대동안 최적값을 못찾았다면 그 종은 아무런 보호 없이 다른 종과의 생존경쟁으로 내몰리는 것이죠.
그러므로 여기서는 종의 개체수에 따른 적응도 보정은 사용하지 않습니다.

9. 재생산
지금까지의 재생산프로세스는 거의 동일했고 단지 문제에 따라 교차 및 돌연변이만 달랐었습니다. 그러나 이 경우에는 일반적인 재생산 프로시저를 사용할 수 없습니다.
CNNC용 재생산 프로시저는 다음과 같습니다. 참고로, 재생산 대상 선택은 각 개체의 적응도를 10~100 사이로 재계산한 후 룰렛을 돌리는 재계산법을 사용했으며, 상위 16개의 개체를 그대로 복사하는 Elitism을 사용했습니다(전체 개체수는 512).

function SelectParent(CreatureList parentlist, int spe)
.. // 점수의 상한선과 하한선 찾기
.. minscore := 10000;
.. maxscore := 0;
.. for k := 0, 512 do
..... if parentlist[k].Species == spe then
........ if minscore > parentlist[k].Score then
........... minscore := parentlist[k].Score
........ end
........ if parentlist[k].Score > maxscore then
........... maxscore := parentlist[k].Score
........ end
..... end
.. end

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


procedure Regeneration(CreatureList parentlist)
.. Declear CreatureList nextgen // 다음 세대를 임시로 저장할 버퍼

.. // 16개체 엘리트 적용
.. sort(parentlist) // parentlist를 적응도순으로 정렬
.. for i := 0, 16 do
..... nextgen.Insert(parentlist[i]);
.. end

.. // parent의 종 분류
.. for spe := 0, SpeciesManager.size do
..... SpeciesManager[spe].population := 0
.. end
.. for i := 0, 512 do
..... spe := parentlist[i].size // 각 개체의 크기(노드 갯수)가 곧 종 핸들
..... parentlist[i].species := spe;
..... if spe > SpeciesManager.size then // 처음 만들어진 종이라면
........ SpeciesManager.NewSpecies() // 새로운 종 등록
........ SpeciesManager[spe].population := 1
........ SpeciesManager[spe].Species := spe
........ SpeciesManager[spe].prevent := 30
..... else
........ SpeciesManager[spe].population := SpeciesManager[spe].population + 1
..... end
.. end

.. // 보호해야 할 종 확인 - 각 종마다 남아있는 prevent값 누적
.. totalprevent := 0
.. for spe := 0, SpeciesManager.size do
..... if SpeciesManager[spe].population > 0 then
........ totalprevent := totalprevent + SpeciesManager[spe].prevent
........ SpeciesManager[spe].prevent := SpeciesManager[spe].prevent - 1
..... end
.. end

.. // 전체 개체수의 절반(256)을 보호종을 위해 할당하고,
.. // 각 종의 prevent 비율로 할당
.. Declear CreatureList malelist // 보호종의 수컷(?)들만을 모아놓을 버퍼
.. for spe := 0, SpeciesManager.size do
..... if SpeciesManager[spe].population > 0 then
........ regennum := SpeciesManager[spe].prevent * 512 / (totalprevent * 2)
........ for k := 0, regennum do
........... // spe 중에서 적응도 재계산 순서로 선택
........... selectedmale := ParentSelect(parentlist, spe);
........... malelist.Insert(selectedmale)
........ end
..... end
.. end

.. // 보호종의 암컷(?)을 찾아 교배시킴
.. for k := 0, malelist.Size do
..... spe := malelist[k].Species
..... // parentlist에서 spe를 적응도순서로 골라냄
..... female := ParentSelect(parentlist, spe);
..... // malelist[k]와 female로 새로운 개체 만듦
..... CrossOver(malelist[k], female, child)
..... nextgen.Insert(child);
.. end

.. // 나머지 갯수 채움
.. while nextgen.Size != 512 do
..... male := ParentSelect(parentlist); // 종구분없이 골라냄
..... female := ParentSelect(parentlist, male.Species); // 같은 종에서

..... // male과 female로 새로운 개체 만듦
..... CrossOver(male, female, child)
..... nextgen.Insert(child);
.. end
.. parentlist := nextgen // 새로운 세대로 교체
end

GA - CNNC를 이용한 XOR 회로[4] - 돌연변이

6. 돌연변이
교차에 의해 만들어진 아기CNNC는 약간의 돌연변이 처치를 받습니다.
교차는 아무리 많이 하더라도 구조(라기보다는 히든노드 수)를 바꿀 수 없습니다. 그때문에 돌연변이가 필수인 것이죠.

돌연변이의 역할은 다음과 같습니다.

① 작은 돌연변이
이것은 구조를 바꾸기보다는 복제 후 각 노드의 상수(Bias, SigmoidFactor) 및 각 채널의 강도에 약간의 변경을 가합니다. 때로는 활성화되어 있던 채널을 닫거나 닫혀있던 채널을 열기도 합니다. 즉, 노드(세포) 갯수는 고정된 상태에서 새로운 연결을 만들거나 연결을 제거하는 역할을 합니다.
미소돌연변이는 큰 변이 없이 최적의 상수값을 찾아가기 위해 사용합니다.

procedure MicroMutantation(GeneNode node)
.. if MutantRate() then
..... node.Bias := Random(-5, 5)
.. else
..... node.Bias := node.Bias * Random(0.8, 1.2)
.. end

.. if MutantRate() then
..... node.SigmoidFactor := Random(-5, 5)
.. else
..... node.SigmoidFactor := node.SigmoidFactor * Random(0.8, 1.2)
.. end

.. for c := 0, gene.ChannelSize do
..... if node.RecvChannel[c] == 0 then
........ if MutantRate() then
.......... node.RecvChannel[c] := Random(-5, 5)
........ end
..... else
........ if MutantRate() then
.......... node.RecvChannel[c] := 0
........ else
.......... node.RecvChannel[c] := node.RecvChannel[c] * * Random(0.8, 1.2)
........ end
..... end
..... // SendChannel에 대해서도 동일한 처리
.. end
end

② 큰 돌연변이
거대돌연변이는 새로운 노드를 추가 또는 삭제하여 전혀 새로운 구조를 만들기 위해 사용됩니다.

procedure NodeAppend(Gene gene)
.. // 각 파라미터 초기화
.. newnode.Layer := Random(0, 1)
.. newnode.Bias := Random(-5, 5)
.. newnode.Sigmoid := Random(-5, 5)
.. //채널 초기화
.. for k := 0, ChannelSize do
..... newnode.RecvChannel[k] := 0
..... newnode.SendChannel[k] := 0
.. end

.. // 입력노드 연결
.. inputnode := NodeFind(gene, -100, 100)
..... // 모든 노드들(input node + hidden node + output node) 중에서 임의선택
.. channel := Random(0, ChannelSize)
.. newnode.RecvChannel[channel] := Random(-5, 5)
.. if inputnode.SendChannel[channel] == 0 then
..... inputnode.SendChannel[channel] := Random(-5, 5)
.. end

.. // 출력노드 연결
.. outputnode := NodeFind(gene, -100, 1)
..... // Layer가 0 이상(hidden node + output node) 인 것들 중에서 임의선택
.. channel := Random(0, ChannelSize)
.. newnode.SendChannel[channel] := Random(-5, 5)
.. if outputnode.RecvChannel[channel] == 0 then
..... outputnode.RecvChannel[channel] := Random(-5, 5)
.. end
.. gene.Insert(newnode)
end

procedure NodeRemove(Gene gene)
.. node := NodeFind(gene, 0, 1)
......... // Layer가 0과 1 사이(히든노드들) 중 임의의 노드 하나 선택
.. if node != NULL then
..... gene.Remove(node) // 제거할 히든노드가 있을 경우에만 삭제
.. end
end

그러므로 돌연변이 루틴은 다음과 같습니다.

procedure Mutantation(Gene gene)
.. // 작은돌연변이
.. for node := 0, NodeSize do
..... MicroMutantation(gene.Node[node])
.. end

.. // 큰돌연변이
.. if MutantRate() then
..... NodeAppend(gene)
.. else if MutantRate() then
..... NodeRemove(gene)
.. end
end

GA - CNNC를 이용한 XOR 회로[3] - 교차

5. 교차
재생산에 대해 말하기 전에 먼저 교차를 어떻게 해야 할지 생각해 봅시다.
다음 두 유전자를 보죠. 보기이므로 간단하게 만들어 보았습니다.

+1.1/1/2(0000000000000000)(0010000100000000)
-0.1/1/2(0010000000000000)(0000000000000000)
-0.2/1/2(0000000100000000)(0000000000000000)

+1.1/3/4(0000000000000000)(0000001000000100)
-0.1/3/4(0000000000000100)(0000000000000000)
-0.2/3/4(0000001000000000)(0000000000000000)

둘 다 기본적인 OR회로와 같은 형태를 가지고 있습니다. 이 둘을 교차시키면 최소한 동일한 OR회로가 나와야 할 것 같습니다.
① 먼저 저 유전자를 단순한 1차원 유전자라 간주하고 1점교차를 시도해 보겠습니다.

+1.1/1/2(0000000000000000)(0010000100000000)
-0.1/1/2(0010000000000100)(0000000000000000)
-0.2/3/4(0000001000000000)(0000000000000000)

+1.1/3/4(0000000000000000)(0000001000000100)
-0.1/3/4(0000000000000000)(0000000000000000)
-0.2/1/2(0000000100000000)(0000000000000000)

이것으로 신경망을 만들어보면 알 수 있겠지만, 앞쪽것은 입력노드와 출력노드를 연결하던 연결 하나가 사라지고 말았습니다. 뒷쪽것은 아예 연결이 모두 사라졌네요. 결국 다음과 같이 망가진 두개의 신경망이 생기고 말았습니다.

② 그렇다면 저 3개의 노드를 한묶음으로 생각하고 교차를 해 봅시다.

+1.1/1/2(0000000000000000)(0010001000000100)
-0.1/1/2(0010000000000000)(0000000000000000)
-0.2/1/2(0000000100000000)(0000000000000000)

+1.1/3/4(0000000000000000)(0000000100000000)
-0.1/3/4(0000000000000100)(0000000000000000)
-0.2/3/4(0000001000000000)(0000000000000000)

마찬가지 결과입니다. 윗그림과 똑같이 망가진 신경망 두개가 생기는군요.

③ 잘 생각해 보면 하나의 연결에 영향을 미치는 것은 송신채널과 수신채널에 나뉘어져 있습니다. 그렇다면 송신채널과 수신채널을 겹쳐놓고 교차시키는 것이 나을 수도 있겠군요.

+1.1/1/2(0000000000000000)
........(0010000100000100)
-0.1/1/2(0010000000000100)
........(0000000000000000)
-0.2/1/2(0000000100000000)
........(0000000000000000)

+1.1/3/4(0000000000000000)
........(0000001000000000)
-0.1/3/4(0000000000000000)
........(0000000000000000)
-0.2/3/4(0000001000000000)
........(0000000000000000)

이 경우에는 두번째 것은 연결 하나가 끊어졌지만 첫번째 것은 온전하게 남아 있습니다. 다른 교차법에 비해 그나마 낫군요.
하지만 또한가지 문제가 있습니다. 다음 두 유전자는 어떻게 교차를 시킬 수 있을까요?

+1.1/1/2(0000000000000000)(0011000100000000)
+0.7/1/2(0001000000000000)(0000000000000100)
-0.1/1/2(0010000000000100)(0000000000000000)
-0.2/1/2(0000000100000000)(0000000000000000)

+1.1/3/4(0000000000000000)(0000001000000100)
-0.1/3/4(0000000000000100)(0000000000000000)
-0.2/3/4(0000001000000000)(0000000000000000)

이 둘을 교차시키기는 쉽지 않습니다. 그러므로 CNNC에서의 교차는 '노드 수가 같을 경우에만' 하는 것으로 규정합니다.

지금까지 만들었던 유전자 알고리즘에서, 교차는 다음과 같은 방식으로 해 왔습니다.

① 두 부모 유전자의 복제를 만든다.
② 만들어진 복제의 유전자를 교차시켜 자식유전자로 한다.

즉 두 부모 유전자로부터 두 자녀유전자가 생겼습니다.
그러나 CNNC에서는 교차를 하더라도 하나는 망가지는 경우가 종종 생깁니다. 그러므로 CNNC에서는 방법을 바꾸어 두 부모유전자를 섞어 하나의 자식유전자를 만들게 됩니다.
이때는 각종 인수들(Bias, SigmoidFacter 등) 및 채널정보를 두 부모유전자의 적응도비율에 의해 부모 양쪽에서 가져옵니다. 이때 1점교차가 아니라 랜덤교차를 사용합니다.
만약 한쪽 적응도가 100, 다른쪽이 50이라면 대략 다음과 같은 자식이 나옵니다.

+1.1/3/2(0000000000000000)
........(0000001000000100)
-0.1/1/2(0000000000000100)
........(0000000000000000)
-0.2/1/2(0000001000000000)
........(0000000000000000)

물론 이 방식도 랜덤함수에 의해 잘못된 자식이 나올 가능성도 배제할 수는 없습니다만, 정상적인(그리고 보다 우수한) 자손이 나올 가능성이 더 크며 잘못된 자식은 다음 세대에 도태되므로 큰 문제를 일으키지는 않습니다(물론 알고리즘의 효율성이 조금 떨어질 수는 있죠).

procedure CrossOver(Gene male, Gene female, Gene child)
.. if male.NodeSize != female.NodeSize then // 궁합이 안맞음(노드수가 다름)
..... child.Valid := false
..... return
.. end

.. // 각 부모를 layer순으로 정렬(입력노드와 출력노드가 교차되지 않도록)
.. sort(male)
.. sort(female)

.. TotalFitness := male.Fitness + female.Fitness
.. MalePriority := male.Fitness / TotalFitness

.. // 각종 파라미터 나누기
.. for k := 0, male.NodeSize do
..... if MalePriority > Random(0, 1) then
........ child.Node[k].Layer = male.Node[k].Layer
..... else
........ child.Node[k].Layer = female.Node[k].Layer
..... end
..... // 생략, Bias와 SigmoidFactor도 동일하게 복사
.. end

.. // 채널 복사
.. for c := 0, 16 do
..... rnd := Random(0, 1)
..... for k := 0, male.NodeSize do
........ if MalePriority > rnd then
........... child.Node[k].SendChannel[c] := male.Node[k].SendChannel[c]
........... child.Node[k].RecvChannel[c] := male.Node[k].RecvChannel[c]
........ else
........... child.Node[k].SendChannel[c] := female.Node[k].SendChannel[c]
........... child.Node[k].RecvChannel[c] := female.Node[k].RecvChannel[c]
........ end
..... end
.. end
.. child.Valid := true
end

GA - CNNC를 이용한 XOR 회로[2] - 유전자 설계

3. 유전자설계
신경망에서 하나의 노드에 필요한 정보는 다음과 같습니다.
① 입력스트림 : 입력노드들과 그 노드와의 연결 강도. float형의 벡터이며 그 크기로 연결강도를 표시합니다. 이 XOR회로에서는 16개의 채널을 준비합니다.
② Layer : 노드를 구분하기 위해 사용. Layer가 0보다 작으면 입력노드, 1보다 크면 출력노드, 그 사이면 은닉노드
③ Bias : 입력스트림의 하나로 만들 수도 있지만 여기서는 노드가 따로 가지고 있음
④ SigmoidFactor : 입력의 합을 출력으로 계산할때 시그모이드 팩터를 사용
XOR회로의 경우 하나의 CNNC는 2개의 입력노드, 1개의 출력노드(그 외에 몇개가 될지 모르는 은닉노드)로 구성됩니다. 초기상태에는 은닉노드가 없으므로 CNNC 하나의 유전자는

+1.1/Bias/SF(ABCDEFGHIJKLMNOP)(abcdefghijklmnop)
-0.1/Bias/SF(ABCDEFGHIJKLMNOP)(abcdefghijklmnop)
-0.2/Bias/SF(ABCDEFGHIJKLMNOP)(abcdefghijklmnop)

과 같습니다. 이 경우 Bias, SF(SigmoidFactor), A~P, a~p는 모두 float형입니다. 가장 앞의 숫자는 Layer이며 0 이하는 입력노드, 1 이상은 출력노드를 의미합니다. 뒤의 A~P, a~p의 리스트는 각각 송신채널, 수신채널입니다. 이 값이 0이면 그 채널로 송신/수신을 않는다는뜻이며 0이 아니라면 그 채널로 송수신을 한다는 뜻입니다.

procedure InitGene(Gene gene)
.. // 3개의 노드를 만듦
.. InitNode(gene.Node[0], -0.2)
.. InitNode(gene.Node[1], -0.1)
.. InitNode(gene.Node[2], 1.1)

.. // 입력과 출력노드 사이에 초기링크 만들기
.. MakeLink(gene.Node[0], gene.Node[2])
.. MakeLink(gene.Node[1], gene.Node[2])
end

procedure InitNode(Node node, double layer)
.. node.Layer = layer
.. node.Bias = Random(-5, 5)
.. node.SigmoidFactor = Random(0.001, 3)
.. for k := 0, 16 do
..... node.SendChannel[k] := 0
..... node.RecvChannel[k] := 0
.. end
end

procedure MakeLink(Node from, Node to)
.. channel := Random(0, 15)
.. from.SendChannel[channel] := Random(-5, 5)
.. to.RecvChannel[channel] := Random(-5, 5)
end

4. 발생(Ontogeny)
개념상으로는 앞에서 말한대로 채널을 통한 노드들간의 채널통신으로 이해했지만, 실제 적용하기 위해서는 기존의 신경망방식으로 바꾸는 것이 좋습니다. 즉 송신채널과 수신채널이 일치하는 노드들끼리 연결을 만드는 것입니다.
만약 두 노드의 송신채널과 수신채널이 동시에 0이 아닐 경우 두 노드 사이에는 연결이 생깁니다. 이 연결의 크기는 송신채널의 값과 수신채널의 값에 의해 결정됩니다.
아무리 송신채널이 강하게 송신해도(송신채널의 값이 커도) 수신채널에서 약하게 수신한다면(수신채널의 값이 작으면) 두 노드 사이의 연결강도는 약해집니다. 반대로 수신채널의 값이 커도 송신을 약하게 한다면(송신채널의 값이 작으면) 마찬가지로 연결은 약해지죠.
여기서는 두 채널값으로 연결의 강도를 계산하는 공식으로 기하평균을 사용했습니다. 기하평균은 다음과 같이 계산됩니다.



procedure Ontogeny(Gene gene, Brain brain)
.. // 각 노드에 해당하는 세포를 만듦
.. for k := 0, gene.NodeNumber do
..... brain.Cell[k].Layer := gene.Node[k].Layer
..... brain.Cell[k].Bias := gene.Node[k].Bias
..... brain.Cell[k].SigmoidFactor := gene.Node[k].SigmoidFactor
.. end

.. // 각 세포들 연결
.. for k := 0, brain.CellNumber do
..... for m := 0, brain.CellNumber do
........ // 링크정보를 알기 위해 brain.Cell[k,m]에 해당하는 노드를 찾음
........ nodek := FindNode(gene, brain.Cell[k])
........ nodem := FindNode(gene, brain.Cell[m])
........ // k와 m이 얼마만큼의 세기로 연결되어 있는지 확인
........ weigth = 0;
........ for c := 0, 16 do
........... mult := nodek.SendChannel[c] * nodem.RecvChannel[c]
........... if mult != 0 then
.............. gioavg := sqrt(mult) // 기하평균 계산
.............. weigth := weigth + gioavg
........... end
........ end
..... MakeLink(brain.Cell[k], brain.Cell[m], weigth)
..... // k->m으로 강도 weigth의 입력 만듦
.. end
end

5. 적응도 계산
위에서 만들어진 brain을 가지고 적응도를 계산합니다. 자세한 알고리즘은 생략하겠지만, 입력셀에 랜덤으로 0/1을 넣고 신경망을 돌려 나온 값과 XOR계산값을 비교하여 그 차이가 작을수록 해당 CNNC의 적응도를 높이는 방식입니다. 임의의 입력값으로 100회를 반복한 후 결과를 최종 적응도로 결정했습니다.

단, 이때 출력에 따른 적응도함수를 다음과 같이 한다면 어떨까요?

.. output := think(a, b)
.. correct = a ^ b
.. if abs(correct - output) > 0.5 then
..... AddFitness(0)
.. else
..... AddFitness(10)
.. end

이 방식의 가장 큰 문제점은, 참값과의 차이가 0.51인(보다 적은 변이로 참값으로 갈 수 있는) 신경망과 0.9인 신경망 둘 다 적응도가 0으로써 둘 사이의 적응도 차이를 알 수 없다는 점입니다. 유전자알고리즘의 원칙인 조금이라도 더 적응도가 우수한 것을 찾을 수가 없는 것이죠. 그러므로 적응도함수는 반드시 꼭대기가 없는 경사함수가 되어야 합니다.
이 XOR 신경망에서는 다음과 같은 적응도 함수를 사용했습니다.

.. output := think(a, b)
.. correct = a ^ b
.. diff = abs(output - correct)
.. subfit = 1 - diff // 차이가 작을수록 적응도 높아짐
.. AddFitness(subfit * subfit * 10)

그냥 subfit를 적응도로 사용해도 되지만 여기서는 참값에 가까와질수록 선택압을 높이기 위해 subfit의 제곱을 사용하여 오른쪽 그림과 같은 함수가 되었습니다.

각 XOR신경망에 대해 랜덤입력에 의한 적응도테스트를 100회 실시하여 그 합을 적응도로 간주, 재생산을 실시합니다.

GA - CNNC를 이용한 XOR 회로[1] - 소개

1. 개요

일반적으로 신경망이라면 각 신경세포들과, 그 신경세포들 사이를 연결하는 신경섬유로 구성되어 있습니다. 신경세포는 신경섬유를 통해 연결된 다른 신경세포로부터 자극을 받아 활성화되며, 또한 신경섬유를 통해 다른 신경세포를 자극함으로써 신호가 전달됩니다.

CNNC(Cluster of Neuron Network by Channeling)는 개념적으로는 신경세포는 있지만 신경섬유는 없는 구조입니다. CNNC의 신경세포들은 신경섬유를 통해서가 아니라 특정한 채널을 통해 자신의 활성화 정도를 송신합니다. 만약 다른 신경세포가 그 채널을 통해 수신을 하고 있다면 그 세포들은 신경섬유에 의해 연결된 것으로 간주할 수 있습니다.
만약 8개의 채널을 가진 5개의 신경세포가 다음과 같은 채널을 통해 송수신하고 있다면(붉은색은 활성화, 회색은 비활성화),

신경세포	송신채널	수신채널
가	01234567	01234567
나	01234567	01234567
다	01234567	01234567
라	01234567	01234567
마	01234567	01234567

라에서 0번채널로 송신한 내용은 나와 다에서 0번채널로 수신합니다(즉 라와 다, 라와 나의 연결이 존재합니다). 그러나 마에서 2번 채널로 송신한 것은 받아들이는 신경세포가 없으므로 사라집니다. 마찬가지로 가에서 수신하는 4번채널 역시 송신하는 세포가 없으므로 비활성이나 마찬가지입니다. 결국 위와 같은 CNNC는 다음과 같은 신경망과 동일합니다

2. XOR 회로
아시다시피 XOR게이트는 두개의 입력을 받아 왼쪽과 같은 출력을 보이는 회로입니다. 신경망으로 OR나 AND 게이트를 만드는 것은 쉽지만, XOR게이트를 만드는 것은 약간 복잡합니다. OR과 AND는 입력층과 출력층만으로 쉽게 만들 수 있지만 XOR게이트는 중간의 은닉층이 필요하기(신경망의 구조 자체가 달라져야 하기) 때문입니다.
CNNC가 XOR회로를 만들었다고 제대로된 신경망 진화 알고리즘이라고 할 수 없지만, XOR회로를 못만든다면 CNNC는 제대로된 신경망 진화 알고리즘이라고 할 수 없죠.
그러므로 CNNC의 첫 도전으로 XOR 회로를 만들어보기로 하겠습니다.