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