模拟退火算法解决TSP问题

《模拟退火算法解决TSP问题》由会员分享，可在线阅读，更多相关《模拟退火算法解决TSP问题（5页珍藏版）》请在装配图网上搜索。

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

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

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

4、%搜索开始while ttf%tf最终温度是while循环的结束条件for i=1:Lfval_after,route_after=exchange(route,dislist);if fval_afterfvalroute=route_after; fval=fval_after;elseif exp(fval-fval_after)/t)randroute=route_after; fval=fval_after;endendii=ii+1;drawTSP(Clist,route,fval,ii,0);% 作图程序if fvalfval_bestroute_best=route; fval

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

6、0.1463;0.1707 0.2293;0.2293 0.761;0.5171 0.9414;0.8732 0.6536;0.6878 0.5219;0.8488 0.3609;0.6683 0.2536;0.61950.2634;%10cities d=2.691for i=1:10for j=1:10DLl0(i,j)=(city10(i,1)-city10(j,1)入2+(city10(i,2)-city10(j,2)入2)入0.5;endendDLn=DLl0; cityn=city10;endif n=30city30=41 94;37 84;54 67;25 62;7 64;2

7、99;68 58;71 44;54 62;83 69;64 60;18 54;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;4521;41 26;44 35;4 50;%30 cities d=423.741 by D B Fogelfor i=1:30for j=1:30DL30(i,j)=(city30(i,1)-city30(j,1)入2+(city30(i,2)-city30(j,2)入2)入0.5;endendDLn=DL30; cityn=city30;endif

8、 n=50city50=31 32;32 39;40 30;37 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

9、;43 67;%50 cities d=427.855 by D B Fogelfor 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;endendDLn=DL50; cityn=city50;endif n=75city75=48 21;52 26;55 50;50 50;41 46;51 42;55 45;38 33;33 34;4

10、5 35;40 37;50 30;55 34;54 38;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

11、;7 43;9 56;15 56;1070;17 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 Fogelfor i=1:75for 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;endendDLn=DL75; cityn=cit

12、y75;end function F=CalDist(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=ce

13、il(n*rand) %the location of two exchanged numberendIoc1=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

14、_after);endfunction m=drawTSP(Clist,BSF,bsf,p,f) CityNum=size(Clist,1);for i=1:CityNum-1plot(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;end plot(Clist(BSF(CityNum),1),Clist(BSF(1),1),Clist(BSF(CityNum),2),Clist(BSF(1),2) ,ms-,LineWidth,2,MarkerEdgeColor,k,MarkerFaceColor,g);title(num2str(CityNum),城市TSP);if f=0text(5,5,第,int2str(p),步， 最短距离为,num2str(bsf);elsetext(5,5,最终搜索结果：最短距离,num2str(bsf);endhold off;pause(0.05);结束。