用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
! k% [/ M, d2 y" R
# N5 d$ @5 e; G( x* M- Q A=xlsread('33点矩阵s上三角');
2 l( @$ e8 p5 M& d9 T& E>> for i=1:33;
       for j = 1:33
, N! o, {3 ]3 Y- K2 |: R                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
% J) H8 S$ a/ \# {5 R2 ?) Y  o                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
" z! h0 ?% V, i5 A$ ~" T3 m         
) k6 D; U7 J) s) U0 a4 q9 A    end
end
8 t, R! y, K% j; W- a3 q

& c/ N* z3 H/ `: q5 u0 ~ 这样A为邻接矩阵了。然后运行百度的代码：
- K: P  ]7 Q7 H+ ?
0 _. b1 J+ p3 b* }9 t$ L
function [f,T]=TSPSA(d,t0,tf)
* V5 E4 A+ r, ]  c0 T" ^%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
! n  y8 p; P5 D3 e% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
) S" Q9 p% |. v8 k& x  g& `t=t0;
pi0=1:n;
min_f=0;
' B- v6 l. \: A5 |3 U6 lfor k=1:n-1
, j# G0 I/ @9 G& G; N6 M  ~min_f=min_f+d(pi0(k),pi0(k+1));
end
( n" m: _( i8 `0 d8 e; E# Umin_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
while t>tf
for k=1:L;
7 o, |( |* K6 B: Jkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
! k4 L3 A. v; `, sif d_f<0
pi0=pi_1;
; t+ H5 W) U: @* ?! Kelseif exp(d_f/t)>r_r
( v! S9 P- D4 x% [/ a# L5 |pi0=pi_1;
else
pi0=pi0;
% @9 N& c9 y; }) ]; f  H& Fend
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));
3 d' Z- i1 B$ N! x8 c* M, nif min_f>f_temp
6 r8 z- o4 L( b5 Y$ N- Zmin_f=f_temp;
& d! K! B4 R5 _( }, p1 Lp_min=pi0;
end
& {4 V5 ]% S" l5 N' ~t=0.87*t;
end
5 [3 A! H" ~+ e, i4 g- y+ Gf=min_f;
+ a8 O; C2 [2 P* K9 }T=p_min;
' c8 G8 K- `3 Z; L: |%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
* a( q! X) c- H4 T[m,n]=size(d);
9 K- D$ \5 N3 r# ~; y3 Eclear m;
u=rand;
4 ~0 o; J, j- ~9 ~% u- mu=u*(n-2);
u=round(u);
if u<2
u=2;
! o; q, p* k* z: v  H3 w$ X2 rend
; j) H( A, n7 M- S) e" P( `if u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
1 j/ M+ l0 r. X" f) Q8 A1 Bif v<1
: G  w7 k1 H& L/ f" D7 t& lv=1;
* B' c9 K" z. L, S7 k2 o& s9 b# Qend
/ W& x3 |3 R/ Z$ G; zv=u+v;
if v>n
v=n;
end
" u% ?( X3 E* N" o. Cpi_1(u)=pi0(v);
7 i0 U9 M' d, e/ fpi_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
: n% I1 s- D; `; T( T' i# aend
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
8 v. u% m( B; |  k9 q) `+ `) m2 Zend
end
: _. V5 ~( y. ?* h/ dd_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
# h$ D* y  X' V% w1 l) m! v! I* Mfor k=(u+1):n
/ o) t+ G# U( U) ~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
# M5 H7 P! X0 j, Hd_f=d_f-d(pi0(k-1),pi0(k));
& a& H# D* `/ Z& D8 u! u0 m$ }end
; Q- ^( ^$ L( R) h1 \/ b! @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));
6 j8 Z& i# c. d) A8 y* ~4 y: W# Hfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
for k=(u+1):n
1 F5 B' Q( D6 R0 P8 `d_f=d_f-d(pi0(k-1),pi0(k));
  X/ H$ c1 c! ?0 nend
end
pi_r=pi_1;
  C1 F3 l! w# X+ v" ?
得到：
  [f,T]=TSPSA(A,0,99)
; H+ D. k+ m3 j
1 i# ~; S' l! t% u2 vf =

) u0 w+ S2 q$ z7 y   Inf


. d) A% r  j9 kT =

* y/ i0 v/ ?: x* g8 L3 K  `" c7 [  Columns 1 through 18
- y* w  n0 `, ]8 N9 b8 m
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

) X0 P5 \/ @: v5 N  Columns 19 through 33

+ o7 l; h/ ?# x    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

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

冰E柠檬

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

magic2728

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