用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
1 k; @6 x$ U5 v% J
A=xlsread('33点矩阵s上三角');
>> for i=1:33;
; f; D5 C4 f. A- s: Y       for j = 1:33
6 G+ [% v6 I% @3 r; q1 B9 x: |+ I                   if i<j
. z- `3 Q8 N) O& F                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
5 ]; E$ ^/ ~$ Z! |                   end   
( ^, S6 |% q% k- Q                 if isnan(A(i,j))
1 F5 A& S$ G) f; [                 A(i,j)=inf;
. b* ~. Z) p* D* h1 C; _9 x9 t                 end
3 W' y+ e8 j0 f! \5 z1 I         
    end
6 {2 b6 }0 [5 f5 S3 U end
+ L( v! k+ ]0 N; P' ]" @5 [

6 f# g: y* C6 n 这样A为邻接矩阵了。然后运行百度的代码：
' T3 Y- `' \/ D

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
7 `6 y. d' |/ T" _6 m1 q8 J% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
: Z  ^; v9 m0 x3 J9 k1 P! H[m,n]=size(d);
L=100*n;
t=t0;
) d- `! i6 i  ^pi0=1:n;
1 `5 x2 a4 s. K9 Ymin_f=0;
for k=1:n-1
, h, \' J0 C" N& zmin_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(n),pi0(1));
' c+ y1 J( y1 i% mp_min=pi0;
while t>tf
9 r3 \: N5 A* V9 l; X* Y2 efor k=1:L;
/ [; i& `1 _" X: p% e5 K- Pkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
0 i) {* Q2 {3 c- X& G' r0 _6 Nr_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
3 s2 V7 }# F5 ]. Zpi0=pi0;
! Q3 G* E5 s" L: {! ^  l- Hend
end
f_temp=0;
4 m% l  a- ?% gfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
+ f, u/ G0 ?: q  `f_temp=f_temp+d(pi0(n),pi0(1));
# G. @% q# Y4 d! T: D0 A# \! tif min_f>f_temp
min_f=f_temp;
p_min=pi0;
end
t=0.87*t;
& m/ W* |( d- ^6 H9 `# K% o4 Send
/ _+ w* |+ H" {& B: N9 df=min_f;
2 F! o. R" ~8 R9 O- W/ c# K- q- aT=p_min;
& Y2 t; ]- Q' K& e%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
" X" U( r5 A0 a  f2 @* l# dclear m;
. g- V7 n# W, v6 V( [u=rand;
u=u*(n-2);
u=round(u);
) J# ~5 u! Y) `5 r; ]( S8 Z6 Qif u<2
/ y5 y$ K: `- H: T2 Du=2;
1 z! r: ?; T8 P  K6 F9 Dend
if u>n-2
; r( W% t3 A. B) Wu=n-2;
end
v=rand;
0 X" A) u1 s4 c, @  A3 G6 U4 zv=v*(n-u+1);
v=round(v);
if v<1
, w" q7 |# {4 B! v- e3 I0 H6 B" hv=1;
end
+ s9 {# R/ ~! p4 C% u1 v9 z5 dv=u+v;
if v>n
v=n;
( s3 V5 B; u: r( t1 w9 s/ p1 fend
: W7 |9 n) O" e$ ?  [+ Dpi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
2 m. \; m6 M' \% v6 Y3 o" `for k=1:u-1
5 r: s8 }/ N- Z) `+ G0 }pi_1(k)=pi0(k);
. L# Y# t- N+ \; Send
& J% ~, J" n2 z# o- yend
if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
  Q5 U0 f# W; a" Oend
end
if v<n
9 N' P# G2 m8 x2 efor k=(v+1):n
pi_1(k)=pi0(k);
% j( B& }7 Z* [4 \2 M& h6 X* _/ c% cend
3 O) Y4 E5 l& G# B+ Gend
- V3 Y# [: c. c- q, u( n6 [" S% Qd_f=0;
if v<n
, m4 O% W7 `% |* Od_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
" c2 @% M1 k0 p" Sfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
. k+ d+ C' ]' E' A: g! B  _* Jd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
* M3 q& T2 y, x" Q; A+ t6 y' Hfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
5 z- A5 ?% K& ^end
" v8 ]6 G/ Y" i& J, `, Felse
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
1 I5 R2 ]0 c' Q* zd_f=d_f-d(pi0(k-1),pi0(k));
end
end
pi_r=pi_1;
  `/ ^& X" _3 g* l$ o; o
得到：
! S8 X3 y7 z5 m& }: ?  [f,T]=TSPSA(A,0,99)
( c& b9 J  y, ]  ?3 ]/ F& _
3 x# m' E0 R& N; q! H$ @7 [f =

5 }; g# `% d9 T! D# J3 }# X7 W" _   Inf
  x- q# }  U. z2 X; T8 ]* y3 i

T =

  Columns 1 through 18

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

  Columns 19 through 33

    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
' i4 i% N) U3 ?2 \; }1 r
这个初始，结束温度是自己随便设定的？？
$ y, W# K4 N  m) e" U. u得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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