GA - 장사꾼여행문제(TSP) [1] - 유전자 설계

TSP(Travelling Salesman Problem)는 잘 알려진 대로, 여러개의 도시를 최단거리로 순회하는 방법을 찾는 대표적인 NP문제입니다. 쉽게 말하면 '다항식적으로 문제를 풀 수 없다' -> '무식하게 모든 경우의 수를 계산해서 풀어야 한다.'는 것이죠.

이 문제의 어려운 점은 도시가 늘어날수록 가능한 조합이 엄청난 속도로 증가한다는 것입니다. 이를테면 5개의 도시일 경우 5! = 120가지 조합을 계산해서 최소값을 찾으면 되지만, 10개의 도시라면 10! = 3628800가지 조합, 20개라면 20! = 2432902008176640000가지 조합을 따져야 합니다. 100개의 도시라면? 9로 시작하는 158자리 길이의 숫자만큼의 조합을 계산해야 합니다. 그야말로 '빅뱅부터 우주의 종말까지' 계산해도 끝나지 않을 계산량이죠.
그래서 이런 문제는, '최소값'을 찾는 것은 포기하고 '근사값'을 찾는 여러가지 알고리즘이 개발되어 있습니다.

여기서는 장사꾼이 최소 이동거리로 150개 도시를 지나는 문제를 유전자 알고리즘을 사용해서 근사값을 찾는 방법을 알아보겠습니다.

만약 '무식한 방법'으로 최선의 경로를 찾기 위해서는 150!개 경우의 수를 다 계산해야 합니다. 150!의 값은 다음과 같은 263자리 숫자입니다. 5713383956445854590478932865261054003189553578601126418254 83758331798291248453983931265744886753111453771078787468542 0416266625019868450446635594919592206657494259209573577892 9325357290444962472405416790722118445437122269675520000000 000000000000000000000000000000

1. 유전자 설계
TSP를 위한 가장 간단한 유전자는 돌아다닐 도시를 차례로 나열하는 것입니다. 만약 0~9까지 10개의 도시를 이동한다면, 유전자 9421850637은 9->4->2->1->8->5->0->6->3->7->9번 도시의 순서로 돌아다닌다는 의미입니다. 그러므로 1850637942나 0637942185, 3794218506 등도 동일한 유전자라고 할 수 있습니다. 또한 반대로 도는 2497360581 역시도 동일한 유전자입니다

역순유전자를 동일한 것으로 처리하기 위해서는, 모든 도시에 대해 A->B 이동시의 비용과 B->A 이동시의 비용이 동일해야 합니다. 만약 역방향으로 이동할 때의 비용이 차이난다면(바람이나 해류가 존재할 때 등) 역방향유전자를 동일한 것으로 처리할 수 없습니다.

이렇게 만드는 유전자의 경우에는 한가지 제약이 생깁니다. 같은 도시가 둘 이상 나와서는 안된다는 것이죠. 이를테면 9421850137과 같은 유전자는 6번도시는 빠뜨리고 1번도시는 두번 방문하게 되므로 제대로된 유전자가 아닙니다.
그러므로 최초 유전자를 초기화할 때라든지 교차, 돌연변이 등 유전자에 조작을 가할 경우에는 위와 같은 제약을 어기지 않도록 조심해야 할 필요가 있습니다.