用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
/ B" L/ x/ ^0 e/ Z! g; {
A=xlsread('33点矩阵s上三角');
>> for i=1:33;
       for j = 1:33
7 V8 |9 s6 ], W4 U2 F( I                   if i<j
                 temp(i,j)=A(i,j);
& d  b9 M6 ~3 e  R5 ?                 A(j,i)=temp(i,j);
                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
9 G/ }4 r/ P- X$ m' h                 end
         
    end
end
& x; T! x0 _2 t0 @/ _* S5 F
, v2 n* [% G, e' o( F: \7 Y
这样A为邻接矩阵了。然后运行百度的代码：


3 b! z* m% j) m+ ]function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
[m,n]=size(d);
2 K2 v' j5 p2 h+ s, RL=100*n;
# s! A4 q9 \) q' ^8 ~) V& p" W, k$ xt=t0;
9 y2 A8 h; z9 c- `+ r& O0 tpi0=1:n;
min_f=0;
+ Z* u6 A6 m/ @9 @* ^' Ufor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
& V. y4 i* t% l1 Bend
* j- |1 Q1 b" Omin_f=min_f+d(pi0(n),pi0(1));
5 ?1 |5 e2 d+ J" y9 K" p7 I4 }( xp_min=pi0;
1 f4 y1 T, ~6 ^, dwhile t>tf
1 ]7 {  A  \# m# O9 }0 x; {1 }for k=1:L;
9 c, q9 D! k# [! ~! ~* Pkk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
r_r=rand;
7 ?% K7 K) A9 H( R  o6 Kif d_f<0
! q& ?1 e* W8 R% e% b% w: Ppi0=pi_1;
elseif exp(d_f/t)>r_r
pi0=pi_1;
else
* J4 _7 E( s% o) bpi0=pi0;
end
" L! k* B+ V% ~end
2 @7 h; @( J) b+ ^4 t1 s% B8 nf_temp=0;
for k=1:n-1
' P/ s$ h* h1 d4 Xf_temp=f_temp+d(pi0(k),pi0(k+1));
& J3 L, L) q" v" yend
) v3 r  ^+ E! G+ Af_temp=f_temp+d(pi0(n),pi0(1));
, ], M# Z* J$ B; u# y* @if min_f>f_temp
min_f=f_temp;
p_min=pi0;
0 B" n4 b4 D  f  x$ Vend
t=0.87*t;
end
f=min_f;
" U$ e/ a2 _( X5 L# A$ f. V( {; gT=p_min;
%aiwa要调用的子程序,用于产生新解
function [d_f,pi_r]=exchange_2(pi0,d)
* Y  S% U, E( G; ]$ D: N8 d[m,n]=size(d);
& \1 R- n6 _. t; k: ^clear m;
: f0 @. ~( Z8 L: o  v8 ku=rand;
u=u*(n-2);
' A6 g# q' b- g! Mu=round(u);
if u<2
u=2;
end
if u>n-2
0 P; W' b9 t2 ^; |5 e' Ju=n-2;
7 t, D! y' _" R" q; ?" a- [, Nend
2 J9 u6 }2 c9 G6 B$ [v=rand;
! R  \/ ^5 D; sv=v*(n-u+1);
6 S  @% T- b& N6 E8 dv=round(v);
if v<1
v=1;
9 |: D% Y' E3 _) a% x8 hend
) q- }5 W7 M4 W8 {, x& Qv=u+v;
if v>n
v=n;
end
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
for k=1:u-1
; f8 |: G9 V* n% {# npi_1(k)=pi0(k);
% E" @' }* t/ p! q1 X8 Rend
end
* @; j1 u6 {' B/ T" d; Xif v>(u+1)
- V# M( O7 S3 X$ E* ]for k=1:v-u-1
! P! s# ^0 l2 \3 l8 Y3 i' api_1(u+k)=pi0(v-k);
end
end
+ J; H# @0 Q4 H2 q) F7 hif v<n
# x6 [- D' }' g5 M# Vfor k=(v+1):n
, u: L. z. Z6 ~pi_1(k)=pi0(k);
end
end
d_f=0;
if v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
) o0 k! ~2 M5 o+ ifor k=(u+1):n
/ Z1 H0 p, R; L' r5 [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));
for k=(u+1):n
% t$ d* S/ V8 k8 C2 i2 ^6 }d_f=d_f-d(pi0(k-1),pi0(k));
0 ^+ W+ ^; }- Y$ @  O1 Q6 |1 J3 dend
else
1 `( _9 C3 e, N8 M4 W8 hd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
* Z0 t% z; P% Z$ i1 ~" Qfor k=(u+1):n
" |2 K. y( [! q; ?9 sd_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));
7 i! t  }3 }0 ]. R$ W  v. s' S; c9 lend
end
7 d3 x: P6 }  ?$ y0 x) Z# {pi_r=pi_1;

得到：
2 q$ _  m8 P: m8 J, v  [f,T]=TSPSA(A,0,99)

5 Q/ ]2 d; \" z. D" _' C- {f =
' E- m. O2 _: |5 h) |
   Inf
. [) \' C  `( V2 E) @+ B3 R
# j% e1 c6 O5 S
! G  B1 L# K* y2 x* g& uT =

  Columns 1 through 18

; m9 k% G, o) ]2 r- T3 \1 X- u     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
5 k) ?* f& N' f0 v8 a# _: U
$ s! P% Z/ l6 K5 K( j8 G6 F' W  Columns 19 through 33

4 ~% ^5 U7 r* q1 ?; v0 n5 L9 m    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33
3 |7 K4 f3 R2 k! a. m: ^) g5 }
- [6 M# U2 e4 z1 P9 c2 P1 Q  q这个初始，结束温度是自己随便设定的？？
: m; H  |; F2 Y, h( r% s6 b8 P得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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