用模拟退火求TSP如何？

慢跑20

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

: ?* u7 g3 d: }/ m$ { A=xlsread('33点矩阵s上三角');
: Q0 U' T' \# I1 G, x>> for i=1:33;
       for j = 1:33
                   if i<j
* u- h9 u, k1 x9 }8 B1 b3 B                 temp(i,j)=A(i,j);
& l+ W/ o' c8 S9 q                 A(j,i)=temp(i,j);
! r4 W; C9 ]$ D  J+ \" x                   end   
+ }+ ~4 s$ W( c. N3 z% G                 if isnan(A(i,j))
7 O  ]7 P# s  a# Y# v% }) ?                 A(i,j)=inf;
                 end
) ~7 K9 z9 F" W; J# Y7 y         
    end
$ X6 e- {) x0 c" @. Z end

+ o. `' l$ i/ e. E
. k& i  \3 ^3 o5 l8 _+ j6 } 这样A为邻接矩阵了。然后运行百度的代码：

& e3 h% u& R2 k- H2 A2 U; ?3 [; m
1 _: `& t/ g, Nfunction [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
; p; @3 J- s% n& [/ ]# e% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
* W- T6 }0 U( n, v" iL=100*n;
6 \/ |2 f/ h2 m. Y; at=t0;
pi0=1:n;
min_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
  f3 B* c) r% b" X, [& \: zwhile t>tf
) J  Y# r! U) G9 efor k=1:L;
; H* r1 d) \- N- Ykk=rand;
* }( C7 ^3 [" O- n[d_f,pi_1]=exchange_2(pi0,d);
% _2 d1 ~% w9 S$ W; w- ?  i0 zr_r=rand;
$ r5 @" e! t& r8 dif d_f<0
* ?8 F; ]4 m0 ~0 k: wpi0=pi_1;
elseif exp(d_f/t)>r_r
7 K: g% w- p9 M) J. M2 fpi0=pi_1;
else
pi0=pi0;
3 M1 ^. a' g# h! K( \end
end
f_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
6 ?# _5 B2 t' S: b% Q! \/ w( [' j/ `f_temp=f_temp+d(pi0(n),pi0(1));
7 T8 i, n+ o: Y2 tif min_f>f_temp
min_f=f_temp;
! M0 r4 W4 H6 mp_min=pi0;
" N5 R- r& }2 h$ `end
t=0.87*t;
7 c& h- }2 M" J$ j5 ^* Hend
* \7 [; ^% D2 {& y7 a" W7 Lf=min_f;
T=p_min;
0 |* u* l6 l' d7 p$ W* S%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
# i% c1 j4 R; M9 A; [clear m;
! W8 a, m/ G/ xu=rand;
u=u*(n-2);
/ g9 j- t/ w! T3 |9 Y) ]* `5 Su=round(u);
if u<2
u=2;
end
7 Y5 F5 K  F9 }0 pif u>n-2
u=n-2;
( H. P' I$ `$ G9 C# ~7 @2 m5 `end
v=rand;
5 e6 D2 h  E8 s! Zv=v*(n-u+1);
. q$ O4 |- S0 i9 U$ J3 _v=round(v);
if v<1
6 [" |% p+ {5 G! V$ c/ vv=1;
end
v=u+v;
if v>n
9 E+ _* ^/ m% Wv=n;
; q) {* \  a3 }4 D. Tend
* Y+ o2 n1 B5 |pi_1(u)=pi0(v);
7 k% h( r2 Y! d0 W' }9 \* k( tpi_1(v)=pi0(u);
if u>1
for k=1:u-1
pi_1(k)=pi0(k);
end
: K" U, j/ u0 @4 n+ J4 t0 p: H4 tend
if v>(u+1)
) _( @( y9 }( e8 h2 i  W4 vfor k=1:v-u-1
' @( T  {* J3 c2 Api_1(u+k)=pi0(v-k);
end
end
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
end
) Y! F# n8 }8 K# M! N/ B9 ?end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
! n/ ~5 N6 O7 t3 f! T3 a* k' c. Mfor k=(u+1):n
- L: C3 Z6 \/ Q) Jd_f=d_f+d(pi0(k),pi0(k-1));
4 e* o7 q& b  mend
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
9 [; Q3 l0 K, P& X# bfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
else
4 Z4 O  B# Z* i0 U1 q; e/ P: ^/ bd_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
. _: O3 }+ I3 }d_f=d_f+d(pi0(k),pi0(k-1));
end
for k=(u+1):n
+ ^" T; Q, F5 R" ?- W; Cd_f=d_f-d(pi0(k-1),pi0(k));
- q6 s# O* \  |- @: n4 B4 ~end
- O" w# T) c7 Z& k2 `* ]5 Wend
pi_r=pi_1;
/ u/ |; z: W, R. h0 v: _
5 i, I, K- @  ]% ?* b, r得到：
5 b# ^$ P8 u7 ^& x( q1 l% b  [f,T]=TSPSA(A,0,99)
6 ^3 X/ c- q3 H9 G
: G+ k. z1 X8 P+ W# Y. }5 q( yf =

7 V% `: Y( s' ~. V  S   Inf
) T5 o8 H: r+ B* R: E. m, |

5 j6 `# [0 x( P4 D, t$ [% nT =
! L; B* A: [# z6 l$ b  u* Z
- y! v" {- W- W; |+ B, a8 u/ _+ _  Columns 1 through 18
# J) i1 q* W% c5 v2 p8 l0 o
  O2 d7 n  M/ o2 W8 j     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

  Columns 19 through 33
4 n( C- w" ?$ g9 _7 ?
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

这个初始，结束温度是自己随便设定的？？
: u$ t. a5 O2 V! A* _) t" K2 E得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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