GA - 오델로 - 경쟁 및 재생산

3. 경쟁
이제 유전자도 설계했으니 이들을 경쟁시켜서 적응도를 측정해야 합니다. 그런데 무엇과 경쟁시킬까요? 특정한 AI를 하나 만들어서 이 AI와 경쟁시켜야 할까요?
아, 전에도 종종 사용했던 공진화를 이용하면 구태여 AI를 따로 만들 필요가 없겠네요. 일이 줄었습니다.
여기서는 이 오델로플레이어들을 6개의 무리로 나누었습니다. 각 무리에는 512개씩의 오델로플레이어를 포함시켰습니다. 그리고는 이들 사이에서 경쟁을 시켰습니다.
각 오델로플레이어들은 같은 무리에 있는 것들과는 싸우지 않습니다. 다른 무리에 있는 것들과 싸우게 됩니다.

procedure Compatition()
.. for h := 0, 6 do
..... for p := 0, 512 do
........ Horde[h][p].Fitness := 0; // 모든 객체의 적응도 초기화
..... end
.. end

.. // 경쟁 시작
.. for white := 0, 6 do
..... for black := 0, 6 do
........ if white != black then
........... // Horde[white]와 Horde[black]간의 대결
........... // 랜덤한 상대를 만나기 위해
........... for k := 0, 512 do
.............. CardDeck[k] = k;
........... end
........... for k := 0, 512 do
.............. rnd := Random(0, 512);
.............. tmp = CardDeck[k];
.............. CardDeck[k] = CardDeck[rnd];
.............. CardDeck[rnd] = tmp;
........... end
........... for k := 0, 512 do
.............. Compatition(Horde[white][k], Horde[black][CardDeck[k]];
........... end
........ end
..... end
.. end
end

Compatition프로시저는 생략하겠습니다. 두 오델로플레이어끼리 대결을 시킨 후, 남아있는 자신의 돌 수를 Fitness에 더하는 프로시저입니다.

4. 재생산
이렇게 적응도를 구했으면 보다 많은 돌을 가진 오델로플레이어를 찾아 재생산을 시킵니다. 일단 재생산 대상은 T=0.99인 4차 토너먼트법 - 2⁴ = 16개의 후보를 선택 후 토너먼트를 반복해서 하나 설정, 토너먼트의 승부는 1% 확률로 적응도 낮은 것이 승 - 으로 결정했습니다.

4.1 교차
다음과 같은 유전자를 가진 두 오델로플레이어가 선택되었다고 합시다.

가
'...+...', 0.327
'.MM.+EE.', 0.932
'EE+.M..', 0.142
'.MEEE+EE', 0.527
'EMMEE+EM', 0.106
'..EE+EEE', 0.172
'MME+MM..', 0.018
'..E+...', 0.437


나
'.MM.+EE.', 0.762
'..M+...', 0.007
'..EE+EEE', 0.120
'..M.+EE', 0.607
'E+EMME', 0.742
'EMMEE+EM', 0.224


검은색으로 표시된 유전자는 '가'와 '나'에 다 있지만, 붉은색으로 표시된 유전자는 '가'에만, 녹색 유전자는 '나'에만 존재하는 유전자입니다. 이를테면 '나'는 '..E+...'라는 패턴을 만난 적이 없습니다. 만약 '나'가 그 패턴을 만난다면 어떨까요? 규칙에 의해 이 패턴을 랜덤한 가중치와 함께 추가할 것입니다. 그러므로 지금 추가하더라도 상관 없겠죠.
교차를 하기 전에 '가'와 '나'는 서로가 가지고 있는 패턴을 공유합니다.


가
'...+...', 0.327
'.MM.+EE.', 0.932
'EE+.M..', 0.142
'.MEEE+EE', 0.527
'EMMEE+EM', 0.106
'..EE+EEE', 0.172
'MME+MM..', 0.018
'..E+...', 0.437
'..M+...', 0.725
'E+EMME', 0.176


나
'.MM.+EE.', 0.762
'..M+...', 0.007
'..EE+EEE', 0.120
'..M.+EE', 0.607
'E+EMME', 0.742
'EMMEE+EM', 0.224
'...+...', 0.301
'.MEEE+EE', 0.815
'MME+MM..', 0.328
'..E+...', 0.663


즉 '가'와 '나' 둘 다 10개의 동일한 패턴(가중치는 다르지만)을 가진 유전자가 되었습니다.
이후에는 '가'와 '나'에서 동일한 패턴을 꺼내서 50%확률로 가중치를 바꾸면 교차 완료입니다.

function FindPattern(gene, pattern) // gene에서 pattern과 동일한 것 찾음
.. for k := 0, gene.Size do
..... if IsSamePattern(gene.Pair[k].Pattern, pattern) then
........ return k; // 찾았으면 위치 리턴
..... end
.. end
.. return -1;
end

procedure CrossOver(childA, childB)
.. geneA = childA.Gene
.. geneB = childB.Gene
.. for locA := 0, geneA.Size do
..... locB := FindPattern(geneB, geneA.Pair[locA].Pattern
..... if locB == -1 then // 맞는 패턴이 없음, B에 추가
........ geneB.Pair[childB.Gene.Size].Pattern = geneA.Pair[locA].Pattern
........ geneB.Pair[childB.Gene.Size].Weight = Random(0, 1)
........ childB.Gene.Size + childB.Gene.Size + 1
..... end
.. end
.. // 생략 - 동일한 방법으로 B에만 있는 유전자 A에 추가

.. // 교차 시작
.. for locA := 0, geneA.Size do
..... locB := FindPattern(geneB, geneA.Pair[locA].Pattern
......... // 동일한 패턴을 B에서 찾음

..... if Random(0, 1)＜ 0.5 then // 50%확률로 가중치 교환
........ tmp = geneA.Pair[locA].Weight
........ geneA.Pair[locA].Weight = geneB.Pair[locB].Weight
........ geneB.Pair[locB].Weight = tmp
..... end
.. end
end

4.2 돌연변이
돌연변이는 비교적 간단합니다. 오델로플레이어의 모든 유전자를 돌면서 일정확률로 가중치값을 변화시키면 됩니다.

procedure Mutantation(child)
.. for k := 0, child.Gene.Size do
..... if Random(0, 1)＜ 0.001 then
........ child.Gene.Pair[k].Weight = Random(0, 1)
..... end
.. end
end

5. 이주
앞에서 설명한 것처럼, 오델로플레이어들을 공진화시키기 위해 고립된 6개의 무리를 만들어 그 안에서만 번식이 일어나도록 하였습니다. 특히 512개밖에 안되는 무리 안에서만 번식시킨다면 아무리 돌연변이를 적용시키더라도 유전자가 획일화되기 쉽습니다. 그러므로 이렇게 유전적으로 고립시킨 경우에는 가끔씩 일부 개체들을 이주시켜 새로운 유전자를 섞어주는 것이 좋습니다.

procedure Migration()
.. if Generation % 10 == 9 then // 10세대에 한번씩
..... do
........ a := Random(0, 6)
........ b := Random(0, 6)
..... while a == b

..... aa := Random(0, 512)
..... bb := Random(0, 512)
..... tmp = horde[a][aa];
..... horde[a][aa] = horde[b][bb];
..... horde[b][bb] = tmp;
end

GA - 자원운송계획 - 고립과 이주

8. 고립과 이주


갈라파고스 군도의 수많은 섬들에 핀치새들이 살고 있습니다. 그들은 섬 밖의 다른 핀치새들과는 교류가 끊긴채 섬 안의 핀치새들끼리만 짝짓기를 하며 번식했습니다. 그 결과 핀치새들은 섬에 따라 조금씩 다른 형태로 - 다양성을 유지한 채로 - 남아 있습니다.(그림 및 사진 출처)

유전자 알고리즘에서도 다양성을 유지하기 위해 이와 같은 원리 - 고립(isolate)을 사용할 수 있습니다. 커다란 하나의 개체군을 번식시키는 것이 아니라 작은 개체군 여러개를 번식시키는 것이죠.
게다가 가끔씩 일부 개체를 다른 개체군으로 이주(migration)시킨다면, 새로운 유전자를 받아들여 다양성이 더 늘어나는 효과를 얻을 수 있습니다.

이 운송문제에서는 크기 8193의 개체군 하나만을 사용했었습니다. 이번에는 크기 1025의 개체군 8개로 나누어 실행해 보도록 하겠습니다. 그러기 위해서는 메인루틴이 약간 달라지겠군요.

begin
.. declear Horde[8][1025];
.. for k := 0, 8 do
..... for g := 0, 1025 do
........ call Initialize(Horde[k][g]) // 유전자초기화
..... end
.. end

.. for generation := 0, 500 do
..... for k := 0, 8 do
........ // k번째 무리에 대해 적응도 계산
........ for g := 0, 1025 do
........... call FitnessCalc(Horde[k][g])
........ end
........ // k번째 무리 재생산(Elite기법 + T=0.99의 토너먼트법)
........ call Regenerate(Horde[k])
..... end
..... // 일정확률로 개체 이주시킴(바꾸기)
..... if MigrationRate then
........ hordeA := Random(0, 7)
........ hordeB := Random(0, 7)
........ slotA := Random(0, 1024)
........ slotB := Random(0, 1024)
........ call Swap(Horde[hordeA][slotA], Horde[hordeB][slotB])
..... end
.. end
end

9 새로운 결과
8개 그룹별로 최고적응도가 다음과 같이 나왔습니다. 그중에서도 최대적응도는 붉은색으로 처리했습니다.

499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 437/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 2 0 0 0 0 0 0 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 1 0 2 2 0 0 7 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 421/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 4 0 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 0 2 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0

이 경우 연료소모량은 421로 단일개체군일 경우보다 좋은 결과가 나왔다는 것을 알 수 있습니다.