푸른 소나무숲 - 꿈을 꾸되 늘 깨어 있으라: 8-Queen

레이블이 8-Queen인 게시물을 표시합니다. 모든 게시물 표시

GA - 다도해의 여덟여왕

정말 오랜만에 GA-Genetic Algorithm에 대한 글을 올리는군요. 원래 GA를 중심으로 하려고 만든 블로그인데 어느새 주종이 바뀐듯...^^;

앞에서 한번 여덟여왕문제를 다뤄본 적이 있습니다. 그때는 생태계가 단 하나의 우점종으로 점령되어 버리는 일이 많았기에 그것을 방지하고자 종(種 species)을 관리하는 코드를 삽입했죠.

그런데 자연계에서는 '종을 관리'하는 주체가 없습니다. 그런데도 자연계에서는 이 실험에서처럼 하나의 종이 전체를 점유하는 일이 없습니다. 오히려 하나의 종이 둘로 나뉘는 현상이 종종 보이고 있죠. 이것은 어떤 이유로 인한 생식 격리 때문입니다. 이를테면 너무 먼 거리에 있다거나 산맥이나 바다 등으로 인해 왕래가 불가능해졌기 때문입니다.

그렇다면 이러한 '생식적 격리'를 유전자 알고리즘에 적용해보면 어떨까요?

다음과 같은 넓은 바다에 여러개의 섬이 늘어서 있습니다. 그리고 각 섬마다 하나씩의 GA Creature(주어진 문제를 풀 수 있으며 유전자 알고리즘에 의해 후손을 생산할 수 있는 개체)들이 하나씩 살고 있습니다. 일반적인 유전자 알고리즘에서처럼 이들은 문제를 풀고 적응도를 증가시킵니다.

다도해(archipelago)

번식기(?)가 되면 다음과 같은 순서에 의해 다음 세대를 만듦니다.
1. GA Creature들 중 하나⒡가 암컷이 되어 페로몬을 흗뿌립니다. 이 페로몬은 대양 전체에 퍼지지 않으며 ⒡ 주위 몇개의 섬에만 영향을 미칩니다.
2. 페로몬을 감지한 다른 GA Creature들이 ⒡에게로 몰려들어 경쟁을 벌입니다. 이 경쟁은 다른 유전자 알고리즘의 선택 알고리즘과 동일합니다. 그리하여 우승자 ⒨이 선택됩니다.
3. ⒡와 ⒨이 짝짓기하여 두개의 알을 낳습니다. 이 알 중 하나는 ⒡의 둥지에, 다른 하나는 ⒨이 가져가서 자신의 둥지에 놓습니다.
4. 알을 낳은 ⒡는 다시 수컷으로 돌아가고 다른 GA Creature가 암컷⒡이 되어 페로몬을 뿌립니다.
5. 모든 GA Creature가 한번씩 암컷이 되어 알을 낳을 때까지 반복합니다.
6. 모든 GA Creature는 죽고 알에서 새로운 GA Creature가 태어납니다.

이렇게 되면 어느 하나의 GA Creature가 높은 적응도를 가진다고 해도 이 유전자가 영향을 주는 범위는 페로몬이 퍼지는 영역에 불과합니다. 물론 시간이 지나면 영향력이 점점 늘어나겠지만 그동안에 다른 영역에서 새로운 적응도를 가진 다른 GA Creature가 자랄 수 있기에 다양성이 유지될 수 있습니다.

그런데 위와 같은 경우에는 하나의 GA Creature가 알을 두개씩 낳게 되므로 다음 단계의 GA Creature는 두배로 늘어나게 됩니다. 가외의 알들은 다음과 같이 처리합니다.

7. 알 하나를 부화시킵니다.
8-1. 만약 그 알이 위치한 섬이 비어있다면 부화한 GA Creature는 그 섬에 정착합니다.
8-2. 만약 그 섬에 다른 GA Creature가 있다면 부화한 GA Creature는 주위 임의의 섬으로 이주를 합니다.
8-2-1. 만약 이주한 섬이 비어 있으면 그 섬에 정착합니다.
8-2-2. 만약 이주한 섬에 다른 GA Creature가 있다면 서로 싸워 이긴 쪽이 섬을 차지합니다.

이런 식으로, 앞에서 풀어봤던 여덟여왕문제를 다시 한번 풀어 봤습니다. 섬의 갯수 16384개에 종 관리코드는 생략하고 풀어본 결과입니다.

