유전 알고리즘을 이용한 외판원 문제의 근삿값 구하기

외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.

 

정의

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다.

그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 이 문제는 반드시 시작점으로 돌아와야 한다는 제약 조건을 없애도 계산 복잡도는 변하지 않는다.

 

(ko.wikipedia.org/wiki/외판원_문제)

외판원 문제 - 위키백과, 우리 모두의 백과사전

 

개요

외판원 문제(TSP)를 DFS로 풀 경우 O(N!)이라는 극악의 시간 복잡도가 나온다.

 

정직하게 DFS로 풀 경우 노드가 15개만 되어도 15! = 1307674368000(1조 3천억)라는 값이 나와 인류가 멸망할 때까지도 프로그램이 끝나지 않을 것이다. 

 

때문에 백준에 올라온 외판원 순회 2는 때문에 노드를 최대 10개로 제한하여 3628800가지의 경우만 계산하면 풀 수 있게 만들었고, 외판원 순회 3은 점화식을 사용해 푸는 DP 문제로 만들었다.

 

그런데 최근에 외판원 문제의 근삿값을 구하는 재미있는 방법을 발견했다. 바로 유전 알고리즘을 이용한 풀이이다.

 

1. 생물 집단은 환경에 적응하며 증식

2. 증식할 때 부모는 자신의 유전 정보를 자손에게 전달

3. 적응하지 못한 개체는 살아남아 증식할 가능성이 낮으므로 도태됨

 

유전 알고리즘은 위와 같은 적자생존 이론을 기반으로 한다.

이 글에서는 유전 알고리즘에 대해선 깊게 다루지 않고 간단하게 넘어가도록 하겠다.

 

염색체: 유전 정보를 담고 있는 하나의 집합

유전자: 염색체를 구성하는 유전 정보

자손: 부모 염색체들의 유전 정보로 생성된 염색체

적합도: 염색체가 얼마나 적응했는지(적합한 해에 가까워졌는지) 나타내는 수치

선택: 자손을 만들어 낼 후보 염색체를 고르는 연산

교배: 후보 염색체를 조합해 다음 세대 염색체를 만드는 연산

변이: 돌연변이. 유전적 다양성을 위해 교배 과정에서 일정 확률로 특정 유전자 정보를 변형하는 연산

 

유전 알고리즘은

 

1. 초기 집단 생성

2. 적합도 평가

3. 종료 조건 확인

4. 선택

5. 교배

6. 변이

7. 2번으로 돌아감

 

의 과정을 반복한다. 구조가 매우 간단한 만큼, 적합도를 평가하고 자손을 만들어내는 연산에서 알고리즘에 성능이 좌우된다.

 

초기 집단 생성

처음에는 어떤 염색체도 존재하지 않기 때문에 초기 집단을 설정해야 한다. 초기 집단의 적합도는 중요하지 않기 때문에 유전 알고리즘에서는 주로 초기 염색체를 임의의 값으로 지정한다.

 

외판원 문제에서는 하나의 도시는 한 번만 방문할 수 있기에 데이터가 중복되지 않게끔 수정했다.

 

적합도 평가

$$Evaluate(p)=(\frac{XY_m*100}{cost(p_i, p_j)})^2$$

 

염색체 $p$의 적합도 $Evaluate(p)$는 위과 같이 표현했다.

 

모든 도시를 순회한 후 출발 지점으로 돌아오는 데 걸리는 비용이 클수록 적합도가 낮아야 하기 때문에, cost의 역수를 취하고 적당한 값을 곱했다.

 

평가 함수는 임의로 만든 것이므로 위와 같지 않아도 된다.

 

선택

다음 세대의 염색체를 만들어낼 두 부모를 선택해야 한다. 주로 쓰이는 선택 연산들에는 룰렛 휠 선택, 랭킹 선택, 엘리트 보존 선택, 토너먼트 선택 등이 있다.

 

내가 사용한 것은 룰렛 휠 선택(roulette wheel selection)으로, 각 염색체마다 적합도에 비례하는 만큼의 룰렛의 영역을 할당해주고, 룰렛을 돌려 염색체를 선택하는 것이다.

 

 

