用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
, m% Z0 _1 c6 Q  }- F6 V
6 x' M8 j: S* j) T, V& A A=xlsread('33点矩阵s上三角');
>> for i=1:33;
       for j = 1:33
                   if i<j
" j  R+ G: c6 _/ }% v: J5 r                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
                 if isnan(A(i,j))
# o) W; A" h" X% N* n* c+ E                 A(i,j)=inf;
                 end
" o( f" ?. m1 ?- X; V         
    end
4 O4 _6 `0 z& X end


- \+ }3 D) o; o7 g5 k+ T6 k 这样A为邻接矩阵了。然后运行百度的代码：


function [f,T]=TSPSA(d,t0,tf)
1 V& N6 ]! w! w3 M%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
* S7 d2 O/ M& d2 Q$ d9 s  z4 j8 {% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
+ a- w1 a, q% K' V( K# R7 Q2 St=t0;
5 m/ v( m9 i7 |& k: Xpi0=1:n;
0 H4 u  A! C% |+ \; hmin_f=0;
1 }5 p  r: |& ^0 m" g8 @6 L7 `) n' rfor k=1:n-1
- P7 C5 o, Y( c+ }# p* ymin_f=min_f+d(pi0(k),pi0(k+1));
: C0 P% i; k! [end
min_f=min_f+d(pi0(n),pi0(1));
0 Z) A$ }$ h. |6 G# N1 f( _p_min=pi0;
7 n/ _% U& t9 R8 t. mwhile t>tf
for k=1:L;
kk=rand;
# G+ _; d0 P& I# m  `[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
3 A4 S8 Y6 |4 |7 S  n- f$ \else
pi0=pi0;
! c3 j4 b* {. N, D4 Qend
  U) T9 f# l: T9 ~end
( x5 N; b+ u; {f_temp=0;
8 x5 O3 a1 a& wfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
1 @, ]0 s* M/ {4 uend
' c: t9 B1 j9 O2 P% C3 B0 ]f_temp=f_temp+d(pi0(n),pi0(1));
) K' K- f4 t1 ]  P2 H; Y; \( {if min_f>f_temp
min_f=f_temp;
p_min=pi0;
5 V, Z, ~# l: O( u( d$ Send
) o8 ]9 |3 ^3 r+ y0 t+ e$ ut=0.87*t;
9 n- D3 m* g  Y) R( I) {end
6 u6 x: h( \" s. |$ H0 Qf=min_f;
" j$ K" z% D! h7 {- x# g' T: ^* fT=p_min;
8 F* i( |4 Y% B/ B%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
) d/ c4 x+ W+ N/ w" w  v  @; c! O[m,n]=size(d);
$ I( i7 r' T: L5 O1 jclear m;
9 I" O* B) F2 m5 B4 A6 Qu=rand;
  \1 ?& [; X4 T( Du=u*(n-2);
/ \# i: f- S0 f% R: du=round(u);
if u<2
u=2;
end
if u>n-2
3 L; R. }( O! }, w5 x3 Uu=n-2;
8 j. F% ], B0 c- d& L8 f# @5 M$ Uend
; J5 ^- G5 K/ `4 ?0 `v=rand;
v=v*(n-u+1);
v=round(v);
9 m: b# t' c; D8 vif v<1
v=1;
end
, F3 J# @" s: Z1 N* t; mv=u+v;
, l5 W0 d8 F- T+ |if v>n
7 _9 V) a% l8 ]1 q0 }v=n;
end
; I3 a; r0 d  B/ Api_1(u)=pi0(v);
pi_1(v)=pi0(u);
# p" U" s9 w! n1 qif u>1
+ ^: \$ v1 {9 R+ c9 ?$ Wfor k=1:u-1
pi_1(k)=pi0(k);
end
) M/ d! \3 i  U2 A3 bend
if v>(u+1)
/ F% o  _: L0 f9 ]& Ofor k=1:v-u-1
1 d# M, Q6 f% x2 ^pi_1(u+k)=pi0(v-k);
end
end
if v<n
% a: J$ l) n) Z$ H0 }5 n7 dfor k=(v+1):n
; p9 ?  a" [6 v0 _0 P; b( o1 B+ npi_1(k)=pi0(k);
end
" \0 P$ E1 m1 Z; Fend
  I% e" \. w( |/ \$ cd_f=0;
if v<n
$ F: h/ ^! }4 \" Qd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
# J* L. ]4 c. v6 C# Vfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
. T1 V; C- i! I8 c1 G; L$ g1 Iend
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
( `8 `; v9 k- L$ @, M) c3 Bfor k=(u+1):n
+ T8 z9 I) r. Y! r- j+ R$ \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));
4 r9 `) ~8 N$ Y" }0 D. kend
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
3 W- |; y5 W7 B. ?( Mend
* a# x- K6 t; m3 d" c/ Tend
pi_r=pi_1;

得到：
+ L- a7 l/ x  {  [f,T]=TSPSA(A,0,99)
+ Y/ T  X: O0 B: e, d! i( K
& L& \/ X. n* lf =
# k1 x( n- f% R$ G0 \# d
   Inf

: z* K$ U+ E5 r( f4 `9 b9 p( w
T =

  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
. ~$ y4 j( X' H
) u) {3 O+ Z$ |6 J  Columns 19 through 33
5 p& b7 b+ L" C% L  {/ d
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
, F/ M4 f$ I3 N- R1 {9 _/ B
7 E- X4 I) M$ H. ^  k8 a* u) P这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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