用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
( U5 a0 K% Q4 B9 f- |) N$ t
0 S! A" u9 K7 @- P% d5 s A=xlsread('33点矩阵s上三角');
>> for i=1:33;
  E  _: t; x3 e8 v; L  T! v) b       for j = 1:33
% H6 ~# l0 e7 x2 C                   if i<j
, E4 b9 k7 p$ Y0 R                 temp(i,j)=A(i,j);
$ V" Z/ S$ @0 k! q, m# W; D                 A(j,i)=temp(i,j);
                   end   
                 if isnan(A(i,j))
( ~! u) O, d, A& _5 F: v                 A(i,j)=inf;
                 end
         
: S, z7 Y; h  d* [9 }    end
' \/ b$ v  N0 B: I end
( X& \5 o, p( T0 a8 G& R, k

: O7 b5 |8 l& E# }# |+ O 这样A为邻接矩阵了。然后运行百度的代码：
( G' ]5 t/ C5 \/ S, ~( a; V

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
& S5 k; J; p1 x3 }! v! f% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
7 s6 O: g5 {8 n7 L5 W  _; z[m,n]=size(d);
( z  a3 o6 }" C% l) k( D5 JL=100*n;
t=t0;
pi0=1:n;
min_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
, j; @/ q" w2 j. k6 K# V# x1 `1 zend
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
while t>tf
9 ?; d9 l* M: X' R: w$ Cfor k=1:L;
7 M$ Z1 o! E% t, ^, V7 xkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
  m9 ]! o7 N& H- N, x( Y) dif d_f<0
) F5 p( d/ L# f- {( D5 B) _pi0=pi_1;
9 d' x" F+ j) u& Z8 F7 f& Y% telseif exp(d_f/t)>r_r
. V: Q9 p7 Z1 ]) O+ n% Opi0=pi_1;
$ [4 P! H/ ]' H7 c# O* g( g0 b/ K& helse
pi0=pi0;
end
end
f_temp=0;
& P- ~* S8 s, Z; s6 Tfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
5 C* F. A) V) F. T3 `+ C2 o* Dmin_f=f_temp;
p_min=pi0;
end
t=0.87*t;
end
f=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
/ |; T  Y6 ?6 }) A2 cfunction [d_f,pi_r]=exchange_2(pi0,d)
. c- k( D0 E7 \8 C[m,n]=size(d);
clear m;
' I5 o# }$ C$ Tu=rand;
u=u*(n-2);
u=round(u);
if u<2
u=2;
! i' x1 B5 U& L  k0 send
! F$ @6 E2 D7 F! Z1 ?' hif u>n-2
- i" F. M. W2 i) k8 d3 P3 [u=n-2;
- @5 Z5 _7 s, A! \1 W3 m1 vend
- Q/ K" g# u& z* a2 }+ s% Fv=rand;
' b) C" K, d. q! X; s$ H3 Cv=v*(n-u+1);
' y: \* i' g/ k' M4 {v=round(v);
. Z$ M$ `8 Q. c$ nif v<1
% ]3 m: a' \3 }6 Iv=1;
) e8 ~$ i& |, P3 {end
, C( B2 C+ h( c8 B  Y# wv=u+v;
  D( q, w& o$ h" q$ c, O2 |if v>n
6 D7 Z( K+ p- v, fv=n;
1 g$ B% @- }+ O0 B; Eend
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
for k=1:u-1
  z9 _8 e, n5 h; \9 {( _/ n  F- [pi_1(k)=pi0(k);
0 f  @/ F9 L5 `+ b  v1 O0 \+ T$ rend
end
if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
  G6 \# S$ Y) g+ k4 |( mend
) X! G* u% k# r, V# uend
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
& b* r+ V1 Z# r: Q! Vend
end
d_f=0;
4 a4 d% v6 y4 I0 c) f0 z' }; }9 uif v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
, t: w0 E: \& ?' Sfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
( M. p$ r- r# N. P! v& Sd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
7 [9 h( V+ {& l; d$ h4 Qd_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));
, P. R$ M& P" l) l8 t2 G+ I! \8 lfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
. Z) E5 ]6 N5 ?- @9 k& ?  mend
7 ^7 i( u6 f! f- [8 Vfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
end
pi_r=pi_1;

: n% n, n) S6 p. q  v1 V# q. i得到：
  [f,T]=TSPSA(A,0,99)
! P2 D* M7 M+ J3 m1 \2 }
# Z) T2 _! ]2 Y8 pf =

   Inf

& m- ?' M0 `8 z0 I/ `
T =
# n" S4 |, e7 G4 U  }
  Columns 1 through 18
- B: \( d+ W# c6 j% [3 Y1 E# [# b
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

  Columns 19 through 33
( U  }& F$ \' j: f( K# g: l5 B& t) G
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

& C! H  q# s" [( y0 \- P0 u这个初始，结束温度是自己随便设定的？？
$ a) t4 {' \# Q1 q得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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