用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
7 A) V( K# R# x& S8 }+ ~  U2 z0 N
/ M* `: B, Q  ^; J A=xlsread('33点矩阵s上三角');
  a9 E3 V: F& A, `; e  j8 |& N>> for i=1:33;
       for j = 1:33
' ]6 G* F+ {1 }4 k+ M' A) s                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
# j0 t/ `* V! D& y6 R                   end   
                 if isnan(A(i,j))
/ C4 ?2 @! V! H# a6 y% {                 A(i,j)=inf;
                 end
         
    end
2 r& v' e' o( l2 R6 R2 b  v end
: K; Q/ }; m- ~

2 b2 T" J3 a4 J2 C3 W% B0 S, e( \ 这样A为邻接矩阵了。然后运行百度的代码：

5 r3 q8 c/ }" s, P2 d, T- R
function [f,T]=TSPSA(d,t0,tf)
8 F% s/ S6 R8 `: u# i2 w%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
$ p  O: l% U& c1 a) B0 s( ?% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
3 J2 u0 v; e( w$ I# kL=100*n;
5 Y2 [, ~# D  Lt=t0;
pi0=1:n;
min_f=0;
, z/ w3 L8 g4 x/ W% o9 p' Gfor k=1:n-1
% k! ^* a! F2 C9 G! O; o% L1 {min_f=min_f+d(pi0(k),pi0(k+1));
* Y6 L$ H8 H/ J8 i! P$ G3 Hend
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
, w- {# F/ t! n: l/ \7 j) a/ Cwhile t>tf
: }2 q4 p1 L/ N* e) \5 s6 a2 Jfor k=1:L;
! \) O( M+ n# t; I' h0 A! Pkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
5 h" c. S8 O4 t: ur_r=rand;
  Z$ A6 i; n! {0 j+ Bif d_f<0
pi0=pi_1;
! |, T( @4 u7 s) ^1 ]) K$ Lelseif exp(d_f/t)>r_r
: C5 o4 n% {: v4 r, wpi0=pi_1;
5 d/ s1 Q- A# T2 m# {) celse
pi0=pi0;
" f# L8 @( d* t) y4 B8 r- ?end
end
, t4 D( h5 d/ g& R& l2 Y. f; g, df_temp=0;
for k=1:n-1
6 }1 @8 C4 Q! B) j' ~2 Gf_temp=f_temp+d(pi0(k),pi0(k+1));
/ ^* a; L5 @2 i8 Qend
2 B$ a5 u" P, [3 e5 Bf_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
min_f=f_temp;
p_min=pi0;
end
0 n$ a. p3 D, w9 Wt=0.87*t;
end
f=min_f;
$ E8 U, I! M9 x. W  T! Q0 E. I8 FT=p_min;
8 e% I6 k) k6 D1 [9 G3 Y%aiwa要调用的子程序,用于产生新解
) O$ y$ v$ L, \function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
clear m;
u=rand;
3 k! s% x2 I3 S$ nu=u*(n-2);
) `8 F3 A2 c) F3 o0 c8 K* F2 Ju=round(u);
1 J2 s2 i- s" X! S+ h, i9 ?if u<2
  v( l, C- U0 `2 ru=2;
end
if u>n-2
u=n-2;
7 @0 z* W$ W/ C8 X& g  Wend
. i! w, X8 O) t* h- {3 t* |7 \v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
v=1;
end
v=u+v;
if v>n
v=n;
end
) N' ^8 n; H9 _3 T' e' dpi_1(u)=pi0(v);
2 n; G! ?( b; gpi_1(v)=pi0(u);
$ f% Z) X5 Y3 p0 q9 Sif u>1
for k=1:u-1
pi_1(k)=pi0(k);
9 w" |" G: w& Wend
5 o7 d* O& y7 C2 Q. Tend
5 N; }) y& Y  i. T. T  B' bif v>(u+1)
; k0 F  D9 ~! \! J6 g; D. J/ `for k=1:v-u-1
" o8 T. B1 R9 @$ C" P6 n# Spi_1(u+k)=pi0(v-k);
  C: c! P6 P& o6 G" \. |6 ^: H" Gend
end
+ Q; ^3 V) Q8 w, l2 h0 d- iif v<n
for k=(v+1):n
# k- a7 M9 f' j$ npi_1(k)=pi0(k);
  [  @& X! @1 i& M4 E% hend
5 l4 Z& d; X4 Z: E0 aend
) [0 ~. m$ T0 t/ s0 O' Y& wd_f=0;
if v<n
" e3 h2 |  X; A7 gd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
0 B' P1 E$ ^* W; |/ G- w! @; J5 afor k=(u+1):n
7 w% t0 P5 p9 bd_f=d_f+d(pi0(k),pi0(k-1));
0 f' e# \. y! p' z4 ^end
/ d$ [$ q3 c, M) j3 h: I% R& ?% K0 xd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
2 T2 i) E4 H# b/ q1 _( D0 V( `% Bd_f=d_f-d(pi0(k-1),pi0(k));
# K2 U2 p% D' p/ s) ]- lend
$ E& Z( [3 K7 W6 J3 Qelse
d_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
7 p) w3 k2 `  ~. dd_f=d_f+d(pi0(k),pi0(k-1));
+ |! g: Z+ E. @* D, [1 E, }end
; j6 Y5 e$ P7 @: Pfor k=(u+1):n
8 q! H! \* ]1 j& J8 {d_f=d_f-d(pi0(k-1),pi0(k));
end
end
6 H0 H' G0 f7 j: t* jpi_r=pi_1;

得到：
# n: j1 A8 ]" v9 y9 M  [f,T]=TSPSA(A,0,99)

7 ~, |* I9 n  |+ B# d3 w% v4 J+ Pf =

8 g) S9 }* q8 f" L* B$ X& D   Inf
  V& V0 h) I5 H; q+ y

1 C" L7 Z4 C( A! M6 yT =

  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
) [$ X; i5 N, R4 x& ]/ k
3 m: R/ P# @; y+ Q  Columns 19 through 33

    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

9 O$ p8 t  Z. l. X, \- V这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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