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개의 서로 다른 배열을 얻을 수 있습니다.