内容发布更新时间 : 2024/11/15 13:30:01星期一 下面是文章的全部内容请认真阅读。
用模拟退火算法求TSP问题的程序清单
中国各省会城市地理位置（经纬度）.xls
城市 经度 纬度
北京 116.24 39.55
天津 117.12 39.02
郑州 114.3 34.46
太原 112.33 37.54
昆明 102.42 25.04 呼和浩特 111.41 40.48 长沙 112.59 28.12 武汉 114.17 30.35 重庆 106.54 29.59 兰州 103.51 36.04 福州 119.18 26.05 上海 121.27 31.14
广州 113.14 23.08
南宁 108.19 22.48
包头 110 40.58 长春 125.19 43.54 哈尔滨 126.36 45.44 深圳 114.3 22.62 香港 115.12 21.23 银川 106.16 38.27 石家庄 114.3 38.02 南京 118.46 32.03
南昌 115.55 28.4
沈阳 123.25 41.48
西安 108.57 34.17 济南 117 36.4 成都 104.04 30.4 西宁 101.48 36.38 合肥 117.17 31.52
海口 110.2 20.2
贵阳 106.42 26.35 杭州 120.1 30.16 台北 121.3 25.03
拉萨 91.08 29.39
澳门 115.07 21.33
地球半径R=6400千米；高度h=10千米。
(1)TSP——模拟退火主函数
function [Lujing,Changdu]=TSP_moni_tuihuo(R,d,dili_weizhi) T0=20000; Tf=1; err=1; Tol=1e-5; L=10000; alpha=0.95;
m=size(dili_weizhi,1); sequence=1:m; x0=sequence;
L0=Length_Route(R,d,dili_weizhi,x0); SEQUENCE=[]; while (T0>Tf) for i=1:L
x1=suiji_duihuan(sequence);
L1=Length_Route(R,d,dili_weizhi,x1); if L1 err=L1-L0; gailv_accept=exp(-err/T0); if gailv_accept>rand x0=x1; L0=L1; end end if abs(err) SEQUENCE=[SEQUENCE;x0,L0]; T0=alpha*T0; end Lujing=x0;Changdu=L0; for j=1:m duiyingguanxi(x0(j)); end figure(1); p=qiuji_touying(R,d,dili_weizhi); for j=1:m p1(j,:)=p(x0(j),:); end p1=[p1;p1(1,1:2)]; plot(p1(:,1),p1(:,2),'*-'); （2）对换函数 function y=suiji_duihuan(sequence) L=length(sequence); suiji=rand(1,L); a=min(suiji); b=max(suiji); a_index=find(suiji==a); b_index=find(suiji==b); c=find(sequence==a_index); d=find(sequence==b_index); t=sequence(c); sequence(c)=sequence(d); sequence(d)=t; y=sequence; y; （3）求路径长度函数 function y=Length_Route(R,d,dili_weizhi,sequence) city_distance=chengshi_juli(R,d,dili_weizhi); [m,n]=size(city_distance); sum=0; for i=1:m-1 sum=sum+city_distance(sequence(i),sequence(i+1)); end sum=sum+city_distance(sequence(m),sequence(1)); y=sum; （4）求城市距离函数 function y=chengshi_juli(R,d,dili_weizhi) [m,n]=size(dili_weizhi);%m is the number of cities in China dili_weizhi=pi/180*dili_weizhi; city_distance=zeros(m); zuobiao=zeros(m,3); for i=1:m zuobiao(i,1)=(R+d)*cos(dili_weizhi(i,2))*cos(dili_weizhi(i,1)); zuobiao(i,2)=(R+d)*cos(dili_weizhi(i,2))*sin(dili_weizhi(i,1)); zuobiao(i,3)=(R+d)*sin(dili_weizhi(i,2)); end for i=1:m for j=i+1:m R0=R+d; dot_ji=sum(zuobiao(i,:).*zuobiao(j,:)); city_distance(i,j)=R0*acos(dot_ji/(R0^2)); end end city_distance=city_distance'+city_distance; y=city_distance; y; （5）球极投影函数 function y=qiuji_touying(R,d,dili_weizhi) [m,n]=size(dili_weizhi);%m is the number of cities in China dili_weizhi=pi/180*dili_weizhi; city_distance=zeros(m); zuobiao=zeros(m,3); for i=1:m zuobiao(i,1)=(R+d)*cos(dili_weizhi(i,2))*cos(dili_weizhi(i,1)); zuobiao(i,2)=(R+d)*cos(dili_weizhi(i,2))*sin(dili_weizhi(i,1)); zuobiao(i,3)=(R+d)*sin(dili_weizhi(i,2)); end qiuji_zuobiao=zeros(m,2); for i=1:m qiuji_zuobiao(i,1)=(R+d)*zuobiao(i,1)/(R+d-zuobiao(i,3)); qiuji_zuobiao(i,2)=(R+d)*zuobiao(i,2)/(R+d-zuobiao(i,3)); end y=qiuji_zuobiao/100; （6）对应关系函数 function y=duiyingguanxi(s) switch s case 1 disp('北京') case 2 disp('天津') case 3 disp('郑州') case 4 disp('太原') case 5 disp('昆明') case 6 disp('呼和浩特') case 7 disp('长沙') case 8 disp('武汉') case 9 disp('重庆') case 10 disp('兰州') case 11 disp('福州') case 12 disp('上海') case 13 disp('广州') case 14 disp('南宁') case 15 disp('包头') case 16 disp('长春') case 17 disp('哈尔滨') case 18 disp('深圳') case 19 disp('香港') case 20 disp(' 银川') case 21 disp('石家庄') case 22 disp('南京') case 23 disp('南昌') case 24 disp('沈阳') case 25 disp('西安') case 26 disp('济南') case 27 disp('成都') case 28 disp('西宁') case 29 disp('合肥') case 30