（MATLAB）模拟退火算法解決起點固定的TSP問題
-
- 1. 問題描述
- 2. 程式修改思路
- 3. 程式運作結果
1. 問題描述
問題描述和解題思路請看我這篇部落格：
https://blog.csdn.net/weixin_45727931/article/details/108110323
将該例題的題幹再次複制下來：
本題并沒有要求旅行商的起點在哪兒，不太符合實際情況。實際上，我們更常常會遇到的是解決起點固定的TSP問題，比如無人機巡航等。本題，假設旅行商的起始位置坐标是[2000,2000]。
2. 程式修改思路
本着盡可能動較少代碼的原則，我隻修改了距離計算函數func3，還有繪制圖像的部分。
修改後func3函數如下：
%%%%%%%%%%%%%%%%%%%%%%%%%%%%計算路線總長度%%%%%%%%%%%%%%%%%%%%%%%%
function len=func3(start,city,n)
len=0;
for i=1:n-1
len=len+sqrt((city(i).x-city(i+1).x)^2+(city(i).y-city(i+1).y)^2);
end
len=len+sqrt((city(1).x-start(1))^2+(city(1).y-start(2))^2);
len=len+sqrt((city(n).x-city(1).x)^2+(city(n).y-city(1).y)^2);
end
主函數部分，給所有的func3函數多輸入一個參數start，代表起始點坐标。
主函數部分代碼如下：
%%%%%%%%%%%%%%%%%%%%%%模拟退火算法解決TSP問題%%%%%%%%%%%%%%%%%%%%%%%
% 如果将該算法改為固定位置，起始位置為[2000,2000]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%初始化%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
clear all; %清除所有變量
close all; %清圖
clc; %清屏
start=[2000,2000];
C=[1304 2312;3639 1315;4177 2244;3712 1399;3488 1535;3326 1556;...
3238 1229;4196 1044;4312 790;4386 570;3007 1970;2562 1756;...
2788 1491;2381 1676;1332 695;3715 1678;3918 2179;4061 2370;...
3780 2212;3676 2578;4029 2838;4263 2931;3429 1908;3507 2376;...
3394 2643;3439 3201;2935 3240;3140 3550;2545 2357;2778 2826;...
2370 2975]; %31個省會城市坐标
n=size(C,1); %TSP問題的規模,即城市數目
T=100*n; %初始溫度
L=100; %馬可夫鍊長度
K=0.99; %衰減參數
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%城市坐标結構體%%%%%%%%%%%%%%%%%%%%%%%%%%
city=struct([]); %結構體變量，類似python中的字典
for i=1:n %city（i）的值為第i座城市的坐标
city(i).x=C(i,1);
city(i).y=C(i,2);
end
l=1; %統計疊代次數
len(l)=func3(start,city,n); %每次疊代後的路線長度
% figure(1);
while T>0.001 %停止疊代溫度
%%%%%%%%%%%%%%%%多次疊代擾動，溫度降低之前多次實驗%%%%%%%%%%%%%%%
for i=1:L
%%%%%%%%%%%%%%%%%%%計算原路線總距離%%%%%%%%%%%%%%%%%%%%%%%%%
len1=func3(start,city,n);
%%%%%%%%%%%%%%%%%%%%%%%%%産生随機擾動%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%随機置換兩個不同的城市的坐标%%%%%%%%%%%%%%%%%
q = randi([1,n],1,2); %這是我改的方法
while q(1) == q(2) % q取1到n之間兩個不同的數
q = randi([1,n],1,2);
end
tmp_city=city;
tmp=tmp_city(q(1));
tmp_city(q(1))=tmp_city(q(2));
tmp_city(q(2))=tmp;
%%%%%%%%%%%%%%%%%%%%%%%%計算新路線總距離%%%%%%%%%%%%%%%%%%%%
len2=func3(start,tmp_city,n);
%%%%%%%%%%%%%%%%%%新老距離的內插補點，相當于能量%%%%%%%%%%%%%%%%%
delta_e=len2-len1;
%%%%%%%%%%%%新路線好于舊路線，用新路線代替舊路線%%%%%%%%%%%%%%
if delta_e<0
city=tmp_city;
else
%%%%%%%%%%%%%%%%%%以機率選擇是否接受新解%%%%%%%%%%%%%%%%%
if exp(-delta_e/T)>rand()
city=tmp_city;
end
end
end
l=l+1;
%%%%%%%%%%%%%%%%%%%%%%%%%計算新路線距離%%%%%%%%%%%%%%%%%%%%%%%%%%
len(l)=func3(start,city,n);
%%%%%%%%%%%%%%%%%%%%%%%%%%%溫度不斷下降%%%%%%%%%%%%%%%%%%%%%%%%%%
T=T*K;
% for i=1:n-1
% plot([city(i).x,city(i+1).x],[city(i).y,city(i+1).y],'bo-');
% hold on;
% end
% plot([city(n).x,city(1).x],[city(n).y,city(1).y],'ro-');
% title(['優化最短距離:',num2str(len(l))]);
% hold off;
% pause(0.005);
end
figure(1);
for i=1:n-1
plot([city(i).x,city(i+1).x],[city(i).y,city(i+1).y],'bo-');
hold on;
end
plot([city(n).x,start(1)],[city(n).y,start(2)],'ro-');
plot([city(1).x,start(1)],[city(1).y,start(2)],'ko-');
title(['優化最短距離:',num2str(len(l))])
hold off;
figure(2);
plot(len)
xlabel('疊代次數')
ylabel('目标函數值')
title('适應度進化曲線')
3. 程式運作結果
适應度進化曲線如下：
最優化路徑如下：