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를 이용한 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회 실시하여 그 합을 적응도로 간주, 재생산을 실시합니다.