用模拟退火求TSP如何？

慢跑20

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

1 b4 E) A+ N7 E2 X A=xlsread('33点矩阵s上三角');
! h6 ?7 ]  o2 k2 ?. \. n. f>> for i=1:33;
; Q0 V, s: ^5 a) E9 Q/ |" t) n5 z6 W       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
1 {8 E, T/ j/ [) @+ |                 A(j,i)=temp(i,j);
                   end   
3 B2 I% V& Z5 J/ l$ d% ~3 o  x                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
* N1 b1 t9 \. t; Z         
# B$ w$ z5 P7 K  J    end
, Y! M/ _1 z( }& b  q( ? end
/ S+ d! Z6 C! ~: G3 y, P4 p: R
+ S8 E# [" {. U6 B5 _
这样A为邻接矩阵了。然后运行百度的代码：
% c: W$ T. I& ~0 n# y

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
. J& d. Z, `( G. I! {: B' V$ cL=100*n;
t=t0;
pi0=1:n;
min_f=0;
for k=1:n-1
9 o' X' m: L4 i/ Q; f& Y3 t- `' W9 omin_f=min_f+d(pi0(k),pi0(k+1));
" m; ^6 I5 t7 C: D0 Kend
) o+ Q+ O9 S' gmin_f=min_f+d(pi0(n),pi0(1));
# h6 \" @/ k4 {$ \: w0 qp_min=pi0;
while t>tf
- I' |9 A, G; X. K" _for k=1:L;
& o3 g. N5 Z+ r+ V7 N3 k: pkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
1 J4 |; C/ R4 u. O8 @; c  Xpi0=pi_1;
else
: I1 P: Z9 ]* O/ o* G( H0 opi0=pi0;
end
end
$ h2 w( f+ a, o$ j9 P% a8 c8 vf_temp=0;
+ x* k1 D3 w' w; e6 D) p) Qfor k=1:n-1
0 y/ o7 I4 D. X* x& Tf_temp=f_temp+d(pi0(k),pi0(k+1));
' L+ ^8 C/ t2 e; w# @/ ?" i- U2 T6 tend
% ^9 r# K$ O# P6 q* c% A  {( [f_temp=f_temp+d(pi0(n),pi0(1));
) M1 f( i, K/ Wif min_f>f_temp
min_f=f_temp;
p_min=pi0;
" w; f6 i, u, G6 `; t+ P6 N7 t8 ]end
t=0.87*t;
end
f=min_f;
T=p_min;
) c  l$ F6 q5 n: K. m7 s%aiwa要调用的子程序,用于产生新解
8 v  _) j# p( K  k( |) Zfunction [d_f,pi_r]=exchange_2(pi0,d)
7 v2 P- t' W9 F" F2 d5 V- s. z[m,n]=size(d);
; ]( A1 t& R3 J) hclear m;
" b  \% \2 C' ~; K) U1 d# Du=rand;
u=u*(n-2);
% O4 N0 f/ Y3 ~& _& C$ w1 m: @8 Hu=round(u);
* \; r& }6 C; B3 Vif u<2
u=2;
end
if u>n-2
( q1 j0 {6 \0 h7 J3 E8 Tu=n-2;
: H4 v6 E6 Q2 x( nend
9 F  q1 s! G9 @v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
v=1;
- E# ?3 k7 J* M2 Pend
v=u+v;
if v>n
v=n;
end
pi_1(u)=pi0(v);
5 C% q' \/ R+ a7 fpi_1(v)=pi0(u);
if u>1
for k=1:u-1
9 H* f% C0 Q' b% s4 H1 v8 Gpi_1(k)=pi0(k);
# W  o0 r$ h5 n: \  w0 ~end
; X/ Y8 R( h* E# ~- X) ^! M: Uend
- L/ v5 y% |0 n* G' E* [, |if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
# T# Y2 J% i) _- Iend
end
if v<n
$ b% R' E- \' m8 g" i4 i" {for k=(v+1):n
! n* ]# C# N) q: p9 bpi_1(k)=pi0(k);
8 ^( R7 f; T* U& o) _end
end
d_f=0;
7 w! m% A, Q4 i- o7 Rif v<n
: w5 ?* |2 a. Md_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
5 V: g  E! h& J1 Gd_f=d_f+d(pi0(k),pi0(k-1));
end
0 X. E  S4 Y& e3 x( d/ td_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
- N4 J! v. g, f* `- y& p2 E2 kd_f=d_f-d(pi0(k-1),pi0(k));
; i( K  \% P$ `end
4 |. F- c2 ?6 S4 T3 C  ^else
6 T# n# Z/ ^/ b, X# g4 \4 U( s% i4 ^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
# w9 ?& R# f2 j, M. U% a/ ]* I9 Pd_f=d_f+d(pi0(k),pi0(k-1));
) q7 \+ \) P3 ~- b! }3 K7 ~end
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
8 c0 x4 j5 n- N2 xend
! ?1 P% X' C3 i, f: ]$ Y: }7 m7 c' Qend
1 t. O4 P8 _. gpi_r=pi_1;
; I: ]* g7 C- Z  @! X$ ]" H% D" O
得到：
  [f,T]=TSPSA(A,0,99)
8 j+ O2 v6 a8 ?  Z( q; t$ E" a
f =
& [) T! R$ I, e# V  E
   Inf


4 @! j1 c$ e6 V6 d; q6 P% oT =

  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
* t: x' [7 k7 m& g- P, N
: n5 d3 ^" c/ g3 w$ ^6 G3 w, H  Columns 19 through 33

8 z: X2 M- R' [2 e    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
$ Y4 M# y- A: @3 b. h
  E9 C7 G: |3 K% c7 C6 x2 o& d! H' i这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点，优化起始点可以随机选取也可根据经验选取.
# V& ~5 t2 \4 h9 x: l$ X9 GF是目标最优值,T为最优路线。
+ B, c( ]# q, Y6 n6 T9 JF是无穷可能说明所求目标值没有路径到达没有最优解，或者是不是由于哪个步骤出现了什么问题（比如数据，或者邻接矩阵那里等等。。。）导致没有最优解。。。T表示的是最优解的起点到终点的最优路线。。。。。

magic2728

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