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