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 - CNNC를 실은 꼬마자동차[2] - 입력과 출력, 교차

5. 꼬마자동차의 신경망 입력
꼬마자동차가 알아야 할 정보는, 바로 앞의 블럭정보, 그리고 연료가 어디 있는지에 대한 정보입니다.
꼬마자동차 CNNC의 입력노드 중 3개는 앞쪽에 어떤 장애물이 있는지(있으면 1, 없으면 -1), 마지막 하나는 연료의 위치를 -1~+1 사이의 float값으로 입력합니다.

procedure Detect(Car car, StoneRoad road)
.. cl := car.Locate.Len
.. cw := car.Locate.Wid

.. // 앞쪽 3칸 블럭정보
.. if road[cl - 1][cw - 1] == ROCK then
..... SetCharge(car.CNNC, 0, 1) // 0번셀에 입력
.. else
..... SetCharge(car.CNNC, 0, -1)
.. end
.. if road[cl - 1][cw + 0] == ROCK then
..... SetCharge(car.CNNC, 1, 1) // 1번셀에 입력
.. else
..... SetCharge(car.CNNC, 1, -1)
.. end
.. if road[cl - 1][cw + 1] == ROCK then
..... SetCharge(car.CNNC, 2, 1) // 2번셀에 입력
.. else
..... SetCharge(car.CNNC, 2, -1)
.. end

.. // 기름통 위치정보(차에서 가장 가까운)
.. fl := road.Fuel(car).Locate.Len
.. fw := road.Fuel(car).Locate.Wid
.. SetCharge(car.CNNC, 3, (fw - cw) / (fl - cl)) // 3번셀에 입력
end

6. 꼬마자동차의 신경망 출력
신경망 출력을 꼬마자동차의 움직임으로 바꾸기 위해 3개의 출력노드를 사용합니다. 그리고 각 출력노드의 출력양에 따라 직진할지 왼쪽이나 오른쪽으로 움직일지 결정하는 것입니다.
그러나 신경망의 특성상 가능하면 노드수를 줄이는 것이 최적화시키는데 도움이 됩니다. 여기서는 출력노드를 두개로 만들어, 더 강한 출력을 보이는 쪽으로 이동시키도록 하겠습니다. 즉,

procedure Action(Car car, StoneRoad road)
.. left = 0
.. right = 0
.. l := GetCharge(car.CNNC, 0);
.. r := GetCharge(car.CNNC, 1);
.. if l > 0 then // 왼쪽으로 움직이려는 경향
..... left := left + l
.. else // -왼쪽(즉 오른쪽)으로 움직이려는 경향
..... right := right - l
.. end .. if r > 0 then // 오른쪽으로 움직이려는 경향
..... right := right + r
.. else // -오른쪽(즉 왼쪽)으로 움직이려는 경향
..... left := left - r
.. end
.. // 출력이 강한 쪽으로 이동
.. rnd := Random(0, 2)
.. if left > rnd then
..... if right > rnd then
........ MoveForwar(car)
..... else
........ MoveLeft(car)
..... end
... else
..... if right > rnd then
........ MoveRight(car)
..... else
........ MoveForwar(car)
..... end
.. end
end

출력노드를 하나로 해 놓고, +1에 가까울수록 왼쪽으로, -1에 가까울수록 오른쪽으로 움직이도록 할 수도 있지만, 생각만큼 수렴이 잘 되지 않더군요. 우선은 출력노드 두개짜리로 실행해 봤습니다.

7. 적응도 계산
위와 같은 식으로 256개의 꼬마자동차와 64개의 돌길 개체를 만듧니다. 이 256개의 꼬마자동차 각각은 64개의 돌길을 통과하고 각 꼬마자동차와 돌길의 적응도를 결정합니다.
① 꼬마자동차의 적응도 : 평지로 진입할 때마다 10점추가, 장애물을 통과할때 10점감점
② 돌길의 적응도 : 자동차가 기름을 먹으면 5점감점, 장애물로 진입하면 10점추가

8. 교차
꼬마자동차의 경우는 앞의 XOR회로와 같은 일반적인 CNNC식 교차를 사용했습니다.
돌길의 경우는 길 전체를 길이 100의 선형유전자로 간주하고 일반적인 일점교차를 사용했습니다.

