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