用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
# R: a& w+ q  V7 i
A=xlsread('33点矩阵s上三角');
8 u+ C% J1 F; [" d  J* `>> for i=1:33;
       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
$ U% q3 K6 p8 i5 K, {                 if isnan(A(i,j))
4 K& w/ e& B5 L* `# }8 O                 A(i,j)=inf;
                 end
         
! l% X* z) j$ @) c( x    end
end

2 }- p" W0 Y9 p7 ^# a4 L1 H
# B! R7 e4 Q  D4 c 这样A为邻接矩阵了。然后运行百度的代码：
/ I, O9 }* ?: z

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
) s2 M$ t( y- |& ^  A' h9 |% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
2 p" s6 c$ j* e4 j# \+ `. u* iL=100*n;
t=t0;
pi0=1:n;
1 N5 v# V% Y  O: N7 k. Q6 {min_f=0;
for k=1:n-1
8 C1 L) v) t: k5 Y$ H2 bmin_f=min_f+d(pi0(k),pi0(k+1));
end
5 q- I$ s. C8 X7 f6 `% Jmin_f=min_f+d(pi0(n),pi0(1));
; G% `9 _3 G' Qp_min=pi0;
while t>tf
for k=1:L;
kk=rand;
( U9 C2 _# Z, k# n- c[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
& s0 c# y! k2 ?, T, yif d_f<0
% T- N* `- H8 A4 ~8 g8 b1 o( ~pi0=pi_1;
elseif exp(d_f/t)>r_r
: [. s! J* E$ {pi0=pi_1;
else
% }, g9 J" u+ R+ d" V5 r& xpi0=pi0;
end
end
f_temp=0;
for k=1:n-1
% a" W0 ^3 f$ @$ ?f_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
! V- W' G- z- H4 p) @! N6 kif min_f>f_temp
. }$ w  P1 O& n+ I1 Tmin_f=f_temp;
p_min=pi0;
end
t=0.87*t;
end
f=min_f;
5 P7 T/ o1 b* i1 b9 e' g+ o4 eT=p_min;
%aiwa要调用的子程序,用于产生新解
" E9 ^9 U1 G% Gfunction [d_f,pi_r]=exchange_2(pi0,d)
$ F4 S! e* ~7 l[m,n]=size(d);
clear m;
u=rand;
! E# }' d4 c$ N. h4 v. fu=u*(n-2);
7 p' |0 P1 x' ^) [8 S& D' C* Du=round(u);
if u<2
u=2;
end
if u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
, J" N' r9 c+ }" qv=round(v);
6 L; O1 |* m5 E0 H, x, Vif v<1
1 @2 B& A! O: N. r& P$ H( ^v=1;
end
v=u+v;
if v>n
, d8 p$ b1 E& h& q8 \v=n;
end
pi_1(u)=pi0(v);
) O3 k) {( T! k+ N( ]: R/ Hpi_1(v)=pi0(u);
# g! C# M, @3 J% l4 `if u>1
for k=1:u-1
pi_1(k)=pi0(k);
. Y& J" X; X  \% h5 P, k# U$ Send
0 _$ o+ _" C2 y2 t* X) Cend
0 A& X7 u9 G7 e8 O, sif v>(u+1)
/ ~8 ~1 E$ H% o" O! |for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
6 _  l6 ]2 }$ gif v<n
" ?' @* s5 ~$ Y; k; ^1 efor k=(v+1):n
pi_1(k)=pi0(k);
0 a( f: G( L8 }- ]& X, m5 {end
, @- W- W& |" a# X% uend
  @* F( t- x/ l8 G, ud_f=0;
) _( p4 c7 Q& I) R# E/ `$ w: Kif v<n
8 r9 F( n0 m; xd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
* I: A6 Q" V; G) Tfor k=(u+1):n
) r. u& p5 q/ W& id_f=d_f+d(pi0(k),pi0(k-1));
% n$ H! o. `% g% C7 W+ Nend
' q: [' W& X2 k; c3 Id_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
7 |( w, \! s0 C3 V1 c' |3 v1 ~for k=(u+1):n
/ i7 u. N$ d7 H' U( ?d_f=d_f-d(pi0(k-1),pi0(k));
& _# H  k* u. ]' lend
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));
for k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
; Y, E1 C# j- _. G3 j. \end
5 E* P. q8 v0 e. b6 ^# afor k=(u+1):n
' T+ A+ e9 o' S5 A& Cd_f=d_f-d(pi0(k-1),pi0(k));
, b3 u: N" w% @0 x% Cend
end
pi_r=pi_1;

4 K( R2 p. `5 ~3 ?' k得到：
  [f,T]=TSPSA(A,0,99)
1 _! E. B  f  D4 J2 i+ Y
f =
+ j7 n4 g" D4 Y; w$ ?# J
/ {) c" \+ |! ^/ `/ b  L% R   Inf
$ x, F& Y( L8 l

$ x" F0 N- Y0 v9 ^; KT =

& J8 ]6 s  o4 ]0 q  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

0 A+ }9 U3 O7 @, |% K" }4 {" _  Columns 19 through 33
7 ?4 x" P6 Z9 Q' _) g
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

这个初始，结束温度是自己随便设定的？？
- L( w( [1 g& W2 T得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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