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들로 계속 실행