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