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번에서는 동쪽으로).
그러므로 최초에 설계한 유전자로는 이 두 경우를 나눌 수 없고, 결국 이런 종류의 미로는 찾을 수 없다는 결론이 나옵니다.
과연 이러한 미로를 통과할 수 있는 슬라임은 탄생할 수 있을까요?