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