用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
$ N, g" r  c8 J
$ w/ j5 r1 Y: {; c7 R# H" S$ ~0 V5 W4 U A=xlsread('33点矩阵s上三角');
>> for i=1:33;
+ |: O) [- X6 n5 J       for j = 1:33
                   if i<j
  ?2 }7 f3 V: D( P                 temp(i,j)=A(i,j);
; w; q7 q( ~4 z& c$ {                 A(j,i)=temp(i,j);
                   end   
. b8 n5 w8 }/ i) g                 if isnan(A(i,j))
4 M- x7 S" ?! [5 O                 A(i,j)=inf;
& U& _2 Y  p1 m                 end
# [7 A3 T( W4 {# U         
4 g/ H# J& H9 {* ~2 [: |9 t# e    end
end


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

9 `! H) w8 ]7 m& v6 Z# O
function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
: x  D. K7 P8 t2 X7 w$ n0 D% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
% {2 ~# P0 d& j( u1 F9 `* m- z: F* {+ L* |L=100*n;
* w- F! y$ b) q& u8 ?t=t0;
pi0=1:n;
min_f=0;
. T% ^6 ^4 Q& m  jfor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
2 f# Q  _% `, `/ Oend
min_f=min_f+d(pi0(n),pi0(1));
0 i" F6 K8 P& s* u/ Kp_min=pi0;
: S* F, b9 \1 j9 jwhile t>tf
for k=1:L;
/ b9 \( n$ f9 @0 M3 g5 ckk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
6 ~" o! i- C9 r+ B1 j4 k+ Tr_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
$ j8 u" k- ?; spi0=pi_1;
1 r8 M! q5 b3 |: X" }" F4 Kelse
9 X$ B6 I" c" i: X8 k5 bpi0=pi0;
end
6 X' ?- h5 m, [/ D3 ^2 d3 v% X; bend
1 L, W8 y; ]- P1 p9 jf_temp=0;
' }  g7 t) y( W- `; t/ G& U  Bfor k=1:n-1
, t$ G7 \! X. s; i- G) Z9 U) Tf_temp=f_temp+d(pi0(k),pi0(k+1));
+ q9 T: h3 R+ o6 _1 x" n/ ?end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
# V$ S" Y2 }0 }min_f=f_temp;
p_min=pi0;
, e( d% `4 J- _) }end
t=0.87*t;
end
7 e* _6 u0 T7 n7 U) W, ~/ D% |f=min_f;
8 W7 F; O! S. E/ X2 @6 JT=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
) H  G; w* b$ U. y3 t! _# k[m,n]=size(d);
6 s. x) Y' u- D0 Q9 ^" vclear m;
; B5 F; r" Y9 eu=rand;
u=u*(n-2);
) r* L4 v; r) K7 _# m/ _6 m* ?u=round(u);
# W+ v3 d5 _* A& y8 T, iif u<2
4 g* U: {& O  f6 Vu=2;
4 L! E% A/ ]; a3 j: B$ g9 Z. lend
5 Q' Z1 u% |3 A- Y! U3 d) ]if u>n-2
- k- s6 w. `( r8 @$ w7 au=n-2;
end
9 [3 ]: m  D. s& ^: ov=rand;
v=v*(n-u+1);
, L! A: G7 S2 G3 _8 nv=round(v);
if v<1
v=1;
end
) A5 d* f: Z  ~2 C# mv=u+v;
if v>n
  X1 G" R2 q# Jv=n;
) e, o5 U8 \9 X2 r& z- i8 }7 O$ R' bend
& \* Z3 a% H! o" P5 P" p9 tpi_1(u)=pi0(v);
% b) N" H8 r" L, Vpi_1(v)=pi0(u);
if u>1
for k=1:u-1
% S" V, y( s4 Q3 F/ g0 Upi_1(k)=pi0(k);
+ W" _' x; q9 t2 Jend
4 ?& r7 M6 ]# W9 Send
if v>(u+1)
( g* a, u+ e  z  e  h; Xfor k=1:v-u-1
* t: l) Q* W; z) H. Z+ ~; @: epi_1(u+k)=pi0(v-k);
end
end
* n) i9 H+ s4 \5 p! t! \9 S! O) Bif v<n
for k=(v+1):n
0 R( c4 J+ R! ?2 Wpi_1(k)=pi0(k);
  |& P2 K6 w2 u4 ~  ]3 b; c. C6 Yend
& s( V' V5 I' Send
* m4 C5 b- |, G* i& b7 X) cd_f=0;
if v<n
& f# M! \" h. n- q6 _d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
6 K. A  d7 N$ e$ Y" a4 hfor k=(u+1):n
! a- f" N$ }' j: G4 md_f=d_f+d(pi0(k),pi0(k-1));
4 @: f# b% P" g) S. S' uend
* c: a2 Q! }, ?2 ^d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
# j5 i0 q( o' I0 ofor k=(u+1):n
, O$ Z3 w; |& Id_f=d_f-d(pi0(k-1),pi0(k));
end
( A  k7 r7 |# j/ b7 Kelse
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
  C. O* t; Q% r3 Gfor k=(u+1):n
3 q; z# z6 u; e& [8 _; Md_f=d_f+d(pi0(k),pi0(k-1));
end
) n( \& M/ D! B. h# mfor k=(u+1):n
. f2 p5 S* ^1 p+ G. |4 Sd_f=d_f-d(pi0(k-1),pi0(k));
end
" h/ ]9 {$ _7 V$ f; I; dend
pi_r=pi_1;

$ l8 y/ s7 ~1 a6 `# G得到：
  [f,T]=TSPSA(A,0,99)

f =
9 l& f* R+ N' \3 I9 v7 O
$ g+ Y7 O# _; Y$ B   Inf
/ X4 o- H% n2 M% D8 b4 s
$ L  i' B, p6 F% P" M- x
* T- r8 G" y) I6 _T =
6 H) X* I( S! A. ]/ h, ^9 [6 E2 ]
7 O- _7 Q1 }9 y8 {! y  Columns 1 through 18
* y4 s7 q  F% J, F- C
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
2 c$ m7 B$ i# q" `  e1 t/ L7 K
6 e; M9 ]  T! ]0 v3 A  Columns 19 through 33

    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

这个初始，结束温度是自己随便设定的？？
1 B8 S% ]! P$ ]/ f) K6 V5 \得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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