procedure CrossOver(StoneRoad a, StoneRoad b)
.. cut := Random(1, 99)
.. for l := 0, cut do
..... for w := 0, 11 do
........ tmp := a[l][w]
........ a[l][w] := b[l][w]
........ b[l][w] := tmp
..... end
.. end
end

9. 돌연변이
돌연변이 역시 꼬마자동차의 경우에는 CNNC의 돌연변이 루틴을 사용합니다.
돌길의 돌연변이는 두 단계로 이루어집니다. 첫째, 일정한 확률로 장애물을 만들기(또는 장애물을 없애기), 둘째, 기름통 위치 바꾸기입니다.

procedure Mutantation(StoneRoad gene)
.. for l := 0, 99 do
..... for w := 1, 10 do // 가장자리는 장애물로 유지
........ if MutantRate then
........... if gene[l][w] == ROCK then
.............. gene[l][w] := ROAD
........... else if gene[l][w] == ROAD then
.............. gene[l][w] := ROCK
........... end
..... end
.. end

.. for l := 0, 99 do
..... for w := 1, 10 do // 가장자리는 장애물로 유지
........ if gene[l][w] == FUEL then
........... if MutantRate then
.............. gene[l][w] := ROAD
.............. gene[l][Random(1, 10)] := FUEL
.............. break // w 루프 탈춮
........... end
........ end
..... end
.. end
end

10. 재생산
256개 꼬마자동차들이 모두 64개 돌길에서 달려 본 후 꼬마자동차와 돌길을 재생산합니다. 역시 꼬마자동차의 경우는 CNNC의 재생산 루틴을 사용했으며(이 경우 상위 8개의 꼬마자동차를 다음 세대에 그대로 복사하는 Elitism을 사용했습니다.)
돌길의 경우에는 T==0.95, Round==4인 토너먼트법(임의로 2⁴=16개의 돌길을 고른 후 95%의 확률로 적응도 높은 쪽이 이기는 토너먼트를 4회 반복)으로 재생산시켰습니다.

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

GA - 장사꾼여행문제(TSP) [2] - 유전자 초기화, 재생산

2. 유전자 초기화

일반적으로 유전자를 초기화하기 위해서는 유전자의 각 비트에 랜덤값을 넣으면 되지만, 이 경우에는 앞에서 말한 유전자의 제약 때문에 무조건 랜덤값을 넣을 수는 없습니다. 만약 도시 10개짜리 보기에서 유전자에 랜덤값을 넣어 5042852301란 유전자를 만들었다면, 이 유전자는 0번, 2번, 5번 도시는 두번씩, 6번, 7번, 9번 도시는 방문하지 않는 잘못된 유전자가 만들어집니다.

그러므로 이 경우에는 카드섞기 방법으로 초기화를 해야 합니다.

procedure InitGene(Gene gene)
.. // 0~149까지의 도시를 하나씩 넣음

.. for bit := 0, 150 do

..... gene[bit] := bit

.. end

.. //배열을 뒤섞음

.. for bit := 0, 150 do

..... exchange := Random(0, 150)

..... temp := gene[bit]

..... gene[bit] := gene[exchange]

..... gene[exchange] := temp

.. end

end

이와 같이 하면 150개의 도시에 대해 중복이나 결실 없는 무작위순열을 얻을 수 있습니다.

3. 적응도테스트 및 적응도

적응도를 계산하는 자세한 알고리즘은 생략하겠습니다. 유전자에 그려진 도시순서대로 한바퀴 돌며 이동하는 도시와 도시 사이의 거리를 합산하면 됩니다.

다만, 이경우에는 도시사이의 거리와 적응도는 역관계입니다. 거리가 길수록 적응도가 낮아지기 때문입니다. 여기서는 단순하게 적응도 = -(거리의 총합)으로 정의했습니다. 이렇게 하면 모든 적응도는 음수가 되긴 합니다만, 룰렛법을 사용할 수 없다는 점 이외에는 아무런 차이가 없습니다. 혹시 음수적응도가 마음에 안든다면, 가장 긴 이동거리를 가진 도시를 찾아서 (가장 긴 이동거리) - (거리의 총합) 으로 해도 됩니다. 이렇게 하면 적응도가 가장 떨어지는 개체가 0, 나머지는 양수의 적응도를 가질 수 있습니다.


