用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
4 T2 e+ M7 G, ^3 ~+ x6 b6 u% a
: F7 K7 ?7 A. f1 f9 } A=xlsread('33点矩阵s上三角');
7 i# a* n# J* n0 k' v: D$ H>> for i=1:33;
       for j = 1:33
: k6 p* p7 a6 P                   if i<j
* ^& I$ S9 n# }* w5 k* c                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
/ U  B! k* P5 P/ A2 a. g  o                   end   
                 if isnan(A(i,j))
( ~. b$ [# A% \                 A(i,j)=inf;
) V2 I5 E* M# `! I  `                 end
         
    end
' r- d& Z7 q4 r3 U0 Y; y: E end


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

5 \2 K# L8 ?& Q8 d9 ]: b) e
function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
. V. @% A. c+ n' ~$ v( M[m,n]=size(d);
L=100*n;
t=t0;
: E  ]4 u  J0 o7 w* [  _pi0=1:n;
min_f=0;
' k* N, O8 j& \8 u* T2 M) g1 |for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
end
$ c; B2 J. D2 K' z+ o1 pmin_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
$ b% `; D1 N! X9 j" u4 uwhile t>tf
for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
) f; R& _8 O2 @6 d$ Bif d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
end
end
f_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
6 y4 ?  e2 H5 C7 ^5 Gend
) E* t& e5 d0 r2 c3 j6 kf_temp=f_temp+d(pi0(n),pi0(1));
6 z2 I) G! b- p# A$ v: y; H$ f4 lif min_f>f_temp
min_f=f_temp;
$ F& L) [/ W0 E; c3 Op_min=pi0;
: D  ]! L: J  U( o1 K) `end
8 n8 k# ]/ s/ v/ Z$ w  m% x' [t=0.87*t;
end
f=min_f;
/ @7 s+ `# H: o9 W8 u' m- z5 q, |T=p_min;
% j3 k' g# }1 ^; F3 D( ]%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
: b2 R& q5 d. E- ^0 g0 x[m,n]=size(d);
clear m;
) u3 b( V* Z* z# Du=rand;
u=u*(n-2);
u=round(u);
$ W! O. g, W) x+ q# y0 W# \' Jif u<2
u=2;
) Z, w2 a  P, L0 N+ q: n2 tend
$ _/ U3 E2 i$ |- `0 Uif u>n-2
, O: q. x& T) o4 V8 J: H$ Ku=n-2;
+ ?, q: B) s' ]( h2 Q. p  ~( m4 L4 pend
v=rand;
v=v*(n-u+1);
$ N: l; R& `( g4 g/ b/ @v=round(v);
if v<1
v=1;
end
2 _5 f4 a7 {, o+ U  Y5 H: u) mv=u+v;
if v>n
v=n;
end
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
! s- e, }5 Y) b& B, Eif u>1
& q4 L9 c$ D: O* A; C6 }0 u* t% Efor k=1:u-1
/ }$ h! u! r, L$ ~9 vpi_1(k)=pi0(k);
% E7 C- N% X. {) `  V, Eend
0 F! G3 l( x$ ]  Vend
if v>(u+1)
4 v. \0 {+ {# w: \5 A& wfor k=1:v-u-1
4 m2 |4 j) K- B0 n; Npi_1(u+k)=pi0(v-k);
end
" @, U# G' X+ Z. wend
( A6 h. d0 c0 l9 oif v<n
: @$ I! g0 G' Jfor k=(v+1):n
9 q( ~1 y& E5 M6 {+ qpi_1(k)=pi0(k);
4 [' p! Z. p- }& R4 J0 O! ~  J4 ]end
end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
6 B: h0 u! [3 `1 R0 |- o" v& kfor k=(u+1):n
) V8 K, t" Z/ x" R6 o0 fd_f=d_f+d(pi0(k),pi0(k-1));
& G- j; ~( q9 \end
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
9 w% i7 Z& P2 R& F- Gd_f=d_f-d(pi0(k-1),pi0(k));
, C8 w) `8 P, s! l# Q; Q: b$ O: W" Rend
else
+ _) P8 L' g* J/ md_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
* |9 q3 _& ~% e+ ?2 K1 F5 Y: d$ Od_f=d_f+d(pi0(k),pi0(k-1));
  C4 i# I2 t; }: d7 N: gend
for k=(u+1):n
0 ^% H  x" {3 D2 K' x2 \* q/ fd_f=d_f-d(pi0(k-1),pi0(k));
end
end
pi_r=pi_1;

& e) I/ x9 t. ?" A& P. b% l得到：
0 I3 `6 P. P1 _% ]8 _  [f,T]=TSPSA(A,0,99)
8 V6 f: \& S3 z( S. ^7 x$ N
f =
9 O& q" U+ e2 r3 w3 {& J$ s, g
   Inf
: d. W: @  d! j! w5 W) ?, h7 E
" g( w0 |( j% m1 M( W% {; y$ z
T =

' j  O: F5 e7 d( T. `# o  Columns 1 through 18
, y' f3 w  S) J$ Y* L) B. D5 j
+ g- F  `& ^- E3 R6 m2 `/ f7 X3 J     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
6 S4 q8 S) k3 O+ G7 c
  Columns 19 through 33
1 w$ ~$ `0 G( Q" x! S
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
) c- M) m5 x& t, y# f3 U7 p# f
: Y6 g$ {9 k8 o: E这个初始，结束温度是自己随便设定的？？
: l4 g+ \/ C2 D+ d- b. P得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点，优化起始点可以随机选取也可根据经验选取.
+ k+ [$ b+ Y+ L" s! Y7 y7 VF是目标最优值,T为最优路线。
( ~% o' k) }2 Z! XF是无穷可能说明所求目标值没有路径到达没有最优解，或者是不是由于哪个步骤出现了什么问题（比如数据，或者邻接矩阵那里等等。。。）导致没有最优解。。。T表示的是最优解的起点到终点的最优路线。。。。。

magic2728

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