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