GA - 여덟여왕문제(8-Queen's Problem)[4] - 마무리

8-Queen Problem의 최종해답은 다음과 같습니다.(출처)


보시다시피 12가지 배열이 존재합니다. 그리고 저 배열들의 회전, 거울상이동 등을 허용한다면 총 92가지 배열이 가능합니다.
앞의 문제에서 종을 판단할때 회전같은 변환은 하지 않았습니다. 그렇다면 이론적으로 92개의 종이 나와야 하겠죠.

앞의 TSP에서도 마찬가지였지만, 유전자알고리즘이라는 것이 랜덤함수에 의존하는 면이 있습니다. 답을 쉽게 찾는 대신 원하는 답을 찾기가 힘들다고나 할까요?

'답을 찾아라'같은 문제라면 유전자알고리즘이 효과적입니다.
'가능한한 많은 답을 찾아라'라는 문제도 (아쉬운 대로) 유전자알고리즘으로 찾을 수 있습니다.
'모든 답을 찾아라'라면 유전자알고리즘으로서는 무리가 따름니다. 이 문제의 경우 92개의 답을 모두 찾아도 93번째 답은 없다는 것을 유전자알고리즘으로는 알 수 없기 때문입니다.

참고로 만약 유전자알고리즘으로 가능한한 많은 답을 찾기 위해서는 다음과 같은 방식을 사용하는 것이 좋습니다.
㉠ 가능한한 개체수를 많이 만들어 실행시킵니다. 개체수가 많을수록 다양성이 커져 더 많은 답을 찾을수 있습니다.
㉡ srand로 랜덤함수를 바꾸어가며 여러번 실행시킵니다.

지적설계론은 지적설계자를 모욕하는 행위 - 팬더의 엄지

작고하신 스티브 굴드의 '팬더의 엄지'로 유명해진 팬더의 엄지 이야기입니다.
팬더의 손가락을 보면 오른쪽 그림과 같이 손가락이 여섯개임을 알 수 있습니다. 하지만 해부학적으로 봤을때 손가락은 다섯개 뿐입니다. 엄지손가락은 손의 종자골이 변형되어 튀어나온 것입니다. 이 새로운 엄지손가락 덕분에 팬더는 주식인 대나무를 손으로 잡아서 먹을 수 있는 것이죠.

하지만 여기서 한가지 의문점이 생깁니다. 만약 창조주가 팬더에게 엄지손가락을 주려고 했다면 왜 영장류와 같은 엄지손가락을 주지 않았을까요? 왜 애매한 뼈를 억지로 변형시켜, 엄지손가락이 아닌 '엄지손가락 같은' 손가락을 주었을까요?

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