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


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



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



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



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



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



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



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



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



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



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



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



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

창조론 이야기 - 진화의 정지?

유전자 알고리즘의 원리를 먼저 설명하겠습니다.

위와 같은 함수의 최소값을 유전자알고리즘으로 구하는 방법입니다.


우선 일정한 범위에서 랜덤한 값을 취한 후 함수값을 계산합니다.

위와 같이 6개의 랜덤값이 나온 경우 (지금 찾으려는 것이 최소값이므로) 함수값이 최소인 나를 고릅니다. 그리고 나를 번식(재생산 및 돌연변이)시킵니다. 즉 2세대의 값은 나를 중심으로 나 근처에 분포하게 됩니다.

여기서도 최소값인 가를 번식시킨다면 3세대는 가를 중심으로 분포합니다.

이러한 작업을 반복하면 수치들은 최소값에 모이게 되며, 마침내는 함수의 최소값 주위에 옹기종기 모여있는 모습을 발견할 것입니다^*.

그런데, 최초에 랜덤값의 분포가 다음과 같다면 어떨까요?

이 경우에는, 선택된 점들 중 최소값은 마입니다. 결국 마를 중심으로 재생산을 하기에, 다음세대는

가 되며, 결국 이 경우에는 최소값이 아닌 극소값 - 전체적인 최적은 아니지만 근방에서의 최적 - 으로 모이게 됩니다. 그리고 만약 이와 같은 상황이 된다면, 아무리 변이를 만들어도 그것은 이미 수렴된 값보다 나쁜 값이 되어 도태될 것이기에 더이상의 개선효과가 없는(진화가 안되는) 것으로 보일 것입니다.

창조과학회의 주장

Phyllium bioculatum

잎벌레가 4700만년동안 진화하지 않았다^**는 것이 진화론이 거짓이라는 증거랍니다. 하지만 조금만 생각해 보면 알 수 있죠.

잎벌레가 살아남을 수 있는 이유는 '겉모습이 나뭇잎을 닯아서'입니다. 그런데 이 잎벌레에게 변이가 일어나서 모습이 (나뭇잎과) 달라진다면 어떻게 될까요? 그 변이체는 다른 포식자의 눈에 쉽게 띄어 잡아먹혀 도태될 것입니다. 즉, 잎벌레에게 있어서 현재의 모습이 전체적인 최적은 아닐지라도 위 알고리즘에서처럼 근방에서의 최적인 상태입니다. 그 때문에 4700만년 동안이나 더이상의 진화를 멈춘 듯이 보이는 것입니다.

이들의 모습이 변하기 위해서는 주위의 환경이 변해야 합니다. 주위 나뭇잎의 모습이 변한다면 이들도 그 나뭇잎의 모습에 맞추어 자신의 모습을 바꾸어 갈 것입니다. 결국 이런 간단한 생각조차 거부하는 창조과학회의 주장은 그야말로 진화적으로 생각하는 것의 대안은 생각을 하지 않는 것이다의 전형을 보여주는 것이죠,

뱀발 : 창조주의 졸작인 인간의 눈 역시 마찬가지로 생각할 수 있습니다. 최초의 시세포가 혈관 뒤에 있던 세포였기에, 문어의 눈이 아니라 현재 척추동물의 눈 - 전체적인 최적은 아니지만 근방에서의 최적 - 으로 수렴된 것이죠.


^* 이 보기는 유전자 알고리즘을 사용하기에 적절치 않은 문제입니다. 유전자알고리즘보다는 미분을 이용하는 것이 더 빠르고 정확한 방법입니다. 여기서는 이해하기 쉬운 보기를 제시한 것입니다.

^** 사실 '진화하지 않았다'는 것 역시 창조론적인 생각이죠. 그들 역시 진화를 했습니다. 창조론을 부정하는 살아있는 화석을 참고하세요.

GA - 미로 속 슬라임 - 흠뻑 젖은 슬라임

8. 젖은 슬라임
앞과 같은 미로를 통과하기 위해서는, 슬라임이 과거에 어디를 통과했는지에 관한 기억이 필요합니다. 그래서 왔던길로 돌아가지 말아야 하는 것이죠.

내가 어디서 왔는지를 표시하기 위해 슬라임이 수액을 분비한다고 해 봅시다. 슬라임은 이동할 때마다 자신이 있는 위치를 수액으로 흠뻑 적십니다. 슬라임의 이동경로를 따라 수액의 흔적이 남을 겁니다. 이 수액은 시간이 갈수록 조금씩 말라갑니다.
그와 함께 슬라임은 자기 주위의 습기를 알 수 있는 감지기를 가지고 있습니다. 이것으로 자기가 어디서 왔는지 알 수 있겠죠.

이 젖은슬라임을 만들기 위해서는 약간의 변형이 필요합니다. 먼저 미로에 습기를 저장할 수 있도록 해야 합니다.