4. 재생산대상 선택

다음 단계는 각자의 적응도에 따라 재생산할 대상을 고를 차례입니다. 윗 항에서처럼 적응도가 0보다 작으니 룰렛법을 사용할 수는 없지만 앞에서 사용했던 재계산법이나 순위법을 사용할 수는 있습니다.
하지만 이 문제에서는 새로운 선택법 - Tournament법을 사용하겠습니다.

토너먼트법이란, 일단 0과 1 사이의 수 T를 정합니다.
재생산 대상을 선택하기 위해 먼저 두개의 개체를 랜덤하게 정합니다. 그 둘 중 적합도가 높은 것을 Shigh, 적합도가 낮은 것을 Slow라 합니다.
다시한번 0과 1 사이의 랜덤값 r을 발생시킵니다. 그리고 r이 T보다 작다면 Shigh를, r이 T보다 크다면 Slow를 선택하는 방법입니다.

말로 해서 복잡한데, 알고리즘은 다음과 같습니다.

function SelectParent(double T)
.. // 임의의 두 개체 선택 후 Shigh에 적합도가 높은것, Slow에 적합도가 낮은 것을 나누어 넣음
.. A := Random(0, 150)
.. B := Random(0, 150)
.. if Salesman[A].fitness > Salesman[B].fitness then
..... Shigh := A
..... Slow := B
.. else
..... Shigh := B
..... Slow := A
.. end
.. // 다시한번 랜덤값 만듦
.. r = Random(0.0, 1.0) // 0~1 사이의 실수형 랜덤값 얻음
.. if T > r then
..... return Salesman[Shigh]
.. else
..... return Salesman[Slow]
end
이때 T는 0.5 이상의 값을 선택해야 합니다. 만약 0.5 이하라면 오히려 적합도가 낮은 것이 선택될 확률이 커지죠.
일반적으로 T가 클수록 선택압이 높아져 빨리 수렴하는 대신 해의 품질이 떨어지는 경향이 있습니다. 반대로 T가 작다면 수렴속도가 느려지죠.
사실 토너먼트법은 그다지 선택압이 높은 방법이 아닙니다. 개체군의 크기(전체 개체군 수)를 N이라 한다면, 최고적합도를 가진 개체가 선택될 확률은 2(1/N * T)에 불과합니다.

여기서는 단순하게 2개의 개체를 선택했지만, 2n개의 개체를 선택한 후 토너먼트식 대결을 계속하여 최후의 승자를 선택하는 방법도 있습니다.

5. Elitism

엘리트주의란, 최대 적합도를 가진 개체를 보호하는 알고리즘입니다. 일반적인 재생산 과정은 두 개체의 유전자를 섞어 새로운 유전자를 만드는 것이므로, 최대적합도의 유전자가 선택되더라도 그 유전자가 다음 세대에 그대로 복제되지는 않습니다. 앞에서의 꼬마자동차 보기에서와 같이, 영웅이 탄생하더라도 다음 대에서는 일단 사라졌다가 영웅의 부분유전자들이 어느정도 증식한 후에야 다시 나타납니다. 엘리티즘은 이러한 현상을 막기 위해 최대적합도를 가진 개체를 다음세대에 복제하는 것을 말합니다.
엘리티즘을 잘못 사용하면 계속 복제되는 엘리트가 계속 재생산대상으로 선택되어 다양성이 훼손되는 결과가 생길 수 있습니다. 하지만 이 TSP에서는 토너먼트법이 워낙 선택압이 낮은 관계로 엘리티즘을 추가했습니다.

한 세대의 개체수는 30001개로 정의했습니다. 그중 하나는 전세대의 가장 우수한 개체를 복제하고, 나머지 30000개는 토너먼트방식으로 교차와 돌연변이를 통해 만듦니다.

