《五个城市的TSP问题(MATLAB程序)》由会员分享,可在线阅读,更多相关《五个城市的TSP问题(MATLAB程序)(4页珍藏版)》请在金锄头文库上搜索。
1、五个城市的 TSP 问题,距离矩阵为:01015621008139158020156132005291550设初始温度为10,结束温度为0.7,则程序如下:d=0, 10, 15, 6, 2;10, 0, 8, 13, 9;15, 8, 0, 20, 15;6, 13, 20, 0, 5;2, 9, 15, 5, 0;t0=10; tf=0.7;f,T=trp(d,t0,tf)得结果如下:f=43T=1 4 5 2 3MATLAB 的程序如下:function f,T=trp(d,t0,tf)% f 为目标函数最优值,T 为最优路线,d 为距离矩阵,t0为初始温度,tf 为结束温度m,n=si
2、ze(d);L=100*n;t=t0;pi0=1:n;min_f=0;for k=1:(n-1)min_f=min_f+d(pi0(k),pi0(k+1);endmin_f=min_f+d(pi0(n),pi0(1);p_min=pi0;while ttffor k=1:Lkk=rand;d_f,pi_1=exchange_2(pi0,d);r_r=rand;if d_fr_rpi0=pi_1;else pi0=pi0;endendf_temp=0;for k=1:n-1f_temp=f_temp+d(pi0(k),pi0(k+1);endf_temp=f_temp+d(pi0(n),pi0(
3、1);if min_ff_tempmin_f=f_temp;p_min=pi0;endt=0.87*t;endf=min_f;T=p_min;%下面的函数产生新解function d_f,pi_r=exchange_2(pi0,d)m,n=size(d);clear m;u=rand;u=u*(n-2);u=round(u);if un-2u=n-2;endv=rand;v=v*(n-u+1);v=round(v);if vnv=n;endpi_1(u)=pi0(v);pi_1(v)=pi0(u);if u1for k=1:u-1pi_1(k)=pi0(k);endendif vu+1for
4、k=1:(v-u-1)pi_1(u+k)=pi0(v-k);endendif vnfor k=(v+1):npi_1(k)=pi0(k);endendd_f=0;if vnd_f=d(pi0(u-1),pi0(v)+d(pi0(u),pi0(v+1);for k=(u+1):nd_f=d_f+d(pi0(k),pi0(k-1);endd_f=d_f-d(pi0(u-1),pi0(u)-d(pi0(v),pi0(v+1);for k=(u+1):nd_f=d_f-d(pi0(k-1),pi0(k);endelsed_f=d(pi0(u-1),pi0(v)+d(pi0(u),pi0(1)-d(pi0(u-1),pi0(u)-d(pi0(v),pi0(1);for k=(u+1):nd_f=d_f+d(pi0(k),pi0(k-1);endfor k=(u+1):nd_f=d_f-d(pi0(k-1),pi0(k);endendpi_r=pi_1;