procedure MazeProcess(slime, maze)

   // 슬라임을 출발점에 세움

   slime.LocX := 1

   slime.LocY := 1

   maze.Clear() // 미로 안의 모든 습기 제거

   // 미로 안에서 슬라임 움직임

   for k := 0, 900 do // 미로 안에서 슬라임이 움직이는 횟수

                     // 미로가 클수록 커져야 함

      // 미로 안의 습기 말리기

      for x := 0, 15 do

         for y := 0, 15 do

            if maze.Wet[x][y] > 0 then

               maze.Wet[x][y] := maze.Wet[x][y] - 1

            end

         end

      end

      // 슬라임이 수액 분비

      maze.Wet[slime.LocX][slime.LocY] := 100

      // 어디로 움직일지 생각

      movedirect = SlimeThink(slime, maze)

      // 이동할 위치

      if movedirect == 'E' then

         newx := slime.LocX + 1

         newy := slime.LocY

      elseif movedirect == 'W' then

         newx := slime.LocX - 1

         newy := slime.LocY

      elseif movedirect == 'S' then

         newx := slime.LocX

         newy := slime.LocY + 1

      elseif movedirect == 'N' then

         newx := slime.LocX

         newy := slime.LocY - 1

      end

      // 이동한 결과 계산

      if maze.IsBlock(newx, newy) then // 블럭에 충돌

         slime.Fitness := slime.Fitness - 10 // 적응도 감소

      else // 충돌하지 않을 경우

         slime.LocX := newx

         slime.LocY := newy

         slime.Fitness := slime.Fitness - 1 // 적응도 감소

         // 목적지에 도착했나?

         if maze.IsGoal(slime.LocX, slime.LocY) then

            slime.Fitness := slime.Fitness + 1000 // 적응도 대폭 증가

            break // for 루프 탈출

         end

      end

   end

end

즉 슬라임이 있는 위치의 습도는 100, 슬라임이 떠난 후 1씩 감소합니다.

function SlimeThink(slime, maze)

   // 슬라임 동서남북의 블럭정보 얻기

   curstate.detect.EastBlock := maze.IsBlock(slime.LocX + 1, slime.LocY)

   curstate.detect.WestBlock := maze.IsBlock(slime.LocX - 1, slime.LocY)

   curstate.detect.SouthBlock := maze.IsBlock(slime.LocX, slime.LocY + 1)

   curstate.detect.NorthBlock := maze.IsBlock(slime.LocX, slime.LocY - 1)

   // 사방의 습기 찾기

   curstate.detect.EastWet := maze.WetOrder(slime.LocX + 1, slime.LocY)

   curstate.detect.WestWet := maze.WetOrder(slime.LocX - 1, slime.LocY)

   curstate.detect.SouthWet := maze.WetOrder(slime.LocX, slime.LocY + 1)

   curstate.detect.NorthWet := maze.WetOrder(slime.LocX, slime.LocY - 1)

   // 나갈 입구의 방향 찾기

   curstate.detect.ExitEast := maze.IsExitEast(slime.LocX, slime.LocY)

   curstate.detect.ExitWest := maze.IsExitWest(slime.LocX, slime.LocY)

   curstate.detect.ExitSouth := maze.IsExitSouth(slime.LocX, slime.LocY)

   curstate.detect.ExitNorth := maze.IsExitNorth(slime.LocX, slime.LocY)

   // GeneList(유전자들의 묶음)에서 curstate 찾기

   fnd := slimt.GeneList.Find(curstat)

   if fnd == nil then // 처음 만나는 상황

      // effect부분을 랜덤으로 만듦

      for k := 0, 10 do

         curstate.effect[k] = Random("EWSN") // EWSN 중에서 하나 선택

      end

      slime.GeneList.Append(curstate) // 현재 상황 추가

      fnd = curstate

   end

   // 여기까지 해서 fnd에는 현재상황에 맞는 유전자가 들어있음

   return fnd.effect[Random(0, 9)]

end

이때 EastWet~NorthWet을 설정하는 데는 각 방향의 습기를 그대로 저장할 수도 있지만, 그렇게 된다면 유전자 수가 너무 많아질 수 있습니다. 동서남북 최대 100단계이니 100000000개 가까이 유전자가 늘어날 수 있죠(물론 불가능한 조합도 있습니다만)
그러므로 여기서는 각 방향의 습기 등수를 가져오도록 했습니다(가장 많이 젖은 곳이 0, 그다음 젖은 순서대로 1, 2, 3). 그 외는 앞의 슬라임과 동일합니다.

9. 젖은 슬라임의 결과
'수액에 젖은' 슬라임으로 100세대를 진화시킨 결과입니다.

 

그리고 앞의 슬라임이 통과하지 못했던 미로를 통과한 결과입니다.