엘리티즘을 포함한다면 유전자 알고리즘의 순서도에서 다음 부분이 바뀌어야 합니다.

..... T := 0.9 // 이 값은 변화 가능..... declear Creature nextgeneration[GenerationNo] // 다음세대 creature를 만들 버퍼
..... store maxfitness to nextgeneration//전세대에서 최대적합도를 가진 개체를 그대로 넣음
..... while(not fill nextgeneration) do // nextgeneration이 채워질 동안 반복
........ Creature a, b
........ while 1 do........... a := SelectParent(T) // 적응도에 의해 재생산할 creature 선택
........... b := SelectParent(T) // a, b에 선택된 것의 복사본 만듦
........... if a != b then // 다른 Creature간의 유전자 혼합을 위해
.............. break........... end
........ end
........ call CrossOver(a, b) // a, b의 유전자를 섞음
........ call Mutantation(a) // a, b에 적당한 돌연변이 가함
........ call Mutantation(b)
........ store a, b to nextgeneration // a, b를 다음 세대 버퍼에 넣음
..... end
..... creature := nextgeneration // 새로 만들어진 creature들로 계속 실행

GA - 자동차[3] 선택압

유전자 알고리즘 시작 부분에서 나온 것처럼, 유전자알고리즘은 '우수한 개체'를 재생산함으로써 진행됩니다. 여기서 '우수한 개체가 선택될 가능성'을 선택압이라고 합니다.

앞의 꼬마자동차 문제로 돌아가 보죠.
1000세대가 지나면서 가끔씩 1000점짜리 꼬마자동차가 생기긴 했습니다만 번번히 번식기회(?)를 놓치고 도태되고 말았습니다. 그 이유가 무엇일까요?

어느 순간 1000점짜리 꼬마자동차가 하나 탄생했습니다. 나머지 127대는 평균 950점대에 분포되어 있습니다. 꼬마자동차에서 재생산대상을 선택하기 위한 Roulette법에 의한다면, 점수의 총합은 950 * 127 + 1000 = 121650입니다. 그러므로 1000점짜리 꼬마자동차가 선택될 가능성은 1000/121650 = 0.00822 = 0.822%, 즉 1% 이하가 됩니다. 전체 128개 꼬마자동차 중에서 1% 이하라면 다른 꼬마자동차들과 거의 동일한 확률로 재생산된다고 봐야 하겠죠.
그러므로 1000점짜리 꼬마자동차를 늘리기 위해서는 선택압을 높일 필요가 있겠습니다.

선택압을 높이기 위해서는 재생산을 위한 부모를 찾는 방식을 바꾸어야 합니다. 여기서는 다음과 같은 두가지 방법을 시도해 봤습니다.

1. 순위법
순위법은 1위부터 차례로 순서를 매긴 후 등수에 따라 점수를 다르게 다시 주는 방법입니다. 여기서는 1위에게는 1000점, 2위에게는 950점, 3위에게는 900점 등으로 점수를 다시 계산했습니다.

function SelectParent()
.. sort car[] // 자동차 리스트를 소트(car[0]에 최대값이 들어가도록)

.. curscore := car[0].score
.. newscore := 1000;
.. order := 0;
.. for k := 0, 128 do
..... order := order + 1
..... if car[k].score == curscore then // 동점자일때는 같은점수
........ car[k].score := newscore
..... else
........ curscore := car[k].score
........ newscore = 1000 - order * 50;
........ car[k].score := newscore
..... end
.. end
.. // 이후는 Roulette법과 동일
end

