用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
8 _& Z4 z0 e3 K- O) _: @9 x
A=xlsread('33点矩阵s上三角');
9 T* V7 G/ S8 `5 f6 s>> for i=1:33;
( [3 G3 `! |* @; p: {: b& Q       for j = 1:33
. n" L( \5 u# U# E7 D) J: \3 X                   if i<j
6 k1 H8 h6 m( V8 L7 Z                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
5 [2 _) U; K  g' i, K                   end   
; |4 G; S  ^! U6 G' v# [0 l. E0 Z( p                 if isnan(A(i,j))
                 A(i,j)=inf;
/ K1 ]. ^1 {2 Y3 e7 Q- X                 end
         
% e4 |- @  @/ q7 c, n% K8 F/ S/ \    end
end
* m2 ?) _% S8 _4 @5 s
1 @! g9 R' v% ?+ W3 F. Z
- \# T3 h) v& |1 N! d& o 这样A为邻接矩阵了。然后运行百度的代码：
* ?0 L1 X# m7 I
* _/ o- C6 q* z, \" h
+ d$ x! ]7 Q8 {, C9 g# yfunction [f,T]=TSPSA(d,t0,tf)
0 B0 i3 g9 q" }& ?$ k3 ^& Y: o( W%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
t=t0;
8 V6 {/ s- _) n. F+ N$ U+ G2 j# hpi0=1:n;
- m/ S- ?# w* I( t! Zmin_f=0;
for k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
; D: h2 C7 o: p  @4 m! {end
6 r2 b+ @4 p8 n4 ^  H- g* gmin_f=min_f+d(pi0(n),pi0(1));
. Q4 u5 N: U! v4 @p_min=pi0;
" \6 e1 G; V" K' U& o. Mwhile t>tf
. Z% k' H8 P& @3 U6 Cfor k=1:L;
4 D. N9 R( M9 s! S6 z: Akk=rand;
; }/ e& ?  S- l: H+ r[d_f,pi_1]=exchange_2(pi0,d);
+ j7 D: {% M5 V" j8 G! }r_r=rand;
! L- R3 X5 j1 t1 sif d_f<0
0 f  C& {( K/ D$ \pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
end
end
f_temp=0;
% N( q5 w) |2 h  Lfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
6 m0 o- C% {1 D4 t( u3 }end
$ R5 a8 `7 B) U" |. _7 n% A, }, ff_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
+ ^3 y, Y( F' R5 N7 T8 j& Mmin_f=f_temp;
# e7 P8 J  m7 d, q+ Cp_min=pi0;
3 G3 A4 n: t+ t. V% Zend
* }! R. n  e5 S- x6 m# b/ ^t=0.87*t;
end
8 O* T+ ?* [! R+ j9 af=min_f;
  ^3 H8 |& \, r7 o, ~! ?& kT=p_min;
! J' ~, N9 U# b* Q5 e0 D%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
1 B8 S; c: l- {1 H5 G[m,n]=size(d);
& F/ _4 A! y8 Tclear m;
u=rand;
0 l6 m  A% {; a0 qu=u*(n-2);
u=round(u);
if u<2
8 n- N( Z2 ~5 f7 `" R; hu=2;
& S0 J* ?# E# T$ oend
if u>n-2
u=n-2;
' h. l* S, Z: d# R5 n" i0 z/ Kend
4 R% J  H0 Q1 Y& o* V, Qv=rand;
v=v*(n-u+1);
9 q4 f3 f  b% u4 H& ?9 X: pv=round(v);
2 W& w, a" S# r7 a, \# H/ Pif v<1
0 Y. r- }& I2 g' B4 F6 M2 a- p. U0 Wv=1;
end
8 x$ J* B. w% I' W4 Sv=u+v;
# O8 k& g( Y# x+ X: D  r4 z. a1 Pif v>n
v=n;
. M7 H: w: f% f7 cend
pi_1(u)=pi0(v);
4 u3 b8 _' O( Xpi_1(v)=pi0(u);
# \0 n) p; p( |3 W: Q" R) sif u>1
for k=1:u-1
pi_1(k)=pi0(k);
- w0 Y' ^. N& s; d4 u( |' }end
end
if v>(u+1)
) E6 @- d1 i- K! o) L0 i5 I4 afor k=1:v-u-1
- ^9 u& X+ e9 b) ?1 npi_1(u+k)=pi0(v-k);
% U9 j* W1 s* g) send
; r! O7 T2 ?5 O1 N4 e: Z* |( cend
7 G. }3 [. e: gif v<n
for k=(v+1):n
% w$ c2 ?# n& c. _7 {, G4 Opi_1(k)=pi0(k);
end
9 [' G; Z4 Q0 C( D6 Hend
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
$ \/ |5 k% T4 a2 k$ E' R5 yd_f=d_f+d(pi0(k),pi0(k-1));
; q8 u: i- v! rend
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
! ?& ~  E; V- X3 v! O1 \9 q' p; \+ [for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
end
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));
end
for k=(u+1):n
) P7 X: H9 \$ hd_f=d_f-d(pi0(k-1),pi0(k));
# ~! u3 r4 z& O4 Oend
/ v  e- b! h$ W' C, D- y2 {9 o8 v; |end
. s! Y" Z+ q- F" h% R( ppi_r=pi_1;

) k# p% V  Q5 a6 u$ Y得到：
  [f,T]=TSPSA(A,0,99)
: P- O5 S: x4 I# e
( e' }+ Y: h7 e8 Q& |: l+ q. m& Gf =

   Inf


T =

  Columns 1 through 18

9 B# b& ^3 G$ I     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

+ |9 M# W9 ~$ e* T, d  Columns 19 through 33

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

: Y- O7 L8 O  @  }7 a. d# a0 n, D4 M这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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