用模拟退火求TSP如何？

慢跑20

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

3 G; P$ K8 g8 F% e( q" z A=xlsread('33点矩阵s上三角');
; L/ D" K# y. F8 ]) F& o0 M2 ~. W7 b>> for i=1:33;
       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
& t+ k7 w% U3 _+ H                   end   
- r: D: e5 a0 s7 d                 if isnan(A(i,j))
7 p; V6 h+ Y/ c- H# i                 A(i,j)=inf;
                 end
         
  ~% V* D- o" q1 t1 R    end
1 M& s2 w/ H9 o6 l% k0 u% c end

* f9 p, ?5 f- p' n+ W* F/ R6 d
这样A为邻接矩阵了。然后运行百度的代码：


9 J6 j7 d- v2 V  ]5 u9 qfunction [f,T]=TSPSA(d,t0,tf)
% R4 m" z7 g: S& U%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
6 F  I- f% N! l: B4 m, \- y% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
/ F  S' [& x8 r- a* `8 EL=100*n;
t=t0;
7 |# z( Z" O+ ]5 P8 G$ Mpi0=1:n;
7 k$ x& R+ p8 H% s, j8 [, @min_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
end
, P! }* s; F0 {8 H: n2 Jmin_f=min_f+d(pi0(n),pi0(1));
( ]% o, f" |4 o2 @: kp_min=pi0;
while t>tf
( G: j+ K2 f% S3 \for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
4 h4 X8 `2 f9 |pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
# g& ^0 z7 W/ t" I0 h: Jelse
9 }- ^7 O  h, L' U2 vpi0=pi0;
7 {; V' g( p3 m' iend
end
f_temp=0;
for k=1:n-1
/ G  \: S. k% ?- u9 Yf_temp=f_temp+d(pi0(k),pi0(k+1));
6 A' R! `; [3 t% Qend
f_temp=f_temp+d(pi0(n),pi0(1));
/ Z* g- W/ Q8 {' B8 N& V: q5 Uif min_f>f_temp
, i. _/ n+ j1 D- W" A% kmin_f=f_temp;
p_min=pi0;
5 k) D# S* X" X" L9 L/ H- \5 {' yend
( n/ y4 X* F  @- lt=0.87*t;
end
1 O1 w8 I# R: [- ^& _: Hf=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
/ n8 l9 v4 p$ d" }+ c2 k) Zfunction [d_f,pi_r]=exchange_2(pi0,d)
( m8 U; `' X% g* \1 ]1 \. u# C[m,n]=size(d);
- F! u# t7 B* K8 d3 ~8 l5 Jclear m;
1 }' {1 O2 K0 ^1 r" Eu=rand;
u=u*(n-2);
, M: x, c' X1 c: f0 g( `, Bu=round(u);
if u<2
u=2;
  c& y6 u+ ~/ ?! Mend
8 Z7 z- {0 u$ oif u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
' D$ Q: A# \* ~1 v& w7 F, Iif v<1
v=1;
0 E, b3 ~% I  d  C3 A! a8 H* B' yend
0 Q% G' e/ w! L; I% ]" r( \v=u+v;
if v>n
v=n;
& M3 Z4 c  e5 Yend
' f8 `# G7 c7 r  d4 W' Mpi_1(u)=pi0(v);
pi_1(v)=pi0(u);
9 B; y' ?: ^! y, L& Jif u>1
2 Y  h2 v/ @# N8 q/ Gfor k=1:u-1
pi_1(k)=pi0(k);
1 Z( Q4 [6 l3 qend
# f4 z; C+ j, O# I8 q2 L# G. Q- wend
7 ~* I! Z: s  B  Uif v>(u+1)
for k=1:v-u-1
) Y: H; `. C8 |! D* {pi_1(u+k)=pi0(v-k);
end
end
+ O6 M' Y6 G4 s" i2 iif v<n
for k=(v+1):n
$ i9 Z4 i+ i) ]5 }( epi_1(k)=pi0(k);
end
; `/ `; Z/ d( c3 H/ q& P; iend
d_f=0;
6 m) w1 o# ~. bif v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
% p, r+ E4 y( W! X0 ]  O9 S% H5 Vfor k=(u+1):n
) f! S) w1 p( c# m" G3 r% ]d_f=d_f+d(pi0(k),pi0(k-1));
end
% y1 U& W. i# T2 M" D9 P6 fd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
0 x8 R, n5 C7 ^+ Bfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
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));
( S- _2 p% J; c- B/ d. jfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
1 o! E( D/ D$ E* t9 G. z' d! n' Gfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
* }) y8 C) Z1 o8 J/ Pend
end
pi_r=pi_1;

得到：
9 T3 j5 F# v, v) r" {2 M  [f,T]=TSPSA(A,0,99)
. }) [) b4 {( Z
f =
6 q3 w* V* C+ \# U6 ^2 a
! W; n, O: A7 K1 @7 G0 w2 d1 W" A   Inf

8 V& |+ V  _3 P, }+ p  f
T =
; }/ t0 j  E4 N* P
/ t8 K/ E/ @5 c$ @  Columns 1 through 18

2 L7 n" p) Q8 g* ]: r     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
! a! h" c# x7 _# N$ V* D, [, |) \! Q
  Columns 19 through 33
: z: p" D7 ?4 R# H. x
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
$ W! b1 n8 E0 r
这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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