두 개의 미로 모두 최적의 슬라임이 탄생했습니다. 단, 두개의 미로를 모두 통과할 수 있는 슬라임이 태어난 것은 아닙니다. 첫째 미로를 돌파하는 슬라임을 둘째 미로에 넣는다면 제대로 못찾을 것입니다.
이러한 현상을 막기 위해서는 미로 자체를 변화시켜야겠죠.

GA - 미로 속 슬라임 - 결과

3. 재생산
재생산루틴은 오델로의 경우와 거의 동일합니다.
3.1 선택
재생산 대상 선택은, 여기서는 T=0.9, num=2(4개를 뽑아 2회 겨루기)인 토너먼트법을 사용했습니다.
3.2 교차
오델로의 경우와 비슷합니다. 두 슬라임의 유전자리스트를 동기화시킨 후 일정한 확률로 동일한 두 유전자를 교환합니다.
3.3 돌연변이
역시 detect부분은 건드리지 않고 effect부분 10개의 방향비트들을 일정한 확률로 바꿉니다.

procedure Mutantation(slime)

   for k := 0, size(slime.GeneList) do

      if RandomRate then

         // 모든 비트 돌연변이

         for b := 0, 10 do

            slime.GeneList[k].effect[b] := Random("EWSN")

         end

      else

         // 비트 하나하나 돌연변이

         for b := 0, 10 do

            if RandomRate then

               slime.GeneList[k].effect[b] := Random("EWSN")

            end

         end

      end

   end

end

4. 결과 1
우선은 위와 같은 방식으로 100세대를 진화시켰습니다. 각 세대마다 최고 적응도를 얻은 슬라임을 찾아 100번의 시도 중 성공횟수와 이동횟수, 충돌횟수를 그래프로 그린 것입니다.

그래프에서 잘 보이지는 않지만 성공횟수는 가장 밑에 깔려 있습니다(모두 0). 충돌횟수는 점점 줄어들고 반면 이동횟수는 늘어나지만, 정작 중요한 성공횟수에서는 좌절할 수밖에 없습니다. 즉, 슬라임의 진화는 대실패란 뜻이죠.ㅡㅡ;


5. 용불용설(用不用說 : Use Disuse Theory)
용불용설은 과학적으로 폐기된 이론입니다. 용불용설이 설득력을 가지려면 외부 환경이 유전자에 직접 영향을 미치는 메커니즘이 밝혀져야 합니다. 그러나 환경이 유전자에 영향을 미치는 그러한 메커니즘은 자연계에서 발견되지 않았습니다.
하지만 이 슬라임의 창조주(?)는 프로그래머입니다. 이 슬라임에 용불용설을 설계해 놓는 것은 프로그래머 마음이죠(어째 창조론/지적설계론자가 된듯....)
여기서는 슬라임이 장애물에 충돌한다면, 슬라임을 충돌시킨 유전자를 수정하는 식으로 코딩했습니다.

function SlimeThink(slime, maze)

   // 슬라임 동서남북의 블럭정보 얻기

   curstate.detect.EastBlock := maze.IsBlock(slime.LocX + 1, slime.LocY)

   curstate.detect.WestBlock := maze.IsBlock(slime.LocX - 1, slime.LocY)

   curstate.detect.SouthBlock := maze.IsBlock(slime.LocX, slime.LocY + 1)

   curstate.detect.NorthBlock := maze.IsBlock(slime.LocX, slime.LocY - 1)

   // 나갈 입구의 방향 찾기

   curstate.detect.ExitEast := maze.IsExitEast(slime.LocX, slime.LocY)

   curstate.detect.ExitWest := maze.IsExitWest(slime.LocX, slime.LocY)

   curstate.detect.ExitSouth := maze.IsExitSouth(slime.LocX, slime.LocY)

   curstate.detect.ExitNorth := maze.IsExitNorth(slime.LocX, slime.LocY)

   // GeneList(유전자들의 묶음)에서 curstate 찾기

   GeneFind := slimt.GeneList.Find(curstat)

   if GeneFind == nil then // 처음 만나는 상황

      // effect부분을 랜덤으로 만듦

      for k := 0, 10 do

         curstate.effect[k] = Random("EWSN") // EWSN 중에서 하나 선택

      end

      slime.GeneList.Append(curstate) // 현재 상황 추가

      GeneFind = curstate

   end

   // 여기까지 해서 fnd에는 현재상황에 맞는 유전자가 들어있음

   GeneSlot = Random(0, 9)

   return GeneFind.effect[GeneSlot]

end

여기서 GeneFind와 GeneSlot은 전역변수입니다. 즉 이번 슬라임의 이동에 영향을 준 유전자를 저장하고 있습니다. 그리고

