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로 단일개체군일 경우보다 좋은 결과가 나왔다는 것을 알 수 있습니다.

GA - 자원운송계획 - 실행결과

7. 실행결과
앞에서와 같은 방식으로 500세대동안 번식시킨 결과입니다.

499 : 455/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 2 0 0 3 0 3
H 0 0 0 0 0 0 0 0 0 0
I 0 0 0 0 0 0 0 2 0 0
J 0 0 0 0 0 0 0 0 0 0

앞의 455는 소모된 연료양, 뒤의 0은 자원의 과부족상황으로 모자라거나 남는 자원이 없이 잘 분배되었다는 뜻입니다.
밑에 있는 것이 유전자(이동상황)로, C에서 남는 2개(7개생산에 5개소모)를 H로 보내는군요. H는 C에서 오는 2개 외에 G에서 3개, I에서 2개 받아서 필요한 7개가 채워집니다. 우선은 해를 찾았습니다.

GA - 자원운송계획 - 재생산

4. 재생산
8193개의 개체들 중 최고적응도의 개체를 골라 엘리트로 복사하고, 나머지 8192개의 개체는 유전자알고리즘을 사용해 재생산했습니다.
T=0.99의 Tournament법을 사용하여 우수개체를 골라 교차 및 돌연변이를 일으켰습니다.

5. 교차
일반적인 유전자알고리즘의 경우와 같이 여기서도 재생산 대상을 두개 선택한 후 그들을 교차시킵니다. 그러나 유전자가 예전의 1차원 유전자가 아니라 2차원 유전자라는 문제가 있습니다.
일반적으로 2차원 유전자의 교차는 (아니 1차원부터 2차원, 3차원 이상의 고차원 유전자의 교차는) 구획나누기 이후 구획 재배치로 정의될 수 있습니다. 문제는 구획을 어떻게 나누느냐가 됩니다.
다음의 보기는 2차원의 경우이지만 n차원으로 확장시킬 수 있습니다.

① 다음 그림과 같이 x, y축을 몇개의 구획으로 나눕니다. 그후 아래 그림과 같이 순서대로 교차시키는 것입니다. 이것은 1차원교차에서 주로 사용했던 n점교차를 확장한 형태입니다.

② 또다른 방법은 구획을 다음 그림과 같이 도형으로 나누는 경우도 있습니다. 이 경우에는 구획 재배치가 쉽지 않아 보이지만, 간단히 짝수(0 포함) 또는 홀수개의 도형에 포함되는 구획만 교환하면 생각보다 쉽게 됩니다.

③ 마지막으로 임의로 선을 그어 구획을 나눌 수 있습니다.
①, ②번은 각각 하나의 축만, 그리고 각 차원에서의 원/구를 생각하면 되므로 4차원 이상의 유전자에도 비교적 쉽게 적용할 수 있습니다. 그러나 ③번은, 개념적으로는 3차원에서는 3각형평면의 연속, 4차원에서는 삼각뿔 도형의 연속, ... 등으로 할 수 있으나 직관적으로 다가오지 않아 상당히 어려운 작업이 될 수 있습니다.
여기서는 3개의 임의의 원을 그려 ②번과 같은 식의 교차를 시행했습니다.

procedure CrossOver(MoonBase a, MoonBase b)
.. // 세개의 임의의 원을 만듦
.. for k := 0, 3 do
..... circle[k].f := Random(0, 10) // 유전자크기가 10X10이므로
..... circle[k].t := Random(0, 10)
..... circle[k].radius := Random(0, 10)
.. end
.. for f := 0, 10 do
..... for t := 0, 10 do
........ covered := 0
........ // 3개 원중 몇개에 겹쳐지는지 계산
........... for k := 0, 3 do
.............. // (f,t)와 k번째 원 중심간 거리 계산
.............. df := f - circle[k].f
.............. dt := t - circle[k].t
.............. dist := sqrt(df * df + dt * dt)
.............. // 만약 거리가 반지름보다 작다면(원에 포함된다면)
.............. if dist < circle[k].radius then
................. covered := covered + 1
.............. end
........... end
........ if covered % 2 then // 홀수개에 겹쳐져 있다면 교환
........... temp := a[f][t]
........... a[f][t] := b[f][t]
........... b[f][t] := temp
........ end
..... end
.. end
end


6. 돌연변이
10×10개의 칸 하나하나에 대해 돌연변이를 적용시킵니다.

procedure Mutantation(Gene gene)
.. for f := 1, 10 do
..... for t := 1, 10 do
........ if gene[f][t] == 0 then
........... if MutantationRate then
............. gene[f][t] := Random(0, 10)
........... end
........ else // f->t로의 운송량 있을 경우
........... if MutantationRate then // 운송을 제거
............. gene[f][t] := 0
........... end
........... else if MutantationRate then // 운송량 변경
............. gene[f][t] := gene[f][t] + Random(-1, 1)
........... end
........... else if MutantationRate then // 운송을 나눔
............. T := Random(1, 3)
............. split := Random(0, gene[f][t])
............. gene[f][t] := gene[f][t] - split
............. gene[f][T] := gene[f][t] + split
........... end
........ end
..... end
.. end
end

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배의 가중치를 더 주었습니다(만약 이 가중치가 없다면, 유전자알고리즘은 차라리 자원을 운송하지 않고 연료를 아끼는 쪽으로 갈 수도 있습니다).