EDA365电子论坛网

标题: 遗传算法解决TSP问题MATLAB实现(详细) [打印本页]

作者: thinkfunny    时间: 2020-10-14 15:34
标题: 遗传算法解决TSP问题MATLAB实现(详细)

& \5 h/ z$ A4 J5 i3 w文章目录/ O) H. {3 P' s' A+ f# C* u
" G; D1 ?! Y8 e6 I' M
问题定义:巡回旅行商问题& A& E7 S7 ]2 M4 c2 N) d4 g
给定一组n个城市和俩俩之间的直达距离,寻找一条闭合的旅程,使得每个城市刚好经过一次且总的旅行距离最短。
1 u& C1 v7 k! b! x0 T2 h! ?- \3 F$ _' i3 C0 V- k
TSP问题也称为货郎担问题,是一个古老的问题。最早可以追溯到1759年Euler提出的骑士旅行的问题。1948年,由美国兰德公司推动,TSP成为近代组合优化领域的典型难题。
$ k6 g7 N3 ^2 L# r. a/ [  q( x" D5 \7 I( R: N* w( O
TSP是一个具有广泛的应用背景和重要理论价值的组合优化问题。 近年来,有很多解决该问题的较为有效的算法不断被推出,例如Hopfield神经网络方法,模拟退火方法以及遗传算法方法等。0 F  ?, \9 q4 o( v+ D$ \8 e7 W
; S" U# p9 K- o( M
TSP搜索空间随着城市数n的增加而增大,所有的旅程路线组合数为(n-1)!/2。在如此庞大的搜索空间中寻求最优解,对于常规方法和现有的计算工具而言,存在着诸多计算困难。借助遗传算法的搜索能力解决TSP问题,是很自然的想法。6 D! ~  b& H' L' H
$ ^% R2 x, L% D' J1 z" [6 F
基本遗传算法可定义为一个8元组:
" ^) V% |$ N3 v
2 H7 L5 ?6 u) M一是完全随机产生,它适合于对问题的解无任何先验知识的情况。随机性较强,因而也较公正
( a5 K, _  `( Z: ^7 ?. S- N: R4 `% M( G6 J0 |
二是某些先验知识可转变为必须满足的一组要求,然后在满足这些要求的解中在随机地选取样本。这样选择初始种群可使遗传算法更快的达到最优解。种群有一定的目标性和代表性,但取例不如完全随机的广泛,而且先验知识是否可靠也是一个问题" e2 `! }( e0 y

, k$ b4 T* c7 X% a遗传算法在进化搜索中基本不利用外部信息,仅以适应度函数为依据,利用种群中每个个体的适应度值来进行搜索。TSP的目标是路径总长度为最短,路径总长度的倒数就可以为TSP的适应度函数:7 _$ x. a3 }1 A) r# T
! o, ]- V6 T) d: J
4 I6 }) a6 U# x. v$ y$ y; U4 d) w

$ Y  J5 S( r0 p% ~一般地说,选择将使适应度较大(优良)个体有较大的存在机会,而适应度较小(低劣)的个体继续存在的机会也较小。简单遗传算法采用赌轮选择机制,令Σfi表示群体的适应度值之总和,fi表示种群中第i个染色体的适应度值,它产生后代的能力正好为其适应度值所占份额fi/Σfi。
) S4 V* k1 L' i$ t8 h7 f1 Y* M3 U: t+ g2 v* M9 R+ ?3 m# d
基于路径表示的编码方法,要求一个个体的染色体编码中不允许有重复的基因码,也就是说要满足任意一个城市必须而且只能访问一次的约束。基本遗传算法的交叉操作生成的个体一般不能满足这一约束条件。0 P% S# e0 A+ ]" X, b  b& \6 ?

. _  R7 _. F) B+ E$ ^2 S部分匹配交叉操作要求随机选取两个交叉点,以便确定一个匹配段,根据两个父个体中两个交叉点之间的中间段给出的映射关系生成两个子个体。
( z9 H7 G) i" Z+ N
0 x; z# w# {1 b$ r4 B 9 ]% C* U/ g+ e( ?
" G; c. _; ^' t( A$ M
遗传算法解决TSP 问题基于二进值编码的变异操作不能适用,不能够由简单的变量的翻转来实现4 G0 v! R8 h! Q

