用模拟退火求TSP如何？

慢跑20

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

; M' Y6 S  r6 N A=xlsread('33点矩阵s上三角');
>> for i=1:33;
, {% T8 X+ G- p* O: l! W       for j = 1:33
                   if i<j
: K8 l% ]+ K! M* i                 temp(i,j)=A(i,j);
! ^7 R  T' C: |# o; n+ b0 H                 A(j,i)=temp(i,j);
, ~' i" O, S  x0 [9 P, K                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
$ I, x- @% U( G- I' p/ a2 i9 Y( U                 end
         
    end
$ r3 Z7 b! J6 ]/ @4 m& g end

$ s! ?8 e# _; |5 d! s! _- z) E6 B! `
这样A为邻接矩阵了。然后运行百度的代码：
" ?0 b. Z  v" t

function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
3 i$ x2 d5 m3 Z. I% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
0 z+ c4 @$ I4 a2 \( F' o[m,n]=size(d);
L=100*n;
t=t0;
2 l* N* b. |( hpi0=1:n;
min_f=0;
3 x4 H* F9 O1 r  o9 mfor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
end
min_f=min_f+d(pi0(n),pi0(1));
7 x) W( r. B( y2 o8 `p_min=pi0;
while t>tf
for k=1:L;
1 }0 T' o; x+ n- jkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
3 z% S% O7 \+ b+ d; H$ Api0=pi_1;
- y( G: m# ^3 E3 {. F& k$ celseif exp(d_f/t)>r_r
& n6 w6 X6 S7 D. Z6 g0 mpi0=pi_1;
8 J9 S3 f; a$ delse
pi0=pi0;
end
end
5 M7 c; {/ w7 `/ T! |# N- X0 lf_temp=0;
, D2 E  a5 p, y0 t0 x0 Nfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
3 K" m2 b, i4 b  u% Y( gf_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
min_f=f_temp;
. V8 K( b* U. X. H5 M3 tp_min=pi0;
end
! y8 t2 `" L7 \- X1 S6 V7 nt=0.87*t;
end
; l3 t/ c5 v: O0 ], |. L7 Z' {f=min_f;
" b  B+ ~( o- X% l. GT=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
/ q+ b6 Q/ w' t( {[m,n]=size(d);
$ S- s: `+ K. Iclear m;
4 ]$ Z) a0 @% e9 i9 ~- l5 n* Q8 [% X0 mu=rand;
0 {8 [2 S$ F% _7 p6 |u=u*(n-2);
& f9 Y. U8 w6 \- ]. C3 \u=round(u);
if u<2
u=2;
end
if u>n-2
1 V) c: y# _3 v, M/ c- d7 Hu=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
/ U) x" O! r9 Z- P8 m% d1 U- ]7 G6 zif v<1
v=1;
* a& Y' Q( f$ J. a' bend
+ @& P. ~- P( \$ t, u: _) @v=u+v;
5 s! N* {( n5 Pif v>n
. f1 R/ s+ D( \5 z. Pv=n;
end
' z. n+ @2 v2 q- @, f! \pi_1(u)=pi0(v);
/ A& r4 d* y$ g9 e0 w3 Lpi_1(v)=pi0(u);
, {3 G; e" N: `if u>1
for k=1:u-1
2 C* s- N0 R8 g. H7 Api_1(k)=pi0(k);
end
" f  j2 q/ M+ u  Zend
if v>(u+1)
* B1 U2 T& j4 c6 y2 _for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
' K4 l) b/ R( {# {+ send
end
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
end
6 O1 `( `0 Y$ K% X2 |" k! Pend
* i( T# j3 q: ]) O1 @' y# V7 J& kd_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
5 h4 {5 ~" t/ b6 Mend
" @2 U* q. [, F& {0 S( f+ Z% hd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
" K+ S' Q  {+ S. k8 }/ q' {d_f=d_f-d(pi0(k-1),pi0(k));
6 I+ O& \' _$ o, V0 @5 Yend
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));
2 S2 m2 `* w8 @' P& G1 bfor k=(u+1):n
# S9 h' s. A: U: I9 l. bd_f=d_f+d(pi0(k),pi0(k-1));
8 P- b; J4 ?- A% I8 tend
7 K* t) l7 d  d4 Efor k=(u+1):n
8 C+ `- ~$ n% k# K9 ^8 D$ Y9 B0 Pd_f=d_f-d(pi0(k-1),pi0(k));
end
end
+ Z; V/ ]5 S1 lpi_r=pi_1;

得到：
  [f,T]=TSPSA(A,0,99)

f =
8 o" c( q$ Y  z$ M
   Inf
9 k) r$ Z6 H! q0 I! ^% E' O
7 t  o8 C6 u) C$ j' M
T =

  Columns 1 through 18
( C, R/ v0 E4 B" q3 n* [
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18

2 o3 Y6 ^5 G) g" ~  Columns 19 through 33
6 {5 t2 T/ J, |7 C
0 i; _  P- J1 T' H( N    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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