$$P(c_x) = \frac{Evaluate(c_x)}{\sum_{i}^{n(c)}Evaluate(c_i)}$$

 

$c_x$가 선택될 확률 $P(c_x)$는 위와 같이 나타낼 수 있다.

 

(각각 적합도가 1, 3, 5인 염색체 A, B, C가 존재할 때 A, B, C가 선택될 확률은 $\frac{1}{9}$, $\frac{3}{9}$, $\frac{5}{9}$)

 

교배

이제 전 단계에서 선택한 두 염색체를 교배해 새로운 염색체를 생성해야 한다.

교배 또한 일점 교배, 다점 교배, 균등 교배, 산술 교배부터 사이클 교배, 순서 교배, 휴리스틱 교배, PMX, 간선 재결합 교배, 다차원 교배, 내추럴 교배 여러 연산이 존재한다. 나는 간단한 일점 교배를 사용했다.

 

일점 교배란 간단히 하나의 교차점을 기준으로 구간을 나누어 새로운 유전자를 만드는 방식이다.

 

(1) A B C D

(2) D C A B

 

라는 두 염색체가 존재할 때, 교차점이

 

(1) A B | C D

(2) D C | A B

 

와 같이 잡혔다면, (1)의 A, B와 (2)의 A B를 가져와 (3) A B A B라는 새로운 염색체를 만들어낸다.

하지만 외판원 문제에서는 모든 도시는 한 번밖에 방문할 수 없다. 출발 지점을 제외하곤 중복될 수 없다는 말이다.

 

그래서, 1번의 유전자는 그대로 가져오되, (2)의 유전자는 (1)에서 얻지 못한 유전자들을 순서대로 가져오는 것으로 변경했다. 이 방식대로면 (1)의 A, B와 (2)의 D, C를 가져와 A B D C라는 새로운 유전자를 만들 수 있다.

 

변이

변이는 교배를 통해 생성된 자식 염색체의 일부 유전자들을 확률적으로 변형시키는 연산이다.

부모 염색체들을 교배하는 것으론 만들 수 없거나 만들기 힘든 조합이 생길 수 있다. 이를 극복하기 위해 낮은 확률로 변이를 일으켜준다. 대부분의 변이 결과는 부정적이지만 시간이 흐르면서 자연스럽게 도태되어 사라지고, 가끔 발생하는 성공적인 변이는 집단 전체의 품질을 향상시키는 역할을 한다.

 

변이 또한 정적 변이와 동적 변이로 나눌 수 있다.

 

정적 변이는 모든 세대에서의 변이 확률이 같다. 변이 확률을 높게 설정한다면 유전적 다양성이 증가하고 적응 능력이 떨어져 수행 시간이 감소한다. 변이 확률을 낮게 설정한다면 유전적 다양성이 감소하고 수행 시간이 증가한다.

 

하지만 이미 많은 세대를 거치며 주어진 환경에 충분히 적응한 상태에서 변이가 일어나면 오히려 부정적인 영향을 끼칠 수 있다. 때문에 품질이 좋지 않은 초기 세대에는 변이 확률을 높이고, 후반에는 변이 확률을 감소시키는 것이 동적 변이이다.

 

-

 

위 내용을 토대로 외판원 순회를 직접 만들어 보았다. 데이터의 수치는 다음과 같다.

 

위치의 범위: $-100\leq x, y\leq 100$

도시의 수: 15개

출발 지점: 0번

종료 조건: 가장 큰 적합도를 가진 유전자가 100세대가 넘을 동안 변화가 없을 경우

변이 확률: 3% (동적 변이)

거리 제한: 없음(모든 노드가 연결됨)

집단 수: 5

결과

변이 확률과 변이를 동적 변이로 하느냐, 정적 변이로 하느냐에 따라 프로그램의 수행 시간이 많이 차이가 난다.

 

정적 변이를 사용하고 변이 확률이 0.1%일 때는 2000세대까지 올라가기도 했지만

변이 확률을 높이고 동적 변이로 바꾼 후 평균적으로 200세대 정도에서 값이 수렴한다.

 

아직 제대로 만들었다는 생각은 들지 않아서 더 연구해야 할 것 같다.