procedure MazeProcess(slime, maze)

   // 슬라임을 출발점에 세움

   slime.LocX := 1

   slime.LocY := 1

   ........

      // 이동한 결과 계산

      if maze.IsBlock(newx, newy) then // 블럭에 충돌

         slime.Fitness := slime.Fitness - 10 // 적응도 감소

         GeneFind.effect[GeneSlot] := Random("EWSN")// 충돌시킨 유전자 수정

      else // 충돌하지 않을 경우

         slime.LocX := newx

         slime.LocY := newy

         slime.Fitness := slime.Fitness - 1 // 적응도 감소

         // 목적지에 도착했나?

         if maze.IsGoal(slime.LocX, slime.LocY) then

            slime.Fitness := slime.Fitness + 1000 // 적응도 대폭 증가

            break // for 루프 탈출

         end

      end

   end

end

즉,돌연변이에 의해 장애물에 충돌하는 슬라임이라도 이후에는 그 유전자를 수정하여 더이상 충돌하지 않도록 만드는 것입니다.

6. 결과 2
용불용설까지 적용한 결과는 다음과 같습니다.

하나의 그래프로 나타내기 위해 적당히 배율을 조정했습니다. 여기서 뚜렷이 알 수 있듯 충돌횟수는 급격히 줄어들었습니다. 무엇보다 성공횟수가 불과 7세대만에 만점(100번 시도에 100번 성공)에 도달했으며, 그 후에도 이동횟수도 점차 감소하는(헤매지 않고 목적지로 이동하는) 현상을 보이고 있습니다. 아까의 대실패에 비하면 성공인듯 싶군요.

그런데 과연 성공일까요?

7. 이 슬라임의 약점
이번에는 이 슬라임을 다음과 같은 미로에 넣어 보도록 합시다.

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @
@ S                         @
@ @ @ @ @ @ @ @ @ @ @ @ @   @
@                           @
@   @ @ @ @ @ @ @ @ @ @ @ @ @
@                           @
@ @ @ @ @ @ @ @ @ @ @ @ @   @
@                           @
@   @ @ @ @ @ @ @ @ @ @ @ @ @
@                           @
@ @ @ @ @ @ @ @ @ @ @ @ @   @
@                           @
@   @ @ @ @ @ @ @ @ @ @ @ @ @
@                         E @
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @

이러한 미로에서 100세대동안 진화시킨 결과는 다음과 같습니다.

미로만 바꾸었을 뿐인데 성공률은 뚝 떨어지고 말았습니다. 왜 이런 결과가 나왔을까요.
다음과 같이 슬라임이 1번위치에 있을 때와 2번위치에 있을 때를 비교해 봅시다.

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @
@                           @
@ @ @ @ @ @ @ @ @ @ @ @ @   @
@     1                     @
@   @ @ @ @ @ @ @ @ @ @ @ @ @
@         2                 @
@ @ @ @ @ @ @ @ @ @ @ @ @   @
@                           @
@   @ @ @ @ @ @ @ @ @ @ @ @ @
@                           @
@ @ @ @ @ @ @ @ @ @ @ @ @   @
@                           @
@   @ @ @ @ @ @ @ @ @ @ @ @ @
@                         E @
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @

두 위치에 있을 때 주위의 장애물 구조는 동일합니다(남북에만 장애물). 또한 목적지의 방향 역시 동일합니다(남서쪽). 그럼에도 불구하고, 두 위치에 있을때 슬라임이 가야 할 방향은 반대입니다(1번일 경우는 서쪽으로, 2번에서는 동쪽으로).
그러므로 최초에 설계한 유전자로는 이 두 경우를 나눌 수 없고, 결국 이런 종류의 미로는 찾을 수 없다는 결론이 나옵니다.
과연 이러한 미로를 통과할 수 있는 슬라임은 탄생할 수 있을까요?

GA - 미로 속 슬라임 - 개요

"찾았다"

어느 병사의 외침에 다른 병사들이 달려왔다. 그들 한가운데에는 슬라임 한마리가 반투명한 몸체를 흔들며 서 있었다. 병사들은 슬라임을 둘러싸고 무기를 슬라임에게 향했다.

그것은 창 같지만 창이 아니었다. 창날이 있어야 할 곳에 넓적한 판자가 달려 있었다.

"시작하십시오"

대장이 옆에 있는 노마법사에게 말하자, 다섯명의 젊은 마법사들이 슬라임을 중심으로 오망성을 이루었다.

"자, 모두들 주의하시오. 저놈이 포위망을 뚫으면 안됩니다"

노마법사의 명령에 이어 젊은 마법사들은 주문을 읇기 시작했다. 갑자기 슬라임이 붉은 빛에 휩싸이는 듯 싶더니 몸부림을 쳤다. 그와 함께 병사들의 판자에서는 룬문자가 빛나기 시작했다. 그 판자에 닿은 슬라임은 감전이라도 된 듯 물러났다. 하지만 그와 함께 병사들 역시 몇걸음씩 뒤로 물러나곤 했다.

