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

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

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