用模拟退火求TSP如何？

慢跑20

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

A=xlsread('33点矩阵s上三角');
% J' o  ^. z) ]& t" m6 `# |' F: [>> for i=1:33;
       for j = 1:33
1 u/ v, l0 H: R, v" j  L# f                   if i<j
                 temp(i,j)=A(i,j);
0 J$ G9 A3 \6 J6 }                 A(j,i)=temp(i,j);
" {& r$ [9 j* k; g8 l2 P                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
# m3 b# M9 e* C5 P         
    end
' X7 X: n, P( g/ h3 J end


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

+ Z+ m" y- S1 V/ N( P+ `9 w  g
* V' X4 h3 U# d* L" gfunction [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
t=t0;
pi0=1:n;
min_f=0;
for k=1:n-1
; F: `- F3 K7 g8 }min_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
while t>tf
- ]+ d: n2 n- H. V0 ~for k=1:L;
6 v* a/ R$ O2 c: l# H. [kk=rand;
; W6 r* Z7 H3 D/ g3 s% C[d_f,pi_1]=exchange_2(pi0,d);
# C' o6 L8 g# R# F! A# y7 pr_r=rand;
if d_f<0
pi0=pi_1;
) S8 I6 c; l& I$ }1 {  Pelseif exp(d_f/t)>r_r
pi0=pi_1;
else
/ z; n) M/ Z, F6 A  Bpi0=pi0;
; G0 Q# {$ h3 Y; send
8 P- s) W! ?' ]% {/ |6 j$ Nend
f_temp=0;
for k=1:n-1
1 F/ Y8 `: u8 s/ z, o' A7 Jf_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
0 I$ V; a+ ^5 e9 }if min_f>f_temp
min_f=f_temp;
p_min=pi0;
end
t=0.87*t;
, h$ d+ `& O9 }% nend
3 o: r, c! r5 ef=min_f;
2 W% @' V1 H$ n+ r1 w% Z. W: P7 xT=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
; ?! k% r* X6 D3 O  K# A9 gclear m;
u=rand;
& n& B- Y# }& j' G) ju=u*(n-2);
# a, U+ h7 s8 b/ g' n7 gu=round(u);
if u<2
u=2;
8 d$ U' c( n' u* ~end
; ?9 S) ^9 N; @, @: ~% Jif u>n-2
u=n-2;
end
4 s* c7 c5 E6 ov=rand;
9 Z  h. r3 L) B( x7 t$ Dv=v*(n-u+1);
v=round(v);
if v<1
v=1;
end
3 B% |, n# X( ^+ y/ i) \" nv=u+v;
3 l7 ?2 F( p  q4 a3 f& lif v>n
, w6 w/ \4 j1 U) H# e1 b; j7 uv=n;
9 R$ ?4 e2 `9 R) D$ G! {9 h% `end
pi_1(u)=pi0(v);
/ x; J) E. c% ^: J6 v, W/ J5 L& @+ S& i) Ypi_1(v)=pi0(u);
! A- {* _( Q( [) @if u>1
7 k7 |  w" e" wfor k=1:u-1
) `% u6 l' s, o9 H9 ~) U* y5 {$ upi_1(k)=pi0(k);
end
9 @8 T/ R: O8 d  @  Y( u; uend
6 [* |6 t) `: F1 A5 f5 m0 Xif v>(u+1)
for k=1:v-u-1
- E  B2 K1 W6 D5 L: ], ]" Lpi_1(u+k)=pi0(v-k);
  |% S, O3 B( E% ~( ~: x) X4 Bend
; d/ L+ b2 l0 B" J- i1 \end
if v<n
for k=(v+1):n
& W+ ]( c  I+ p- f) D, W3 gpi_1(k)=pi0(k);
$ M/ S; a9 B/ q. gend
7 b- t. I/ R' K2 D4 r, Hend
. R4 r9 `# u4 E2 t8 Cd_f=0;
* u- s- _* ^) j" g, Qif v<n
* U* |, x$ ]% Z" A; H( C5 td_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
# U! f7 \" q4 M  n* t1 Xd_f=d_f+d(pi0(k),pi0(k-1));
end
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
0 K; ?2 |) b, ]& `; Xfor k=(u+1):n
3 k: w- Y3 C  I5 X! Id_f=d_f-d(pi0(k-1),pi0(k));
end
5 H' P, R5 \. r& y; Melse
( U% n) f+ J$ ^6 J5 a; G& nd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
, g, ?5 y$ |, B, p9 yfor k=(u+1):n
. A, a8 A4 n0 C% a& @. B0 h6 p/ Wd_f=d_f+d(pi0(k),pi0(k-1));
( H  W2 [6 Q5 N! Z7 t; Send
- p( L. A  b, q( X  P3 lfor k=(u+1):n
* t. ~4 p5 ~+ V3 k0 nd_f=d_f-d(pi0(k-1),pi0(k));
. c& d' e) g& _: c8 L! e* Nend
end
% ]6 z; }) C1 z3 i7 ]3 y; Lpi_r=pi_1;
1 L* g+ b. d$ E' |' F" @: h* _
/ ?: u9 N7 q- w2 L# j& c得到：
) }/ }$ a7 i% [' ]: A  [f,T]=TSPSA(A,0,99)

f =
5 V" \6 ?2 y$ ~& A( w
4 Q% ^( d% a/ o) c   Inf
$ k* N1 i6 w9 a) [; k$ \! G
2 M! O; s! z( j0 A, x* Z. a& Y
T =
4 S7 C3 `/ D* A8 \1 _3 b
  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
( ~1 B. q' W) @1 A7 U) T& W
. S" z' H7 ^# g7 _/ i1 N  Columns 19 through 33

9 l! {+ b7 J4 j; i7 j- Q    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
6 w% d1 W' S3 W1 L
这个初始，结束温度是自己随便设定的？？
" I# s# i( m: I0 Q% s; r$ W! Z" F得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

在利用模拟退火算法进行优化之前，必须首先选取一个优化的起始点，优化起始点可以随机选取也可根据经验选取.
$ P/ Y+ E% m0 e- U; Z. h" ]4 OF是目标最优值,T为最优路线。
% z9 Y% n( }4 D8 g* s6 b7 \) SF是无穷可能说明所求目标值没有路径到达没有最优解，或者是不是由于哪个步骤出现了什么问题（比如数据，或者邻接矩阵那里等等。。。）导致没有最优解。。。T表示的是最优解的起点到终点的最优路线。。。。。

magic2728

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