시뮬레이티드 어닐링 (SA)의 TSP 적용

시뮬레이티드 어닐링 (SA, simulated annealing)은 처음에 순회외판원문제(TSP, traveling salesman problem)와 같은 조합 최적화(combinatorial optimization) 문제를 해결하기 위해 도입되었다.

대표적인 조합 최적화 문제인 TSP는 $n$ 개의 서로 다른 도시의 좌표 $(x, y)$ 가 주어졌을 때, 각 도시를 한번씩 모두 방문하는 최단 경로를 찾는 문제다. TSP는 이동 경로 계획, 생산 계획, 적재 계획, 마이크로칩 설계, 유전학 등 응용 분야가 꽤 넓다.

조합 최적화 문제의 대부분은 NP-hard문제에 해당하기 때문에 다항식 시간 최적해를 구할 수 없다. 이 때문에 개별 개체의 수가 매우 큰 경우에는 최적해 대신에 빠르고 효율적으로 계산할 수 있는 근사해가 선호되며, 이에 관한 알고리즘이 많이 나와있다. 일례로 포인터넷(pointer net)을 이용한 TSP 솔루션이 게시글 (https://pasus.tistory.com/292)에 나와 있으니 참고하기 바란다.

TSP 관련 데이터셋은 다음 사이트에 공개되어 있다.

https://drive.google.com/drive/folders/0B2fg8yPGn2TCMzBtS0o4Q2RJaEU?resourcekey=0-46fqXNrTmcUA4MfT6GLcIg

데이터셋에는 $n$ 개 도시의 2D 좌표와 이 도시 집합에 대한 해당 TSP 최적 경로가 나와 있다. 여기서는 10개의 도시에 대해서 10,000개의 경로가 들어있는 데이터를 사용한다. 데이터 구조는 다음과 같다.

x1 y1 x2 y2 x3 y3 x4 y4 x5 y5 … x10 y10 output 1 3 8 6 10 9 5 2 4 7 1

먼저 도시의 2D 좌표 (x1 y1 x2 y2 x3 y3 … x10 y10) 가 있고, 그 다음에는 "output", 그리고 도시에 대한 방문 순서 (1 3 8 6 10 9 5 2 4 7 1) 가 있다. 방문 순서는 경로가 최소인 최적해를 나타낸다. 예로서 몇 개의 실제 데이터를 보면 다음과 같다.

0.607122 0.664447 0.953593 0.021519 0.757626 0.921024 0.586376 0.433565 0.786837 0.052959 0.016088 0.581436 0.496714 0.633571 0.227777 0.971433 0.665490 0.074331 0.383556 0.104392 output 1 3 8 6 10 9 5 2 4 7 1 
0.930534 0.747036 0.277412 0.938252 0.794592 0.794285 0.961946 0.261223 0.070796 0.384302 0.097035 0.796306 0.452332 0.412415 0.341413 0.566108 0.247172 0.890329 0.429978 0.232970 output 1 3 2 9 6 5 8 7 10 4 1 
0.686712 0.087942 0.443054 0.277818 0.494769 0.985289 0.559706 0.861138 0.532884 0.351913 0.712561 0.199273 0.554681 0.657214 0.909986 0.277141 0.931064 0.639287 0.398927 0.406909 output 1 5 2 10 7 4 3 9 8 6 1

여기서는 10,000 개의 데이터 중 임의로 1개를 선택하여 SA 알고리즘을 사용하여 최단 경로를 갖는 도시 방문 순서를 계산하고자 한다. 각 경로 별로 최적해가 나와 있으니 SA 결과와 비교하면 좋을 것이다. 임의의 경로 1개를 선택하는 매트랩 코드는 다음과 같다.

M = readmatrix('tsp_10_test_exact.txt');
idx = randi(size(M,1));
tsp_data_pick = M(idx,:);
tsp_data = [tsp_data_pick(1:2:19)
            tsp_data_pick(2:2:20)];

tsp.opt_route = tsp_data_pick(22:end);

효율적인 어닐링 알고리즘을 얻으려면 적절한 제안 분포가 매우 중요한데 TSP에서는 어떤 방법으로 후보 해(candidate solution)를 생성하면 좋을까.

$x \sim generate (x^{(i)})$

관련 문헌에 의하면 두가지 방법 정도가 제안되어 있다. 먼저 현재의 도시의 방문 순서 $x^{(i)}$ 에서 임의로 두 도시를 선택한 후 선택된 두 도시 사이의 방문 순서를 역으로 뒤집는 방법이다.

두번째는 비교적 단순한 방법으로서 현재의 도시의 방문 순서 x^((i))에서 임의로 두 도시를 선택한 후 서로 뒤바꾸는(swap) 방법이다.

여기서는 스왑 방법을 사용하며 해당 매트랩 코드는 다음과 같다.

function route_new = swap(route)

idx=randsample(length(route)-2,2)+1;
    
i = idx(1);
j = idx(2);
    
route_new = route;
route_new(i) = route(j);
route_new(j) = route(i); 

end

초기 온도를 $T_{1} = 1$ , 냉각 스케줄을 $T_{i + 1} = 0.995 T_{i}$ 로 했을 때 결과는 다음과 같다.

10,000 개의 데이터 중 3687번째 데이터가 선정되었는데 SA 결과가 최적 루트와 일치한다 (반대방향으로).

3687th data selected
 
SA route      : 1   6   9   8   7   3   5  10   4   2   1
optimal route : 1   2   4  10   5   3   7   8   9   6   1
 
initial cost: 4.9618
SA cost     : 2.6485
optimal cost: 2.6485

아래 그림에서 검은색 점은 출발 도시이며, 왼쪽은 도시를 차례로 방문하는 경우, 가운데는 최적 경로, 오른쪽은 SA로 계산한 경로를 나타낸다.

다음은 두번째 결과로서, 6240번째 데이터가 선정되었는데 SA 결과가 최적 루트보다 방문 거리인 cost가 조금 크게 나왔다.

6240th data selected
 
SA route      : 1  10   8   7   4   6   3   9   2   5   1
optimal route : 1   2   9   3   6   4   7   8  10   5   1
 
initial cost: 4.463
SA cost     : 2.564
optimal cost: 2.3628

아래 그림을 보면 방문 도시가 SA가 계산한 루트와 최적 루트가 시작 도시 부근에서 조금 다른 것을 알 수 있다. 로컬 최소값에 빠진 것으로 짐작할 수 있다.

앞서 언급했듯이 SA는 적절한 후보 해를 추출하는 방법 또는 제안 분포와 적절한 냉각 스케줄을 선택하는 것이 매우 중요하다.

SA 알고리즘을 다시 정리하면 다음과 같다.

온도(temperature) $T_{1}$ 와 해(solution) $x^{(1)}$ 를 초기화한 후, 다음을 $T_{i} = T_{m i n}$ 이 될 때까지 반복한다.

1. 후보(candidate) 해를 추출한다.

$x \sim generate (x^{(i)})$

2. 만약 $Δ E = E - E_{i} = f (x) - f (x^{(i)}) < 0$ 이면 후보 해를 새로운 해로 수락한다 ( $x^{(i + 1)} = x$ ).

만약 $Δ E \geq 0$ 이면,

2-1. 후보 해의 수락 확률(acceptance probability)을 계산한다.

$\begin{array}{r} α = min (1, \exp (- \frac{Δ E}{T_{i}})) \end{array}$

2-2. 확률 $α$ 로 후보 해 $x$ 를 새로운 해로 수락하거나 거절한다.
즉 균등분포 $U [0, 1]$ 에서 샘플 $u$ 를 추출한 후, $u \sim U [0, 1]$ , 만약 $u < α$ 이면 후보 해를 새로운 해로 수락하고 아니면 거절한다.

3. 선택한 냉각(cooling) 스케줄에 따라 다음 온도 $T_{i + 1}$ 를 낮춘다.

다음은 TSP를 위한 SA 매트랩 코드다.

%
% Simulated Annealing for TSP
%
% (c) st.watermelon

clear; 
close all;

% TSP setup
M = readmatrix('tsp_10_test_exact.txt');
idx = randi(size(M,1));
tsp_data_pick = M(idx,:);
tsp_data = [tsp_data_pick(1:2:19)
            tsp_data_pick(2:2:20)];

tsp.opt_route = tsp_data_pick(22:end);
tsp.n_node = 10;

for i = 1 : tsp.n_node
    tsp.node(i).x = tsp_data(1,i);
    tsp.node(i).y = tsp_data(2,i);
end

% parameters
T0 = 1;       % initial temperature
T = T0;

cooling_rate = 0.995;
max_iter = 2000;

% 0. initialize
route = [1 randperm(tsp.n_node-1)+1 1];
dist = cost(route, tsp.node);

for t = 1 : max_iter

    dist_hist(t) = dist;

    % 1. route candidate sampling by swapping
    route_new = swap(route);
    
    % 2. accept or reject
    dist_new = cost(route_new, tsp.node);
    dE = dist_new - dist; % to downhill 
    if dE < 0
        route = route_new;
        dist = dist_new;
    else
        % 2-1. acceptance probability
        alpha = min(1, exp(-dE/T));
    
        % 2-2. accept or reject
        u = rand(1);
        if u < alpha
            route = route_new;
            dist = dist_new;
        end
    end

    % 3. update temperature
    T = T * cooling_rate;

    if T < 1e-6
        break;
    end

end


% result
figure,plot(dist_hist); xlabel('iteration');

disp([num2str(idx), 'th data selected']);
disp(' ');
disp(['SA route      : ', num2str(route)]);
disp(['optimal route : ', num2str(tsp.opt_route)])

init_route = [1:tsp.n_node 1];
dist_init = cost(init_route, tsp.node);
dist_sa = cost(route, tsp.node);
dist_opt = cost(tsp.opt_route, tsp.node);
disp(' ');
disp(['initial cost: ', num2str(dist_init)])
disp(['SA cost     : ', num2str(dist_sa)])
disp(['optimal cost: ', num2str(dist_opt)])

plot_tsp(init_route, tsp.node, 'initial route');
plot_tsp(route, tsp.node, 'SA route');
plot_tsp(tsp.opt_route, tsp.node, 'optimal route');

%%
function plot_tsp(route, node, fig_title)

figure
%plot([node(:).x node(1).x], [node(:).y node(1).y], '-k');
plot([node(route(:)).x], [node(route(:)).y], '-k');
hold on
plot([node(:).x], [node(:).y], 'o', 'MarkerSize', 10, 'MarkerFaceColor', 'r');
plot([node(1).x], [node(1).y], 'o', 'MarkerSize', 10, 'MarkerFaceColor', 'k');
hold off
title(fig_title);
end

%%
function dist = cost(route, node)

dist = 0;

for i = 1:length(route)-1
    current_node = route(i);
    next_node = route(i+1);
    dist = dist + sqrt((node(current_node).x-node(next_node).x)^2 ...
                       + (node(current_node).y-node(next_node).y)^2);
end

end

%%
function route_new = swap(route)

idx=randsample(length(route)-2,2)+1;
    
i = idx(1);
j = idx(2);
    
route_new = route;
route_new(i) = route(j);
route_new(j) = route(i); 

end

'AI 수학 > 최적화' 카테고리의 다른 글

시뮬레이티드 어닐링 (Simulated Annealing) (0)	2025.02.12
파티클 군집 최적화 (Particle Swarm Optimization) (0)	2024.12.20
라인서치 (Line Search) 방법 (0)	2022.04.21
프라이멀-듀얼 내부점 방법 (Primal-Dual Interior-Point Method) (0)	2022.04.15
장벽 내부점 방법 (Barrier Interior-Point Method) (0)	2022.04.13

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

DeepCampus

시뮬레이티드 어닐링 (SA)의 TSP 적용

'AI 수학 > 최적화' 카테고리의 다른 글

댓글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역

시뮬레이티드 어닐링 (SA)의 TSP 적용

'AI 수학 > 최적화' 카테고리의 다른 글

관련글

댓글

티스토리툴바

개인정보

단축키

내 블로그

블로그 게시글

모든 영역