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중 임의 선택 가 되어야 합니다. 다만 이 꼬마자동차에서는 돌연변이 효과를 확인하기 위해 일부러 모든 경우 직진하는 코드를 넣었습니다.