여행하는 세일즈 문제 1

 

1.

 

전산 알고리즘의 가장 기본적인 것은 특정 영역에서 최대값, 최소값을 찾는 알고리즘입니다. 함수 f가 정의역 D에서 정의된다면 함수 f가 최대가 되는, 또는 최소가 되는 정의역 D에 있는 점을 찾는 것입니다. 함수 f는 효용도 될 수 있고, 행복감도 될 수 있고, 또는 회귀방정식에서 길이를 가장 짧게 하는 최소제곱법도 될 수 있고, TSP 문제처럼 거리가 가장 짧은 경로를 찾는 것이 될 수 있습니다.

 

최대, 최소값을 찾는 것은 방정식 g(x)=0을 만족하는 근을 찾는 것이 같습니다. 최대, 최소가 되기 위해서는 최소한 f'(x)=0을 만족해야 하기 때문입니다. f'(x)=g(x)로 놓으면 g(x)=0을 만족하는 방정식의 근을 찾는 문제랑 같아집니다.

 

 

 

2.

찾는 방법을 모르겠으면 가장 무식한(brute force)한 방법인 격자(grid) 방식을 해 볼 수 있습니다. 정의역 D를 바둑판 모양을 잘게 사각형으로 쪼개 각 사각형의 중심에서 값을 비교해 본다는 것이죠. 비교할 때 양이 많으면 이웃을 정의하여 점프해나가는 것입니다. 이걸 local search라 합니다.

 

 

SA 알고리즘도 기본적으로 격자 방식이랑 비슷합니다. 최대값을 구하는 경우를 설명하져. 처음 한 점 i에서 출발해서 그 점의 이웃에 있는 j를 뽑아 i와 j에서 함수값을 구해 j에서 값이 더 높으면 i에서 j로 옮겨 타고, i가 여전히 함수값이 더 높으면 다른 j를 뽑아 다시 비교하고. 이런 식으로 더 높은 j 가 나올 때 까지 계속합니다. 그런 다음 j가 선택되면 이젠 j의 이웃에서 k를 뽑아 더 높은 함수값이 나오는 k가 있을 때까지 한다는 것이죠. 이것 어느 수준까지 계속 반복합니다.

 

즉 f(i) > f(j) 일 경우 i 유지

f(j) > f(i) 일 경우 j로 옮김

 

을 계속 합니다. 아래 그림 참조

 

 

 

 

 

1) 여기서 annealing의 특징이 나옵니다. j 가 i보다 더 낮은 함수 값이 나오더라도 일정 확률로 j로 옮겨 탑니다.

 

즉 f(i) > f(j) 일 경우 i를 계속 유지해야 하지만 SA에서는 일정 확률로 j로 옮겨 탑니다. 물론 시간이 지날수록 이 옮겨 탈 확률이 점점 낮아지겠죠. 이렇게 j가 더 낮은데도 옮겨 타는 이유는 지역 최대값(local maximum)에 빠지는 것을 막기 위해서입니다. relaxation 이라고 합니다. 이 말이 수치해석에서 일반적으로 쓰이는 용어인지는 모르겠습니다. 아래 그림 참조

 

 

 

 

 

 

2) SA 알고리즘의 또 다른 특징은 온도 c를 천천히 내린다는 것입니다. 소위 cooling scheduale 이라고 하는데 이건 MCMC나 Gibbs sampler에서는 관계없는 것 같고요. 혹시 또 모르죠. 이건 집어 넣은 알고리즘도 있을 수 있으니까요.

 

그럼 여행하는 세일즈맨 문제로 돌아와서요. 여기서 중요한게 두 가지 있습니다. 하나는 정의역 D는 도시들의 집합이 아니고, 여행 경로의 집합이라는 것이죠. 즉 정의역의 원소는 도시가 아니고 여행 경로입니다. 이 정의역을 Solution space S로 표시하겠습니다. 그리고 또 하나 중요한 개념을 이웃(neighborhood) 구조 개념입니다. 그래서 SA 알고리즘을 적절하게 구현하려면 이 문제의 정의역인 S와 S의 원소인 특정 i가 있을 때 i의 이웃을 잘 정의해야 합니다. i의 이웃을 N(i)로 표시하겠습니다.

 

이웃구조 개념이 좀 어색할 수 있는데 수학에서 굉장히 많이 나오는 개념입니다. 흔히 일반인이 이상한 수학이라 많이들 생각하는 위상수학(topology)에서 위상의 정확한 정의가 이 이웃구조입니다. 여러분이 아는 열린집합(open set)을 전부 모아 놓은 집합이 바로 topology의 정의이고(정확하게는 이것보다는 더 큽니다) 이 열린집합으로 설명될 수 있는 수학적 성질을 공부하는 것이 위상수학입니다. 예를 들어 함수의 연속 성격도 열린집합으로 설명될 수 있습니다(아마 그럴겁니다. 오래되어서 다 까먹었네요.)

 

