用模拟退火求TSP如何？

慢跑20

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

A=xlsread('33点矩阵s上三角');
" _/ N/ |  V6 ?* m>> for i=1:33;
  R) {) N5 Z$ `; ~       for j = 1:33
2 ?* ~' T. t& [7 M                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
; h+ H# I5 N& P: d* q$ B( O% _; F                   end   
. I1 Z& j. ~/ m5 ~                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
         
9 Y; P( D* X$ N- z4 ^    end
. P: W* F1 V# U% ^& p0 z end
! E( V& v; r" G
7 \& a3 H2 C3 u" V/ U& c5 B
这样A为邻接矩阵了。然后运行百度的代码：
+ [/ [6 C# D- U6 o

7 z: O/ ~/ J  T( B" H0 L( ^/ I5 Gfunction [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
7 s6 A8 x4 H; M, A: Q) Z. U+ L[m,n]=size(d);
0 f; t9 a! b9 j6 H/ E* p3 F" D7 PL=100*n;
t=t0;
pi0=1:n;
min_f=0;
/ z1 m* P3 ~  q  G; Kfor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
$ @; v4 {- X' @7 jend
min_f=min_f+d(pi0(n),pi0(1));
5 a/ G! n0 f$ W! b% Yp_min=pi0;
% ]) G. W( Z- f1 a! Lwhile t>tf
for k=1:L;
kk=rand;
- b1 m/ w- M: X[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
: L% j: ]- \9 ^- D% l8 V0 I& rif d_f<0
0 j6 e, {6 @( Jpi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
% F4 F3 v$ a! n% `$ A3 [" @9 _2 ^pi0=pi0;
9 c/ m4 e8 {9 _. ~% o: z$ e  iend
) h" @" P, O4 A( M; ^+ x! y" }end
f_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
6 @4 Z, s0 [& M: b1 Zf_temp=f_temp+d(pi0(n),pi0(1));
! Y4 g, ^# a7 B+ G4 }if min_f>f_temp
min_f=f_temp;
p_min=pi0;
end
t=0.87*t;
end
f=min_f;
T=p_min;
( A- s+ M7 E$ E# q# h%aiwa要调用的子程序,用于产生新解
0 \' w8 Z7 ^1 r0 h# p5 B7 h: tfunction [d_f,pi_r]=exchange_2(pi0,d)
* g0 z0 k4 s, p1 F6 o[m,n]=size(d);
+ r+ ?/ X. z* A( Q+ yclear m;
u=rand;
u=u*(n-2);
u=round(u);
if u<2
5 ?  r2 b* a/ k2 p/ ^& _u=2;
; p) ]' Q# `, x6 w4 I' [# Pend
if u>n-2
u=n-2;
- B3 z) X; ^7 r8 S" Uend
v=rand;
v=v*(n-u+1);
% Y* g) `' S! p; f4 P6 T4 kv=round(v);
if v<1
3 G) j! G3 a8 Wv=1;
; d0 @7 z/ b% h# j, p/ N% Z; _end
" ]/ p% m, a. K- J% R+ J# V# ]2 Zv=u+v;
if v>n
5 ?* a7 Y5 L' X/ |7 s) H# o2 gv=n;
end
pi_1(u)=pi0(v);
2 T: V# s1 U+ @  tpi_1(v)=pi0(u);
if u>1
for k=1:u-1
$ O' b1 W( N+ v" z. y, M4 qpi_1(k)=pi0(k);
- B0 h+ l' P5 Y6 I& W) Y3 g- v3 hend
end
if v>(u+1)
; r  K$ R' U. V: [" s3 U3 v1 @; ?for k=1:v-u-1
' j) A3 h" y- s, a, E; I, ]pi_1(u+k)=pi0(v-k);
* a- |0 C  l5 [6 A& dend
end
) {' W' N  |/ y# S1 \if v<n
for k=(v+1):n
' y/ L: f2 z4 e7 ]0 U& a6 m" Epi_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));
) k- B4 H( K. H1 S. P- s* Xend
/ e, |& U) g0 z. T/ l; g* z1 Rd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
! _, C0 n7 Y2 I3 ]9 ?+ Pd_f=d_f-d(pi0(k-1),pi0(k));
' P9 w& f, p4 x0 ^' S" lend
+ _" V8 A0 ~7 o- Z' _$ p7 ~else
" ~9 r5 V% _/ C$ _2 h4 D- |) Ed_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));
3 ~' f$ ?/ ?0 e( D1 p- Send
! }7 N! q, {0 h0 p5 f. {for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
9 v7 x* r/ l" O% j, e, c0 _end
end
9 C# R% _# @( C4 Kpi_r=pi_1;
1 v0 n/ i% I; m: u0 Y
, `+ e  F2 \; p) q3 z得到：
  [f,T]=TSPSA(A,0,99)
2 O) Y: E# U$ r1 ^3 v6 C9 r" g* f# T
- X% e* w, {4 R) pf =

$ h: x' S0 ^2 s   Inf
; I  [8 J5 f- P" p
: t6 F) ~( g( m- J$ L, q
5 A. ?0 P( ^+ u1 JT =
2 D( @, P. ?1 m
  H" K. N) Y& E& K) l9 N  Columns 1 through 18

+ l! }1 _) G5 L0 j$ u     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
9 \6 F! ?( Y, o
& }* x3 K' O) Q: N  Columns 19 through 33
% x( t- U$ V: ~% e, Z" D" a
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

8 x8 c. \6 c% }, N/ o这个初始，结束温度是自己随便设定的？？
- }! T8 p; Q3 P% g# m$ i3 A% G' t得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

magic2728

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

冰E柠檬

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