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 - 오델로 - 유전자 작업 프로시저들

2. 유전자 초기화 및 각종 작업 프로시저
앞에서 이야기한 것처럼 오델로플레이어가 기존에 마주치지 못했던 패턴을 만난다면 그 패턴을 추가합니다. 그러므로 초기화는 유전자묶음을 비우는 것으로 할 수 있습니다.

procedure GeneInitialize(gene)
.. gene.Size := 0;
end

그리고, 현 상황에서 만든 패턴을 가지고 가중치를 가져오기 위한 프로시저(함수)입니다.

fuction WeightOfPattern(gene, pattern)
.. for k := 0, gene.Size do
..... // gene.Pair[k]는 패턴과 가중치의 쌍
..... if IsSamePattern(gene.Pair[k].Pattern, pattern) then
........ // 패턴이 일치할 경우
........ return gene.Pair[k].Weight;
..... end
.. end
.. // 같은 패턴을 찾지 못했을 경우 패턴추가
.. // gene.Size위치에 추가
.. rndweight := Random(0, 1) // 0~1 사이의 랜덤값
.. gene.Pair[gene.Size].Pattern := pattern;
.. gene.Pair[gene.Size].Weight := rndweight;
.. gene.Size := gene.Size + 1;
.. return rndweight;
end

즉 패턴을 찾았으면 해당패턴의 가중치를, 찾지 못했으면 임의의 가중치로 추가한 후 가중치를 리턴합니다.
이 함수에서 사용한 IsSamePattern은 다음과 같이 방향을 무시하고 비교하는 함수입니다.

function IsSamePattern(patternA, patternB)
.. lenA := patternA.PatternLength;
.. lenB := patternB.PatternLength;
.. if lenA != lenB then // 길이가 다를 경우
..... return false;
.. end
.. for k := 0, lenA do
..... if patternA[k] !=patternB[k] then // 다를 경우
........ break; // for루프 빠져나감
..... end
.. end
.. if k == lenA then // 루프를 다 돌았음 - 일치
..... return true;
.. end
.. for k := 0, lenA do
..... if patternA[k] != patternB[lenB - k - 1] then // 역순으로 비교, 다를경우
........ return false
..... end
.. end
.. return true; // 비교완료, 동일함
end

GA - 오델로 - 유전자설계

오델로(Othello)라는 게임이 있습니다. 8×8의 칸에 교대로 돌을 놓으며, 내 돌 사이에 상대방의 돌을 끼워넣으면 내 돌로 바뀌는 것이죠. 물론 오델로게임을 하는 AI는 많이 나와 있습니다. 그런데 이 오델로게임을 하는 AI를 유전자알고리즘으로 진화시킬 수 있을까요?

1. 유전자설계 및 작동방식
일반적으로 이런 게임에서는 놓을 수 있는 자리를 탐색 후 각 자리에 가중치를 계산, 가장 높은 가중치를 갖는 장소를 찾는 것이 일반적입니다. 이를테면 다음과 같은 상황에서 흰돌이 놓을 차례라면
흰돌을 놓을 수 있는 '가'~'마'까지 다섯군데의 가중치를 계산합니다.
오델로에서 가장 중요한 것은 직선으로 상대방 돌을 포위할 수 있는가 없는가입니다. 그러므로 '나' 위치의 가중치를 계산한다면 다음과 같은 네 방향의 패턴을 추출합니다.
이때 주의할 것은 흰돌이냐 검은돌이냐가 아니라 내돌이냐 상대방돌이냐로 구분을 해야 합니다. 흑돌이냐 백돌이냐로 구분하면 흑의 입장이냐 백의 입장이냐에 따라 가중치가 달라지기 때문이죠.
그러므로 빈칸을 '.', 상대방돌을 'E', 내돌을 'M', 가중치를 계산할 장소(여기서는 '나' 칸을 의미)를 '+'로 한다면, 붉은색선 방향으로는 '..+EMM..', 노란색선 방향으로는 '...+....', 녹색선 방향은 '..+EE..', 보라색선은 '..+E..'이란 패턴이 추출됩니다. 이렇게 추출된 패턴으로부터 가중치를 구하면 됩니다.

