GA - 여덟여왕문제(8-Queen's Problem)[3] - 종(種) 유지

7. 종(種) 분류에 의한 다양성 유지

유전자 알고리즘시의 다양성을 유지하기 위한 한가지 방법으로 개체를 종으로 분류하여 관리하는 방법이 있습니다. 즉, 한 세대의 개체들이 각각 어느 종에 속해 있는지 결정한 후 그 종의 숫자가 클수록 패널티를 주는 것입니다. 앞에서 나왔던 것처럼 어느 한 개체가 다수를 점하게 되어 그 종의 개체수가 늘어나면 그만큼 적응도가 낮아져 재생산대상으로 선택될 가능성이 줄어듧니다. 그때문에 다른 종의 개체들이 살아남을 수 있도록 하는 - 다양성을 유지하도록 하는 것입니다.

7-1. 종 결정
우선 매 세대마다 각각의 개체(하렘)가 어느 종에 속하는지 확인해야 합니다. 그리고 각각의 종에 대해서 개체수가 몇개인지 확인해야 합니다. 다음 알고리즘에서 Dictionary는 지금까지 발견된 모든 종을 가지고 있는 리스트입니다.
매 세대 적응도를 계산하기 전 Dictionary의 모든 population을 0으로 클리어한 후 모든 Harem에 대해 다음 프로시저를 호출, 어떤 종에 속하는지, 그리고 각 종의 개체수는 얼마인지를 계산해야 합니다.

procedure SpeciesIdentify(Harem A)
.. for k := 0, Dictionary.size do
..... if SameSpacies(Dictionary[k].sample, A) then // A가 k번째 샘플과 같은 종일 경우
........ A.species = k // A가 k번째 종이라고 설정
........ Dictionary[k].population := Dictionary[k].population + 1 // 개체수 증가
........ return
..... end
.. end
.. // 어떤 종인지 확인 못했음 - 새로 발견된 종
.. AddElement(Dictionary) // Dictionary에 새로운 종을 등록하기 위해 원소 하나 추가
.. Dictionary[k].sample := A // k번째 종을 묘사하기 위한 샘플 저장
.. Dictionary[k].population := 1 // 하나가 발견되었으므로 1로 세팅
.. A.species = k // A가 k번째 종이라고 설정
end

SameSpacies함수는 생략하겠습니다. 간단히 말하자면 sample과 A의 각각 유전자대로 8*8의 체스판 위에 여왕들을 올려놓은 후 두 배열이 같은지를 확인합니다. 만약 모든 여왕들이 동일한 위치에 서 있다면 둘은 같은 종입니다.

7-2 종의 개체수에 따른 적응도(Fitness) 보정
앞에서 각 하렘의 여왕들이 서로를 방해하는 경우의 수 ConflictNumber를 구한후 -ConflictNumber를 적응도로 간주했습니다. 여기서는 이 하렘이 속한 종의 개체수를 보정해 주어야 합니다. 즉 이 경우에

function Fitness(Harem A)
.. species_ID := A.species
.. species_population := Dictionary[species_ID].population
.. return -A.ConflictNumber - species_population / 10
end

즉, 종의 개체수가 10 증가할 때마다 적응도는 1씩 감소하는 형태가 됩니다.

8. 최종결과

Generation : 499 : 24
[11](-1/3)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * . Q .
. * . Q . * . *
* Q * . * . * .
. * . * . * . Q
* . * . * Q * .
Q * . * . * . *
* . Q . * . * .
. * . * Q * . *

[41](-2/2)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . Q . * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *
* . * . * . * Q
. Q . * . * . *
* . * Q * . * .
. * . * . Q . *

[55](3/-2)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . Q . * .
. * . * . * Q *
Q . * . * . * .
. * Q * . * . *
* . * . * . * Q
. * . * . Q . *
* . * Q * . * .
. Q . * . * . *

[14](3/-3)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * . Q .
Q * . * . * . *
* . Q . * . * .
. * . * . * . Q
* . * . * Q * .
. * . Q . * . *
* Q * . * . * .
. * . * Q * . *

[51](-3/0)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * Q * .
. * . Q . * . *
* . * . * . Q .
Q * . * . * . *
* . Q . * . * .
. * . * Q * . *
* Q * . * . * .
. * . * . * . Q

[46](-3/-1)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . * . * Q
. Q . * . * . *
* . * . Q . * .
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *
* . * Q * . * .
. * . * . Q . *

[32](-2/1)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *
* . * . * Q * .
. * Q * . * . *

[46](-2/3)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * Q * .
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *

[55](3/1)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* Q * . * . * .
. * . Q . * . *
* . * . * Q * .
. * . * . * . Q
* . Q . * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *

[23](-1/2)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * Q * . * .
. Q . * . * . *
* . * . * . * Q
. * . * . Q . *
Q . * . * . * .
. * Q * . * . *
* . * . Q . * .
. * . * . * Q *

[53](3/-1)(1/2)(-2/3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* Q * . * . * .
. * . * Q * . *
* . * . * . Q .
Q * . * . * . *
* . Q . * . * .
. * . * . * . Q
* . * . * Q * .
. * . Q . * . *

[20](-3/1)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . Q . * . * .
. * . * . Q . *
* . * . * . * Q
. Q . * . * . *
* . * Q * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *

[28](-2/-2)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . Q . * . * .
. * . * Q * . *
* Q * . * . * .
. * . * . * . Q
* . * . * Q * .
. * . Q . * . *
* . * . * . Q .
Q * . * . * . *

[41](3/0)(-3/2)(1/3)(3/2)(2/-1)(1/3)(-2/3)(-3/-1)
* . * Q * . * .
. * . * . * . Q
Q . * . * . * .
. * Q * . * . *
* . * . * Q * .
. Q . * . * . *
* . * . * . Q .
. * . * Q * . *

[6](3/2)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . Q . * .
. Q . * . * . *
* . * Q * . * .
. * . * . Q . *
* . * . * . * Q
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *

[10](-3/-1)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * . * Q
. Q . * . * . *
* . * Q * . * .
Q * . * . * . *
* . * . * . Q .
. * . * Q * . *
* . Q . * . * .
. * . * . Q . *

[36](3/0)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * Q * . * .
. * . * . Q . *
* . * . * . * Q
. * Q * . * . *
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. Q . * . * . *

[11](-1/-3)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . * . Q .
. * . * Q * . *
* . Q . * . * .
Q * . * . * . *
* . * . * Q * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *

[38](-3/0)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* . * . * Q * .
. * . * . * . Q
* Q * . * . * .
. * . Q . * . *
Q . * . * . * .
. * . * . * Q *
* . * . Q . * .
. * Q * . * . *

[28](-1/-2)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * Q * . * .
. * . * . * Q *
* . * . Q . * .
. * Q * . * . *
Q . * . * . * .
. * . * . Q . *
* . * . * . * Q
. Q . * . * . *

[9](-2/-3)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . * . * Q * .
. * . Q . * . *
* Q * . * . * .
. * . * . * . Q
* . * . Q . * .
. * . * . * Q *
Q . * . * . * .
. * Q * . * . *

[21](-1/-2)(-3/2)(1/3)(3/2)(2/-1)(1/3)(-2/3)(-3/-1)
* . * . Q . * .
. * . * . * Q *
* Q * . * . * .
. * . * . Q . *
* . Q . * . * .
Q * . * . * . *
* . * . * . * Q
. * . Q . * . *

[7](0/3)(-1/-2)(-1/-3)(3/2)(2/-1)(-1/-3)(3/-2)(-1/3)
* Q * . * . * .
. * . * . * . Q
* . * . * Q * .
Q * . * . * . *
* . Q . * . * .
. * . * Q * . *
* . * . * . Q .
. * . Q . * . *

[13](-2/-2)(2/1)(-1/-3)(2/-1)(2/-1)(1/3)(-2/3)(3/1)
* . Q . * . * .
. * . * . Q . *
* . * Q * . * .
. Q . * . * . *
* . * . * . * Q
. * . * Q * . *
* . * . * . Q .
Q * . * . * . *


위의 결과에서 볼 수 있듯이 500세대 후 총 24개의 서로 다른 배열을 얻을 수 있습니다.

GA - 여덟여왕문제(8-Queen's Problem)[3] - 다양성에 대하여

6. 1차결과

앞에서 나온 대로 교차와 돌연변이를 실행하여 16384개의 하렘을 500세대동안 진화시켰습니다.
그 결과는 다음과 같습니다.

Generation : 499 : 1
[16349](0/-3)(3/2)(-2/3)(3/2)(2/-1)(1/3)(-2/3)(-3/-1)
* . Q . * . * .
. * . * . Q . *
* Q * . * . * .
. * . * . * Q *
* . * . Q . * .
Q * . * . * . *
* . * . * . * Q
. * . Q . * . *

.은 체스판의 흰 칸, *은 검은 칸, Q는 여왕이 위치한 자리입니다. 분명히 찾긴 찾았는데... 전체 16384개의 하렘들 중 동일한 하렘이 16349개나 생겼군요. 다양성이 완전히 훼손되고 말았습니다. 왜 이런 결과가 나왔을까요?

다른 형태의 해답 A, B, C, D가 유전자 알고리즘에 의해 생겼다고 해 봅시다. 개체 비율은 다음과 같다고 가정해 보죠.

A	B	C	D
25.01%	25%	25%	24.99%

재생산시 A, B, C, D는 동일한 적응도를 가지므로 각각이 선택될 확률은 각각의 개체비율과 동일합니다. 이때 A와 A가 만나 교배를 한다면 A가 다시 나오겠죠. A와 B가 만나 교배를 한다면, 이미 나온 답을 섞으면 그것은 엉뚱한 해답, 곧 낮은 적응도를 가진 개체가 나올 것입니다.
즉, 다음세대에 A가 나올 확률은 전세대의 A가 선택될 확률의 제곱이 됩니다(A가 두개 선택되어야 교배결과 A가 나오므로). 그러므로 다음 세대 각 개체의 비율은

A	B	C	D
6.255001%	6.25%	6.25%	6.245001%
25.02%	25%	25%	24.98%

약간 많던 A의 개체비율은 더 올라갔고(25.01%->25.02%) 반대로 약간 적던 D의 개체비율은 더 떨어졌습니다(24.99%->24.98%). 이런 식으로 해서 세대가 반복되면 다음 그림과 같이 불과 20세대도 지나기 전에 A가 전체를 차지해 버립니다.


즉 불과 0.01% 우세였던 개체가 자신과 같은 점수였던 다른 개체들을 밀어내고 혼자 전체를 차지해 버리는 것이죠.

그렇다면 어떻게 해야 이 시스템의 다양성을 유지하여 많은 해답을 구할 수 있을까요?

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