순위법으로 선택압을 높여 유전자 알고리즘을 진행시킨 결과는 다음과 같습니다.
Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
......
Generation 48 MaxScore:990 MinScore:850 AverageScore:928
Generation 49 MaxScore:1000 MinScore:830 AverageScore:919
Generation 50 MaxScore:980 MinScore:820 AverageScore:926
Generation 51 MaxScore:990 MinScore:830 AverageScore:922
......
Generation 225 MaxScore:990 MinScore:810 AverageScore:925
Generation 226 MaxScore:1000 MinScore:820 AverageScore:925
Generation 227 MaxScore:1000 MinScore:810 AverageScore:923
Generation 228 MaxScore:990 MinScore:810 AverageScore:928
Generation 229 MaxScore:990 MinScore:800 AverageScore:925
Generation 230 MaxScore:1000 MinScore:810 AverageScore:928
Generation 231 MaxScore:1000 MinScore:800 AverageScore:945
Generation 232 MaxScore:1000 MinScore:800 AverageScore:969
Generation 233 MaxScore:1000 MinScore:940 AverageScore:974
......
Generation 680 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 681 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 682 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 683 MaxScore:1000 MinScore:900 AverageScore:999
Generation 684 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 685 MaxScore:1000 MinScore:1000 AverageScore:1000
Generation 686 MaxScore:1000 MinScore:1000 AverageScore:1000

최초의 만점 꼬마자동차(이것을 영웅이라 부릅시다^^)는 49세대만에 나타났다가 도태되었습니다. 그러나 이 경우 영웅은 많은 재생산기회를 가지므로 영웅의 유전자는 교차에 의해 분리되어 많은 다음세대의 꼬마자동차들에 흩어져 들어갑니다. 이 영웅유전자를 일부라도 가진 꼬마자동차들은 비교적 높은 점수를 얻을 수 있고 다음 재생산 대상이 될 수 있으므로 영웅유전자는 자꾸만 늘어납니다. 결국 영웅유전자끼리 만날 가능성은 점점 커지고(230세대) 마침내는 모든 꼬마자동차가 영웅유전자를 가질 수 있는 것이죠(600세대 이후). 이 이후 가끔씩 보이는 감점은 돌연변이에 의한 결과입니다.

2. 재계산법
재계산법은 꼬마자동차들 사이의 점수분포를 제한된 범위 안에 분포하도록 재계산하는 방식입니다. 룰렛방식 부모선택의 경우 1000세대 이후의 점수분포는 주로
Generation 1006 MaxScore:990 MinScore:840 AverageScore:938
Generation 1007 MaxScore:990 MinScore:850 AverageScore:935
Generation 1008 MaxScore:990 MinScore:860 AverageScore:937
Generation 1009 MaxScore:990 MinScore:810 AverageScore:938
Generation 1010 MaxScore:980 MinScore:870 AverageScore:933
810~990 사이였습니다. 이 범위를 꼬마자동차의 경우 10~1000 사이로 확대하여 재계산한 후 룰렛법과 같은 방식으로 계산합니다.

function SelectParent()
.. // 점수의 상한선과 하한선 찾기
.. minscore := 10000;
.. maxscore := 0;
.. for k := 0, 128 do
..... if minscore > car[k].score then
........ minscore := car[k].score
..... if car[k].score > maxscore then
........ maxscore := car[k].score
.. end

.. if maxscore != minscore then // 모든 자동차의 점수가 다 같은 경우는 적용할 수 없음
..... // max를 1000, min을 10으로 맞춤
..... newmax := 1000
..... newmin := 10
..... diff := maxscore - minscore; // 보정 전의 스코어 차이
..... for k := 0, 128 do
........ score := car[k].score
........ score := score - minscore
........ score := score * (newmax - newmin) / diff + newmin
........ car[k].score := score
..... end
.. end
.. // 이후는 Roulette법과 동일
end

재계산법으로 돌린 결과입니다.

Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
......
Generation 47 MaxScore:980 MinScore:700 AverageScore:898
Generation 48 MaxScore:990 MinScore:740 AverageScore:919
Generation 49 MaxScore:1000 MinScore:780 AverageScore:918
Generation 50 MaxScore:980 MinScore:820 AverageScore:926
Generation 51 MaxScore:990 MinScore:830 AverageScore:922
Generation 52 MaxScore:990 MinScore:850 AverageScore:928
......
Generation 492 MaxScore:990 MinScore:820 AverageScore:931
Generation 493 MaxScore:1000 MinScore:860 AverageScore:935
Generation 494 MaxScore:990 MinScore:870 AverageScore:937
Generation 495 MaxScore:990 MinScore:780 AverageScore:936
Generation 496 MaxScore:1000 MinScore:860 AverageScore:937
Generation 497 MaxScore:1000 MinScore:860 AverageScore:938
Generation 498 MaxScore:1000 MinScore:810 AverageScore:942
Generation 499 MaxScore:1000 MinScore:850 AverageScore:943

