用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
  g4 U4 z' f' ?
1 r7 R7 j+ p( p7 A% n' i A=xlsread('33点矩阵s上三角');
8 u% k  E. E3 `$ @/ _6 p. u: G>> for i=1:33;
       for j = 1:33
                   if i<j
9 P8 m! |: V7 @+ S5 ?8 n7 C; \9 G                 temp(i,j)=A(i,j);
) ?# c7 y; m8 U% C  Z4 m5 b                 A(j,i)=temp(i,j);
0 U- g* R* l2 B& n8 E2 |                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
) o% j+ e: A" ~' w* }$ M                 end
         
    end
: ?( e# \, q/ B6 U" ~* e end


7 F: \. K" a6 B- }% t/ Q0 Q 这样A为邻接矩阵了。然后运行百度的代码：


function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
3 l9 R" L' b  Z# K, s1 [# `0 Y% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
  a& G; B; T$ @, a[m,n]=size(d);
1 q3 N' F2 b* NL=100*n;
; N! W4 L+ ?# |t=t0;
pi0=1:n;
min_f=0;
8 u0 W. V: o% P4 d, ~for k=1:n-1
/ J; |. d$ o0 W# fmin_f=min_f+d(pi0(k),pi0(k+1));
end
2 H7 \( G, G# lmin_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
/ W3 B* n, g6 jwhile t>tf
( w4 D4 O( t# @0 L% ]1 Efor k=1:L;
9 U  w/ J5 T! p; skk=rand;
5 Z7 ]& t5 p) |  B% E. Z0 L[d_f,pi_1]=exchange_2(pi0,d);
9 E* M0 l: K+ d, u( H6 O( x% I  @r_r=rand;
" a( b3 V# E: z/ F' e) ?" ?if d_f<0
2 T; A, ?; ^0 q8 ~' Upi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
end
( Y: D: e/ E, u5 }end
f_temp=0;
for k=1:n-1
5 }$ O) u+ ]9 E. r- J2 {" Rf_temp=f_temp+d(pi0(k),pi0(k+1));
3 {  T0 W, D% }- x" w% }end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
min_f=f_temp;
* x, l' L6 X) H* x# op_min=pi0;
end
t=0.87*t;
end
; }/ l8 a: W) I, hf=min_f;
T=p_min;
' j- ]* R" M& A/ p0 f1 O: Y%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
: ^- Y; I/ f- x[m,n]=size(d);
# I: v" ?) |6 e4 t* uclear m;
u=rand;
+ F' `. p, v) r0 U4 X  x" i- j( W5 pu=u*(n-2);
u=round(u);
if u<2
' |8 \" b8 F3 b4 S3 B7 f5 Xu=2;
end
if u>n-2
u=n-2;
end
v=rand;
v=v*(n-u+1);
v=round(v);
if v<1
+ N# j* P0 R- W2 Tv=1;
end
v=u+v;
7 Y' I8 h: O) k1 N  B5 B: Fif v>n
v=n;
end
pi_1(u)=pi0(v);
1 i) Y3 O; k" J  w+ spi_1(v)=pi0(u);
if u>1
for k=1:u-1
# }) o7 l' J/ S4 B  t$ Epi_1(k)=pi0(k);
end
; R# d8 E7 B- ?4 qend
8 i- t! y: E+ Z. y6 H' ~if v>(u+1)
for k=1:v-u-1
3 S5 b2 Q* l2 m7 n" Lpi_1(u+k)=pi0(v-k);
' Y% o. y' G& O/ t2 mend
end
if v<n
for k=(v+1):n
pi_1(k)=pi0(k);
, C( S0 v3 [* w5 Pend
end
3 ]( F/ D5 W4 S9 U$ f5 ud_f=0;
if v<n
4 M2 Q& X5 c- Q, G4 }# i" yd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
1 ?; N( p4 H" D4 P1 [# l! Hfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
: @3 R! N: I0 b+ X& ?7 Hend
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
# z8 R7 S" \  X9 k" q+ @# u$ ~end
3 Q* f/ ^  F4 n" H+ `* T: ?1 b! |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));
) A; J8 h* A1 U# L- sfor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
7 a' L5 K% Q/ c# |) z% Gend
$ ?2 j1 q, D; n7 h% x% d1 H8 vfor k=(u+1):n
! {: h  ]( R+ }# f  y$ sd_f=d_f-d(pi0(k-1),pi0(k));
end
end
5 Q) t3 S' S! D8 m- c" u" \" C5 g5 _pi_r=pi_1;

- J. o5 i8 M8 q3 R" l4 K3 u* r得到：
6 z7 Q% T8 W- G  [f,T]=TSPSA(A,0,99)
3 t: I" S/ w# N9 Y
f =
9 \7 Q9 J! o% Z" H- J5 y0 b
: g; y: g9 w& z& R+ j4 Y   Inf

6 d  n1 R: x! z
$ A3 m) _2 c! [0 wT =

4 g0 I, t$ _1 u( P  Columns 1 through 18

     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
8 X: ^3 S, C, {& J8 i1 J% Q
  Columns 19 through 33
" ?9 W0 k8 u% P% B' M
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
/ a& Y5 N2 _/ `
( `2 t+ S" ~9 l* C$ u  M; S这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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