用模拟退火求TSP如何？

慢跑20

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

A=xlsread('33点矩阵s上三角');
>> for i=1:33;
       for j = 1:33
( \5 H6 V  r2 p% S9 f1 q/ b' y                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
  m$ u4 M* h' q. q9 a% B                   end   
                 if isnan(A(i,j))
9 Q! r6 P7 k1 E- C0 V                 A(i,j)=inf;
                 end
         
. e" o9 ^# o! R$ F0 t' s( H" f. o    end
end


! V* y1 g4 S: i* N/ E! s8 ^ 这样A为邻接矩阵了。然后运行百度的代码：
, A3 R8 c6 e3 u1 |8 G0 U: X
$ O2 @) V( s& ^7 T
function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
* k' q/ v% @5 J. z) @2 E( \. b0 M3 s% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
t=t0;
pi0=1:n;
min_f=0;
' B/ n; J) ]- Tfor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
5 h6 `5 ^+ H/ `$ q! @end
$ c. ^' w- a1 P# g# G2 N6 bmin_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
! x5 [/ {% j* Gwhile t>tf
for k=1:L;
kk=rand;
2 r! ~, ]2 ^$ K0 Y4 n* [- l  ?[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
* B, o2 f( K: e; Z4 L$ A" ?if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
/ t/ t6 ]: a8 W' w$ k1 U# Q- Uend
end
f_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
& F& Q& w; N% G4 [6 P" s; L/ {: Uend
f_temp=f_temp+d(pi0(n),pi0(1));
) c% K7 r6 A6 l. [7 a0 rif min_f>f_temp
min_f=f_temp;
* q& v% a7 K* c& k( c6 Gp_min=pi0;
end
t=0.87*t;
: B# r. v. h' T# Aend
+ }( R; W9 N3 d- ff=min_f;
0 _% ~, E  R4 C  fT=p_min;
6 L! z3 \+ s& i4 S  c%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
8 {+ a6 ?) m/ f6 T( B[m,n]=size(d);
clear m;
1 j% D8 Y5 j4 S* t  \- nu=rand;
; C& P  u8 Y5 \: M$ A3 Du=u*(n-2);
( ~. F4 Y5 g2 W; zu=round(u);
if u<2
- B' |0 ^5 N) ^5 Ru=2;
2 D( D/ [9 C- e. c0 v4 Rend
0 `2 q: l1 q& e  ]1 b$ m# A% ~if u>n-2
u=n-2;
+ d5 f8 W; \; G  \end
9 D. A5 O/ ^3 B& dv=rand;
9 }7 k" f$ X2 b! X, ^; uv=v*(n-u+1);
v=round(v);
3 j9 M* O! J$ @# }5 qif v<1
& Z/ Q" R4 K7 \+ z' G3 yv=1;
end
* L8 Q+ T3 W( I) y$ j- }) W  Qv=u+v;
if v>n
v=n;
4 |2 |# p! g7 a: y. @9 y/ `end
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
+ a+ s1 M; I' Kfor k=1:u-1
( h$ J  t. ^7 `1 H& ]" |pi_1(k)=pi0(k);
end
8 {; B7 |+ E5 V: q, Y8 w7 pend
if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
$ O3 `2 L; T( I" iif v<n
1 c  o8 h3 t9 i3 L+ \: ?+ ?9 M8 ufor k=(v+1):n
5 P" T$ z$ `) q& V# \pi_1(k)=pi0(k);
end
8 T$ Y& e+ N: n% E) E6 Tend
. Y7 j5 b. n% a+ }  md_f=0;
8 I1 E# u+ A# T' F* k3 kif v<n
  g5 M9 |! C' a- Nd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
! N$ I' _- R# E7 p7 _( jd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
' `( J) [) I- p% ~; G/ qd_f=d_f-d(pi0(k-1),pi0(k));
8 ^6 B( g  w4 N: g: \end
2 Y3 Y8 r+ W. [else
1 d( ^  Z+ a. q3 @d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
for k=(u+1):n
( n7 S/ R) |# c, {2 s- M% sd_f=d_f+d(pi0(k),pi0(k-1));
' S, n3 _) ?' send
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
# F1 l8 K$ x3 y2 Tend
, P& ~$ z7 ~/ [: O0 opi_r=pi_1;
. o% O) x5 N4 }8 O9 ~) ?& }
3 i3 ?/ k2 T  k6 l' }) p3 e4 {; A得到：
2 X% N% l; o& N% y: \; K; d  [f,T]=TSPSA(A,0,99)

f =

9 h1 F% R, [' \( u) m' `   Inf


9 X) K; @1 }/ ?% Z3 B$ r! k. q2 xT =
/ D  @) v7 C; j( a: f
  Columns 1 through 18
" f; a3 S; G8 |. J( f! V4 Y
8 Q& r- A  V9 u& }     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
! ^) a" G5 W( m+ z" a
  Columns 19 through 33
2 w# H/ d: L! ^* P  r" @
! ]. l& y- b1 j9 c- a% ~/ W    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

5 k. t; c2 ]! `6 |! k这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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