用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
6 W, ~2 B/ o$ E$ J$ K, U$ `7 t3 f' t
0 z2 K/ `; ?7 N( x1 l0 O0 d3 i A=xlsread('33点矩阵s上三角');
0 J5 {, E4 D3 N4 `1 ]* @>> for i=1:33;
* ]# v( M' A! d       for j = 1:33
                   if i<j
2 ~2 q& j9 |% n9 X8 {                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
0 _8 W. u$ ?: Y8 Y) C                 if isnan(A(i,j))
5 X/ z( O8 q& F0 [$ n7 p                 A(i,j)=inf;
                 end
         
: k+ C! U- o5 X; k" \    end
3 h0 a" F! g, G, n1 Y9 ? end

: R: f% w: Y7 ^
这样A为邻接矩阵了。然后运行百度的代码：


function [f,T]=TSPSA(d,t0,tf)
" i5 U1 D5 i5 S! B) L%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
& Y* Z! F" w- p% L7 `% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
t=t0;
9 H8 E8 y2 l. t6 w/ D, i- dpi0=1:n;
min_f=0;
for k=1:n-1
; ]8 }: x, H3 [  X4 H0 f2 u% Wmin_f=min_f+d(pi0(k),pi0(k+1));
: \9 `7 o6 O7 y9 e- Aend
7 z% R) d2 j" w! X! wmin_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
$ c3 o0 z+ o& v  @while t>tf
$ w4 h2 L! b7 o( V5 P) ^# \. A, ofor k=1:L;
kk=rand;
4 s7 P  c4 X, `! t2 \. K[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
& B  K5 O7 k7 ~) U  ^& E3 Vif d_f<0
pi0=pi_1;
1 J& I- f& U2 z- y9 f# E; p. F2 Aelseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
2 M9 k# V' E: H. v7 i( Q' J: ~end
end
2 T$ q9 A) T+ f" l$ O5 ^f_temp=0;
for k=1:n-1
0 w' ^/ H9 c5 Z0 Z" ~3 _8 {7 Bf_temp=f_temp+d(pi0(k),pi0(k+1));
# Z3 u) O1 p# Y9 t4 ~, f5 Mend
- @; u( a6 S. M8 ~' Y. If_temp=f_temp+d(pi0(n),pi0(1));
1 v$ w& [2 k, ?1 h( g4 i$ n% |) b1 zif min_f>f_temp
  ]1 Y, y9 _. ~1 qmin_f=f_temp;
8 V8 ~9 Z4 a* E  P1 yp_min=pi0;
end
  b$ ?$ M/ h# x% Jt=0.87*t;
6 S. [7 c: \, B, [end
( J( E! b0 e" D% N* M7 q3 [f=min_f;
! K3 L4 @: b$ b& B' XT=p_min;
%aiwa要调用的子程序,用于产生新解
) C' L/ v$ r, k- L0 a5 Ffunction [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
clear m;
- b. B0 A, b% b/ Uu=rand;
! ?/ H% _( p/ W3 bu=u*(n-2);
u=round(u);
if u<2
u=2;
/ Y( X; ?5 F: Q. _3 Dend
5 Y; B0 i4 b+ _$ j6 c/ P: h' cif u>n-2
# O/ _- ^* \+ L& f9 ^; ou=n-2;
end
v=rand;
4 d, R/ G3 b5 S- Q/ b5 w! O8 `v=v*(n-u+1);
v=round(v);
. {2 o0 y# f2 K- vif v<1
; L- [$ w% K" Z9 m7 Uv=1;
/ `3 b, R5 w( I, M. xend
2 Z3 y. k- y2 w) d5 Xv=u+v;
if v>n
' Z) P, k; t% M; Hv=n;
. o  `8 j5 `# dend
pi_1(u)=pi0(v);
/ M1 r$ @; }" ]- a# D7 d, Tpi_1(v)=pi0(u);
/ Z. C. O" a5 R; I9 J4 Kif 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
0 m& z  w! [- L7 U( ?end
% k; ]  b4 I$ H  Y5 F! ^if v<n
for k=(v+1):n
" n; S5 D: `+ k) Jpi_1(k)=pi0(k);
end
end
) _( W$ U0 C& s3 Wd_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
3 Q) H+ A! O! a3 B( zd_f=d_f+d(pi0(k),pi0(k-1));
end
, m1 Y; Y, y1 T: H& zd_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));
% j0 }. g- h2 mend
; Y% k% b7 w5 T8 |else
9 H- a, o6 f, }0 B6 k$ u$ E8 k- q4 l* Nd_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
3 w, x8 k% v3 q: F" ?8 _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
) b6 [! N1 ]6 _; o5 [* bend
1 _$ W6 S/ X8 N% p! X  p2 D* [pi_r=pi_1;
  s$ H- x% S0 J! g: v9 }) ]5 L" E3 o) }
& i" }# K: F. q得到：
6 s: h' q2 `% l1 s( A0 l  [f,T]=TSPSA(A,0,99)
; V1 J, C8 e" L2 l2 m/ S
f =

; B! G* b5 b9 p  e9 f+ D: x   Inf
7 c1 e$ M5 p" C  k
* f+ Z* \1 H4 [- n
T =

  Columns 1 through 18

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

/ ?1 J! A9 n5 Q( @- t: {+ S  Columns 19 through 33
! q$ l! R+ N* t/ R* e: A3 |5 ]
- `' W( H4 @+ {8 p7 @: r& X    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
4 _& e1 Q* N; O% j( W9 U2 z
这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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