GA - 자원운송계획 - 고립과 이주

8. 고립과 이주


갈라파고스 군도의 수많은 섬들에 핀치새들이 살고 있습니다. 그들은 섬 밖의 다른 핀치새들과는 교류가 끊긴채 섬 안의 핀치새들끼리만 짝짓기를 하며 번식했습니다. 그 결과 핀치새들은 섬에 따라 조금씩 다른 형태로 - 다양성을 유지한 채로 - 남아 있습니다.(그림 및 사진 출처)

유전자 알고리즘에서도 다양성을 유지하기 위해 이와 같은 원리 - 고립(isolate)을 사용할 수 있습니다. 커다란 하나의 개체군을 번식시키는 것이 아니라 작은 개체군 여러개를 번식시키는 것이죠.
게다가 가끔씩 일부 개체를 다른 개체군으로 이주(migration)시킨다면, 새로운 유전자를 받아들여 다양성이 더 늘어나는 효과를 얻을 수 있습니다.

이 운송문제에서는 크기 8193의 개체군 하나만을 사용했었습니다. 이번에는 크기 1025의 개체군 8개로 나누어 실행해 보도록 하겠습니다. 그러기 위해서는 메인루틴이 약간 달라지겠군요.

begin
.. declear Horde[8][1025];
.. for k := 0, 8 do
..... for g := 0, 1025 do
........ call Initialize(Horde[k][g]) // 유전자초기화
..... end
.. end

.. for generation := 0, 500 do
..... for k := 0, 8 do
........ // k번째 무리에 대해 적응도 계산
........ for g := 0, 1025 do
........... call FitnessCalc(Horde[k][g])
........ end
........ // k번째 무리 재생산(Elite기법 + T=0.99의 토너먼트법)
........ call Regenerate(Horde[k])
..... end
..... // 일정확률로 개체 이주시킴(바꾸기)
..... if MigrationRate then
........ hordeA := Random(0, 7)
........ hordeB := Random(0, 7)
........ slotA := Random(0, 1024)
........ slotB := Random(0, 1024)
........ call Swap(Horde[hordeA][slotA], Horde[hordeB][slotB])
..... end
.. end
end

9 새로운 결과
8개 그룹별로 최고적응도가 다음과 같이 나왔습니다. 그중에서도 최대적응도는 붉은색으로 처리했습니다.

499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 437/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 2 0 0 0 0 0 0 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 1 0 2 2 0 0 7 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 421/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 4 0 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 0 2 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0
499 : 423/0
. A B C D E F G H I J
A 0 0 0 0 0 0 0 0 0 0
B 0 0 0 0 0 0 0 0 0 0
C 0 0 0 0 0 0 0 2 0 0
D 0 0 0 0 0 0 0 0 0 0
E 0 0 0 0 0 0 0 0 0 0
F 0 0 0 3 0 0 0 0 0 0
G 5 3 0 2 2 0 0 5 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 2 0 0 0 0 0 0
J 0 0 0 0 0 0 0 0 0 0

이 경우 연료소모량은 421로 단일개체군일 경우보다 좋은 결과가 나왔다는 것을 알 수 있습니다.