그렇다면 여기서 만들려는 '오델로플레이어'의 유전자는 이러한 '패턴과 가중치의 묶음'으로 할 수 있을 것입니다. 만약 이 오델로플레이어의 유전자가 다음과 같다면

('.M+.E.', 0.7235)
('...+....', 0.798)
('..+EMM..', 0.37)
('..EE+..', 0.625)
('..M+EM.', 0.012)

각 방향에서 찾은 패턴을 이 '유전자 묶음'으로부터 찾아 가중치를 더합니다. '..+EMM..'의 경우는 0.37, '...+....'의 경우는 0.798이 되겠군요. '..+EE..'은 이 묶음에 없지만 대신 '..EE+..'은 존재하는군요. 그 값은 0.625입니다.
그런데 '..+E..'의 경우는 뒤집힌 '..E+..'도 존재하지 않습니다. 이것은 이 오델로플레이어가 이와 같은 패턴을 처음 만난다는 뜻입니다. 이럴 경우는 이 패턴을 끼워넣고 랜덤값을 추가합니다. 즉

('.M+.E.', 0.7235)
('...+....', 0.798)
('..+EMM..', 0.37)
('..EE+..', 0.625)
('..M+EM.', 0.012)
('..+E..', 0.152)

랜덤으로 발생된 0.152라는 가중치를 가지고 '..+E..'라는 패턴이 추가되었습니다. 결국 '나' 위치의 가중치는 0.37 + 0.798 + 0.625 + 0.152 = 1.945가 되겠죠. 이런 식으로 '가'~'마'까지의 가중치를 계산한 후 가장 높은 가중치의 위치를 선택하는 방식으로 만들었습니다.

GA - LISP-link-Language And/OR

5. 유전자 초기화
일반적으로 트리구조는 재귀호출과 동적할당을 통해 구현합니다.
LlL에서는 다음과 같이 유전자 초기화를 합니다.

procedure GeneInit(LlLRoot root)
begin
.. root.Program := new LlLNode;
.. NodeInit(root.Program, 3); // 3은 하위노드를 만들 수 있는 확률
end

procedure NodeInit(LlLNode node, double rate)
begin
.. // node.Command 세팅
.. if Random(0, 1) >= 0.1 then
..... node.Command := RandomCommand; // 19개 명령어들 중 하나
.. eles
..... node.Command := Random(0, 1000); // 0~1000 사이의 상수
.. end

.. // 하위노드 만들기(맥스 3개)
.. node.BrenchNumber := 0;
.. for k := 0, 3 do
..... if rate > Random(0, 1) then
........ node.Brench[node.BrenchNumber] = new LlLNode;
........ NodeInit(node.Brench[node.BrenchNumber], rate / 2);
..... end
.. end
end

6. 변수리스트
명령어리스트에서 본 것과 마찬가지로, LlL에서는 변수를 사용합니다. 그러나 변수의 갯수가 무한이 될 수는 없습니다.
여기서는 32개의 변수를 사용합니다. 그러나 만약 (setv () ())나 (getv ()) 함수의 경우, 32 이상의 변수위치를 가리키게 된다면 32로 나눈 나머지로 위치를 결정합니다.
이를테면

(setv (364) (21))

이라면 364 % 32 == 12이므로 13번째 변수(0까지 포함하므로)에 21값을 넣습니다.

7. 실행
간단한 인터프리터를 만들어서 저 프로그램을 실행시킵니다. 먼저 32개 모든 변수를 0으로 초기화하고, 몇몇변수에 초기값을 넣어 트리모양으로 구성된 프로그램을 따라 실행시킵니다.
이때 프로그램에 따라 (특히 while문이 포함되어 있을 경우) 무한루프에 빠질 가능성이 있으므로 3000개의 명령어를 실행한 후에는 프로그램을 강제로 끝내도록 했습니다.
그리고 그 결과를 그 프로그램의 fitness로 저장한 후 유전자알고리즘으로 진화시켰습니다.