최적의 배치(Best Board)는 이미 10세대때 발견되었습니다. 종을 관리하지 않는 알고리즘이라면 얼마 안 있어 이 최초의 Best Board가 전체 16384개 개체들을 모두 차지하게 되었을 겁니다.
그런데 각 세대의 Best Board 종류는 약 30~35개 사이에서 계속 유지되고 있음을 알 수 있습니다. 즉 따로 종을 나누는 기준을 정하고 종의 인구수를 관리하지 않더라도 다양성이 유지되고 있다는 것을 알 수 있습니다.
Accumulate는 500세대가 지나는 동안 나타났던 모든 Best Board(전멸했던 것을 포함해서)들을 모아놓은 숫자입니다. 500세대 동안 46개의 Best Board를 발견했다는 것입니다(물론 92가지 Best Board들에는 모자라지만 말입니다).
발견된 Best Board들은 다음과 같습니다.

. . . @ . . . . . . . @ . . . . . . . . . . . @ @ . . . . . . .
. @ . . . . . . . . . . . . . @ . @ . . . . . . . . . . . . @ .
. . . . . . . @ @ . . . . . . . . . . @ . . . . . . . . @ . . .
. . . . . @ . . . . . . @ . . . @ . . . . . . . . . . . . . . @
@ . . . . . . . . . . . . . @ . . . . . . . @ . . @ . . . . . .
. . @ . . . . . . @ . . . . . . . . . . @ . . . . . . @ . . . .
. . . . @ . . . . . . . . @ . . . . @ . . . . . . . . . . @ . .
. . . . . . @ . . . @ . . . . . . . . . . @ . . . . @ . . . . .

. . . . . @ . . . . . @ . . . . . . . . . . @ . . . . . @ . . .
. . @ . . . . . . @ . . . . . . @ . . . . . . . . @ . . . . . .
@ . . . . . . . . . . . . . @ . . . @ . . . . . . . . . . @ . .
. . . . . . @ . . . . . @ . . . . . . . . . . @ @ . . . . . . .
. . . . @ . . . @ . . . . . . . . . . . . @ . . . . . . . . @ .
. . . . . . . @ . . . . . . . @ . . . @ . . . . . . . @ . . . .
. @ . . . . . . . . . . . @ . . . @ . . . . . . . . . . . . . @
. . . @ . . . . . . @ . . . . . . . . . @ . . . . . @ . . . . .

. @ . . . . . . . . . . @ . . . . . @ . . . . . . . . @ . . . .
. . . @ . . . . . . @ . . . . . . . . . @ . . . . . . . . . @ .
. . . . . @ . . @ . . . . . . . . . . . . . @ . . . . . @ . . .
. . . . . . . @ . . . . . . @ . @ . . . . . . . . . @ . . . . .
. . @ . . . . . . @ . . . . . . . . . @ . . . . @ . . . . . . .
@ . . . . . . . . . . . . . . @ . @ . . . . . . . . . . . @ . .
. . . . . . @ . . . . . . @ . . . . . . . . . @ . . . . . . . @
. . . . @ . . . . . . @ . . . . . . . . . @ . . . @ . . . . . .

. . . . @ . . . . . @ . . . . . . @ . . . . . . . . . . . @ . .
. . @ . . . . . . . . . . @ . . . . . . . . . @ . . . @ . . . .
@ . . . . . . . . . . . . . . @ . . . . . @ . . @ . . . . . . .
. . . . . @ . . . @ . . . . . . @ . . . . . . . . . . . @ . . .
. . . . . . . @ . . . @ . . . . . . @ . . . . . . . . . . . . @
. @ . . . . . . @ . . . . . . . . . . . @ . . . . @ . . . . . .
. . . @ . . . . . . . . . . @ . . . . . . . @ . . . . . . . @ .
. . . . . . @ . . . . . @ . . . . . . @ . . . . . . @ . . . . .

. . . . @ . . . . @ . . . . . . . . @ . . . . . . . . . . @ . .
. . . . . . @ . . . . . @ . . . @ . . . . . . . . . . . . . . @
@ . . . . . . . . . . . . . @ . . . . . . . @ . . @ . . . . . .
. . . @ . . . . @ . . . . . . . . . . . @ . . . . . . @ . . . .
. @ . . . . . . . . @ . . . . . . . . . . . . @ @ . . . . . . .
. . . . . . . @ . . . . . . . @ . @ . . . . . . . . . . . . @ .
. . . . . @ . . . . . . . @ . . . . . @ . . . . . . . . @ . . .
. . @ . . . . . . . . @ . . . . . . . . . @ . . . . @ . . . . .

