GA - 장사꾼여행문제(TSP) [4] - 돌연변이

8. 돌연변이

교차와 마찬가지로 돌연변이 역시 유전자 최소단위(비트-bit)를 임의로 바꾸는 일반적인 돌연변이를 사용할 수 없습니다. 모든 도시를 한번만 방문할 수 있다는 제한 때문이죠.
여기서 사용한 돌연변이는 두가지입니다.
만약 유전자가 7385920416이라면

㉠ 임의의 경로 뒤집기
임의의 도시와 돌연변이시킬 길이를 임의로 정합니다. 2번도시와 길이 4가 정해졌다면
먼저 2번도시를 첫머리로 옮깁니다.

2041673859

그 후에는 앞에서 4개 길이를 뒤집습니다. 즉 2->0->4->1을 1->4->0->2로 바꿉니다.

1402673859

㉡ 임의의 경로 바꾸기
임의의 도시와 돌연변이시킬 범위의 앞뒤를 임의로 정합니다. 8번도시와 3~7이 정해졌다면, 먼저 8번도시를 첫머리로 재배열합니다.

8592041673

다음에는 0~2와 3~7까지의 경로를 뒤바꿉니다.

2041859673

㉢ 돌연변이 확률
꼬마자동차의 경우처럼 일반적인 돌연변이는 비트 하나하나에 대해 돌연변이 확률을 계산합니다. 그러므로 비트 하나하나에 대한 돌연변이 확률이 작더라도 개체 하나에 대한 돌연변이는 생각보다 크게 나오는 경우가 많습니다.
이 문제의 경우에는 비트 하나하나에 대한 돌연변이가 아니라 개체 전체에 대한 돌연변이를 채택했기에 돌연변이 확률은 좀 높이는 것이 좋습니다.

procedure Mutantation(Salesman s)
.. if Random(0, 10) == 0 then // 10% 확률로 돌연변이
..... if Random(0, 2) == 0 then // 경로 뒤집기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := 0
........ endpnt := Random(1, 150 / 2 + 1)
........ while endpnt > startpnt do
........... // startpnt도시와 endpnt도시를 바꿈
........... tmp := s.gene[startpnt]
........... s.gene[startpnt] := s.gene[endpnt]
........... s.gene[endpnt] := tmp
........... startpnt := startpnt + 1
........... endpnt := endpnt - 1
........ end
..... else // 경로 바꾸기
........ startcity := Random(0, 150)
........ Rolling(s.gene, startcity)
........ startpnt := Random(1, 150 / 2 + 1)
........ endpnt := Random(startpnt + 1, startpnt + 150 / 3 + 1)
........ Salesman tmp
........ tmp := s // 복사본을 만들어 놓음
........ sub := 0
........ for k := startpnt, endpnt do // startpnt~endpnt까지 앞에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
........ for k := 0, startpnt do // 0~startpnt까지 그 뒤에 복사
........... s.gene[sub] := tmp.gene[k]
........... sub := sub + 1
........ end
..... end
.. end
end