[2기 강남 김주영] 쉽고 즐거운 유전자 알고리즘 #2 (TSP의 해결)

안녕하세요. 삼성 소프트웨어 강남 멤버십 19-1기이자, 엘리트 멤버 2기 김주영 입니다. 지난 시간에 이어 이번에는 유전알고리즘을 활용한 순회 세일즈맨 문제(Traveling Salesperson Problem : TSP)의 해결을 포스팅하려 합니다.

1.  순회 세일즈맨 문제란?

먼저 위키피디아의 글을 첨부하여 순회 세일즈맨 문제를 소개하고자 합니다.

“여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인가? 그래프 이론의 용어로 엄밀하게 정의한다면, ‘각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀톤 회로(Hamiltonian cycle)을 구하라’ 라고 표현할 수 있다.” - Wikipedia <외판원 문제 中>

 

위의 설명에서 보듯이 N개의 도시가 있을 때 어떤 경로로 도시들을 순회하는 것이 최적화된 경로일까를 고민하는 문제입니다. 아래 사진과 같이 5개의 도시가 있는 경우 5도시의 번호 조합으로 최적화를 수행하게 됩니다. 예를 들어 1-2-3-4-5 순서로 방문할 수도 있고, 4-3-1-2-5 처럼 얼핏 보기에도 길게 돌아가는 듯한 경로로 문제를 해결할 수도 있습니다.

위와 같은 조합최적화에서 경우의 수는 N! (5! = 5*4*3*2*1) 에 해당하여, 도시의 수 N이 커질수록 계산 량이 기하급수적으로 증가하게 됩니다. 잠깐 살펴보자면 도시의 개수가 5개인 경우에야 120가지의 경우의 수를 모두 계산해서 최적의 해를 구하면 그만이지만, 한국에 있는 시 단위의 행정구역만 세어도 84개입니다. 각 도시의 최적 순회 경로를 판단하기 위한 84!는 3.3142401345653532669993875791301e+126입니다. 3으로 시작하는 126자리의 수네요.. 1000개의 조합을 1초내로 계산할 수 있는 컴퓨터를 사용하더라도 3.3142401345653532669993875791301e+123초의 수행시간이 필요합니다...

최소값을 구하기 위한 모든 경우의 수를 고려하는 방법은 포기하고, 유전자 알고리즘을 이용하여 근사값을 구할 수 있도록 해봅시다!

2. 유전 알고리즘 설계

a. 유전자 설계

각 해는 도시의 순회 경로를 표현하도록 합니다. 5개의 도시 문제에서 사용할 유전자의 모양은 12345,23541,13245 등이 될 것입니다. 12345는 도시를 1->2->3->4->5 순으로 순회하는 해를 뜻합니다. 앞으로 코딩할 예제에서는 40개의 도시를 이용할 예정이니, 유전자의 길이는 40개가 되겠죠!

b. 적합도 함수 (Fitness Function)

적합도 함수를 계산하기 위해 각 도시별 이동비용을 계산하기 위해 40개의 도시에 단순히 2차원 좌표값을 지정해, 각 도시의 거리로 비용을 계산하려고 합니다. 각 도시는 Matlab 예제에서 지원하는 미국 지도 내의 임의의 점으로 표현을 하고, 각 도시의 위치는 해당 점의 위치로 표현을 하고자 합니다.

각 도시간의 거리를 이용하여 각 해의 적합도를 계산한 후에, 해의 적합도를 정렬해 순위기반 선택방법을 적용할 수 있도록 디자인 되었습니다.

c. 선택 방법

선택 방법은 이전 포스팅에 사용했었던 룰렛 휠 방법을 그대로 사용하도록 합니다! 다만 달라진 것은 이전의 룰렛휠 기반은 적합도의 높고 낮은 비중에 따라 선택압이 높고 낮게 결정되었다면, 이번 포스팅의 예제는 해의 순위에 따라 선택압이 조절된다는 점입니다.

d. 교차 방법

두 해의 교차의 경우에는 꽤 복잡하게 진행됩니다. 이전의 유전자 알고리즘 예제에서는 랜덤하게 선택된 여러개의 점을 이용해 번갈아 가며 각 부모 유전자를 유전하는 자식을 생성하였습니다. (더 자세히 알고 싶으시면, 이전 포스팅을 참고해 주세요).

dsdsdv

하지만 이전에 적용하였던 방식은 이번 예제와 같은 조합 최적화 문제에서는 유효하게 적용되지 않습니다. 그림으로 쉽게 설명 드리자면, 기존의 다점 교차방식을 사용하게 되면 왼쪽과 같이 자식해에 같은 도시의 번호가 중첩하는 경우가 생기게 되므로 도시 순회 시 같은 도시를 반복하게 되는 경우가 생기게 됩니다.

조합 최적화 문제처럼 순열을 이용한 유전자 표현을 하게 되는 경우 PMX(Partially Mapped Crossover) 방법이 보통 쓰이게 되는데 이 방법은 교환되는 유전자마다 원래 위치의 유전자를 치환해 줌으로써 유전자가 서로 중첩되는 경우를 방지해주며 교차하는 방법입니다.

하지만 저는 이번 예제에서 더욱 간단한 교차를 위해 두 부모의 교배를 포기하고, 한 부모로부터 유전정보를 변형시켜 자식 유전자를 생성시키는 방법을 적용하였습니다. 부모 유전자의 두 점을 선택하여 점 사이의 유전 정보 순서를 뒤섞는 식으로 교차연산을 대신하였습니다. 이 방법을 적용함으로써 유전정보가 서로 중첩되는 상황을 간단하게 회피할 수 있고, 기존에 유전자가 가지고 있던 부모의 특성을 어느 정도 자식에 전수해 줄 수 있도록 디자인 하였습니다.