8. AND/OR 연산 결과
LlL을 이용하여 AND/OR연산을 할 수 있는지 확인해 봤습니다.
두개의 입력(0/1)을 각각 [0], [1]변수에 넣은 후 출력값을 살펴보았습니다. 다만 출력값이 1 이상이면 1로, 0 이하면 0으로 간주했습니다.
이때 Fitness를 계산하는데 트리의 크기를 고려해야 합니다.
1차원 또는 2차원 유전자의 경우 균일교차로서 교차가 어떻게 일어나더라도 유전자의 크기가 일정합니다. 그러나 나무형유전자의 교차는 불균일교차로서 트리 크기를 제어하지 않는다면 트리가 얼마나 커질지 알 수 없습니다.
그러므로 100번 연산을 해서 점수를 매긴 후, 트리 크기를 뺀 값을 Fitness로 정했습니다.
그 결과가 다음과 같은 프로그램들입니다.

OR
(getv
.. (getv
..... (>
........ (=
........ )
........ (!=
........ )
..... )
.. )
.. (/
.. )
.. (while
.. )
)

And
(getv
.. (getv
..... (＜
..... )
.. )
.. (if
..... (>=
..... )
.. )
.. (-
..... (＜=
..... )
.. )
)

필요없는 부분(나중에 돌연변이에 의해 잘려나갈 부분)을 정리하고 보기쉽게 정리하면 다음과 같은 프로그램이 남습니다.
OR
(getv
.. (getv
..... (1)
.. )
)

And
(getv
.. (getv
..... (0)
.. )
)

결국 OR는 var[var[1]], AND는 var[var[0]]과 동일합니다. 비록 일반적인 형태는 아니지만, AND/OR연산법을 찾은 것은 맞습니다. 물론 이것은 입력이 0/1 뿐이고 입력변수도 [0]과 [1]이기에 가능한 해법입니다.

GA - 자원운송계획 - 유전자설계

다음과 같이 A~J까지 10개의 도시가 배치되어 있습니다.


몇몇 도시에서는 어떤 자원이 생산되며 그 자원은 모든 도시에서 조금씩 소비됩니다. 각 도시들의 자원생산량과 소비량은 다음과 같습니다.

A : 0/ 5
B : 0/ 3
C : 7/ 5
D : 0/ 7
E : 0/ 2
F : 5/ 2
G : 23/ 3
H : 0/ 7
I : 5/ 3
J : 0/ 3

그러므로 각 도시에서 남아도는 자원을 모자라는 도시로 옮기는 수송계획을 짜야 합니다.
이때 가장 경제적으로 수송하기 위해서는 어떻게 해야 할까요? 문제를 간단히 하기 위해 각 자원을 운송하는 비용은 두 도시 사이의 거리에만 관계되는 것으로 합니다.

1. 유전자 설계
여기서는 2차원 유전자를 적용하기로 하겠습니다.
유전자의 구조는 오른쪽 그림과 같습니다. 각각 from도시에서 to 도시로 옮기는 자원량으로 정의합니다.
오른쪽 유전자에 의하면 A도시에서 B도시로 2개, C도시로 6개, E도시로 2개...를 옮긴다는 뜻입니다(물론 A에서 C로 6개 옮겼다가 다시 C에서 A로 6개 옮기니 이 유전자의 적응도는 매우 낮겠지만 말입니다).
기존에는 1차원 선형 유전자만 가지고 놀았지만, 이 문제에서도 유전자가 2차원으로 확장되었다는 것만 빼고는 동일합니다. 다만 1차원유전자에서 사용하던 교차기법은 사용할 수가 없습니다(2차원 이상 다차원유전자의 교차기법은 뒤에서 다루도록 하겠습니다).

2. 유전자초기화
유전자초기화는 일반적인 경우와 동일합니다. 10×10의 매트릭스를 만들고 각 칸을 0으로 만듦니다

procedure GeneInit(Gene gene)
.. for from := 0, 10 do
..... for to := 0, 10 do
........ gene[from][to] := 0
..... end
.. end
end

8193개의 개체를 만들고 각각의 유전자를 위와 같이 초기화시킵니다.