"힘내라, 밀리면 안된다!"

주문이 끝나갈 동안 병사들은 슬라임을 버티고 있었다. 마침내 붉은 빛이 잦아들면서 슬라임은 주먹만한 크기로 줄어들었다. 노마법사는 그제서야 유리병을 꺼내 슬라임을 넣었다.

"됐다. 성공이다."

"잘 됐다니 다행이군요. 그런데 그 슬라임을 뭐에 쓰려고 잡는 겁니까?

"보시겠습니까?"

대장과 함께 텐트로 돌아온 노마법사는 탁자 위의 천을 걷었다. 그곳에는 다음과 같은 미로가 있었다.

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @
@ S @           @           @
@   @   @ @ @   @ @ @     @ @
@       @       @           @
@ @ @ @ @   @ @       @     @
@           @   @ @ @       @
@   @ @ @ @ @       @   @ @ @
@   @           @ @ @       @
@   @   @ @ @       @ @     @
@   @   @         @         @
@       @     @ @     @     @
@ @ @ @     @       @       @
@   @       @   @ @     @ @ @
@               @         E @
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @

노마법사는 슬라임을 왼쪽 위에 넣고는 뚜껑을 닫았다. 그리고 오른쪽 아래에 있는 문을 열었다. 노마법사가 잠시 슬라임에게 주문을 걸자 슬라임은 미로를 돌아다니기 시작했다

"지금 저 슬라임은 자기 주위에 장애물이 있는지 없는지와, 출구의 방향만을 알 수 있습니다. 그것만으로 이 미로를 빠져나와야 합니다. 조금이라도 미로를 더 잘 찾는 슬라임들만 골라서 번식시키면 마침내는 미로를 빠져나오는 슬라임이 만들어질 겁니다. 저는 그런 슬라임을 만들려는 것입니다."

"호오.. 그래요? 그런데 미로찾는 슬라임은 뭐에 쓰실려구요?"

"예? 뭐에 쓸 거냐구요? 저... 그러니까... 글쎄요... 어디에 쓰면 좋을까요?"

1. 유전자 설계
다른 것도 마찬가지지만, 일반적으로 유전자는 어떤 상황에서 어떻게 행동할까로 정의하는 것이 쉽습니다.

1.1 상황패턴
위에서도 말했지만 슬라임이 알 수 있는 것은 동서남북에 장애물이 있는가와 출구의 방향입니다.
슬라임의 현 상황을 묘사하기 위해서는 8개의 숫자가 필요합니다. 만약 윗 그림의 슬라임이 S위치에 있다면

1101 1010

이 될 것입니다. 이때 앞 4자리는 동서남북의 장애물 유무(동, 서, 북쪽에 장애물이 있고 남쪽에는 없다), 뒤 4자리는 출구가 동서남북 어느 쪽에 있는지(출구는 동남쪽이 있음)를 의미합니다.

1.2 행동패턴
다음에는 이 슬라임이 어떻게 행동할까(어떤 방향으로 움직일까)입니다. 간단히 하자면, 동서남북 중 어느쪽으로 갈지만 묘사하면 됩니다. 그러므로 오델로의 경우와 마찬가지로 다음과 같은 상황과 행동의 묶음을 유전자로 할 수 있습니다.

(1101 1010 - S)

(1001 1101 - E)

(0011 1000 - N)

...

즉, 슬라임이 출발점에 있다면 그 슬라임은 남쪽으로 이동하게 될 것입니다.

그러나 만약 이 슬라임이 다음과 같이

@ @ @ @ @ @ @ @ @ @ @ @ @ @ @
@   @           @           @
@   @   @ @ @   @ @ @     @ @
@       @       @           @
@ @ @ @ @   @ @       @     @
@           @   @ @ @       @
@   @ @ @ @ @       @   @ @ @
@   @           @ @ @       @
@   @   @ @ @       @ @     @
@   @   @         @         @
@       @     @ @     @     @
@ @ @ @     @       @       @
@   @       @   @ @     @ @ @
@               @       S E @
@ @ @ @ @ @ @ @ @ @ @ @ @ @ @

출구 바로 앞까지 도착했다면 어떻게 될까요? 이때의 상황은 0011 1000이며, 유전자 묶음에서의 행동은 N, 북쪽으로 이동하는 것입니다. 결국 이 슬라임은 출구 바로 앞에서 좌절하겠죠.
그러므로 여기서는 행동패턴은 단일한 방향이 아닌 10% 단위의 확률로 나타내기로 했습니다. 이를테면

(0011 1000 - ENNENENNEW)

