用模拟退火求TSP如何？

慢跑20

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

) n: E8 [) N; ? A=xlsread('33点矩阵s上三角');
* ~1 R+ s3 D/ R3 a/ b>> for i=1:33;
# J$ A, U8 D$ E; I& y       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
% z7 n" `+ K" r! x* J                 end
         
' _6 N9 Z- \; \8 O: N    end
end


) Z; q6 o7 k# K 这样A为邻接矩阵了。然后运行百度的代码：
9 h( y7 L9 {* {2 \+ N

6 L# g+ s6 f1 Z! G: y8 Ofunction [f,T]=TSPSA(d,t0,tf)
- T: b0 e1 b1 h$ `  k%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
t=t0;
pi0=1:n;
min_f=0;
" U# z7 Q. m! A; xfor k=1:n-1
% n1 y- i8 s2 u( B  [0 \min_f=min_f+d(pi0(k),pi0(k+1));
end
6 I/ P) b* n  Z6 nmin_f=min_f+d(pi0(n),pi0(1));
; X$ g$ `1 K8 A4 k/ Q* yp_min=pi0;
while t>tf
3 a! \- A4 _: L6 Q1 \5 }8 d2 sfor k=1:L;
kk=rand;
4 a0 M% f6 x. p$ {+ G) f  a% S[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
/ W# Z7 t- Q; A. `3 J0 }8 c' {if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
* p( B& G! e8 F* Y' lpi0=pi_1;
* P' y/ Q( P! S$ ielse
7 D" _: J6 N7 Q" t5 k' Tpi0=pi0;
' f8 i0 l; e6 _8 t$ D2 eend
end
f_temp=0;
3 \9 y* a9 _" ?% jfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
4 o9 o9 }# e5 K0 }# Jf_temp=f_temp+d(pi0(n),pi0(1));
3 q2 C2 ?  v1 I- F" T+ |6 eif min_f>f_temp
min_f=f_temp;
p_min=pi0;
! d, B/ Y( z' N3 z# F2 N1 vend
t=0.87*t;
9 S- Y' Y: p2 }* K5 A4 rend
f=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
7 f/ e9 U5 o+ d$ O$ e% X% |clear m;
u=rand;
u=u*(n-2);
) b& ?, k- v2 e2 T) p+ Ju=round(u);
if u<2
u=2;
* }& Z. _: J: A( R0 Hend
6 @, {+ a( r+ |$ {( rif u>n-2
6 a/ I) E0 H# ?+ H6 Q" ]7 w" j. }u=n-2;
( u  l& m2 J! ~9 {% T% Z" i7 N. Kend
: c  r+ e- _: A# Av=rand;
v=v*(n-u+1);
9 T9 d8 z: n) M- q& ~( gv=round(v);
4 b+ T1 J; {' z9 H! Nif v<1
v=1;
! z- t& c: t* I/ z; R; X5 Mend
1 {4 S) h1 a, D' uv=u+v;
if v>n
v=n;
end
+ f' D6 J; G. |- S* opi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
) @; j0 n8 Q' O0 Ufor k=1:u-1
% Y, ]5 d9 g2 l- gpi_1(k)=pi0(k);
+ u5 S4 L  F5 h0 K6 ~end
end
3 r  `6 Z+ M  K8 h- R+ v! Iif v>(u+1)
1 ]/ [# o) s* A  d6 M# ?% Qfor k=1:v-u-1
: {& [; I( L: ~4 }8 }# c5 ipi_1(u+k)=pi0(v-k);
end
" G: F  y& q& m" c6 F3 Pend
* U/ d# D* P5 h% q5 u" C: Uif v<n
9 S5 ]% w1 d7 ofor k=(v+1):n
4 Q: l% b: x* H3 N$ mpi_1(k)=pi0(k);
: m) H9 U9 g5 e) xend
end
. _0 a' |2 s; u6 H% k9 c1 i8 id_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
2 z  g7 }/ o, a0 `- S8 f1 efor k=(u+1):n
, J6 ]& y1 {2 W' wd_f=d_f+d(pi0(k),pi0(k-1));
end
, U+ P0 @* f5 X/ N  a$ f9 r2 B' Wd_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));
$ h+ s  \) g1 L6 @/ o$ g- V. F4 J2 Send
else
- c7 v/ \  ?+ {4 C% ~& e$ _& ud_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
2 a; j6 V+ v& R3 L- O' g/ d5 B/ g0 Ofor k=(u+1):n
/ f# T  g. b7 b$ j0 ~d_f=d_f+d(pi0(k),pi0(k-1));
end
for k=(u+1):n
# M: _4 K: O( dd_f=d_f-d(pi0(k-1),pi0(k));
! x" J* l0 I5 p( o( O3 Vend
9 \' z0 T+ j: B8 y" L+ v2 Oend
pi_r=pi_1;

3 Z: y# K, f3 J& h% t得到：
2 f) N$ h& G2 `) _  [f,T]=TSPSA(A,0,99)
8 y- N9 a; u3 A
! h. n& x7 K$ w- P8 K6 L/ ef =
% V3 V, N, S0 U5 h7 ~
   Inf
. U8 y. m' V1 G

3 A4 c4 D3 P, z: zT =

) M, P% B& p/ x/ H$ x4 }; g: K  Columns 1 through 18

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

1 a  U$ u% t; Q: {& p  Columns 19 through 33
+ n+ F( j; @( L3 H# J% E- u
$ M" Q+ K  q# i9 Y( f# P. l    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

; U1 ?! ?5 _4 N) }( ~" {这个初始，结束温度是自己随便设定的？？
" ]$ ]  s) Q% U2 @. ]4 {5 d得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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