빠르고 늦고의 차이가 있을 뿐 전체적인 모습은 순위법일 경우와 동일합니다.


뱀발 :
그렇다면 유전자 알고리즘에서 선택압이 높을수록 좋은 것일까요? 그것은 아닙니다. 특히 초반에 지나치게 높은 선택압은 개체의 '다양성'을 해칠 수 있습니다. 말하자면 모든 꼬마자동차가 왼쪽에 있는 장애물만 못피하는데, 왼쪽 장애물을 피할 수 있는 유전자가 멸종해서 더이상의 개선이 불가능한 경우가 생길 수 있다는 것이죠.(물론 돌연변이가 있긴 하지만, 돌연변이에만 의존하는 유전자알고리즘은 비효율적입니다)

다양성에 대한 이야기는 다음 기회에 하도록 하겠습니다. 다만, 순위법이든 재계산법이든 후반에 선택압을 높이기 위해 사용할 수도 있지만 반대로 초반에 선택압을 줄여서 다양성을 유지하기 위해 사용할 수도 있습니다.

GA - 자동차[2] 재생산

3. 가상환경에서의 적응도 테스트
이부분은 자세한 알고리즘은 생략하겠습니다. 단지 먼저 1000점을 주고, 임의로 만들어진 도로를 앞에서 설계한 유전자에 따라 일정거리(100칸) 이동시키면서 장애물을 들이받을 때마다 10점씩 감점시키는 것입니다. 다만 만약 앞 3칸이 다 장애물로 채워진 경우, 자동차는 장애물을 들이받을 수밖에 없기에 이런 장애물은 미리 제거하였습니다.

4. 재생산할 꼬마자동차 찾기
높은 점수를 받은 꼬마자동차를 찾아 재생산해야 '더 우수한 꼬마자동차'가 만들어질 수 있습니다. 재생산할 꼬마자동차를 찾는 가장 기본적인 방법은 룰렛법입니다. 룰렛법에 의하면 각자의 꼬마자동차가 선택될 확률은 그 꼬마자동차의 점수와 비례합니다.

function SelectParent()
.. // 모든 꼬마자동차의 점수 합 계산
.. totalscore := 0
.. for i := 0, 128 do
..... totalscore := totalscore + car[i].score
.. end

.. // 점수비율로 선택
.. rnd := Random(0:totalscore - 1)
.. for i := 0, 128 do
..... if car[i].score > rnd then
........ return car[i]
..... end
..... rnd := rnd - car[i].score
.. end
.. error Not Selected
end

5. 교차
선택된 두 꼬마자동차를 복제하는 것만으로는 더 우수한 꼬마자동차를 얻을 수 없습니다. 꼬마자동차의 유전자를 섞어야 선택된 두 부모의 장점을 이어받은 꼬마자동차를 얻을수 있죠.
실제 생물계에서도 오른쪽 그림과 같이 DNA가닥의 교차가 일어납니다.
여기서는 가장 간단한 1점교차를 사용해 유전자를 혼합하기로 하겠습니다. 즉, 임의의 한 점을 골라 그 점을 중심으로 유전자를 바꾸는 것입니다.
이를테면

A : 02101001
B : 11022120
였던 유전자가 3번 위치에서 교차가 일어났을 경우
A : 11001001
B : 02122120
가 되는 것입니다.

procedure CrossOver(Car A, car B)
.. // 교차가 일어날 위치 결정
.. crosspoint = Random(1, 7)

.. // 실제 교차
.. for k = 0, crosspoint do
..... tmp = A.gene[k]
..... A.gene[k] = B.gene[k]
..... B.gene[k] = tmp
.. end
end

한편 교차에는 위와 같은 일점교차뿐 아니라 2점교차 및 n점교차도 존재합니다. n점교차란 n개의 점을 선택해 자른 후 각각의 조각을 서로 바꾸는 교차입니다.
다음 유전자를
A : 02101001
B : 11022120
다음 유전 2, 5, 7점에서 3점교차를 한다면
A : 11101121
B : 02022000
와 같은 두 유전자가 만들어집니다.