와 같이 할 수 있습니다. 여기서 E가 3개, W가 2개, N이 5개이므로 이 경우에는 동쪽으로 갈 확률 30%, 북쪽 50%, 서쪽 20%, 남쪽으로 갈 일은 없게 되겠죠. 이 슬라임은 30%확률로 동쪽으로 갈 것이며 목적지에 도착할 것입니다(물론 20% 확률로 서쪽으로 가겠지만, 그래도 목적지에 도착할 가능성이 0%는 아닙니다).

2. 미로찾기
전체적으로, 이 슬라임은 오델로와 비슷한 루틴을 가지고 있습니다. 각 슬라임은 최초에 아무것도 없는 상태에서 시작하며, 자신이 있는 위치에서 현재 상태를 감지, 유전자리스트에서 유전자를 찾습니다.
다음 함수는 현 위치에서 슬라임이 어느 위치로 이동할지 생각하는 함수입니다.

function SlimeThink(slime, maze)

   // 슬라임 동서남북의 블럭정보 얻기

   curstate.detect.EastBlock := maze.IsBlock(slime.LocX + 1, slime.LocY)

   curstate.detect.WestBlock := maze.IsBlock(slime.LocX - 1, slime.LocY)

   curstate.detect.SouthBlock := maze.IsBlock(slime.LocX, slime.LocY + 1)

   curstate.detect.NorthBlock := maze.IsBlock(slime.LocX, slime.LocY - 1)

   // 나갈 입구의 방향 찾기

   curstate.detect.ExitEast := maze.IsExitEast(slime.LocX, slime.LocY)

   curstate.detect.ExitWest := maze.IsExitWest(slime.LocX, slime.LocY)

   curstate.detect.ExitSouth := maze.IsExitSouth(slime.LocX, slime.LocY)

   curstate.detect.ExitNorth := maze.IsExitNorth(slime.LocX, slime.LocY)

   // GeneList(유전자들의 묶음)에서 curstate 찾기

   fnd := slimt.GeneList.Find(curstat)

   if fnd == nil then // 처음 만나는 상황

      // effect부분을 랜덤으로 만듦

      for k := 0, 10 do

         curstate.effect[k] = Random("EWSN") // EWSN 중에서 하나 선택

      end

      slime.GeneList.Append(curstate) // 현재 상황 추가

      fnd = curstate

   end

   // 여기까지 해서 fnd에는 현재상황에 맞는 유전자가 들어있음

   return fnd.effect[Random(0, 9)]

end

최초에 슬라임을 초기위치(1, 1)에 넣은 후 SlimeThink()를 실행, 미로를 진행하게 됩니다.

procedure MazeProcess(slime, maze)

   // 슬라임을 출발점에 세움

   slime.LocX := 1

   slime.LocY := 1

   // 미로 안에서 슬라임 움직임

   for k := 0, 900 do // 미로 안에서 슬라임이 움직이는 횟수

               // 미로가 클수록 커져야 함

      // 어디로 움직일지 생각

      movedirect = SlimeThink(slime, maze)

      // 이동할 위치

      if movedirect == 'E' then

         newx := slime.LocX + 1

         newy := slime.LocY

      elseif movedirect == 'W' then

         newx := slime.LocX - 1

         newy := slime.LocY

      elseif movedirect == 'S' then

         newx := slime.LocX

         newy := slime.LocY + 1

      elseif movedirect == 'N' then

         newx := slime.LocX

         newy := slime.LocY - 1

      end

      // 이동한 결과 계산

      if maze.IsBlock(newx, newy) then // 블럭에 충돌

         slime.Fitness := slime.Fitness - 10 // 적응도 감소

      else // 충돌하지 않을 경우

         slime.LocX := newx

         slime.LocY := newy

         slime.Fitness := slime.Fitness - 1 // 적응도 감소

         // 목적지에 도착했나?

         if maze.IsGoal(slime.LocX, slime.LocY) then

            slime.Fitness := slime.Fitness + 1000 // 적응도 대폭 증가

            break // for 루프 탈출

         end

      end

   end

end

여기서 충돌하지 않고 이동했을 때도 적응도를 감소시키는 것은, 목적지에 빨리 도달한 슬라임에게 적응도를 높여주기 위함입니다.
이런 식으로 각각의 슬라임은 저 미로를 100회씩 돌게 됩니다.

procedure MainRoutine

   for generation := 0, 100 do

      for k := 0, 4096 do

         SlimeList[k].Fitness := 0

         for m := 0, 100 do

            MazeProcess(SlimeList[k], Maze)

         end

      end

      Rebirth Next  Generation

   end

end

GA - 오델로 - 결과

6. 결과
앞과 같은 방식으로 100세대 동안 진화시킨 결과입니다.
6개 무리에서 가장 적응도가 높은 개체들의 적응도 변화 그래프입니다.



