用模拟退火求TSP如何？

慢跑20

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

A=xlsread('33点矩阵s上三角');
>> for i=1:33;
       for j = 1:33
; |0 m9 G+ s: z# ?                   if i<j
0 ^/ g, D# }) I- j" t( Z6 m                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
                 if isnan(A(i,j))
                 A(i,j)=inf;
                 end
$ ]" N* J; G- P: \& ?( e& j         
" u5 ~0 o; G& v, W9 E    end
end
" c7 Z2 X% y, E4 k, e0 v6 q' T
+ V5 t* C( R/ s- [, \# D6 l
这样A为邻接矩阵了。然后运行百度的代码：
. f' [: f8 ?2 M8 p
) \3 F( F% t  ^. R! I
function [f,T]=TSPSA(d,t0,tf)
+ D( ~  J# P! ?%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
$ k. r0 b, B+ C3 }& y$ a7 z% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
( T" D  B/ q* g1 F( A) C[m,n]=size(d);
9 _0 x/ H+ t, K" n" U) W  PL=100*n;
' x  Q6 Y9 n* n0 p- @& At=t0;
pi0=1:n;
% @3 E7 L/ c! o2 v- z5 Bmin_f=0;
for k=1:n-1
: m, ?8 w9 ^! E) `% ~5 m  Zmin_f=min_f+d(pi0(k),pi0(k+1));
( U) c6 \8 M( e# t6 Pend
- v! v* J0 O; x% `9 _! S; pmin_f=min_f+d(pi0(n),pi0(1));
7 R$ s! [" x  Y  Z( Xp_min=pi0;
0 i' o/ E; ?6 D9 ]while t>tf
) k, K% p$ w/ E- b3 o; h- ^for k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
6 @5 H/ A3 G( W8 }0 X8 Z6 mr_r=rand;
% f* B3 ?$ `/ X3 [* @: {5 d) v# ^if d_f<0
pi0=pi_1;
elseif exp(d_f/t)>r_r
$ q( z: q+ ~' _# O, \7 |pi0=pi_1;
' P; z& R2 d1 y" yelse
- |0 ]& M. J5 `1 d4 Cpi0=pi0;
end
end
: @4 t! h' r' u" Z2 Af_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
end
& D! S% i* o( \" `5 zf_temp=f_temp+d(pi0(n),pi0(1));
if min_f>f_temp
% v6 f6 o) w5 l) W, p2 p- ]4 Q+ ?min_f=f_temp;
p_min=pi0;
end
, _5 Y7 b9 y  p& vt=0.87*t;
end
f=min_f;
T=p_min;
%aiwa要调用的子程序,用于产生新解
3 i/ H9 H1 I8 E( ^1 Bfunction [d_f,pi_r]=exchange_2(pi0,d)
: I' D/ W6 K, ^( ]- a( O+ T4 l[m,n]=size(d);
clear m;
u=rand;
u=u*(n-2);
' m6 C- S& F0 Y: i. a" H& }u=round(u);
; `& q1 L1 x4 K2 b$ v. ^if u<2
u=2;
end
if u>n-2
. ?/ ~1 Q  I6 X9 Cu=n-2;
" S$ N5 D# G; i6 Send
( R% |9 K; X, O; G1 H. ?v=rand;
v=v*(n-u+1);
4 R! k5 l7 ?; c. A5 mv=round(v);
if v<1
v=1;
end
* K5 F1 P* Z2 ev=u+v;
+ [) W/ Q5 J* `  Wif v>n
v=n;
end
pi_1(u)=pi0(v);
pi_1(v)=pi0(u);
if u>1
for k=1:u-1
pi_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
: Z3 M$ ]* s; i, F& i' Y0 pif v<n
& l- Y# {' {: q5 zfor k=(v+1):n
pi_1(k)=pi0(k);
6 [) l6 C+ o3 I  s6 p5 Rend
# m! ^3 ~8 Y( }$ e( V4 dend
: S, D" P2 W: e$ `" @7 sd_f=0;
$ E3 g8 P6 f& q$ V! A0 qif 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));
( z  F3 f0 F% j; o, N8 fend
; f( l7 j2 M5 {( td_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
+ ~" ]# C: m3 u9 N% Afor k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
% l& X& b% X4 ]1 n: ]! b( Cend
' T1 P, Y  S) Q3 V$ B1 X0 Aelse
d_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
% p! k& k/ X+ Y0 `& T) qd_f=d_f+d(pi0(k),pi0(k-1));
* c5 X! L3 t' J6 b, N- G0 |end
for k=(u+1):n
d_f=d_f-d(pi0(k-1),pi0(k));
/ s* K% T; u6 N8 t6 x! fend
+ d0 q6 G5 i/ j' y0 uend
. l. v% @# X' Rpi_r=pi_1;
# T2 @% a* M0 |7 ?( M8 U2 I
得到：
: N1 N: W( D7 q8 N! `8 Z/ J  [f,T]=TSPSA(A,0,99)

f =
! y7 h" ?  b7 ^7 R$ A3 b
! m, ?0 @4 _* Z' y   Inf

3 J. }0 h0 Z4 L8 d
T =

  Columns 1 through 18

# S+ l2 ]8 {; {4 ~     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
1 L) F/ N* D8 X% G
& W8 s  |* R0 ]' W0 ]( ~  Columns 19 through 33
8 d7 {3 |; Z* u8 Q. x3 a
8 P' Q1 {5 j' t' B    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

  F) _- |: E% N" Q; P/ w这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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