用模拟退火求TSP如何？

慢跑20

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

$ Q! k  W& K% @! c; h: J A=xlsread('33点矩阵s上三角');
2 z! P1 Z" |- ?>> for i=1:33;
, P) \6 U3 V/ Q- |2 V$ N  w, c7 U       for j = 1:33
% o: {; j  O* D                   if i<j
                 temp(i,j)=A(i,j);
8 _. E; [+ t1 W  I                 A(j,i)=temp(i,j);
                   end   
8 j& G8 V" K+ r: F% d4 d5 |                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
         
% U. g7 U1 Z) h/ r* i& P1 ?% j- V; I    end
( _  `1 ?8 |5 T0 F, K8 m# k end


  ?( X: Z. @9 l) S1 M; p4 i+ S 这样A为邻接矩阵了。然后运行百度的代码：


function [f,T]=TSPSA(d,t0,tf)
3 E% L; {& L! X%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
. Q7 J8 N' z. `# y/ BL=100*n;
# o- L8 J% r1 Y5 z7 ^t=t0;
  t7 s$ ~4 O  c/ ?: n  spi0=1:n;
min_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
end
, q" J4 J) N4 _min_f=min_f+d(pi0(n),pi0(1));
/ N) f: J9 b" S, ap_min=pi0;
while t>tf
+ Y4 a  Q+ S. ?9 `' W9 qfor k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
: X/ z$ h$ m, h0 S0 R% n. R" u% E. ~r_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
: ^6 e* e% \' Gpi0=pi_1;
" |: h1 A7 p1 M* O: Oelse
2 [" u. n$ ~; k2 y! A+ fpi0=pi0;
( ?& }: W. X9 s. |5 p2 iend
. [+ G' {' N: l4 `# qend
f_temp=0;
! i$ M3 f9 H5 l( Rfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
$ l6 f- Y. c# n3 k, u; e' f9 u. V: yend
% u' O, K; U, R+ d, s+ |f_temp=f_temp+d(pi0(n),pi0(1));
# O4 g# Y2 x( ?* _7 H8 Z: Bif min_f>f_temp
0 L: z/ |2 j: i, l' |min_f=f_temp;
p_min=pi0;
end
5 h/ P$ \- q) O, Mt=0.87*t;
end
: ~, E) Q# q! n* S. X" qf=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
3 w8 L4 F: A- c/ S- N9 w- @function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
6 L6 Y" Q, w& v' _$ U: y6 f  Rclear m;
# W! I, V0 G0 qu=rand;
u=u*(n-2);
$ d0 [7 x' B+ E" B$ |2 l& }u=round(u);
if u<2
u=2;
end
, Y1 y& c- n, O! y3 U" pif u>n-2
  n1 D0 ]5 g) }u=n-2;
# U% ]5 ]) J: c; aend
6 R" \$ g4 P0 jv=rand;
v=v*(n-u+1);
7 i! X" C: ^# q% V  w" [( x- Cv=round(v);
) n) J4 B; Z& Z1 X! vif v<1
v=1;
end
( S/ B+ j4 I6 ev=u+v;
if v>n
0 K/ T% }1 b  o7 Y/ M8 b$ w) Jv=n;
$ Q/ r$ D4 g9 B- U, ~- M3 Qend
( r9 V" X1 d* ]: _% P% x' epi_1(u)=pi0(v);
; ^1 M- C, b0 r% Mpi_1(v)=pi0(u);
. j, D5 v1 F. W: C2 C0 n7 U+ pif u>1
for k=1:u-1
pi_1(k)=pi0(k);
end
end
if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
$ F, |: i/ L2 |& Q) vif v<n
; y8 n9 U' K8 h+ e: @! zfor k=(v+1):n
# M' b4 c) `6 z6 I9 L) C  F5 ^) wpi_1(k)=pi0(k);
# u# i- p2 _7 y* G2 ?; Xend
end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
) m* G9 X6 w) d% `. q2 @6 e- g4 qfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
5 C: j" D( Q; ^" x. yend
; o- Y7 r; J8 E  _  ~# B- r5 wd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
6 ~3 y$ A: q' _( W0 }# A+ X7 n" efor k=(u+1):n
  b7 a2 C2 p1 O! m& J, }- {d_f=d_f-d(pi0(k-1),pi0(k));
. b) I% ^& V, T* F% |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));
) Q( {9 Q) z8 S2 Xfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
; s8 m4 e  o! |9 y& b6 d2 y1 Aend
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
+ `! D/ |+ O+ K  K" n6 Yend
end
pi_r=pi_1;

- R! E) ~! R) j  J2 S# _. k6 d得到：
$ F8 `1 P  K- h& b3 \0 r  [f,T]=TSPSA(A,0,99)
6 j# p; I  ?! E4 [& d" t, s! t6 m7 g/ a' o
7 m: W' O! V! w, t6 `0 p5 w* Hf =

% V- B& ^/ |: ]+ \" Q8 c9 W   Inf


T =

  Columns 1 through 18
# y* o7 ^( U/ T% h+ p
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
2 T3 G% o7 e2 J$ ^5 U6 @
7 g8 M3 s3 q) A9 p6 e( m) [, g% ~' p  Columns 19 through 33

    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
# b) \5 z, M6 J9 [5 e2 q; X
这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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