서로간에 엎치락뒤치락하기는 합니다만, 이것만으로는 얼마나 실력이 좋아졌는지 알 수가 없습니다.
어쩔수 없이 기본이 되는 AI를 하나 만들어서 비교해야겠네요.
StandardAI라 이름붙인 이 AI는 오델로플레이어와 비슷하게 돌을 놓을 수 있는 장소들의 가중치를 계산합니다. 다만 가중치를 유전자에서 계산하는 것이 아니라, 그 위치에서 잡을 수 있는 돌의 수 * 그 위치의 중요도로 계산합니다. 그 위치의 중요도란 가장자리는 10, 가장자리에서 한칸 안쪽은 1, 나머지는 5로 정의합니다.

아무튼 매 세대마다 각 무리에서 최고가중치를 가진 오델로플레이어와 이 StandardAI를 10회 대결시킨 후 오델로플레이어가 얻은 점수를 그래프로 그린 결과는 다음과 같습니다.


여기서는 20세대도 채 지나기 전에 StandardAI를 상대로한 전과가 급상승하는 것을 알 수 있습니다. 참고로 이 때의 유전자 크기(즉 유전자가 가지고 있는 패턴 갯수)는 11039입니다(물론 이것이 최대값인지는 모릅니다. 세대가 진행되면서 더 늘어날 수도 있습니다).

7. 뱀발
결과적으로 유전자알고리즘이 얼마나 진화되었는지 알기 위해 StandardAI라는 새로운 AI를 만들 수밖에 없었습니다.
그렇다면, 구태여 공진화시킬 필요 없이 이 StandardAI와의 대결을 통해 적응도를 계산, 진화시킬 수도 있지 않을까요?
물론 그럴 수도 있습니다만, 만약 StandardAI와의 대결을 통해 진화시킨다면 한가지 큰 단점이 있습니다. 오델로플레이어들이 StandardAI만을 상대하기 위해 진화한다는 점이죠. 만약 StandardAI에게 어떤 약점이 존재한다면 그 약점만을 공략하는 오델로플레이어들이 진화할 가능성이 있습니다. 그렇게 된다면 StandardAI를 상대로는 강하지만 다른 AI(심지어는 StandardAI보다 약하지만 StandardAI의 약점이 없는 AI)들을 상대로는 맥을 못추는 오델로플레이어들이 진화될 수 있습니다.

GA - 오델로 - 경쟁 및 재생산

3. 경쟁
이제 유전자도 설계했으니 이들을 경쟁시켜서 적응도를 측정해야 합니다. 그런데 무엇과 경쟁시킬까요? 특정한 AI를 하나 만들어서 이 AI와 경쟁시켜야 할까요?
아, 전에도 종종 사용했던 공진화를 이용하면 구태여 AI를 따로 만들 필요가 없겠네요. 일이 줄었습니다.
여기서는 이 오델로플레이어들을 6개의 무리로 나누었습니다. 각 무리에는 512개씩의 오델로플레이어를 포함시켰습니다. 그리고는 이들 사이에서 경쟁을 시켰습니다.
각 오델로플레이어들은 같은 무리에 있는 것들과는 싸우지 않습니다. 다른 무리에 있는 것들과 싸우게 됩니다.

procedure Compatition()
.. for h := 0, 6 do
..... for p := 0, 512 do
........ Horde[h][p].Fitness := 0; // 모든 객체의 적응도 초기화
..... end
.. end

