用模拟退火求TSP如何？

慢跑20

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

- _# c! W: O3 B A=xlsread('33点矩阵s上三角');
>> for i=1:33;
/ S& M2 c0 P8 Y3 A: \) J       for j = 1:33
4 Z5 t" ?, W# B                   if i<j
                 temp(i,j)=A(i,j);
. Y: V! z: f, [" {' \% A# [                 A(j,i)=temp(i,j);
                   end   
! Z2 w! ^' ~0 l* C# P9 m                 if isnan(A(i,j))
# A8 N0 M& }; N6 n5 f* W                 A(i,j)=inf;
5 h( J( M% G/ e                 end
: `/ c9 i7 [) \1 i" c: M3 p* A         
6 P8 g+ n: \: V; i5 \' v: U9 V    end
; e& @% }: f  ~8 x+ Z: ? end
9 P+ R3 \* {0 S$ D5 O% x: c
7 U/ R  e2 d3 y" w! e
这样A为邻接矩阵了。然后运行百度的代码：
# f, ]) {) k2 ~. y' N" a, R

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
. q) e; @$ X9 ?# A2 F# N7 Y  t* @8 U% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
  m6 J, H2 U$ q9 D; _, H3 UL=100*n;
t=t0;
; T. c& Z1 |# k( M0 \7 k" p0 p1 Spi0=1:n;
min_f=0;
  t+ c( ?4 U) v8 ]for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
  H- b# n3 c- b1 Z9 Y1 }end
min_f=min_f+d(pi0(n),pi0(1));
6 l0 \8 i# R. H* t9 s0 }p_min=pi0;
# e* \! ?& H/ p* K% Fwhile t>tf
4 Q! c6 M& S' b* {' @for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
/ w2 G4 l/ L  s/ ^/ t* Nif d_f<0
pi0=pi_1;
8 c1 [, K1 O, F6 ?elseif exp(d_f/t)>r_r
pi0=pi_1;
else
0 Q+ n4 j! V: U( Q8 Ppi0=pi0;
4 x- c( D- Q; Q& I" g6 z0 ~end
0 m6 D/ r  h; `9 uend
f_temp=0;
for k=1:n-1
4 y, J* \, b0 Gf_temp=f_temp+d(pi0(k),pi0(k+1));
end
8 Q0 l7 H$ S1 W: N7 z. ef_temp=f_temp+d(pi0(n),pi0(1));
0 i9 ~7 K7 `! K: S8 o( yif min_f>f_temp
min_f=f_temp;
% u+ Y9 L; v. fp_min=pi0;
! v, ~: N" O* Q/ ?1 F+ ~6 yend
t=0.87*t;
4 d4 K. E5 s: K2 E/ s# a5 o! }end
' g/ i7 ]* W" F* O$ r8 Lf=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
* d! Y$ Z; a2 n4 s: _function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
clear m;
u=rand;
# Y; F; m- z$ L" y! au=u*(n-2);
/ p& |5 S; X. f- K! yu=round(u);
if u<2
u=2;
end
if u>n-2
u=n-2;
end
3 l6 L+ U6 S; `$ Q) @2 |5 ~v=rand;
& n2 u1 H8 o  ]6 h) Mv=v*(n-u+1);
2 T$ h, x: C  c% l/ ]( B8 K2 \$ Gv=round(v);
if v<1
' a* P7 ], I0 t( `9 fv=1;
end
  v/ k. Q7 ?- {+ r) o5 y! [v=u+v;
if v>n
v=n;
end
# o+ O' @' ]* k) y$ ipi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
for k=1:u-1
pi_1(k)=pi0(k);
& c4 R6 {1 M: n  n. s6 E7 x: Z/ Jend
% G! }! X$ |1 ], @, |end
$ F% w7 J, I" f) B( N1 |if v>(u+1)
+ j  [" @- n1 i. D: g" {for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
( S3 u& ^7 u: x9 xif v<n
for k=(v+1):n
pi_1(k)=pi0(k);
end
! i0 r! J7 p/ d+ x0 H' r9 R# eend
+ V9 M$ k( `1 ud_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
0 R  W. W* L, u: \' D5 Jd_f=d_f+d(pi0(k),pi0(k-1));
end
2 z2 `. ], q( C& Ld_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
9 l; G7 T3 q0 `" r9 Wfor k=(u+1):n
7 r' O! |- q! D# F1 w/ H) j9 |: k% r5 yd_f=d_f-d(pi0(k-1),pi0(k));
% u* \2 L1 l0 e+ B- Nend
else
8 B: `' u+ _) dd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
4 k4 X/ w4 A, Q# {. Mfor k=(u+1):n
$ E& u: ]( R) Z4 M; M; |d_f=d_f+d(pi0(k),pi0(k-1));
end
for k=(u+1):n
, h5 P: L& R0 X+ u- G- N! Xd_f=d_f-d(pi0(k-1),pi0(k));
end
$ K; [; O6 X8 E' C0 W8 ?( ]end
pi_r=pi_1;
" {% J3 Y* V$ d( S
得到：
  [f,T]=TSPSA(A,0,99)

4 r7 U  @2 I/ g5 F9 e: d2 @* cf =

   Inf
* [+ h) z$ S) q4 u. U, t+ z7 |% j5 y+ Y

$ r/ G! Z1 X, }4 G& D0 w8 oT =
8 e) \# R) H) q- F5 _
" ^2 @0 q- R3 d4 g5 h  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
4 `$ k! j& P. }$ Q' X' N: ^' b
  Columns 19 through 33
0 L8 L5 }( n/ U9 x
; B/ p/ a5 l$ u: G- ?    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
2 Z0 P* @9 a4 B. E, s0 k8 G
这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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