用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
. x( A$ b7 r9 }9 S" S
3 g3 M$ Z# O, J8 N6 o A=xlsread('33点矩阵s上三角');
" E- z( ^) X+ _3 ~>> for i=1:33;
       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
7 H8 }2 t# F* o                   end   
                 if isnan(A(i,j))
! K4 c( h& X- X                 A(i,j)=inf;
  T' X! q5 I( e' G7 ~- `* N. l                 end
- M# x% P: Z" U$ [9 g6 m+ P) {         
  T( c4 C; R& J3 t( d% h    end
end


; {! E8 v7 H: l0 N 这样A为邻接矩阵了。然后运行百度的代码：
: n( M: K2 M+ j, b2 _( f& p7 q  x* |
5 w# T8 F# F4 C1 V
function [f,T]=TSPSA(d,t0,tf)
' B- b% z6 k* L0 _: I5 u9 ?%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
# H4 W* y9 ^% ]& d9 t% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
) B0 H. a' \2 r$ IL=100*n;
# ^3 J1 D. B* _: O( [t=t0;
pi0=1:n;
min_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
end
( A. g; S4 t! G5 I( y6 ~min_f=min_f+d(pi0(n),pi0(1));
' u7 `7 M" {/ W! G) @$ t/ Z  Sp_min=pi0;
$ N5 p, b0 ]" O  lwhile t>tf
for k=1:L;
* X% T2 R0 J' _; _kk=rand;
- y0 F4 G! L, S3 X% ~4 T. i[d_f,pi_1]=exchange_2(pi0,d);
0 v6 E. x* d7 y; s4 g% Dr_r=rand;
( v" t( r9 z) @if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
/ O( J7 i# z5 I; [* {2 kpi0=pi_1;
else
3 P9 J3 [5 s, gpi0=pi0;
  T5 H3 J9 m# d1 V9 _end
end
f_temp=0;
3 c% C0 X  O( U6 S  B& ~  afor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
3 t* ~0 x- C0 {" y# o) \5 gend
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
: e. V& G% Q6 s: A7 g4 rmin_f=f_temp;
! l3 M2 \7 B0 Z3 S9 c1 Up_min=pi0;
4 F' {/ g1 v8 h) u& @end
4 |- @0 `  `1 t! a% W3 Zt=0.87*t;
3 o( N" j8 u- C2 |- T( Pend
f=min_f;
" Z- `: Y" _* T) U( n, eT=p_min;
$ o2 D: m. c' O6 M: n6 X& l! x0 p%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
2 @2 l, X4 E& g& k# R& l5 yclear m;
/ Z5 k- W* D  k, Zu=rand;
& s- T" G1 @; i4 \/ lu=u*(n-2);
: {; a* r" _+ d$ Qu=round(u);
if u<2
u=2;
& s( ?( r) B+ M$ gend
4 w. P/ @6 c# [# S, wif u>n-2
u=n-2;
end
8 C6 i4 s, M, W; kv=rand;
v=v*(n-u+1);
' _& y/ \- c( S( U3 R, R% ^/ hv=round(v);
5 u- e$ [& A  O8 p3 o9 Z; rif v<1
v=1;
end
. w" K; C/ F7 Mv=u+v;
0 {4 u) H6 `. p) W3 ?9 bif v>n
$ ^# |$ ]7 U3 |# o2 x8 kv=n;
end
pi_1(u)=pi0(v);
3 Q0 m7 e- G- V  [0 O2 I3 t0 ipi_1(v)=pi0(u);
0 x: r5 v+ B, l* V3 ]" S$ O+ Zif u>1
9 p( W  g+ Z# D4 [for k=1:u-1
8 a/ }  g0 e  tpi_1(k)=pi0(k);
end
end
9 p# E+ O* Y, p# M0 hif v>(u+1)
for k=1:v-u-1
$ U" l5 P: J4 \! X7 \5 y1 ]pi_1(u+k)=pi0(v-k);
end
) e# d! ]# x0 Nend
6 y* x! w% K: ?4 P# P% V( U4 e( v$ cif v<n
for k=(v+1):n
0 h% M+ l/ F# W% Npi_1(k)=pi0(k);
end
end
d_f=0;
3 P1 Y1 t) [# P( Lif v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
, T8 p- v: O7 D. m9 H5 hd_f=d_f+d(pi0(k),pi0(k-1));
end
" O6 ]: K& r# H& n9 k1 m% |' yd_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));
; g( S" E+ P  x3 I/ send
7 o, N' `0 x  c  I* w2 Xelse
8 K1 t9 O# \7 d2 b# ?d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
, U8 ]8 L6 T6 v" {/ u6 P' H- hfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
  o) F9 k! K# Y! F  f# j' x* iend
2 ]' p1 [2 e4 G( f# m! I" vfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
4 u+ _5 X5 b* o) a: D( e. `end
pi_r=pi_1;
. ]2 R4 S" I" n
得到：
4 |8 ]/ _5 g  E* r( a, f9 m( q  [f,T]=TSPSA(A,0,99)

f =
  m" X/ U2 Y7 H8 [( M
6 p# K* L4 F! D7 ~4 F   Inf


T =
" m% ?+ s2 s# P; {" B* X! |* z
  Columns 1 through 18

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

" g: W, C, ?) h$ n7 U; M  Columns 19 through 33
# Y! n' p  }: V! V- u7 a3 O( G
- m: h: c7 |9 v9 Y0 Z0 Z    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

" t8 K$ ]! T4 G4 A- ~2 G. r8 n这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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