用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
$ q+ @2 v0 h/ @: I, ]% p8 D1 t) C
$ b# ~7 D4 l1 L5 A. H; i A=xlsread('33点矩阵s上三角');
/ C( ^5 h1 v, X>> for i=1:33;
       for j = 1:33
/ Y, i" D7 h4 b+ x                   if i<j
* e4 T8 H; Q1 j, a, j, @$ \4 _                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
$ X% H, W* D5 u2 j                 if isnan(A(i,j))
                 A(i,j)=inf;
6 x, r( a+ O6 W+ G" G5 w# {( L                 end
         
    end
end


这样A为邻接矩阵了。然后运行百度的代码：


( n# n8 q( i- {5 Wfunction [f,T]=TSPSA(d,t0,tf)
; c2 W$ u+ n. V( F4 f6 {4 x%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
, x: g7 i5 q6 |  M9 }5 |8 J$ I* }L=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));
end
% M* f2 \* I& L# A7 Amin_f=min_f+d(pi0(n),pi0(1));
$ J8 v; h9 p/ ?* N# a5 i4 s9 T8 bp_min=pi0;
while t>tf
for k=1:L;
5 X1 @& M( H# E4 h- _6 Xkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
4 y8 n& W. b  I/ L+ jr_r=rand;
3 |: z$ \% f4 o/ R) Gif d_f<0
  {! A2 K1 x! _9 K6 S; s5 }pi0=pi_1;
8 c9 d6 `2 s6 x" y) y2 yelseif exp(d_f/t)>r_r
pi0=pi_1;
else
2 D. N6 }$ t& Ypi0=pi0;
' t- b" T5 F8 S7 uend
end
! k$ q1 L9 P, ^' N1 ~5 wf_temp=0;
3 |  V! @1 x2 f( b% Nfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
7 J* P9 v( ~1 jf_temp=f_temp+d(pi0(n),pi0(1));
7 H. o) I0 o0 b6 R" T5 Lif min_f>f_temp
1 j: `- N) S" p8 F+ ymin_f=f_temp;
& V7 c  n9 m6 [p_min=pi0;
/ u  g( m- [, T2 p# Gend
t=0.87*t;
end
6 k+ o9 S9 [, `+ @f=min_f;
, X7 l  c) R# Q: I+ sT=p_min;
%aiwa要调用的子程序,用于产生新解
0 R2 v9 G3 _; }8 n& k9 [function [d_f,pi_r]=exchange_2(pi0,d)
7 C( B2 {" }9 s  E+ P' H[m,n]=size(d);
clear m;
2 @% {" Z. @- v2 mu=rand;
u=u*(n-2);
u=round(u);
if u<2
9 J1 A- ~$ V9 a9 m8 z4 gu=2;
end
if u>n-2
, A8 H; I- Q) l. p$ o* O8 V4 Su=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
v=1;
end
v=u+v;
# s$ t- [: S6 D- v* cif v>n
v=n;
end
# s1 I. h7 `  u' Q7 I/ R7 u/ Y% Jpi_1(u)=pi0(v);
pi_1(v)=pi0(u);
0 j1 {9 z. X. T2 r" J' Y! hif u>1
for k=1:u-1
pi_1(k)=pi0(k);
, d2 U% A- B0 m8 F' Y6 Tend
end
2 J9 q  h2 F& }& y: J0 Kif v>(u+1)
8 p7 Y* Y4 _/ e1 H  }5 M' B+ [for k=1:v-u-1
1 V+ z- ?9 q6 Zpi_1(u+k)=pi0(v-k);
( i7 s2 S) w! xend
0 J3 C- |. e/ R1 @6 m5 B* pend
if v<n
+ X) a9 V9 |; I& R, s7 `" zfor k=(v+1):n
/ u6 j3 |# W/ F: Q3 jpi_1(k)=pi0(k);
; N; Y) A) [  ?: S0 l& E! F1 \8 uend
3 `2 A) @. N$ x" ?. wend
d_f=0;
if v<n
# {& H' F  @4 Z  ?% `( ]+ md_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
  _% a/ r3 ^. O0 G7 d" Dfor k=(u+1):n
$ s* f4 k/ ?" t" i* @d_f=d_f+d(pi0(k),pi0(k-1));
# K4 i- z6 h# l; Iend
6 g9 G+ ^' C$ p5 C) E$ cd_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));
' N1 S4 m" {6 \6 {: B% b/ Q+ a) pend
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));
) a! L2 S. S! l* P- q% jfor k=(u+1):n
3 ?6 a3 ?; w0 k" H3 Pd_f=d_f+d(pi0(k),pi0(k-1));
end
) A) d9 C# e9 u' y. lfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
% M0 P9 y7 t+ n. k! Kend
end
pi_r=pi_1;
8 _7 E+ T4 `' `
得到：
  [f,T]=TSPSA(A,0,99)
' G& v+ O! y8 q' t0 k7 R3 t
f =
) n2 t4 Z. h7 H1 H4 U4 P
( T( K; z7 O8 F) c   Inf
2 C( ], q& q$ b3 N2 j

T =

  Columns 1 through 18
* |+ ?5 o, L9 a6 b) R
0 t8 y& p5 C5 m. K& _     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

& Q1 G+ b% `/ J6 j+ J) [  Columns 19 through 33

% z& p+ p: Z* Q6 Y6 C    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

& n: R  s, B) Y# y, G2 B这个初始，结束温度是自己随便设定的？？
* ^6 p8 s" K# \% n- M得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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