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 회로를 만들어보기로 하겠습니다.