$ c6 E4 F% h: _$ F8 |3 w3 k5 D在TSP问题中个体的编码是一批城市的序列,随机的在这个序列抽取两个城市,然后交换他们的位置。这样就实现了个体编码的变异,算法如下:
- _; _, X3 d) `6 A$ ^$ F' v
4 G( Q  U7 f4 x' U3 w) W* ^$ [7 N' [$ v2 i
: h3 n, p2 e1 Q$ q" U
流程图% _2 `: j7 X8 i* D

* i* ^( K# F4 Q' r6 \8 y2 d
& \8 G! ~/ S& N1 e: U  M, I: Z2 v8 i9 i* m; b5 s3 Z

( ^8 K7 I& d6 }) s) ?% ]代码7 z* s- s9 u- ]: y* `. c4 s
主函数代码:' x, g- e4 l4 M! L! v
' H2 O! \7 R' y$ y) `
             3 b- }$ R! T1 A
' X7 r( ~6 g  g
calculateDistance.m
, ?9 A' s/ ^5 n6 E) j6 w# M* {
% u1 u2 c3 q& ~) J
6 I" O9 P9 x! u4 F1 D  k
; s( C2 v+ S2 Q3 ]crossover.m. x& f. S+ `5 j% ~$ f3 \" s

5 [6 @& u. E' k$ [  
% m8 R) ^$ g7 g4 Z! r$ B- G* {! Z/ ?
. y$ @. |& x) q4 k% Efitness.m
- y5 H! N! T/ d' c- F& c! ]9 J7 B* `7 X
, ]5 D2 \! f8 c! R  w1 H
/ z* O8 k8 D( \$ v2 B6 J7 D
mutate.m/ ~$ @$ K* k0 O' b" _, R( c
! T2 V* l4 r3 D) ]
( w3 J  _/ p' g
5 S* M( a/ E3 R
paint.m* G: _5 Y1 A. d

- U- a; B8 m" I
6 V  W& e. @, C* @$ |' C& G. \
0 Y" C4 Q+ x* @: XRead.m6 B7 ~1 I, ?* \, j9 n! E
- C! y( W) e  ?5 [
/ n/ z, F* B) E/ D" R7 a
  l7 h' z* V0 l1 ?9 g3 n  z
结果3 ]8 }* {: L, V- o  `, b( y

9 C$ E4 y5 g: o: {8 x+ K$ u测试数据:5 `/ x0 L( ]: S: O/ o" f

, U# W& U0 B0 e( Z
: G' P' |7 h5 @
$ G4 }  l7 ~: T/ j. g初始状态:! [& r$ ]% z2 M2 v! l0 j
2 I' U$ l$ ~5 b+ w9 s, p

2 w& n% g8 A% b; l9 O7 S0 r) w( r0 q. k
最终状态:6 Y: c8 b. k! J6 a2 I

2 E. E! l8 W' y( ?9 | . y5 o; d# O' \" A
5 L1 C9 h6 D# [' s8 k6 V# f/ h5 }
收敛曲线图:# Z8 ]- M6 |5 B- |

) _8 r$ D  e2 b- D- ^ 9 j. {; w# v; H

* h+ F/ K% N! z: O: d! F/ f可以看到,当城市数量适中时,迭代500次最短路径长度有收敛的趋势。
. z2 _" N! k* Z, M& h
& w2 E/ V' Z1 p( N6 Y) d& H8 h当城市数目较多时
5 Z, z. y3 J5 K7 c7 g! X0 I  v9 `' E( F7 _$ c- e0 X7 @9 w

8 }% v$ m7 n0 e( |, }8 y5 g6 w7 `' [$ J0 o% J, V* i5 f
迭代500次,仍然不收敛,可能的问题是陷入了局部最优解。
2 f! t: p% J" h2 z* i8 ^/ [' d& S/ j
总结与观点9 l8 l3 C5 v( m- {* p2 z
2 s+ d! ^6 x' p7 b" ?5 m4 v

作者: ExxNEN    时间: 2020-10-14 16:08
遗传算法解决TSP问题MATLAB实现




欢迎光临 EDA365电子论坛网 (https://bbs.eda365.com/) Powered by Discuz! X3.2