3. 적응도테스트
적응도를 계산하기 위한 요소는 두가지가 있습니다. 먼저 저 유전자대로 자원을 옮기기 위한 연료, 그리고 상품을 다 옮긴 후 필요량을 잘 채웠는지 판단이 필요합니다
① 연료
물건을 옮기기 위한 연료를 계산합니다. 도시간 운송을 위한 연료량은 도시간 거리에만 비례하므로 필요한 연료량은 (자원량) * (도시간 거리)입니다.
그러나 이렇게만 하면 한가지 문제가 생깁니다. 위의 유전자 보기에서처럼 B도시에서 B도시로 8개의 자원을 옮길 경우 연료가 0이므로 이러한 단점을 거를 수가 없는 것입니다. 그러므로 트럭 시동걸 때의 연료를 추가해서 (자원량) * (도시간 거리 + 1)을 필요한 연료량으로 정의합니다.

function FuelExhause(Gene gene, CityList citylist)
.. fuel := 0
.. for from := 0, 10 do
..... for to := 0, 10 do
........ quantity := gene[from][to]
........ distance := DistanceCalculate(from, to) // from도시와 to도시 사이의 거리
........ fuel := fuel + quantity * (distance + 1)
..... end
.. end
.. return fuel
end

② 자원 과부족 상황
유전자에 기록된 대로 자원을 옮긴 후 제대로 자원이 분배되었는지 확인해야 합니다. 각 도시별로 남거나 모자라는 자원의 합을 계산합니다.

function ResourceLeak(CityList citylist)
.. leak := 0
.. for city := 0, 10 do
..... cityleak := citylist[city].Need - citylist[city].AfterTransport
..... if cityleak < 0 then
........ cityleak := -cityleak
..... end
..... leak := leak + cityleak
.. end
.. return leak
end

③ 총 적응도 계산
위에서 계산한 FuelExhause와 ResourceLeak을 가지고 총 적응도를 계산합니다. 이때 둘 다 작을수록 적응도가 높으므로 총 적응도는 다음과 같이 계산합니다.

TotalFitness := -FuelExhause - ResourceLeak * 50

이때 연료보다는 자원배분이 더 중요하므로 ResourceLeak쪽에 50배의 가중치를 더 주었습니다(만약 이 가중치가 없다면, 유전자알고리즘은 차라리 자원을 운송하지 않고 연료를 아끼는 쪽으로 갈 수도 있습니다).

GA - CNNC를 실은 꼬마자동차[1] - 공진화와 유전자설계

1. 개요
장애물을 피해 움직이는 꼬마자동차는 이미 앞에서 진화시켜본 적이 있습니다. 8개의 유전자를 가진 자동차들이었죠.
이번에는 8개의 유전자를 가진 꼬마자동차가 아니라 CNNC를 탑재한 꼬마자동차를 진화시키도록 하겠습니다. 기본적으로 바로 앞 3칸의 블럭정보를 받아들여 CNNC에 기초한 신경망을 돌려 다음 행동을 결정하는 것이죠.
하지만 이번 문제에서는 한가지 요인을 더 넣었습니다. '연료'란 개념을 넣었죠.
꼬마자동차는 최대크기 20의 기름통을 가지고 있습니다. 한칸 이동할 때마다 1씩, 그리고 장애물 위를 통과하기 위해서는 5의 기름을 소모합니다.
물론 자동차가 통과해야 할 거리는 100입니다. 그러므로 길 위에는 10칸마다 하나씩 기름통을 10만큼 채울 수 있는 기름이 존재합니다. 그리고 각 자동차들은 다음 기름통의 위치를 감지할 수 있는 감지기를 추가합니다.

2. 공진화
개인의 발전을 위해 라이벌이 필요하듯, 천적들이 서로가 서로의 선택압으로 작용하여 적응도가 높아지는 경우가 있습니다. 이러한 현상을 공진화라고 합니다.
그렇다면 이 꼬마자동차의 천적은 무엇일까요? 이 꼬마자동차가 극복해야 할 대상, 즉 장애물이 깔려있는 돌길 자체가 천적이 되겠죠.
꼬마자동차의 적응도는 '돌길을 얼마나 멀리 갔는가'에 따라 결정됩니다. 반대로 돌길의 적응도는 '자동차들을 얼마나 방해했는가'로 결정할 수 있습니다. '특정한 장애물 패턴'을 가지고 있는 돌길에 많은 자동차들이 발목을 잡힌다면, 그 돌길은 높은 적응도를 갖고 진화적 우위를 차지해서 결국 그러한 '특정한 장애물 패턴'은 점점 많아집니다. 다시 그 '특정한 장애물 패턴'을 돌파할 수 있는 자동차들이 진화적 우위를 차지합니다.