. . . . . . @ . . . @ . . . . . . . . . . . . @ . . . . . @ . .
. . . @ . . . . . . . . . @ . . . @ . . . . . . . . @ . . . . .
. @ . . . . . . . . . @ . . . . . . . . @ . . . . . . . @ . . .
. . . . . . . @ . @ . . . . . . . . @ . . . . . . . . . . . @ .
. . . . . @ . . . . . . . . . @ @ . . . . . . . @ . . . . . . .
@ . . . . . . . . . . . @ . . . . . . . . . @ . . . . @ . . . .
. . @ . . . . . . . . . . . @ . . . . @ . . . . . @ . . . . . .
. . . . @ . . . @ . . . . . . . . . . . . @ . . . . . . . . . @

. . @ . . . . . . . . . @ . . . . @ . . . . . . . . . . . @ . .
. . . . . . @ . . @ . . . . . . . . . . . . @ . . . . @ . . . .
. @ . . . . . . . . . @ . . . . . . @ . . . . . . . . . . . @ .
. . . . . . . @ . . . . . @ . . . . . . . @ . . @ . . . . . . .
. . . . @ . . . . . . . . . . @ . . . . . . . @ . . @ . . . . .
@ . . . . . . . . . @ . . . . . . . . . @ . . . . . . . @ . . .
. . . @ . . . . @ . . . . . . . @ . . . . . . . . @ . . . . . .
. . . . . @ . . . . . . . . @ . . . . @ . . . . . . . . . . . @

. . . @ . . . . @ . . . . . . . . . . . . . @ . . . . @ . . . .
@ . . . . . . . . . . . @ . . . . . . . @ . . . . @ . . . . . .
. . . . @ . . . . . . . . . . @ . . @ . . . . . . . . . . . @ .
. . . . . . . @ . . . . . @ . . @ . . . . . . . . . @ . . . . .
. . . . . @ . . . . @ . . . . . . . . . . @ . . . . . . . @ . .
. . @ . . . . . . . . . . . @ . . . . . . . . @ . . . . . . . @
. . . . . . @ . . @ . . . . . . . @ . . . . . . . . . . @ . . .
. @ . . . . . . . . . @ . . . . . . . @ . . . . @ . . . . . . .

. . . @ . . . . . . . @ . . . . . . . . . @ . . . . . @ . . . .
. . . . . @ . . . @ . . . . . . . . @ . . . . . @ . . . . . . .
. . . . . . . @ . . . . . . . @ . . . . . . @ . . . . . @ . . .
. . @ . . . . . . . . . @ . . . . @ . . . . . . . . . . . . . @
@ . . . . . . . . . . . . . @ . . . . . . . . @ . @ . . . . . .
. . . . . . @ . @ . . . . . . . . . . . @ . . . . . . . . . @ .
. . . . @ . . . . . @ . . . . . @ . . . . . . . . . @ . . . . .
. @ . . . . . . . . . . . @ . . . . . @ . . . . . . . . . @ . .

. @ . . . . . . . . . . @ . . . . . @ . . . . . . . @ . . . . .
. . . . . @ . . . . . . . . @ . . . . . @ . . . . . . . . . . @
@ . . . . . . . @ . . . . . . . . @ . . . . . . . . . @ . . . .
. . . . . . @ . . . @ . . . . . . . . . . . . @ . . . . . . @ .
. . . @ . . . . . . . . . . . @ . . . . . @ . . @ . . . . . . .
. . . . . . . @ . . . . . @ . . . . . @ . . . . . . . . . @ . .
. . @ . . . . . . . . @ . . . . . . . . . . @ . . @ . . . . . .
. . . . @ . . . . @ . . . . . . @ . . . . . . . . . . . @ . . .

. . . . . @ . . @ . . . . . . . . . . @ . . . . . . . . . . . @
. . . @ . . . . . . . . . . @ . . . . . . . @ . . . @ . . . . .
. @ . . . . . . . . . @ . . . . . . @ . . . . . @ . . . . . . .
. . . . . . . @ . . . . . @ . . . . . . . . . @ . . . . . @ . .
. . . . @ . . . . . . . . . . @ . @ . . . . . . . @ . . . . . .
. . . . . . @ . . @ . . . . . . . . . . @ . . . . . . . @ . . .
@ . . . . . . . . . . . @ . . . @ . . . . . . . . . . . . . @ .
. . @ . . . . . . . @ . . . . . . . . . . @ . . . . . @ . . . .

