用模拟退火求TSP如何？

慢跑20

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

, q/ }( t* e6 s3 j6 V; E/ }; x A=xlsread('33点矩阵s上三角');
: b. T& s9 P2 b* Z5 `1 t>> for i=1:33;
       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
1 \; w1 S. f/ ]& p                 A(j,i)=temp(i,j);
                   end   
, M2 n/ }! u4 r! H+ X                 if isnan(A(i,j))
                 A(i,j)=inf;
* T9 Z  K  g5 [+ B! f+ @' I                 end
2 m9 n8 a9 P/ P: q0 o+ w% \         
    end
end
) M5 U5 q; ?; z  Y) G
6 i7 j0 N7 E( a: A5 Q$ e  D
这样A为邻接矩阵了。然后运行百度的代码：
. q% H5 a  K8 E' M% ]

function [f,T]=TSPSA(d,t0,tf)
( y' b* s+ j  {9 R9 I%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
L=100*n;
% ^2 A4 }, N& n& w% n, B7 E, k% j% Ot=t0;
pi0=1:n;
0 j# X, _8 o$ i' b+ k7 rmin_f=0;
for k=1:n-1
$ C/ d6 w2 X  dmin_f=min_f+d(pi0(k),pi0(k+1));
) r1 {; X9 z7 ~) l0 g! uend
min_f=min_f+d(pi0(n),pi0(1));
$ q9 U( A1 b2 ~9 A; Pp_min=pi0;
while t>tf
/ [; g4 a  M1 l) a7 t- f! ^for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
if d_f<0
5 o4 j( o! m5 Dpi0=pi_1;
elseif exp(d_f/t)>r_r
+ v& P" z6 \! f" n( g6 e& n/ zpi0=pi_1;
else
( Z9 n; z6 c. \) api0=pi0;
end
9 B4 g$ `. y  ]! L. Send
8 k" {& V5 M. G' e4 f+ h' x! Hf_temp=0;
3 Q1 m5 R& }, u. Z3 Afor k=1:n-1
9 a8 y2 Z8 h# t( M4 ]; Ef_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
% K8 C' Y, N. I/ M2 k/ {9 }min_f=f_temp;
) J8 q1 d' z3 Q" a9 Up_min=pi0;
0 f4 O$ j5 P# l6 X6 _end
t=0.87*t;
end
f=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
% T2 y- }; h' W' @0 ^: S1 r8 ?function [d_f,pi_r]=exchange_2(pi0,d)
$ r7 \8 _2 P- v' V( P[m,n]=size(d);
clear m;
, [! X' p! m- s  B! p/ Cu=rand;
3 e, _' v9 N8 tu=u*(n-2);
' L+ P8 a, X) g& u% Ku=round(u);
if u<2
3 S% a$ S, {; G" {* [; l5 su=2;
end
/ [+ w! M. \  R4 P' bif u>n-2
u=n-2;
& z& g7 X- Y& r) B8 P0 Send
v=rand;
v=v*(n-u+1);
v=round(v);
; x* S8 }; _+ Tif v<1
4 o0 P, J1 M. S, ^$ @v=1;
end
v=u+v;
if v>n
+ E, d3 ^8 t$ @* w% p1 [, Y8 Rv=n;
end
pi_1(u)=pi0(v);
. q8 f" O( n" r/ E# F. z6 I9 |/ `pi_1(v)=pi0(u);
if u>1
4 ^/ }, p# j4 r+ `4 |' D$ W4 Yfor k=1:u-1
pi_1(k)=pi0(k);
end
' Y1 a7 y# p# [+ p5 V1 Lend
if v>(u+1)
) h$ r, p. D+ p, g$ y! N1 {0 Q7 afor k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
if v<n
$ I9 [0 c( d7 [6 R+ v5 d+ zfor k=(v+1):n
5 l0 \0 v9 ?6 api_1(k)=pi0(k);
end
1 R; S$ P+ j! F, i# n6 ?  _end
d_f=0;
! }( u' L+ e) Mif 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));
! _& h* M+ _' F" ^; Dend
d_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
3 P3 l3 ?2 g8 Dfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
5 a& M' N8 }' U" B4 [$ w! Bend
  H( P+ B3 E9 gelse
" v6 @$ |9 U5 W8 ^1 W* ^- cd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
, H$ ?& @. X# d8 N6 c8 y6 efor k=(u+1):n
d_f=d_f+d(pi0(k),pi0(k-1));
! U* s# E; U# @! P; x9 W  l0 h4 _end
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
+ \- Z. o3 |/ k( e4 M! ]- }end
end
' ~+ r3 k0 y6 ]pi_r=pi_1;
' `5 o4 R. X! R# Y( g; |
* k  `2 e4 q  Y) K% P$ @' p得到：
  [f,T]=TSPSA(A,0,99)
0 [# q' R# [# W$ c2 \
f =

9 ]- N, B& r3 L) D+ t' w7 V9 h   Inf

- ?/ W0 T$ o1 V, }: D1 \+ `
T =

& L9 d, l( n; L0 Y) k  Columns 1 through 18

7 w/ v6 n. L; V5 w$ `7 ]; B$ q     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
9 X. u& x5 G# B7 d9 ~" a; a
  Columns 19 through 33
, b3 l9 v0 |! b& E
4 v( p! Q# t2 q% M) N) g, K0 ?3 n' D* t# k    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
! _9 |+ H3 y$ I) @# t5 [
4 G: b% z8 D& D8 y' m# v# o这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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