3. 유전자설계 - 꼬마자동차
꼬마자동차의 유전자는 앞의 XOR회로를 진화시키기 위해 사용했던 신경망 그대로입니다. 다만 여기서는 (뒤에서 나올 이유로) 신경세포의 전하량을 0~1이 아니라 -1~+1 사이로 정의했습니다. 이것은 시그모이드함수를 다음과 같이 수정함으로써 간단히 구현됩니다.


4. 유전자설계 - 돌길
돌길의 유전자는, 다음 그림과 같이 설계됩니다. 돌(장애물)과 기름통이 놓여있는 길이 100인 길이죠.



갈색은 장애물, 녹색은 기름통입니다. 그 외의 흰 부분은 장애물 없는 빈 공간입니다.

procedure InitGene(StoneRoad gene)
.. for length := 0, 99 do
..... gene[length][0] := ROCK
..... for width := 1, 10 do
........ gene[length][width] := ROAD
..... end
..... gene[length][11] := ROCK
..... if length % 10 == 5 then
........ gene[length][Random(1, 10)] := FUEL
..... end
.. end
end

코드를 보면 아시겠지만, 최초의 돌길은 양쪽 가장자리를 막고 있는 장애물 외에는 아무런 장애물도 없이 일정 거리마다 연료통만이 흩어져 있는 '가장 쉬운 돌길'들입니다.

미리 말씀드리지만, 유전자알고리즘을 사용하다 보면 유전자알고리즘으로 만들어진 녀석들이 상당히 '얍삽'하다고 느낄 때가 있습니다. 이 문제에서도 알 수 있지만, 결국 '규칙'을 잘 만들지 않으면 이상한 행동을 할 때가 있습니다(사실 그 녀석들도 주어진 규칙 안에서 최대 적응도를 찾은 것이니 뭐라고 할 수도 없죠).

GA - CNNC를 이용한 XOR 회로[2] - 유전자 설계

3. 유전자설계
신경망에서 하나의 노드에 필요한 정보는 다음과 같습니다.
① 입력스트림 : 입력노드들과 그 노드와의 연결 강도. float형의 벡터이며 그 크기로 연결강도를 표시합니다. 이 XOR회로에서는 16개의 채널을 준비합니다.
② Layer : 노드를 구분하기 위해 사용. Layer가 0보다 작으면 입력노드, 1보다 크면 출력노드, 그 사이면 은닉노드
③ Bias : 입력스트림의 하나로 만들 수도 있지만 여기서는 노드가 따로 가지고 있음
④ SigmoidFactor : 입력의 합을 출력으로 계산할때 시그모이드 팩터를 사용
XOR회로의 경우 하나의 CNNC는 2개의 입력노드, 1개의 출력노드(그 외에 몇개가 될지 모르는 은닉노드)로 구성됩니다. 초기상태에는 은닉노드가 없으므로 CNNC 하나의 유전자는

+1.1/Bias/SF(ABCDEFGHIJKLMNOP)(abcdefghijklmnop)
-0.1/Bias/SF(ABCDEFGHIJKLMNOP)(abcdefghijklmnop)
-0.2/Bias/SF(ABCDEFGHIJKLMNOP)(abcdefghijklmnop)

과 같습니다. 이 경우 Bias, SF(SigmoidFactor), A~P, a~p는 모두 float형입니다. 가장 앞의 숫자는 Layer이며 0 이하는 입력노드, 1 이상은 출력노드를 의미합니다. 뒤의 A~P, a~p의 리스트는 각각 송신채널, 수신채널입니다. 이 값이 0이면 그 채널로 송신/수신을 않는다는뜻이며 0이 아니라면 그 채널로 송수신을 한다는 뜻입니다.

procedure InitGene(Gene gene)
.. // 3개의 노드를 만듦
.. InitNode(gene.Node[0], -0.2)
.. InitNode(gene.Node[1], -0.1)
.. InitNode(gene.Node[2], 1.1)

.. // 입력과 출력노드 사이에 초기링크 만들기
.. MakeLink(gene.Node[0], gene.Node[2])
.. MakeLink(gene.Node[1], gene.Node[2])
end

