EDA365电子论坛网

标题: 基于matlab遗传算法求最短路径 [打印本页]

作者: thinkfunny    时间: 2021-3-12 18:09
标题: 基于matlab遗传算法求最短路径

6 s1 E* I/ B- M. J- o3 l" T% \一、简介, |4 @, x! V# _" ~6 d8 g

" g( M3 o: y5 U9 W7 _
4 t8 T+ {9 S& z. Z一、问题分析0 {' z& V3 m# |9 n3 H9 n+ W* ^
, Y% }: E5 V' e1 X  [* {6 k
如图如示,将节点编号,依次为1.2.3.4.5.6.7.8.9.10.11,由图论知识,则可写出其带权邻接矩阵为:% l3 g& {& V, j% S2 X
* \  P7 G2 V- `6 |; ~
$ J& u+ `. y. e' _4 O0 j

7 D' I; b3 _. c  g500 1 500 500 0 3 500 2 500 500 5003 W. R$ C6 s, S. u8 q" M4 e# h9 }+ r

# K0 w6 u: j% g5 H! e" {500 500 1 500 3 0 4 500 6 500 500
5 t7 w0 ^& {9 h+ p% h: [# x: f( D4 h# p# }
500 500 500 9 500 4 0 500 500 1 500$ _# i1 s" ]. M0 `
  a- r2 U6 {% \( q) T2 Y5 S! K
500 500 500 500 2 500 500 0 7 500 9" E  b- ]7 X9 L! ^( `1 F' x3 A* L

3 m: J  G! N- c; o2 O$ W) a$ h500 500 500 500 500 6 500 7 0 1 2
2 `6 r- d, ~5 d. T8 a
8 x& b2 a& s/ e2 s; A500 500 500 500 500 500 1 500 1 0 40 r2 L4 y7 T% W

- p7 W3 D' H6 f  _500 500 500 500 500 500 500 9 2 4 02 Y0 V, b! K2 o5 B6 l
; q+ y+ ~4 {0 W# K, y4 R- ?
注:为避免计算时无穷大数吃掉小数,此处为令inf=500。
0 Z4 g- F! @7 t! ^* \2 z# f- ?
, i  [1 u6 y3 N: ]% {0 O) H+ K$ {8 S  p& `6 N' i# [2 k# }' f
问题要求求出任意两点间的最短路径,Floyd算法采用的是在两点间尝试插入顶点,比较距离长短的方法。我思考后认为,用遗传算法很难找到一个可以统一表示最短路径的函数,但是可以对每一对点分别计算,然后加入for循环,可将相互之间的所有情况解出。观察本题可发现,所有节点都是可双向行走,则可只计算i到j的路径与距离,然后将矩阵按主对角线翻折即可得到全部数据。
' q9 D. U9 ~2 v% D& B3 {( _; C6 A" J4 H

+ ~: ]2 W7 P7 V% B" q( p
6 K+ P1 N7 ]+ V' @" `/ I二、实验原理与数学模型% w# k9 c! n# Z$ T  \5 P! c
2 e' ^. S* k' s
实现原理为遗传算法原理:/ I5 m' a( C; ]4 l5 V2 f- e4 {

# `0 O) o' S. ^# U按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选,使得适应度高的个体被保留下来,组成新的群体,新的群体既继承了上一代的信息,又优于上一代。这样周而复始,群体中个体适应度不断提高,直到满足一定的条件。, s8 m, }, R" _# N/ U6 u6 l) G8 j3 q
! T: b! I# u- W
数学模型如下:7 E' E) d1 V+ l- B% X# ]

( T' |, ?( Y! A) n( G8 r9 d0 l1 V
" ?" ^( B) O# Z) D8 R8 E9 B. J
8 c4 B( y1 w% z# h+ g, k& v( Z, Z+ m: y& }4 ~, p- q2 p! w; M) C
实验具体:& R; v: |- d3 r1 b; K& G0 Q; [9 W
- X# _* B' U; L( [( C5 A9 E5 R
第一:编码与初始化! v! g  w2 F1 ^
: N" |" \, m* H" `+ z/ T) V# i
因采用自然编码,且产生的编码不能重复,于是我采用了randperm函数产生不重复的随机自然数。因解题方法是使用的是计算每一对点,则我们编码时将第一个节点单独放入,合并成完整编码。
% r# J, P. d7 w( ~2 O2 r) u- ?8 D+ _4 L9 X- C( U, E9 @
因为节点有11个,可采用一个1行11列的矩阵储存数据,同时,由于编号为数字,可直接使用数字编码表示路径的染色体。具体如下:8 |4 p0 g/ m& N3 L
& n6 p! M+ A: [
采用等长可变染色体的方式,例如由2到9的路径,染色体编码可能为(2,5,1,8,4,6,9,3,10,7,11),超过9之后的编码,用来进行算子的运算,不具备实际意义。
, {: `; j) D. b( t+ n' M4 E0 i7 I) x7 M0 A6 d
第二:计算适应度,因取最短路径值,即最小值,常用方法为C-F(x)或C/F(x)(C为一常数),此处采用前一种方式。于是,可进一步计算相对适应度。6 H8 A, ?/ I4 u9 Y, d5 k6 m- A
8 u2 `/ f0 l; O" }
第三:选择与复制5 r& M' \5 B# ]% I+ o% P0 i) f) x
' S  @8 {8 Z' y- _; A
采用轮盘赌算法,产生一个随机值,比较它与累计相对适应度的关系,从而选择出优良个体进入下一代。+ q* z# `4 T, Q+ s5 i2 g
$ S' h8 P- e* |6 v* ?1 z( K
第四:交叉。
5 T( ~& k) O4 M' |& V
. s: |! v* a4 g6 u* b因编码是不重复的数字,所以采用传统的交叉方法,即上一行与下一行对位交叉,会产生无效路径,于是,采用了不同的交叉方法,具体如下:' r7 g+ j" r6 _9 F- N

' n9 W6 S' a3 k( a$ L4 U4 g(1)在表示路径的染色体Tx 和Ty中,随机选取两个基因座(不能为起点基因座)i和j, 即将i个基因座和第j个基因座之间的各个基因座定义为交叉域,并将交叉的内容分别记忆为temp1和temp2。
- R, D$ C9 [" w: w$ F0 \8 x9 T
3 F. i, M0 ~$ }' _(2)根据交叉区域中的映射关系,在个体Tx中找出所有与temp2相同的元素,在个体Ty中找出所有与temp1相同的元素,全部置为0。: u" Q+ F# d  s& i1 V* p) i; i! X

! S, m: x3 p7 {- h$ D4 O(3)将个体Tx、Ty进行循环左移,遇到0就删除,直到编码串中交叉区域的左端不再有0:然后将所有空位集中到交叉区域,而将交叉区域内原有的基因依次向后移动。因0元素可能较多,在程序实现时,我是将非零元素提出,后面再合成。( q8 H0 R) k/ P  D% p

' f- c7 w8 U0 Y2 b/ Y2 G(4)将temp2插入到Tx的交叉区域,temp1插入到Ty的交叉区域。形成新的染色体。
' Z( ^7 M/ w# ~" ]& g) C; @
6 i/ B. R" \( n0 a第五:变异: P: |, z+ `  P1 U/ x: o

7 w/ F3 A2 m7 U) l8 u( I9 w染色体编码为从1到11的无重复编码,所以不能采用一般的生成一个随机数替代的办法。此处采用交换变异法。即随机产生两个数,交换两个节点的顺序。
/ X9 L& m/ {$ `# L1 U3 m1 |, @  q1 ?: M( q( N: ?  b0 H
/ e+ A/ d2 v/ H6 C
$ R  ]) I# z$ j9 _7 c$ t
二、源代码- M& z  _& h$ w- c' ^6 r/ ^7 ~
: o/ Y  h7 B, o8 x- \* G
3 K6 u0 s5 r: E/ g# T5 p1 C# Y* h
三、运行结果
# J  W% L6 k5 H' j+ `" u2 i! n5 @. Y9 |9 @8 C. }6 x1 p
距离矩阵:a(i,j) i表示起点,j表示终点。
) a4 _; Q, B& o* p8 m  N2 j2 Q' B! b" M7 X9 |4 C2 j( _; m
outdistance =6 r/ L, |/ U; e. C) {
& i: M' Y  B- r! _1 C: |

. t; ^( Q; @( `( |# U% F7 Y  o7 A& J% w
14 12 9 13 11 8 4 9 2 3 0  ~4 \0 U0 m+ u1 W5 L  t1 y

* }, V. T# b! _% y, y9 M7 i7 Z' d路径:b(i,j) i表示起点,j表示终点。
: c* S: r( ?' n' z9 L2 O8 f- V* @. o" ]' O
outpath:# J& c" j& N5 o& ]$ U( H) ^; c

2 c" x4 l2 C4 t- _ . ~8 l- Z* J9 T% s

8 r6 b/ {$ U! g, R) U' ^5 |6 ?  d( P* |0 R6 `) i
3 l* s* ~; T2 q& I8 ?' T

作者: NingW    时间: 2021-3-12 18:28
基于matlab遗传算法求最短路径




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