用模拟退火求TSP如何？

慢跑20

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

A=xlsread('33点矩阵s上三角');
>> for i=1:33;
       for j = 1:33
% c3 p7 a  q7 {- |1 j2 ~                   if i<j
6 @+ m, U# Z2 Z$ T# L                 temp(i,j)=A(i,j);
% w1 E9 K7 x# ]                 A(j,i)=temp(i,j);
7 H8 z$ h/ B: ]                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
+ J3 L$ s. p) ~3 @                 end
         
7 e5 m. o# p4 ?    end
end


2 a% B4 _% z  t; G 这样A为邻接矩阵了。然后运行百度的代码：


function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
5 V  j. q+ O: U' d8 }7 J" X' l% 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
" d$ X5 X2 ~) H+ Amin_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(n),pi0(1));
; x5 u& _( f" b- R( _p_min=pi0;
+ w7 o$ f7 o2 ]6 Gwhile t>tf
9 R1 f2 w: p* E+ bfor k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
; A$ U' e7 C# ^' ^" J( T3 v0 j0 Jpi0=pi_1;
elseif exp(d_f/t)>r_r
8 t" O5 W* x6 |, \2 npi0=pi_1;
+ \& O9 w7 n7 Nelse
$ Q" E/ L5 [# q0 A6 ^) E# T& xpi0=pi0;
; _* H  z2 a+ F. G1 l2 ~  Nend
end
9 x3 P2 D( B0 J: ^. E9 x7 `% `1 Nf_temp=0;
for k=1:n-1
3 M6 u4 U7 w; s* M) W, k) sf_temp=f_temp+d(pi0(k),pi0(k+1));
0 J8 a) d9 q: Qend
9 t9 t9 s/ k- A6 O$ `( Ff_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
! E" [/ p; I8 k/ E, kmin_f=f_temp;
0 V8 E5 f3 q6 |& j' G' kp_min=pi0;
end
' e3 }5 Q3 d& p3 v& J# \" R4 `t=0.87*t;
end
f=min_f;
& [8 I- i+ d' `5 _( nT=p_min;
6 L' `# ~! d7 e1 N( A, y* x%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
- g# a; q% E# P[m,n]=size(d);
clear m;
. N. T% T) w; D! `# o6 Zu=rand;
# \1 h' ?& u3 Y4 k2 J  V% Zu=u*(n-2);
u=round(u);
if u<2
) M+ J/ d8 E% _1 F% e! Ju=2;
end
if u>n-2
u=n-2;
2 Q' ?9 K$ b! e. Send
v=rand;
8 y5 D) n7 n% x$ O3 l, ?v=v*(n-u+1);
v=round(v);
9 Y- H/ r6 z4 r7 L. N9 Oif v<1
v=1;
end
v=u+v;
: x- h! Z* `* p! K& E6 p0 Yif v>n
$ {6 L! _6 D, F) w9 jv=n;
end
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
9 h- x$ G$ M1 a; ^6 S& Kif u>1
for k=1:u-1
& W7 b) v8 J: A4 u  zpi_1(k)=pi0(k);
* m" J& m& Q) x; M6 b. c2 }1 bend
end
* O, ]4 Y+ Y4 o- ]if v>(u+1)
$ z1 s- R" s" U. m$ G2 _: t- q  k3 gfor k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
$ c4 V' u8 m. H5 G6 K. bend
2 m) E6 @& w5 [( q$ D  d* y' kif v<n
for k=(v+1):n
pi_1(k)=pi0(k);
4 o- j! \/ n) w, [6 uend
- f' X1 P' D- G4 Cend
d_f=0;
( J' a4 x/ I" I' Dif v<n
3 v5 z; p, [% ad_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
. F) p6 c* K( ^0 O. vfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
; {' o1 ]3 z8 X- g( Z7 Bend
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));
  ^  E) P( W% _& t8 _! Cend
else
6 v; _. ~! x0 }% K* S/ Hd_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
4 m8 h! p! R7 [1 ^4 d1 m9 y! od_f=d_f+d(pi0(k),pi0(k-1));
end
- H+ h4 r* a7 N- H; Xfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
; u) r+ \/ I& C) m" h+ n0 }  W3 Lend
. i- k6 n9 s5 ]" l8 wend
* `9 @  D0 Y2 c, P* rpi_r=pi_1;
* t. M. H) g% O$ X5 f3 b5 J
得到：
& r4 x# S' S) B2 U. X( s  [f,T]=TSPSA(A,0,99)

f =

: I5 y, `/ p: V& \% B   Inf

- g; d  i1 q/ ^, R) m7 P
T =

6 B; |( B0 ?* s+ I  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
4 u  n& H! S6 P: h6 ~. s
2 @* o' ^: `  x0 {2 M: \" \  Columns 19 through 33
# }4 A. j& u1 `, P1 H" z: g
; x; A& S* b; Y0 q3 k/ F# V    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

) \+ \9 E* t' `3 d0 X  B4 H& d" i这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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