procedure InitNode(Node node, double layer)
.. node.Layer = layer
.. node.Bias = Random(-5, 5)
.. node.SigmoidFactor = Random(0.001, 3)
.. for k := 0, 16 do
..... node.SendChannel[k] := 0
..... node.RecvChannel[k] := 0
.. end
end

procedure MakeLink(Node from, Node to)
.. channel := Random(0, 15)
.. from.SendChannel[channel] := Random(-5, 5)
.. to.RecvChannel[channel] := Random(-5, 5)
end

4. 발생(Ontogeny)
개념상으로는 앞에서 말한대로 채널을 통한 노드들간의 채널통신으로 이해했지만, 실제 적용하기 위해서는 기존의 신경망방식으로 바꾸는 것이 좋습니다. 즉 송신채널과 수신채널이 일치하는 노드들끼리 연결을 만드는 것입니다.
만약 두 노드의 송신채널과 수신채널이 동시에 0이 아닐 경우 두 노드 사이에는 연결이 생깁니다. 이 연결의 크기는 송신채널의 값과 수신채널의 값에 의해 결정됩니다.
아무리 송신채널이 강하게 송신해도(송신채널의 값이 커도) 수신채널에서 약하게 수신한다면(수신채널의 값이 작으면) 두 노드 사이의 연결강도는 약해집니다. 반대로 수신채널의 값이 커도 송신을 약하게 한다면(송신채널의 값이 작으면) 마찬가지로 연결은 약해지죠.
여기서는 두 채널값으로 연결의 강도를 계산하는 공식으로 기하평균을 사용했습니다. 기하평균은 다음과 같이 계산됩니다.



procedure Ontogeny(Gene gene, Brain brain)
.. // 각 노드에 해당하는 세포를 만듦
.. for k := 0, gene.NodeNumber do
..... brain.Cell[k].Layer := gene.Node[k].Layer
..... brain.Cell[k].Bias := gene.Node[k].Bias
..... brain.Cell[k].SigmoidFactor := gene.Node[k].SigmoidFactor
.. end

.. // 각 세포들 연결
.. for k := 0, brain.CellNumber do
..... for m := 0, brain.CellNumber do
........ // 링크정보를 알기 위해 brain.Cell[k,m]에 해당하는 노드를 찾음
........ nodek := FindNode(gene, brain.Cell[k])
........ nodem := FindNode(gene, brain.Cell[m])
........ // k와 m이 얼마만큼의 세기로 연결되어 있는지 확인
........ weigth = 0;
........ for c := 0, 16 do
........... mult := nodek.SendChannel[c] * nodem.RecvChannel[c]
........... if mult != 0 then
.............. gioavg := sqrt(mult) // 기하평균 계산
.............. weigth := weigth + gioavg
........... end
........ end
..... MakeLink(brain.Cell[k], brain.Cell[m], weigth)
..... // k->m으로 강도 weigth의 입력 만듦
.. end
end

5. 적응도 계산
위에서 만들어진 brain을 가지고 적응도를 계산합니다. 자세한 알고리즘은 생략하겠지만, 입력셀에 랜덤으로 0/1을 넣고 신경망을 돌려 나온 값과 XOR계산값을 비교하여 그 차이가 작을수록 해당 CNNC의 적응도를 높이는 방식입니다. 임의의 입력값으로 100회를 반복한 후 결과를 최종 적응도로 결정했습니다.

단, 이때 출력에 따른 적응도함수를 다음과 같이 한다면 어떨까요?

.. output := think(a, b)
.. correct = a ^ b
.. if abs(correct - output) > 0.5 then
..... AddFitness(0)
.. else
..... AddFitness(10)
.. end

이 방식의 가장 큰 문제점은, 참값과의 차이가 0.51인(보다 적은 변이로 참값으로 갈 수 있는) 신경망과 0.9인 신경망 둘 다 적응도가 0으로써 둘 사이의 적응도 차이를 알 수 없다는 점입니다. 유전자알고리즘의 원칙인 조금이라도 더 적응도가 우수한 것을 찾을 수가 없는 것이죠. 그러므로 적응도함수는 반드시 꼭대기가 없는 경사함수가 되어야 합니다.
이 XOR 신경망에서는 다음과 같은 적응도 함수를 사용했습니다.

