模拟退火算法解决TSP问题

1、模拟退火算法解决TSP问题r=i本文主要使用模拟退火算法解决旅行商(TSP)问题，并成功的在Matlab中仿真并得到优化结果。 下面的算法程序中有详细的注释以方便大家了解。1算法仿真的收敛曲线2路径规划结果图2路径规划结果图模拟退火算法(Simulated Annealing，SA)最早的思想是由N. Metropolis1等人于1953年提出。1983 年,S. Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模 拟退火算法从某一较高初温出发，伴随温

2、度参数的不断下降，结合概率突跳特性在解空间中随机寻找 目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种 通用的优化算法，理论上算法具有概率的全局优化性能,目前已在工程中得到了广泛应用，诸如VLSI、 生产调度、控制工程、机器学习、神经网络、信号处理等领域。算法程序：程序分为五部分，下面第一部分是主程序，每个function函数用虚线分开，大家在使用时需要放在不 同的.m文件中。主程序：function sa clearCityNum=50;%城市个数可分别选30，50，7 0dislist,Clist=tsp(CityNum); %tsp函数中包含城市坐

3、标，dislist是距离矩阵，clist是城市坐标 tf=0.01;%最后的温度 alpha=0.80;%温度参数 L=100*CityNum; %马尔可夫链的长度 for i=1:100 route=randperm(CityNum);%随机城市序歹U，即将citynum个城市序歹U打舌L fval0(i)=CalDist(dislist,route);% 城市距离之和最优 end t0=-(max(fval0)-min(fval0)/log(0.9);% 初始温度 fval=fval0(100); route_best=route;% 最优城市序歹U fval_best=fval; %城市

4、距离之和最优 t=t0; ii=0;%搜索开始 while ttf%tf最终温度是while循环的结束条件for i=1:L fval_after,route_after=exchange(route,dislist); if fval_afterrand route=route_after; fval=fval_after; end end ii=ii+1; drawTSP(Clist,route,fval,ii,0);% 作图程序 if fvalfval_best route_best=route; fval_best=fval;endt=alpha*t;fval sequence(ii)

5、=fval;enddrawTSP(Clist,route_best,fval_best,ii,1);% 作图程序 figure(2);plot(1:ii,fval_sequence);%plot the convergence figure title(搜索过程);string1=最短距离,num2str(fval_best);gtext(string1);end function DLn,cityn=tsp(n)%坐标函数，可根据自己需要修改 if n=10city10=0.4 0.4439;0.2439 0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.

6、9414;0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.6195 0.2634;%10 cities d=2.691 for i=1:10for j=1:10DL10(i,j)=(city10(i,1)-city10(j,1)八2+(city10(i,2)-city10(j,2)八2)八0.5;end end DLn=DL10; cityn=city10; endif n=30city30=41 94;37 84;54 67;25 62;7 64;2 99;68 58;71 44;54 62;83 69;64 60;18 5

7、4;22 60;83 46;91 38;25 38;24 42;58 69;71 71;74 78;87 76;18 40;13 40;82 7;62 32;58 35;45 21;41 26;44 35;4 50;%30 cities d=423.741 by D B Fogel for i=1:30for j=1:30DL30(i,j)=(city30(i,1)-city30(j,1)八2+(city30(i,2)-city30(j,2)八2)八0.5;end end DLn=DL30; cityn=city30; endif n=50 city50=31 32;32 39;40 30;3

8、7 69;27 68;37 52;38 46;31 62;30 48;21 47;25 55;16 57; 17 63;42 41;17 33;25 32;5 64;8 52;12 42;7 38;5 25; 10 77;45 35;42 57;32 22; 27 23;56 37;52 41;49 49;58 48;57 58;39 10;46 10;59 15;51 21;48 28;52 33;58 27;61 33;62 63;20 26;5 6;13 13;21 10;30 15;36 16;62 42;63 69;52 64;43 67;%50 cities d=427.855 b

9、y D B Fogel for i=1:50for j=1:50DL50(i,j)=(city50(i,1)-city50(j,1)八2+(city50(i,2)-city50(j,2)八2)八0.5; DL50(i,j)=(city50(i,1)-city50(j,1)八2+(city50(i,2)-city50(j,2)八2)八0.5;end endDLn=DL50;cityn=city50;endif n=75 city75=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;45 35;40 37;50 30;55 34;54 3

10、8;26 13;15 5;21 48;29 39;33 44;15 19;16 19;12 17;50 40;22 53;21 36; 20 30;26 29;40 20;36 26;62 48;67 41;62 35;65 27;62 24;55 20;35 51;30 50;45 42;21 45;36 6;6 25;11 28;26 59;30 60;22 22;27 24;30 20;35 16;54 10;50 15;44 13;35 60;40 60;40 66;31 76;47 66;50 70;57 72;55 65;2 38;7 43;9 56;15 56; 1070;17

11、64;55 57;62 57;70 64;64 4;59 5;50 4;60 15;66 14;66 8;43 26;%75 cities d=549.18 by D B Fogel for i=1:75 for j=1:75DL75(i,j)=(city75(i,1)-city75(j,1)八2+(city75(i,2)-city75(j,2)八2)八0.5; DL75(i,j)=(city75(i,1)-city75(j,1)八2+(city75(i,2)-city75(j,2)八2)八0.5;end endDLn=DL75;cityn=city75;end function F=CalD

12、ist(dislist,s)DistanV=0;n=size(s,2);for i=1:(n-1)DistanV=DistanV+dislist(s(i),s(i+1);endDistanV=DistanV+dislist(s(n),s(1);F=DistanV;function fval_after,route_after=exchange(route,d) n=length(d);location1=ceil(n*rand); location2=location1; while location2=location1location2=ceil(n*rand) %the location

13、 of two exchanged number end loc1=min(location1,location2);loc2=max(location1,location2); middle_route=fliplr(route(loc1:loc2);%the part route which has been exchanged route_after=route(1:loc1-1) middle_route route(loc2+1:n);%the after traveling route fval_after=CalDist(d,route_after); endfunction m=drawTSP(Clist,BSF,bsf,p,f)CityNum=size(Clist,1);for i=1:CityNum-1 plot(Clist(BSF(i),1),Clist(BSF(i + 1),1),Clist(BSF(i),2),Clist(BSF(i+1),2),ms-, LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g);hold on;endplot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),