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