.. output := think(a, b)
.. correct = a ^ b
.. diff = abs(output - correct)
.. subfit = 1 - diff // 차이가 작을수록 적응도 높아짐
.. AddFitness(subfit * subfit * 10)

그냥 subfit를 적응도로 사용해도 되지만 여기서는 참값에 가까와질수록 선택압을 높이기 위해 subfit의 제곱을 사용하여 오른쪽 그림과 같은 함수가 되었습니다.

각 XOR신경망에 대해 랜덤입력에 의한 적응도테스트를 100회 실시하여 그 합을 적응도로 간주, 재생산을 실시합니다.

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

GA - 장사꾼여행문제(TSP) [1] - 유전자 설계

TSP(Travelling Salesman Problem)는 잘 알려진 대로, 여러개의 도시를 최단거리로 순회하는 방법을 찾는 대표적인 NP문제입니다. 쉽게 말하면 '다항식적으로 문제를 풀 수 없다' -> '무식하게 모든 경우의 수를 계산해서 풀어야 한다.'는 것이죠.

이 문제의 어려운 점은 도시가 늘어날수록 가능한 조합이 엄청난 속도로 증가한다는 것입니다. 이를테면 5개의 도시일 경우 5! = 120가지 조합을 계산해서 최소값을 찾으면 되지만, 10개의 도시라면 10! = 3628800가지 조합, 20개라면 20! = 2432902008176640000가지 조합을 따져야 합니다. 100개의 도시라면? 9로 시작하는 158자리 길이의 숫자만큼의 조합을 계산해야 합니다. 그야말로 '빅뱅부터 우주의 종말까지' 계산해도 끝나지 않을 계산량이죠.
그래서 이런 문제는, '최소값'을 찾는 것은 포기하고 '근사값'을 찾는 여러가지 알고리즘이 개발되어 있습니다.

여기서는 장사꾼이 최소 이동거리로 150개 도시를 지나는 문제를 유전자 알고리즘을 사용해서 근사값을 찾는 방법을 알아보겠습니다.

만약 '무식한 방법'으로 최선의 경로를 찾기 위해서는 150!개 경우의 수를 다 계산해야 합니다. 150!의 값은 다음과 같은 263자리 숫자입니다. 5713383956445854590478932865261054003189553578601126418254 83758331798291248453983931265744886753111453771078787468542 0416266625019868450446635594919592206657494259209573577892 9325357290444962472405416790722118445437122269675520000000 000000000000000000000000000000

1. 유전자 설계
TSP를 위한 가장 간단한 유전자는 돌아다닐 도시를 차례로 나열하는 것입니다. 만약 0~9까지 10개의 도시를 이동한다면, 유전자 9421850637은 9->4->2->1->8->5->0->6->3->7->9번 도시의 순서로 돌아다닌다는 의미입니다. 그러므로 1850637942나 0637942185, 3794218506 등도 동일한 유전자라고 할 수 있습니다. 또한 반대로 도는 2497360581 역시도 동일한 유전자입니다

역순유전자를 동일한 것으로 처리하기 위해서는, 모든 도시에 대해 A->B 이동시의 비용과 B->A 이동시의 비용이 동일해야 합니다. 만약 역방향으로 이동할 때의 비용이 차이난다면(바람이나 해류가 존재할 때 등) 역방향유전자를 동일한 것으로 처리할 수 없습니다.

이렇게 만드는 유전자의 경우에는 한가지 제약이 생깁니다. 같은 도시가 둘 이상 나와서는 안된다는 것이죠. 이를테면 9421850137과 같은 유전자는 6번도시는 빠뜨리고 1번도시는 두번 방문하게 되므로 제대로된 유전자가 아닙니다.
그러므로 최초 유전자를 초기화할 때라든지 교차, 돌연변이 등 유전자에 조작을 가할 경우에는 위와 같은 제약을 어기지 않도록 조심해야 할 필요가 있습니다.

GA - 자동차[1] 유전자설계 및 초기화

