查看: 2805|回复: 2

[问题求助] 用模拟退火求TSP如何？

[复制链接]

字体大小: 正常放大

慢跑20

60 主题	8 听众	3684 积分

TA的每日心情

	开心 2017-2-22 14:21

签到天数: 271 天

[LV.8]以坛为家I

群组: 2014年美赛冲刺培训

群组: 物联网工程师考试

群组: 2013年电工杯B题讨论群

群组: 物联网工程师培训

群组: 2013电工杯A题讨论群组

电梯直达

1^#

发表于 2013-7-28 22:52 |只看该作者 |正序浏览

|招呼Ta 关注Ta

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。求经过所有点之间的最短路线问题，。

A=xlsread('33点矩阵s上三角');
>> for i=1:33;
   for j = 1:33
               if i<j
               temp(i,j)=A(i,j);
               A(j,i)=temp(i,j);
               end
               if isnan(A(i,j))
               A(i,j)=inf;
               end

end
end

这样A为邻接矩阵了。然后运行百度的代码：

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(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));
end
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
while t>tf
for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
end
end
f_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
min_f=f_temp;
p_min=pi0;
end
t=0.87*t;
end
f=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
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 u<2
u=2;
end
if u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
v=1;
end
v=u+v;
if v>n
v=n;
end
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
for k=1:u-1
pi_1(k)=pi0(k);
end
end
if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
end
end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
else
d_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):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
end
pi_r=pi_1;

得到：
  [f,T]=TSPSA(A,0,99)

f =

Inf

T =

  Columns 1 through 18

   1    2    3    4    5    6    7    8    9 10 11 12 13 14 15 16 17 18

  Columns 19 through 33

19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

zan

如何

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

相关帖子

使用道具举报

magic2728

61 主题	478 听众	4851 积分

升级 95.03%

TA的每日心情

	慵懒 2014-9-29 19:37

签到天数: 409 天

[LV.9]以坛为家II

群组: 数学中国 2015美赛护航

群组: 数模专题强化培训

群组: 建模思维养成培训

群组: 2015美赛护航（强化）

群组: 2013年数学建模国赛备

3^#

发表于 2013-8-10 17:25 |只看该作者 |招呼Ta 关注Ta

模拟退火算法是一种模拟工业退火时的一种智能算法，是利用这种自然现象带来的启发帮助算法设计。
应该来说，这个算法的各个参数的调整是需要一些经验的。初始温度和结束温度确实需要自己设定才是，而且设定好坏直接决定你的解的好坏。f是无穷表明当前的得到的最优解的路径长度是无穷，也就是说，你现在的路径里，存在两个不相通的目标点；T是路径，可以看出这个路径就是从第一个点顺次走下去，所以应该是你的温度值设定不当，导致退货过程不佳而造成的，应该调整温度来重新测试。

我也说一句

发表

使用道具举报

冰E柠檬

10 主题	43 听众	1434 积分

升级 43.4%

TA的每日心情

	奋斗 2021-8-13 22:51

签到天数: 278 天

[LV.8]以坛为家I

自我介绍: 冰E柠檬

群组: 2013认证赛A题讨论群组

群组: 2013认证赛B题讨论群组

群组: 数学建摸协会

群组: 2013年数学建模国赛备

群组: 高数系列公益培训

2^#

发表于 2013-8-10 17:13 |只看该作者 |招呼Ta 关注Ta

在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点，优化起始点可以随机选取也可根据经验选取.
F是目标最优值,T为最优路线。
F是无穷可能说明所求目标值没有路径到达没有最优解，或者是不是由于哪个步骤出现了什么问题（比如数据，或者邻接矩阵那里等等。。。）导致没有最优解。。。T表示的是最优解的起点到终点的最优路线。。。。。

我也说一句

发表

使用道具举报

返回列表

帐号		密码		只需要一步，快速开始		注册地址	找回密码

[问题求助] 用模拟退火求TSP如何？

相关帖子

社区QQ达人

QQ

电话咨询

关于我们| 联系我们| 诚征英才| 对外合作| 产品服务|