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-Queen's Problem)[2] - 재생산

3. 적응도 계산
역시 자세한 알고리즘은 생략하겠습니다. 각각의 하렘들의 유전자에 따라 여왕들을 배치한 후 각각의 여왕들에 대해 진로를 가로막고 있는 다른 여왕이 있는지 살핍니다. 자신의 진로 위에 다른 여왕이 있을 때마다 ConflictNumber를 하나씩 더합니다. 만약 다른 여왕이 같은 자리를 차지하고 있을 경우, 그 여왕은 가로, 세로, 양쪽 대각선(2~7시방향, 11~5시방향) 네 진로에 걸리므로 ConflictNumber가 4 증가됩니다.
이 하렘의 전체 적응도는 -ConflictNumber가 됩니다(결국 이 문제도 -적응도를 가지게 되었군요)

4. 재생산 대상 선택
앞에서와 같이 Tournament법을 사용했습니다. 다만 여기서는 4차 Tournament법을 사용했습니다.

난수를 통해 16개의 재생산 후보를 골라냅니다. 그리고 이 16개의 후보들을 토너먼트 방식(일반적인 Tournament법과 같이, 0~1 사이의 난수를 발생시켜, 상수 T보다 작으면 적응도가 큰쪽, 상수 T보다 크면 적응도가 작은 쪽이 승자)으로 계속 경쟁시켜 최후의 승자를 재생산 후보로 결정합니다.

5. 교차

여기서는 유전자에 대한 특정한 제한이 없으므로 일반적인 교차를 사용할 수 있습니다. 이 문제에서는 랜덤교차를 사용했습니다.
다만 이경우에, '유전자의 최소단위'가 어떻게 될지 생각해 보는 것이 좋겠군요.

㉠:[(-2/ 1)( 1/ 2)(-3/ 2)(-3/-2)(-3/ 1)( 2/ 3)(-1/ 3)(-2/-1)]
㉡:[(-2/ 1)( 1/ 2)(-2/ 3)( 3/ 2)( 2/-1)(-1/-3)( 3/-2)(-1/ 3)]

위와 같은 두 유전자를 교차시킨다고 생각해 봅시다. 만약

㉠:[(-2/ 1)( 1/ 2)(-3/ 3)( 3/ 2)( 2/-1)(-1/-3)( 3/ 3)(-2/-1)]
㉡:[(-2/ 1)( 1/ 2)(-2/ 2)(-3/-2)(-3/ 1)( 2/ 3)(-1/-2)(-1/ 3)]

와 같이 교차를 시켰다면, ㉠의 (-3/ 3), ( 3/ 3), ㉡의 (-2/ 2)는 (재생산 전에는 앞의 퀸과 부딫치지 않는 위치였음에도) 앞의 퀸과 충돌하는 위치가 되어 버립니다. 그러므로 이 경우에 유전자의 최소단위(bit)는 () 안의 요소가 되어야 합니다.
이 문제에서는 랜덤교차를 사용했으므로 교차 후의 결과는

㉠:[(-2/ 1)( 1/ 2)(-2/ 3)(-3/-2)( 2/-1)( 2/ 3)(-1/ 3)(-2/-1)]
㉡:[(-2/ 1)( 1/ 2)(-3/ 2)( 3/ 2)(-3/ 1)(-1/-3)( 3/-2)(-1/ 3)]

가 될 수 있습니다.

procedure CrossOver(Harem A, Harem B)
.. for k := 0, 8 do
..... if Random(0, 1) > 0.5 then
........ dx := A.gene[k].dx
........ dy := A.gene[k].dy
........ A.gene[k].dx := B.gene[k].dx
........ A.gene[k].dy := B.gene[k].dy
........ B.gene[k].dx := dx
........ B.gene[k].dy := dy
..... end
.. end
end

6. 돌연변이
여기서는 0.0001 확률로 돌연변이시킵니다. 단 이경우에는 dx와 dy에 대해 따로 돌연변이를 시킵니다.

procedure Mutantation(Harem A)
.. for k := 0, 8 do
..... if 0.0001 > Random(0, 1) then
........ A.gene[k].dx := Random(-4, 5) // -4~4 사이의 랜덤값
..... end
..... if 0.0001 > Random(0, 1) then
........ A.gene[k].dy := Random(-4, 5) // -4~4 사이의 랜덤값
..... end
.. end
end

GA - 장사꾼여행문제(TSP) [2] - 유전자 초기화, 재생산

2. 유전자 초기화

일반적으로 유전자를 초기화하기 위해서는 유전자의 각 비트에 랜덤값을 넣으면 되지만, 이 경우에는 앞에서 말한 유전자의 제약 때문에 무조건 랜덤값을 넣을 수는 없습니다. 만약 도시 10개짜리 보기에서 유전자에 랜덤값을 넣어 5042852301란 유전자를 만들었다면, 이 유전자는 0번, 2번, 5번 도시는 두번씩, 6번, 7번, 9번 도시는 방문하지 않는 잘못된 유전자가 만들어집니다.

그러므로 이 경우에는 카드섞기 방법으로 초기화를 해야 합니다.

procedure InitGene(Gene gene)
.. // 0~149까지의 도시를 하나씩 넣음

.. for bit := 0, 150 do

..... gene[bit] := bit

.. end

.. //배열을 뒤섞음

.. for bit := 0, 150 do

..... exchange := Random(0, 150)

