用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
0 Y2 b4 k# v+ S* S+ e3 q
A=xlsread('33点矩阵s上三角');
>> for i=1:33;
3 o! z5 o  v7 s# p- z) ?       for j = 1:33
                   if i<j
) J* @5 a+ m6 V' g0 J+ ~, d- J                 temp(i,j)=A(i,j);
1 u$ S( w. R, |; A3 N                 A(j,i)=temp(i,j);
                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
+ H$ z/ e& J5 ]7 t1 q7 Y                 end
         
    end
0 n5 f3 p% }1 E7 [  V, ?5 R end

$ J" y3 _7 Y* S, S
; Z9 I: ]7 W: S/ w7 U( Z8 x 这样A为邻接矩阵了。然后运行百度的代码：

( e2 q# i5 e( G, |; \5 b
function [f,T]=TSPSA(d,t0,tf)
9 \# E* y1 K. A6 q: ~* V2 l9 C+ i! _%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
% [4 @3 S1 x0 p$ `! i- c* uL=100*n;
t=t0;
7 T2 X1 j8 ^7 ]- epi0=1:n;
$ {& N) Y& z" D+ D$ F  Fmin_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
9 a6 z0 k0 g: v& \end
% @1 d# B, J6 |- Z7 z! |/ ]- imin_f=min_f+d(pi0(n),pi0(1));
& v" w' Y, v' Q' Mp_min=pi0;
while t>tf
for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
# i) s) {  U3 t# {r_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
& @; s4 x! g+ \! a" o- F+ Lpi0=pi_1;
' H5 o- u1 m/ n! b9 Belse
* Y% s$ C& M( ~0 @/ b8 j5 Vpi0=pi0;
end
end
f_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
/ \# c1 h3 k  M; y& {) E$ G, O  Of_temp=f_temp+d(pi0(n),pi0(1));
) U: p  r. `; z: W4 ]6 Jif min_f>f_temp
min_f=f_temp;
9 U. j8 P6 f8 F) Tp_min=pi0;
end
t=0.87*t;
& O. i. ?" g7 q9 L2 V9 cend
f=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
5 k2 Y' {9 ~: K+ M[m,n]=size(d);
+ D; O! h  P* q, wclear m;
  V! u( _/ K( s7 a3 @4 Vu=rand;
3 N! h( w2 k* b9 n& y9 r3 |u=u*(n-2);
u=round(u);
# B( _/ ]0 ^1 g6 }) cif u<2
" `% V/ {+ h- r! t2 Gu=2;
4 b) _5 f9 Q  k2 _# n; I, t; [8 ~1 \9 hend
if u>n-2
9 z" ~+ a! ^( U" H" G7 V+ B3 ~' t! wu=n-2;
end
# e/ c9 @: \2 D8 p1 J. `8 ]v=rand;
2 j7 r4 v& T  D3 Tv=v*(n-u+1);
v=round(v);
  {5 B9 r. }3 j3 @0 i) vif v<1
v=1;
! z5 Z& o' a# |' x1 W' `9 ?' l$ Iend
0 k3 ^* I* _9 m* X7 Nv=u+v;
; Z' J7 h% ?# F9 yif v>n
$ d4 H2 ?1 O1 K1 A0 q3 ?4 ev=n;
end
4 Q' |# [! T$ ?5 o. `pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
& w0 q( Y" b8 O! ]. U7 |& `0 W: Gif u>1
for k=1:u-1
; h9 r; g8 W/ W% v/ opi_1(k)=pi0(k);
end
* @" o) F) C) b1 z( p/ n3 Y$ kend
if v>(u+1)
for k=1:v-u-1
( d/ _. i% H1 i! m) t; Qpi_1(u+k)=pi0(v-k);
" P/ x; ~2 V6 M7 Q, Nend
  @* Y, ]& a% x$ h$ j$ U7 rend
+ u: H* L- w  Q9 e; [if v<n
* L1 {/ u$ E4 Q2 {( pfor k=(v+1):n
pi_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));
6 N0 c; F0 o5 }for k=(u+1):n
$ h8 m6 Z! C3 j/ z7 {7 M6 Nd_f=d_f+d(pi0(k),pi0(k-1));
/ O) u$ q6 }, E( \  D$ U5 ^end
- s8 p$ e$ V2 H4 Gd_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));
& _& A" \. Z4 B: c: H) k4 d" tend
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));
, G7 T8 f& Q7 `for k=(u+1):n
. m0 ~  r5 V! R, u+ k. |' o5 ad_f=d_f+d(pi0(k),pi0(k-1));
: f) p, Y0 X; `2 g/ t* g; Nend
& u. D0 |8 J/ j- Xfor k=(u+1):n
- A: `1 y: w) h2 w8 D; s# a- N# Sd_f=d_f-d(pi0(k-1),pi0(k));
0 H% B+ l4 K2 X1 @2 g' eend
/ \, M" Y. {7 q+ Jend
( @$ h6 u/ T4 j6 D: ~0 @pi_r=pi_1;

& d8 c% P& j4 w2 e4 j7 X" e7 U1 ^得到：
  [f,T]=TSPSA(A,0,99)

f =
0 ~0 b  F& t$ H6 O/ v
   Inf
) Q+ l/ U6 F" B# f

, l+ }4 G7 A  P$ x8 M9 ?T =

  Columns 1 through 18

! C6 `, M* t* Y/ \$ x     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

2 z: {( ~! ?- ^3 q& k2 Y1 j  Columns 19 through 33

. F  h+ O" o4 n# ~    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
/ o/ N9 N3 Q- r8 ]( Q/ @- Q3 C
9 m8 ^% G8 R/ X# [* M$ l: }这个初始，结束温度是自己随便设定的？？
/ j* g4 b+ `) a: Q) R, ^, n得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点，优化起始点可以随机选取也可根据经验选取.
# B  c: T7 ]& ^1 E: ZF是目标最优值,T为最优路线。
9 `3 o. _7 J0 u) T9 X+ A# \3 [F是无穷可能说明所求目标值没有路径到达没有最优解，或者是不是由于哪个步骤出现了什么问题（比如数据，或者邻接矩阵那里等等。。。）导致没有最优解。。。T表示的是最优解的起点到终点的最优路线。。。。。

magic2728

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