用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
, E2 C0 l) p2 q, ^, b
% d' n5 f! [, {% R1 U/ F$ ~1 {* P A=xlsread('33点矩阵s上三角');
0 E2 o* ^7 `& z  E: t# k>> for i=1:33;
       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
8 c% v4 T3 \4 |0 }" W+ g' o7 |9 x                 if isnan(A(i,j))
                 A(i,j)=inf;
2 |" b9 W- L- I; o: o& @! h                 end
         
    end
+ _6 ]6 x1 Y4 n0 Z! N end
) A& f) v1 P' K0 v/ c3 u1 ?. C
- \2 h* F1 g5 t' x2 t
这样A为邻接矩阵了。然后运行百度的代码：

# h$ b4 m. K: X  Q" L( W
function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
( k: w# Z! I% y* u. f% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
- o& |  N+ X& N3 Z; s; KL=100*n;
! p5 L1 U1 K8 O0 N: lt=t0;
pi0=1:n;
min_f=0;
; Z9 f! M- r* nfor 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 b1 B; H; {" q- e+ Q2 Bp_min=pi0;
7 C1 ~% |" m  t. m' J( Y7 Rwhile t>tf
for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
# B. N' K5 Q3 ^7 w' k; zr_r=rand;
  ^% ?* A' w8 X) Aif d_f<0
pi0=pi_1;
* y/ e3 E# z# q3 }" gelseif exp(d_f/t)>r_r
5 Z9 x0 C) S: `, U7 D: o6 tpi0=pi_1;
1 h: v' `' A9 {) }" r# n# V: Q; }/ Nelse
pi0=pi0;
end
6 M( b: M% K* S6 R5 `end
+ H' R# v4 `) Lf_temp=0;
$ D) x# z2 j2 m3 Dfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
! d- g5 S' N3 q4 lf_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
3 v* o' E2 e& l  I1 T! Cmin_f=f_temp;
p_min=pi0;
1 A5 @  p& v7 }' F3 g( eend
: T4 k) @, p0 l6 `, Et=0.87*t;
end
f=min_f;
+ d' K* C9 H8 pT=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
8 P- Q/ M/ u# P! M. }* k9 ?1 J. I[m,n]=size(d);
clear m;
u=rand;
" j8 o- z! k, C. y5 @u=u*(n-2);
' A2 u# T! L" {# N1 _u=round(u);
5 m. p( A3 d% v: f" d# Eif u<2
u=2;
" Z$ N: d4 I: o/ X, r/ f& D5 zend
if u>n-2
3 y( }3 e; v! n. \u=n-2;
" j0 [4 W- ^* L* r0 A! rend
v=rand;
+ E- |( W8 M: }3 O& R4 q; \$ B2 S  _v=v*(n-u+1);
1 H+ D( i9 _1 h# o' ]3 Hv=round(v);
  f& O2 j3 d1 u4 F# [9 Wif v<1
v=1;
end
v=u+v;
if v>n
8 p7 N; I- p8 G9 u  Gv=n;
end
( ]* V5 [9 E% }/ u0 A& K5 `pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
% D. g  [" u1 ^3 d4 wif u>1
for k=1:u-1
pi_1(k)=pi0(k);
end
end
if v>(u+1)
for k=1:v-u-1
- p) p9 P- J- hpi_1(u+k)=pi0(v-k);
end
end
) c2 t, j8 T; e6 b6 _" zif v<n
  t4 \* v/ x. u  E0 f* N1 Dfor k=(v+1):n
pi_1(k)=pi0(k);
end
# u  p, H7 ^* Z0 |2 T* h- Aend
8 d0 _. z4 i/ i) q9 _6 rd_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
( ^9 @5 [( A: V5 i( Hfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
end
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
7 D# T& T/ s/ E; ~( f/ gfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
: k% T6 l0 ]& [# v: x! w# Xend
, R( e- ~$ v) [% uelse
& |- D% X5 v$ N3 td_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
d_f=d_f-d(pi0(k-1),pi0(k));
) o' f/ m( j0 L5 `# b7 Y7 rend
end
  R5 v$ r$ \% P, C! spi_r=pi_1;
+ ?  ?' M4 `! M( T7 h
! X' u* S+ f/ P得到：
. R  T, l& |* T2 M  [f,T]=TSPSA(A,0,99)

f =
, x; q! _! _2 @* J7 u% ], z
' D- h  W" g- l1 Z" v5 h8 \   Inf
  L, U& ?) @; O  ~  ~; X
0 ?* s4 }3 o6 w& e/ Q
T =
7 X+ d  n+ E& \  I5 J0 R4 F9 F( r
  Columns 1 through 18

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

2 }! o; S; Z5 y9 B1 j& l' T  z5 P  Columns 19 through 33

    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
; _5 G" B/ [- u8 B! v2 ~# C# ]! s
这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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