여러분은 오른쪽 그림과 같은 꼬마자동차를 만들었습니다. 그리고는 무선조종이 아니라 이 자동차가 스스로 장애물을 피해 움직이도록 하려고 합니다.
다만 센서가 약한 관계로 오른쪽 그림과 같이 단 세군데(바로 앞, 바로 앞의 왼쪽, 바로 앞의 오른쪽)만을 감지할 수 있습니다. 그리고 그 결과로 직진할지 왼쪽 앞으로 갈지 오른쪽 앞으로 갈지 결정해야 하는 것입니다.

물론 프로그래밍을 배운 사람은 초보자라도 간단하게 프로그램을 짤 수 있을 것입니다. 그러나 지금 이 자동차는 유전자 알고리즘을 공부하기 위한 샘플이니 직접 프로그래밍하는 것은 잠시 미뤄두시기 바랍니다.

1. 유전자 설계
유전자 프로그램을 할때 가장 첫단계는, 이 꼬마자동차의 '유전자를 설계'하는 일입니다. 보통 입력과 출력 사이의 상관관계를 유전자화시켜야 합니다.
이 꼬마자동차 문제에서 입력은 각 세 군데에서 장애물이 있는지 없는지 여부(장애물이 있으면 1, 없으면 0)로 나타낼 수 있습니다. 즉 8가지의 입력이 존재합니다.
출력은 각 상태일 경우 직진할지 왼쪽앞으로 갈지, 아니면 오른쪽 앞으로 갈지 결정해야 합니다.
그러므로 8개의 동작만으로 연결된 다음과 같은 유전자를 만들 수 있습니다.

차량	유전자(0:왼쪽앞으로 1:직진 2:오른쪽앞으로)
가	10212001
나	22120001
다	11220210
라	21010112
마	00211201
...	...

만약 꼬마자동차가 왼쪽과 같은 상황에 처했다면, 입력장치는 011, 즉 3이란 입력을 보냅니다. 각 꼬마자동차들은 자신의 유전자에서 3 위치를 검색, 다음에 어떤 행동을 할 것인지 결정합니다.
'가'의 경우 3 위치에 해당하는 것은 (첫 동작이 0이므로) <1-직진>입니다. 그러므로 '가'는 사람을 치고 지나가겠죠.
'다'의 경우 3위치의 동작은 <2-오른쪽앞>이므로 '다'는 나무를 향해 돌진할 것입니다.

이와같이 해서 꼬마자동차의 입력과 출력을 연결할 수 있는 유전자를 설계할 수 있습니다.

물론 다른 방식으로 유전자를 설계할 수도 있습니다. 그러나 이 꼬마자동차 문제는 유전자 알고리즘을 공부하기 위한 첫단계이므로 가장 간단하고 직관적인 유전자로 설계했습니다.

2. 최초 세대의 유전자 초기화(GeneInit)
이 프로그램에서는 한 세대의 꼬마자동차 수를 128대로 정의했습니다. 128개 꼬마자동차의 배열 또는 벡터를 만든 후 각 꼬마자동차의 유전자를 초기화하는 루틴을 만들어야 합니다.

사실 이 128이란 숫자는 유전자알고리즘에서 적당한 세대인구가 아닙니다. 보통 유전자알고리즘은 '수로 승부하는 방법'이라고 할 수 있습니다. 가능하면 많은 개체를 사용하여, 다양성을 증가시켜야 제대로된 결과가 나올 수 있습니다. 다만 이 꼬마자동차는 상당히 간단한 유전자 구조를 가지고 있기에 세대인구가 적더라도 비교적 빨리 원하는 결과를 얻을 수 있습니다. 보통 유전자알고리즘의 세대인구수는 최소 1000 이상, 대개 10000단위까지 올라갈 수 있습니다.

초기화루틴은 다음과 같이 정의합니다.

procedure GeneInit(KidCar car)
.. for i := 0,8 do
..... car.gene[i] := 1 // 모든 경우에 무조건 직진으로 세팅
end

일반적으로 유전자를 초기화하기 위해서는 유전자의 각 위치(bit)에 유전자가 허용하는 랜덤값을 넣는 것이 정도(正道)입니다. 즉 ..... car.gene[i] := Random(0:2) // 0, 1, 2중 임의 선택 가 되어야 합니다. 다만 이 꼬마자동차에서는 돌연변이 효과를 확인하기 위해 일부러 모든 경우 직진하는 코드를 넣었습니다.