. . . . @ . . . . . . @ . . . .
. . @ . . . . . . . . . . . @ .
. . . . . . . @ . . . . @ . . .
. . . @ . . . . . @ . . . . . .
. . . . . . @ . . . . . . @ . .
@ . . . . . . . @ . . . . . . .
. . . . . @ . . . . @ . . . . .
. @ . . . . . . . . . . . . . @

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

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

GA - 여덟여왕문제(8-Queen's Problem)[1] - 유전자설계, 초기화

체스판 위에 여왕이 서 있습니다. 아시다시피 체스에서의 여왕은 가로, 세로, 대각선으로 진행할 수 있습니다. 만약 체스판 위에 8명의 여왕이 서 있을 경우, 그 여왕들이 서로의 진로를 방해하지 않도록 자리를 잡으려면 어떻게 해야 할까 하는 문제가 8-Queen's Problem이죠.
이 문제의 한가지 해답은 다음과 같습니다.

하지만 이 문제의 해법은 단 하나가 아닙니다. 유전자 알고리즘을 사용해서 이 문제의 해를 (가능한 한 많이) 찾는 것이 목적입니다.

이 문제는 사실은 n-Queen's Problem입니다. 즉 가로세로 n간인 체스판 위에 서로의 진로를 방해하지 않는 n명의 여왕의 자리를 찾는 문제죠. 여기서는 n=8일 경우만 하겠지만 더 크거나 작은 경우 역시 같은 방식으로 찾을 수 있습니다.

1. 유전자 설계
체스판 위에 8명의 여왕 위치를 유전자화시키는 방법은 무엇이 있을까요?

1-1 절대위치지정
가장 간단한 방법이죠. 단순히 8명 여왕의 위치를 좌표로 나열하는 방법입니다.
이를테면, 유전자가
[(7,4)(3,5)(2,6)(4,1)(0,6)(3,5)(3,7)(6,0)]
일 경우, 여왕들은 다음과 같은 자리를 잡게 됩니다. (3, 5)번째 칸에는 두 여왕이 같이 서 있군요.

1-2 상대위치지정
상대위치지정법은 각 좌표가 절대좌표가 아니라 바로 앞 여왕으로부터의 상대좌표를 의미합니다. 만약 유전자가
[(2,3)(-1,4)(-3,1)(6,-2)(3,-5)(-2,1)(-1,4)(4,-2)]
일 경우 여왕들의 자리는 ((0,0)부터 출발해서) 다음과 같이 됩니다. 역시 (4,6)에는 두 여왕이 겹쳐 있군요.

그렇다면 위에서 제시된 절대위치지정법과 상대위치지정법 중에서 어떤 것을 쓰는 것이 좋을까요?

유전자설계시 조심해야 할 점은 '교차시 더 좋은 유전자가 나오도록' 설계를 해야 한다는 점입니다. 이 문제의 핵심은 '다른 여왕의 진로를 방해하지 않는' 위치를 찾는 것입니다. 그러므로 각 여왕 들의 절대적인 위치보다는 각 여왕 사이의 상대적인 위치가 보다 중요합니다. 그러므로 상대위치지정을 했을 경우 교차를 적용한 후에도 앞쪽 퀸의 위치에 따라 자신의 위치가 재조정되므로 교차에 의해 적응도가 줄어드는 현상이 줄어들 수 있습니다.
그러므로 이 문제에서는 상대위치를 지정하는 유전자를 쓰기로 했습니다.

2. 유전자 초기화
하나의 하렘(Harem : 왕비(Queen)들이 모여있는 곳이니...^^ Queen에는 여왕이란 뜻 외에 왕비란 뜻도 있죠.) 유전자는 8쌍의 (dx,dy)로 구성됩니다. 각각의 dx, dy에 임의의 값을 넣어 최초의 하렘을 만들 수 있습니다.

procedure InitGene(Gene gene)
.. for bit := 0, 8 do

..... gene[bit].dx = Random(-4, 5) // -4~4 사이의 랜덤값

..... gene[bit].dy = Random(-4, 5) // -4~4 사이의 랜덤값

.. end

end

16384개의 하렘을 만들어 위와 같은 알고리즘으로 초기화시킨 후 각 하렘들에 대해 유전자 알고리즘을 적용합니다.

읽혀주고 싶은 글타래