.. // 경쟁 시작
.. for white := 0, 6 do
..... for black := 0, 6 do
........ if white != black then
........... // Horde[white]와 Horde[black]간의 대결
........... // 랜덤한 상대를 만나기 위해
........... for k := 0, 512 do
.............. CardDeck[k] = k;
........... end
........... for k := 0, 512 do
.............. rnd := Random(0, 512);
.............. tmp = CardDeck[k];
.............. CardDeck[k] = CardDeck[rnd];
.............. CardDeck[rnd] = tmp;
........... end
........... for k := 0, 512 do
.............. Compatition(Horde[white][k], Horde[black][CardDeck[k]];
........... end
........ end
..... end
.. end
end

Compatition프로시저는 생략하겠습니다. 두 오델로플레이어끼리 대결을 시킨 후, 남아있는 자신의 돌 수를 Fitness에 더하는 프로시저입니다.

4. 재생산
이렇게 적응도를 구했으면 보다 많은 돌을 가진 오델로플레이어를 찾아 재생산을 시킵니다. 일단 재생산 대상은 T=0.99인 4차 토너먼트법 - 2⁴ = 16개의 후보를 선택 후 토너먼트를 반복해서 하나 설정, 토너먼트의 승부는 1% 확률로 적응도 낮은 것이 승 - 으로 결정했습니다.

4.1 교차
다음과 같은 유전자를 가진 두 오델로플레이어가 선택되었다고 합시다.

가
'...+...', 0.327
'.MM.+EE.', 0.932
'EE+.M..', 0.142
'.MEEE+EE', 0.527
'EMMEE+EM', 0.106
'..EE+EEE', 0.172
'MME+MM..', 0.018
'..E+...', 0.437


나
'.MM.+EE.', 0.762
'..M+...', 0.007
'..EE+EEE', 0.120
'..M.+EE', 0.607
'E+EMME', 0.742
'EMMEE+EM', 0.224


검은색으로 표시된 유전자는 '가'와 '나'에 다 있지만, 붉은색으로 표시된 유전자는 '가'에만, 녹색 유전자는 '나'에만 존재하는 유전자입니다. 이를테면 '나'는 '..E+...'라는 패턴을 만난 적이 없습니다. 만약 '나'가 그 패턴을 만난다면 어떨까요? 규칙에 의해 이 패턴을 랜덤한 가중치와 함께 추가할 것입니다. 그러므로 지금 추가하더라도 상관 없겠죠.
교차를 하기 전에 '가'와 '나'는 서로가 가지고 있는 패턴을 공유합니다.


가
'...+...', 0.327
'.MM.+EE.', 0.932
'EE+.M..', 0.142
'.MEEE+EE', 0.527
'EMMEE+EM', 0.106
'..EE+EEE', 0.172
'MME+MM..', 0.018
'..E+...', 0.437
'..M+...', 0.725
'E+EMME', 0.176


나
'.MM.+EE.', 0.762
'..M+...', 0.007
'..EE+EEE', 0.120
'..M.+EE', 0.607
'E+EMME', 0.742
'EMMEE+EM', 0.224
'...+...', 0.301
'.MEEE+EE', 0.815
'MME+MM..', 0.328
'..E+...', 0.663


즉 '가'와 '나' 둘 다 10개의 동일한 패턴(가중치는 다르지만)을 가진 유전자가 되었습니다.
이후에는 '가'와 '나'에서 동일한 패턴을 꺼내서 50%확률로 가중치를 바꾸면 교차 완료입니다.

function FindPattern(gene, pattern) // gene에서 pattern과 동일한 것 찾음
.. for k := 0, gene.Size do
..... if IsSamePattern(gene.Pair[k].Pattern, pattern) then
........ return k; // 찾았으면 위치 리턴
..... end
.. end
.. return -1;
end

procedure CrossOver(childA, childB)
.. geneA = childA.Gene
.. geneB = childB.Gene
.. for locA := 0, geneA.Size do
..... locB := FindPattern(geneB, geneA.Pair[locA].Pattern
..... if locB == -1 then // 맞는 패턴이 없음, B에 추가
........ geneB.Pair[childB.Gene.Size].Pattern = geneA.Pair[locA].Pattern
........ geneB.Pair[childB.Gene.Size].Weight = Random(0, 1)
........ childB.Gene.Size + childB.Gene.Size + 1
..... end
.. end
.. // 생략 - 동일한 방법으로 B에만 있는 유전자 A에 추가

.. // 교차 시작
.. for locA := 0, geneA.Size do
..... locB := FindPattern(geneB, geneA.Pair[locA].Pattern
......... // 동일한 패턴을 B에서 찾음

..... if Random(0, 1)＜ 0.5 then // 50%확률로 가중치 교환
........ tmp = geneA.Pair[locA].Weight
........ geneA.Pair[locA].Weight = geneB.Pair[locB].Weight
........ geneB.Pair[locB].Weight = tmp
..... end
.. end
end

4.2 돌연변이
돌연변이는 비교적 간단합니다. 오델로플레이어의 모든 유전자를 돌면서 일정확률로 가중치값을 변화시키면 됩니다.

procedure Mutantation(child)
.. for k := 0, child.Gene.Size do
..... if Random(0, 1)＜ 0.001 then
........ child.Gene.Pair[k].Weight = Random(0, 1)
..... end
.. end
end

5. 이주
앞에서 설명한 것처럼, 오델로플레이어들을 공진화시키기 위해 고립된 6개의 무리를 만들어 그 안에서만 번식이 일어나도록 하였습니다. 특히 512개밖에 안되는 무리 안에서만 번식시킨다면 아무리 돌연변이를 적용시키더라도 유전자가 획일화되기 쉽습니다. 그러므로 이렇게 유전적으로 고립시킨 경우에는 가끔씩 일부 개체들을 이주시켜 새로운 유전자를 섞어주는 것이 좋습니다.

procedure Migration()
.. if Generation % 10 == 9 then // 10세대에 한번씩
..... do
........ a := Random(0, 6)
........ b := Random(0, 6)
..... while a == b

..... aa := Random(0, 512)
..... bb := Random(0, 512)
..... tmp = horde[a][aa];
..... horde[a][aa] = horde[b][bb];
..... horde[b][bb] = tmp;
end