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들은 다음과 같습니다.


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



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



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



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



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



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



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



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



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



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



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



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