用模拟退火求TSP如何？

慢跑20

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

A=xlsread('33点矩阵s上三角');
>> for i=1:33;
1 B6 B$ L8 q2 V: ~, ]: d1 W       for j = 1:33
" k( }9 ?% r6 G! a  E2 ^                   if i<j
                 temp(i,j)=A(i,j);
                 A(j,i)=temp(i,j);
                   end   
- s( V8 m- m: e( l1 \" O  b                 if isnan(A(i,j))
, c* B$ g- |' U; q0 Z  [: W                 A(i,j)=inf;
( g' F0 s1 `7 s! L                 end
, c5 P  o* q- y% j. Z; G* \, v         
    end
end
2 o# T! L2 O. ?# V* f3 F
- I2 a. a2 @" d1 n2 s* q' h# r5 S
这样A为邻接矩阵了。然后运行百度的代码：

* @: i* A3 X' \  ]) ?& G. K% w* Q5 m  G
2 J: T0 D. B3 P) o8 wfunction [f,T]=TSPSA(d,t0,tf)
%TSP问题（货郎担问题，旅行商问题）的模拟退火算法通用malab源程序
1 K( b; g0 p5 M% f目标最优值,T最优路线,d距离矩阵,t0初始温度,tf结束温度
4 W2 `( C2 `0 u6 f[m,n]=size(d);
L=100*n;
8 ?- f, {) T. @( vt=t0;
" }/ @7 r' g* x  a- Rpi0=1:n;
3 v# `8 \* m# `min_f=0;
% R2 _$ k4 G0 w; f$ B( B% a7 Ufor k=1:n-1
min_f=min_f+d(pi0(k),pi0(k+1));
- W+ {9 M7 D& {  K, vend
' ?. {0 }: m9 @) ]min_f=min_f+d(pi0(n),pi0(1));
p_min=pi0;
, N* e; g% x, _8 ^while t>tf
1 [; w$ ?/ m+ J7 Y. D0 zfor k=1:L;
kk=rand;
[d_f,pi_1]=exchange_2(pi0,d);
. V7 [7 z  O& q1 H% s$ nr_r=rand;
) g4 R. r# V8 Y+ T2 K* P6 ]# Oif d_f<0
pi0=pi_1;
) w$ Z+ |" o% f6 f* T& gelseif exp(d_f/t)>r_r
) A/ V6 j1 t7 A6 O) e7 e, e2 epi0=pi_1;
else
pi0=pi0;
/ n3 l+ A6 x; Q7 f+ c  ]end
# w7 S& U/ K2 A" K' i5 |5 tend
& k& B' n5 a& P; k+ G8 |( J$ Hf_temp=0;
for k=1:n-1
f_temp=f_temp+d(pi0(k),pi0(k+1));
9 T9 [4 W7 g4 V/ Mend
f_temp=f_temp+d(pi0(n),pi0(1));
( m1 r& p1 Q: G2 yif min_f>f_temp
  w' {% [6 u* pmin_f=f_temp;
' m& _% d! G* X; r- Q, W6 |p_min=pi0;
: D  W& F6 x. }) t3 pend
1 e) I) ^& ?- o& Y& jt=0.87*t;
end
# a; Z3 K! O* ~) L8 V" [f=min_f;
# `; Y) n6 p. C/ Q2 [" i6 BT=p_min;
* v& I* Y( i- i* {2 ~+ d3 l# T%aiwa要调用的子程序,用于产生新解
3 y& i4 V4 m1 u: H" L- T4 mfunction [d_f,pi_r]=exchange_2(pi0,d)
[m,n]=size(d);
; R; z3 ~- B5 V2 r  ]9 Eclear m;
u=rand;
u=u*(n-2);
: r6 r) N6 ^$ U3 ]) p6 [u=round(u);
if u<2
0 a+ y) `' z* u9 P7 K  M4 C0 Eu=2;
! w' A- G8 h/ c, J8 [& zend
if u>n-2
u=n-2;
end
8 w( n; H7 i7 Z+ A! v% T" l0 K% |( {v=rand;
v=v*(n-u+1);
v=round(v);
* o1 B1 Y: L4 t  {if v<1
v=1;
end
v=u+v;
( W; O- H3 D& A; `& P9 wif v>n
v=n;
end
/ W9 p# A& S8 a) gpi_1(u)=pi0(v);
; h* `! X& e( Q0 M! ]pi_1(v)=pi0(u);
+ S/ E* ?' D4 \. w' ~$ o+ ]% @. Q4 Gif u>1
for k=1:u-1
. i9 {4 S/ V! \. h) Y4 n& V% [5 vpi_1(k)=pi0(k);
3 F' r. ~- C/ ^  J3 [end
" L7 w: `, ^9 `: xend
$ z' w# {0 Y) Hif v>(u+1)
3 K: N' U* Q: \  c& H+ Zfor k=1:v-u-1
' [, N1 \) F: H! C2 G: npi_1(u+k)=pi0(v-k);
end
end
) k; b# c, h" eif v<n
for k=(v+1):n
& H: I, F& v& I4 d2 Xpi_1(k)=pi0(k);
end
end
d_f=0;
) X5 ]! ?) K$ @7 A" eif v<n
d_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(v+1));
: O0 ?9 q- y0 Nfor k=(u+1):n
* C$ s7 s" u$ `  R% w2 id_f=d_f+d(pi0(k),pi0(k-1));
end
6 z3 r9 S2 C8 I- v  Pd_f=d_f-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(v+1));
2 C3 x+ l& \9 Gfor k=(u+1):n
+ G9 b+ P0 o5 U  U0 y% H2 ~d_f=d_f-d(pi0(k-1),pi0(k));
end
/ h# s1 M5 Q2 L- u% ~) o# v+ eelse
" X! x/ ~$ d% K* {- L( w: u8 td_f=d(pi0(u-1),pi0(v))+d(pi0(u),pi0(1))-d(pi0(u-1),pi0(u))-d(pi0(v),pi0(1));
! j: e: m7 j( F) F2 Afor k=(u+1):n
* s" w, @/ o# c8 z) X: z: Ed_f=d_f+d(pi0(k),pi0(k-1));
' `% K0 H  A# {' J+ F5 c6 H$ Uend
* g# \3 z& a1 b; Sfor k=(u+1):n
) r+ X7 Y, O# s' Z+ cd_f=d_f-d(pi0(k-1),pi0(k));
end
$ j) U6 e4 {, C- [& Fend
pi_r=pi_1;

( g' h' a" I+ G, i4 i2 [0 |得到：
6 z% V; D2 Z5 _! _4 f% @  [f,T]=TSPSA(A,0,99)
4 x- f, s5 _  U. y! ~( p
f =

3 m, Y' p4 h2 m1 p# _9 g   Inf
2 I" T# M. a3 w1 y- f, e# I
' h, r1 O9 v3 L/ b; m0 @6 C
, P- Y' W" Y( M* mT =
$ x* Q/ x4 j( y
  Columns 1 through 18
+ V! i: e2 {4 k5 Q2 Z8 Z3 ^4 J
4 \+ [. ~/ A& N% v     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15    16    17    18
* f- _, r) r: a1 a
  Columns 19 through 33
; w, P2 S7 U3 E; d2 r, R* M% h' @- m/ a& q, ?
    19    20    21    22    23    24    25    26    27    28    29    30    31    32    33

这个初始，结束温度是自己随便设定的？？
得到的这个F是无穷？？？难道？？？  T又是什么意思呢？？

冰E柠檬

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

magic2728

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