用模拟退火求TSP如何？

慢跑20

一直EXCEL中为33个点之间，任意两个点之间的距离（没有数字的是无穷）。 求经过所有点之间的最短路线问题，。
( V; D8 ?7 Q1 ^- {$ b( \  ]+ A
# E: Y: b1 l8 ^5 y A=xlsread('33点矩阵s上三角');
>> for i=1:33;
% X) j/ u; W. ^8 J( y       for j = 1:33
                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
% |  g- Q8 Q# [. `/ W7 A                 if isnan(A(i,j))
                 A(i,j)=inf;
5 `7 `5 ~% l* S+ a                 end
- U; ]4 @# d, c' f         
    end
: e; d$ {$ ]8 L1 n+ ~& B6 M4 D end

/ i  q- B- ^1 H. {4 O
这样A为邻接矩阵了。然后运行百度的代码：


function [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
" H/ V( m- @# R6 F( g[m,n]=size(d);
L=100*n;
5 ]8 F+ M3 e' `8 k2 E$ ^6 `t=t0;
pi0=1:n;
min_f=0;
1 G* B% T# H. c2 ?& P, Cfor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
2 @( g* g0 J. C& v1 Cend
0 ]  J/ ?1 m/ R/ o- Fmin_f=min_f+d(pi0(n),pi0(1));
2 C2 d( U8 i8 ^p_min=pi0;
while t>tf
; s- ^; F6 n' mfor k=1:L;
kk=rand;
' q7 i6 e8 N4 @# w" @) V# L[d_f,pi_1]=exchange_2(pi0,d);
4 \: F; F* s* m& U1 Qr_r=rand;
# X) U0 r# a) E4 ]7 i9 }' yif d_f<0
7 D- `" @1 g/ Fpi0=pi_1;
+ t: @& O  f! yelseif exp(d_f/t)>r_r
pi0=pi_1;
else
pi0=pi0;
end
, \. I; V1 i  Aend
f_temp=0;
2 Z/ s/ e/ O/ i+ V3 kfor k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
f_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
min_f=f_temp;
p_min=pi0;
! l5 |" Q' n  f! s5 w0 |+ Cend
6 T" z" r0 R2 b. x$ N% yt=0.87*t;
6 U# d3 W3 J* X  Nend
+ p+ b3 `/ O8 rf=min_f;
T=p_min;
# ]% C% E! x/ b# E%aiwa要调用的子程序,用于产生新解
6 T2 \1 _6 L8 {" s, Kfunction [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
& S0 Q/ P+ u+ \2 i1 N) f, A4 Xclear m;
* @9 m. a' f2 V( e0 [u=rand;
! H/ [4 O  H: _  F" zu=u*(n-2);
% |( f$ e$ K* v2 R5 ju=round(u);
if u<2
9 Q- ?- I1 h! p# ^2 f# s0 cu=2;
end
- P& N1 ?0 f  J5 x( b" j) Aif u>n-2
u=n-2;
9 i8 K! W3 f4 C& A0 b9 e% ?3 n+ X9 jend
v=rand;
0 {3 z8 v! h. T2 e9 Ov=v*(n-u+1);
v=round(v);
if v<1
; o/ y9 _! g. o2 x" h$ Vv=1;
$ [) y4 x2 K: p* L- Q* ~- kend
# }: e8 S3 A& @! yv=u+v;
if v>n
v=n;
end
! t0 `% W+ R/ F) t) d7 zpi_1(u)=pi0(v);
pi_1(v)=pi0(u);
0 }, @7 u0 {- [  A( gif u>1
for k=1:u-1
+ ]' h# h; D$ ?- gpi_1(k)=pi0(k);
end
end
if v>(u+1)
for k=1:v-u-1
pi_1(u+k)=pi0(v-k);
end
end
" |5 e0 Z+ e- b- [8 ~8 ~$ ]7 hif v<n
for k=(v+1):n
% O) x% S( f- V% H' Cpi_1(k)=pi0(k);
' F; }4 F! s0 t" a6 d& }) m* A; Send
end
: ^* c  A0 a# K9 H3 R9 ^4 {d_f=0;
if v<n
9 W2 g5 M! ?! [0 C9 S  j5 P& b- gd_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
for k=(u+1):n
6 y  i  Z  R, M5 A1 o* j8 ~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));
9 I" e! [3 {$ i/ F* Dfor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
$ X6 Y( ]( W) a- A. N4 t) a  r% P, zend
else
" B9 ~& M+ A5 A/ Cd_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
4 \# V, D" h* u4 x* v% G; z$ m  F, xd_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));
end
4 x' c2 p2 N- [end
pi_r=pi_1;
/ [5 p; ?3 E4 |
得到：
  [f,T]=TSPSA(A,0,99)
5 {) c& M# [1 h' z- x
2 Z/ s* \, `, \3 qf =

   Inf


. M6 j) Q" q: F1 T& |2 |T =
. D$ V  W  v: N  |7 g! p/ E
  Columns 1 through 18
8 H3 `- t/ z7 y8 c/ n6 m
     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
* d$ y4 `- a; [( l2 `9 T. b" g
  Columns 19 through 33

    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

这个初始，结束温度是自己随便设定的？？
# O* Z  t* o- ?& w得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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