e. 변이 방법

변이는 교차와 비슷한 방법을 사용하여 선택된 두 점의 유전정보를 서로 교환해주는 형식으로 채택하였습니다.

f. 기타

(1) Elitism을 적용하여 매 세대마다 가장 높은 적합도를 가진 2개의 엘리트를 다음 세대로 보존하도록 설계되었습니다.

(2) 한 세대의 해의 개수를 100개로 고정하여 진행하였습니다.

3. 구현

MATLAB 2009a

지난 포스팅과 같이 C#을 이용해서 코딩을 완성했다가.. 소스코드를 모두 날리는 바람에 홧김에 MATLAB으로 다시 코딩했습니다.(프로젝트는 절대 USB에 보관하지 맙시다..) MATLAB의 Optimization Toolkit 내의 GA를 이용하면 편하게 할 수 있겠다라는 생각에 시도를 했는데.. SGA(Simple Genetic Algorithm)의 경우에는 정말 몇 개의 파라미터만 던져주면 잘 동작하더라구요.. 하지만 이번 예제와 같이 유전자의 모양자체가 특이한 경우는 거의 대부분을 Custom 해줘야해 시간이 상당히 오래 걸렸습니다. Matlab이 익숙하지 않은 탓도 너무나 크고요!

4. 결과 분석

a. 초기 도시 모습

그림과 같이 40개의 도시의 최적 순회 경로를 찾기 위해 최적화를 수행했습니다. 위에서 설명드린 바와 같이 각 도시간의 거리를 이용해서 적합도를 계산합니다.

b. 반복 결과 과정

 

17회 반복 최적 경로

21회 반복 최적 경로

다음과 같은 경로가 현재의 Best Fitness에 해당합니다. 아직은 정말 아무렇게나 효율없이 이동하고 있습니다. 몇 세대를 더 진행해보며 유전알고리즘의 수렴이 어떻게 이루어지고 있는지 살펴보도록 합시다!

 

50회 반복 최적 경로

61회 반복 최적 경로

점점 경로의 가닥이 잡혀가기 시작합니다. 21회~50회의 반복을 거치면서 가장 최적이 되는 해의 모양이 급격히 변경되었고 일반적으로 전체 지도를 한바퀴돌면서 경로를 찾아가는 모양의 경로가 나타나기 시작합니다.

 

73회 반복 최적 경로

93회 반복 최적 경로

 

104회 반복 최적 경로

129회 반복 최적경로

해의 모양이 우리가 생각하는 최적 경로 모양과 비슷하게 잡혀갑니다. 129회의 최적 경로가 최종적으로 발견된 최적 경로의 것으로 판단되고 유전자 알고리즘이 171회까지 해를 유지한 후 종료합니다. (평균 적합도의 변화량이 기준보다 낮을 경우 유전 알고리즘의 반복이 종료되도록 설정되었습니다. 최대 반복수는 1000 세대 입니다.)

 

171회 반복 최적 경로<수렴 완료>

해의 모양에 있어서 조금 아쉬운 부분들이 보이긴 하지만, 대체적으로 유전자 알고리즘의 수렴을 알아볼 수 있는 좋은 모양을 보여주며 수렴을 종료합니다. 171회 반복 종료 후의 해의 모양이 전역해의 모습은 아닌 듯 하니 더욱더 해의 품질을 높일 수 있는 방법을 생각해보고자 합니다.

c. 한 세대 최대 해 수에 따른 수렴 정도 관찰

 한 세대당 100개의 해를 가지는 유전 알고리즘과 세대당 10000개의 해를 가지는 유전 알고리즘의 수렴정도를 비교해 보았습니다.

10000개의 해

100개의 해

상대적으로 10000개의 해를 가진 왼쪽 그림이 확실히 수렴이 빠른 것을 알 수 있습니다. 뿐만 아니라, 해의 분포가 넓게 위치하기 때문에 평균 적합도(파란 점)의 이동이 적고, 전역해를 찾기에 더욱 유리한 모습을 보이고 있습니다. 100개의 해를 가진 유전 알고리즘은 해의 분포가 전체적으로 고르지 못하기때문에 평균의 이동이 비교적 불규칙적으로 보입니다. 또한 적합도의 수렴이 10000개의 해에 비해 느려 더 많은 반복을 수행하게 됩니다.

5. 마치며..

이번 포스팅에서는 유전알고리즘을 활용한 TSP의 해결에 대한 이야기를 풀어봤습니다. 코딩에 걸린 시간에 비해 포스팅으로 설명할 수 있는 부분이 좀 적었다고 생각되네요. 포스팅에 대한 지적사항은 정말 겸허히 받아들이고 더 좋은 학습을 위해 수정을 하도록 하겠습니다! 질문이나 지적사항은 ohgreat11@gmail.com 으로 보내주시면 감사하겠습니다!

이번 포스팅은 코딩으로 많은 시간을 쏟은 탓일까 아쉬움이 큽니다.. 이 아쉬움을 다음 포스팅에서 풀도록 하겠습니다. 다음 포스팅은 아마도 이번 예제의 소스코드 설명과 함께 MATLAB Optimization Toolkit 사용법에 관련된 내용일듯 하네요!

좋은 하루 되시구요! 다음에 또 뵙겠습니다!