..... temp := gene[bit]

..... gene[bit] := gene[exchange]

..... gene[exchange] := temp

.. end

end

이와 같이 하면 150개의 도시에 대해 중복이나 결실 없는 무작위순열을 얻을 수 있습니다.

3. 적응도테스트 및 적응도

적응도를 계산하는 자세한 알고리즘은 생략하겠습니다. 유전자에 그려진 도시순서대로 한바퀴 돌며 이동하는 도시와 도시 사이의 거리를 합산하면 됩니다.

다만, 이경우에는 도시사이의 거리와 적응도는 역관계입니다. 거리가 길수록 적응도가 낮아지기 때문입니다. 여기서는 단순하게 적응도 = -(거리의 총합)으로 정의했습니다. 이렇게 하면 모든 적응도는 음수가 되긴 합니다만, 룰렛법을 사용할 수 없다는 점 이외에는 아무런 차이가 없습니다. 혹시 음수적응도가 마음에 안든다면, 가장 긴 이동거리를 가진 도시를 찾아서 (가장 긴 이동거리) - (거리의 총합) 으로 해도 됩니다. 이렇게 하면 적응도가 가장 떨어지는 개체가 0, 나머지는 양수의 적응도를 가질 수 있습니다.


4. 재생산대상 선택

다음 단계는 각자의 적응도에 따라 재생산할 대상을 고를 차례입니다. 윗 항에서처럼 적응도가 0보다 작으니 룰렛법을 사용할 수는 없지만 앞에서 사용했던 재계산법이나 순위법을 사용할 수는 있습니다.
하지만 이 문제에서는 새로운 선택법 - Tournament법을 사용하겠습니다.

토너먼트법이란, 일단 0과 1 사이의 수 T를 정합니다.
재생산 대상을 선택하기 위해 먼저 두개의 개체를 랜덤하게 정합니다. 그 둘 중 적합도가 높은 것을 Shigh, 적합도가 낮은 것을 Slow라 합니다.
다시한번 0과 1 사이의 랜덤값 r을 발생시킵니다. 그리고 r이 T보다 작다면 Shigh를, r이 T보다 크다면 Slow를 선택하는 방법입니다.

말로 해서 복잡한데, 알고리즘은 다음과 같습니다.

function SelectParent(double T)
.. // 임의의 두 개체 선택 후 Shigh에 적합도가 높은것, Slow에 적합도가 낮은 것을 나누어 넣음
.. A := Random(0, 150)
.. B := Random(0, 150)
.. if Salesman[A].fitness > Salesman[B].fitness then
..... Shigh := A
..... Slow := B
.. else
..... Shigh := B
..... Slow := A
.. end
.. // 다시한번 랜덤값 만듦
.. r = Random(0.0, 1.0) // 0~1 사이의 실수형 랜덤값 얻음
.. if T > r then
..... return Salesman[Shigh]
.. else
..... return Salesman[Slow]
end
이때 T는 0.5 이상의 값을 선택해야 합니다. 만약 0.5 이하라면 오히려 적합도가 낮은 것이 선택될 확률이 커지죠.
일반적으로 T가 클수록 선택압이 높아져 빨리 수렴하는 대신 해의 품질이 떨어지는 경향이 있습니다. 반대로 T가 작다면 수렴속도가 느려지죠.
사실 토너먼트법은 그다지 선택압이 높은 방법이 아닙니다. 개체군의 크기(전체 개체군 수)를 N이라 한다면, 최고적합도를 가진 개체가 선택될 확률은 2(1/N * T)에 불과합니다.

여기서는 단순하게 2개의 개체를 선택했지만, 2n개의 개체를 선택한 후 토너먼트식 대결을 계속하여 최후의 승자를 선택하는 방법도 있습니다.

5. Elitism

엘리트주의란, 최대 적합도를 가진 개체를 보호하는 알고리즘입니다. 일반적인 재생산 과정은 두 개체의 유전자를 섞어 새로운 유전자를 만드는 것이므로, 최대적합도의 유전자가 선택되더라도 그 유전자가 다음 세대에 그대로 복제되지는 않습니다. 앞에서의 꼬마자동차 보기에서와 같이, 영웅이 탄생하더라도 다음 대에서는 일단 사라졌다가 영웅의 부분유전자들이 어느정도 증식한 후에야 다시 나타납니다. 엘리티즘은 이러한 현상을 막기 위해 최대적합도를 가진 개체를 다음세대에 복제하는 것을 말합니다.
엘리티즘을 잘못 사용하면 계속 복제되는 엘리트가 계속 재생산대상으로 선택되어 다양성이 훼손되는 결과가 생길 수 있습니다. 하지만 이 TSP에서는 토너먼트법이 워낙 선택압이 낮은 관계로 엘리티즘을 추가했습니다.

한 세대의 개체수는 30001개로 정의했습니다. 그중 하나는 전세대의 가장 우수한 개체를 복제하고, 나머지 30000개는 토너먼트방식으로 교차와 돌연변이를 통해 만듦니다.

엘리티즘을 포함한다면 유전자 알고리즘의 순서도에서 다음 부분이 바뀌어야 합니다.

..... T := 0.9 // 이 값은 변화 가능..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... store maxfitness to nextgeneration//전세대에서 최대적합도를 가진 개체를 그대로 넣음
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do........... a := SelectParent(T) // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent(T) // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행