마지막으로 랜덤교차는, 각각의 유전자 하나하나마다 일정확률을 적용시켜 교환할지 말지를 결정하는 교차방법입니다.
A : 02101001
B : 11022120
이것을 랜덤교차시킨다면
A : 11121021
B : 02002100
같이 보다 많이 뒤섞이게 됩니다.

6. 돌연변이
돌연변이는 임의의 비트를 전혀 다른 값으로 바꾸어버림으로써 새로운 정보를 만들고 유전자의 다양성을 증가시키기 위한 기본적인 방법입니다.
돌연변이 없이는 완전히 새로운 정보를 만들어낼 수도 없습니다(이 꼬마자동차는 처음 만들었을때 모든 유전자가 '직진'으로만 채워져 있기에 돌연변이 없이는 옆으로 이동이 불가능하죠). 그러나 돌연변이는 자칫하면 이미 잘 만들어진 유전자를 흐트러뜨릴 수도 있습니다(장애물을 잘 피해가던 꼬마자동차가 돌연변이에 의해 장애물을 들이받을 수도 있습니다). 그러므로 유전자알고리즘에서는, 돌연변이를 적용하더라도그 비율은 매우 낮게 적용합니다.
이 꼬마자동차의 경우에는 각 유전자 비트가 0.1%확률로 돌연변이를 일으키도록 설정했습니다.

procedure Mutantation(Car a)
.. for k = 0, 8 do
..... if Random(0, 999) == 0 then
........ a.gene[k] := Random(0, 2)
..... end
.. end
end

이렇게 새롭게 만든 128개의 꼬마자동차들을 원래의 배열로 옮기면 한 세대가 끝납니다. 이 새로운 세대를 대상으로 적응도테스트를 반복하면 점차 적응성이 높아지는 모습을 볼 수 있습니다.
다음은 실제로 유전자알고리즘을 돌린 결과입니다. 각 세대당 최고, 최저, 평균점수를 표시했습니다.

Generation 0 MaxScore:920 MinScore:690 AverageScore:810
Generation 1 MaxScore:890 MinScore:710 AverageScore:809
Generation 2 MaxScore:900 MinScore:720 AverageScore:802
Generation 3 MaxScore:930 MinScore:710 AverageScore:801
Generation 4 MaxScore:910 MinScore:720 AverageScore:809
Generation 5 MaxScore:910 MinScore:680 AverageScore:807
Generation 6 MaxScore:900 MinScore:710 AverageScore:804
............
Generation 999 MaxScore:1000 MinScore:830 AverageScore:935
Generation 1000 MaxScore:1000 MinScore:790 AverageScore:930
Generation 1001 MaxScore:980 MinScore:830 AverageScore:934
Generation 1002 MaxScore:990 MinScore:870 AverageScore:935
Generation 1003 MaxScore:990 MinScore:850 AverageScore:939
Generation 1004 MaxScore:1000 MinScore:840 AverageScore:935
Generation 1005 MaxScore:990 MinScore:840 AverageScore:934
Generation 1006 MaxScore:990 MinScore:840 AverageScore:938
Generation 1007 MaxScore:990 MinScore:850 AverageScore:935
Generation 1008 MaxScore:990 MinScore:860 AverageScore:937
Generation 1009 MaxScore:990 MinScore:810 AverageScore:938
Generation 1010 MaxScore:980 MinScore:870 AverageScore:933
Generation 1011 MaxScore:1000 MinScore:860 AverageScore:935
Generation 1012 MaxScore:990 MinScore:850 AverageScore:935
Generation 1013 MaxScore:980 MinScore:860 AverageScore:929
......

1000세대 이상 지난 상태입니다. 1000점짜리(모든 장애물을 완전하게 피한) 꼬마자동차가 나타났군요. 하지만 만점 꼬마자동차가 계속 유지되지 않습니다. 만점 꼬마자동차가 도태되었다가 다시 만들어지는 현상의 반복이군요.
다음번엔 이것을 한번 고쳐봅시다.