用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
# V2 v- l) f. k: \  @' I
, q. |# P8 C* ? A=xlsread('33点矩阵s上三角');
>> for i=1:33;
- d5 r+ J3 m) t4 T       for j = 1:33
* s; P. a' P* |/ E$ Y                   if i<j
) ~3 c2 e5 e# R" ?1 v' {9 L                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
/ z1 r1 Y0 a  g' B5 z6 W- `                   end   
# H$ i2 P  t# }  V) Z1 S                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
         
    end
end
! j9 g. Y7 V9 j1 R2 k0 U  \# W! r# O

这样A为邻接矩阵了。然后运行百度的代码：
1 W+ h. a+ ]* w3 v) s
- h$ s/ Y$ z6 K0 Z# f
8 G7 D4 s/ L# u! T+ I7 Q7 e# }function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
8 e$ m8 Z9 L* ^% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
6 R& H5 x7 p! r' V( g8 [L=100*n;
t=t0;
pi0=1:n;
min_f=0;
; x- O$ c5 N7 I1 ^( _  W4 U, nfor k=1:n-1
7 i( i$ z  l" }' t  H2 n% u8 |min_f=min_f+d(pi0(k),pi0(k+1));
2 a* \" M* D# O6 i' w; l! Iend
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
; Z- d4 K2 {5 K  n" d' J+ dwhile t>tf
5 i. t# u4 D- x+ B( i* [for k=1:L;
' s( K/ p8 u  F1 _. _# r& ckk=rand;
: X$ \) F1 M6 [! z[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
, d1 Z5 n3 C" p; q% i; I9 Uif d_f<0
pi0=pi_1;
3 ]5 w9 T1 l2 s! C3 yelseif exp(d_f/t)>r_r
pi0=pi_1;
else
3 t" s1 _1 A6 E2 g6 R/ I* w/ ^pi0=pi0;
end
end
% y8 b( i$ q. j' ?; gf_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
2 ^4 X! ^) Z* O; [f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
+ S: @4 o- H6 n+ w* x2 h! smin_f=f_temp;
/ z) O+ R* o( a9 P3 n. A7 }p_min=pi0;
end
t=0.87*t;
% X+ D1 q- `4 \2 \- `5 G! mend
0 Q% Q. z/ m) T" \f=min_f;
T=p_min;
3 H! e6 C. e+ P%aiwa要调用的子程序,用于产生新解
+ j" j$ z/ C5 K5 M/ vfunction [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
clear m;
+ F' H- f# l; l( {; [, Ju=rand;
  e2 K! O, H; Z! [* ~u=u*(n-2);
u=round(u);
if u<2
+ [" ^, D+ E5 l8 A* f$ _u=2;
end
' ]/ j- C/ |: n% V9 y, b5 Zif u>n-2
u=n-2;
6 u! i; b) R4 X1 O, C/ a7 Q8 s( Kend
+ }4 S+ l3 B1 }v=rand;
v=v*(n-u+1);
v=round(v);
4 A0 f6 a( p+ dif v<1
  [; n" T% \9 I& Cv=1;
end
v=u+v;
if v>n
4 d3 X7 K/ l$ q6 N0 U1 a0 Iv=n;
end
pi_1(u)=pi0(v);
2 X& T% N; F( ?' h1 K! }pi_1(v)=pi0(u);
1 b; {& x- I& T6 G0 p, f1 Nif u>1
for k=1:u-1
pi_1(k)=pi0(k);
end
end
7 g2 `" X, V8 b, wif v>(u+1)
* q2 t' g% h0 f0 T3 Efor k=1:v-u-1
pi_1(u+k)=pi0(v-k);
# L2 ]: [' x5 X; @! H: \end
8 H! [; }7 m5 Iend
& ?% y" }6 c1 f; Q! H2 d. A+ X6 L! s2 \if v<n
* p8 T6 E( s' _7 R2 S, c8 @% n5 v$ Mfor k=(v+1):n
. L; F. o4 r  I- s) Hpi_1(k)=pi0(k);
end
end
1 L% P3 |, v* ?0 q3 ^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
5 K! ?; J+ y  p1 q- h' a2 Id_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));
& |! Y. e8 h# r; bend
1 u( x% A7 x- r4 D: K& pelse
0 K8 q5 o6 r; p$ Md_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
7 [1 ~5 c9 g7 e& yfor k=(u+1):n
3 W( _, T5 H& Y5 u; ]d_f=d_f+d(pi0(k),pi0(k-1));
end
for k=(u+1):n
! U* a: j+ _4 R$ E5 w" nd_f=d_f-d(pi0(k-1),pi0(k));
end
0 f8 M  @9 \6 `+ {& W4 i9 @& r! oend
pi_r=pi_1;
7 N( @. k; E; t# D4 c8 c5 X) Q: }; @
: Q& q, Z3 y7 Z$ a8 y得到：
( w# o7 Y5 b; a  [f,T]=TSPSA(A,0,99)

f =
) T" v+ q- u% z, u" J7 G
- J4 ?5 Q* J1 P' v5 b   Inf
! \6 k) o7 @, r& |8 U
: Q. C# a2 Z7 F3 ]0 A+ @1 w4 ?
T =
+ C+ b4 w$ s# Y) ^6 l* R
  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
) U* n) C3 l7 N+ l
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
  b9 n3 b7 n; i3 e1 D
这个初始，结束温度是自己随便设定的？？
( d# ], o! N4 x. t1 k, e  I得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

magic2728

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

冰E柠檬

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