실수 2차공간의 위상은 2차원 공간에서 여러분이 상상할 수 있는 모든 원의 집합(정확하게는 원의 내부)의 모임이라 생각하시면 되고, 실수 3차 공간에서는 위상은 여러분이 상상할 수 있는 모든 구의 내부의 모임이라 생각하시면 됩니다. 이런 위상을 메트릭에 의해 생성되는 위상이라 합니다.

 

 

 

 

4. TSP 문제 SA 알고리즘

그럼 일단 TSP 문제의 알고리즘을 좀 더 정확하게 써 볼까요.

 

알고리즘

 

start

k=0;

i=i_start;

 

repeat

 

for i=1 to L(k) {

 

generate(j from N(j));

 

if f(j) <= f(i) then i=j;

else

if exp[ (f(i)-f(j)) / T(k)] > random[0,1] then i=j;

}

 

k=k+1;

calculate-length(L(k));

calculate_온도(T(k));

 

until stop criterion;

end;

 

 

 

5. 알고리즘 설명

 

어려워 보이는 것 같지만 사살 별로 어렵지 않습니다.

 

1)먼저 유럽의 도시를 한번 걸쳐 가는 아무 경로를 하나 설정합니다(i_start).

 

2) 처음 설정한 경로의 이웃 경로의 모임을 생각합니다(N(i_start))

이 이웃 경로는 처음 설정한 경로에서 두 개의 도시를 임의로 뽑아 서로 바꾸는 것입니다. 예를 들어 5개 도시 a, b, c, d, e 가 있다고 합시다. 처음 출발 도시를 a라고 하면 마지막 도시도 a가 되어야 합니다. 처음 임의로 설정한 경로가

 

i-start= (a-> c -> b -> e -> d -> a)

 

라고 하죠. 그럼 i_start의 이웃 N(i-start)는 다음과 같이 됩니다.

 

N(i_start)={ (a-> c -> b -> e -> d -> a),

                (a-> b -> c -> e -> d -> a),

                (a-> e -> b -> c -> d -> a),

                (a-> d -> b -> e -> c -> a), 등등

             }

 

3) N(i-start)에서 하나의 경로 j를 임의로 뽑아 f(i_stat)와 f(j)값을 비교합니다.

그래서 f(j) < f(i_start) 이면 경로 j가 경로 i_start보다 짧은 경로이니까 당연히 선택되겠죠. 만약 f(j) > f(i_start) 일 경우라도, 즉 경로 j가 경로 i_start보다 긴 경로라도 일정 확률로 j를 받아 드립니다. 이 부분이 가장 큰 특징이고 여기서 local minimum에 빠지는 것을 막아 줍니다.

 

여기에서 사용하는 분포가 Bolzmann 분포입니다. Bolzaman 분포를 B(x)라 하면 위 알고리즘에 나오는 것은 B(x0)/B(x1)의 형태입니다. 즉 상태 x0에서의 확률값과 상태 x1의 확률값의 비율입니다. 실제 알고리즘 구현시 완전한 확률값을 구해 비교하는 것이 아니라 약간의 pertubation만 구해서 하면 됩니다. f(x)는 목적함수, 즉 TSP에서는 여행경로의 길이가 되겠고, 통계역학에서는 에너지 E가 되겠습니다.

 

4) 이런 식으로 몇 번(L(1)을 시도하다가 온도를 조금 낮추고(T(2)=T(1)*0.9), 다시 위의 방법으로 또 몇 번(L(2))을 시도하다가 또 온도를 조금 낮추고(T(3)=T(1)*0.9*0.9)), 다시 위의 방법으로 또 몇 번(L(3)을 시도합니다. 그래서 어떤 기준에 도달할 때까지 계속 반복합니다.

 

 

 

 

6. 더 생각할 문제

 

여기서 우리가 할 문제가 여러개입니다.

 

1) 이게 마코프 체인인가?

2) 마코프 체인이면 극한분포로 안정분포로 가는가? 안정분포로 가는 조건을 만족시키는가?

3) 통계학의 Gibbs Sampler와 Hastings의 MCMC는 어떻게 연결되는가?

 

다음에 조금 더 쓰죠. 그리고 MCMC에 관한 글을 하나 소개하고요. 쉬운 책을 발견할 수가 없어 조금 어려울 수 있겠습니다.

 

  neal.pdf

neal.pdf

1.08MB