用模拟退火求TSP如何？
一直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 =TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
=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;
=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 =exchange_2(pi0,d)
=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;
得到：
=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又是什么意思呢？？ 在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点，优化起始点可以随机选取也可根据经验选取.
F是目标最优值,T为最优路线。
F是无穷可能说明所求目标值没有路径到达没有最优解，或者是不是由于哪个步骤出现了什么问题（比如数据，或者邻接矩阵那里等等。。。）导致没有最优解。。。T表示的是最优解的起点到终点的最优路线。。。。。 模拟退火算法是一种模拟工业退火时的一种智能算法，是利用这种自然现象带来的启发帮助算法设计。
应该来说，这个算法的各个参数的调整是需要一些经验的。初始温度和结束温度确实需要自己设定才是，而且设定好坏直接决定你的解的好坏。f是无穷表明当前的得到的最优解的路径长度是无穷，也就是说，你现在的路径里，存在两个不相通的目标点；T是路径，可以看出这个路径就是从第一个点顺次走下去，所以应该是你的温度值设定不当，导致退货过程不佳而造成的，应该调整温度来重新测试。
页:
[1]