数学建模社区-数学中国

标题: 详解遗传算法（含MATLAB代码） [打印本页]
作者: 杨利霞    时间: 2021-8-6 15:33
标题: 详解遗传算法（含MATLAB代码）
& A9 o- T! u- E# q4 O+ t
详解遗传算法（含MATLAB代码）
8 r6 T( x8 |6 w8 ]& |& ^; _目录
( v# [8 Z! E. S6 T' m0 a; X6 o. E/ K' v; C3 D5 s

5 w$ w2 N* ^' X一、遗传算法概述% u5 s: T+ I% g, F

- h0 J: |& r' q, r, f3 j
2 g  Q2 o( A- F1 s6 K' G! @二、遗传算法的特点和应用
3 K' I1 g$ K5 D( @/ x/ [# V
9 q4 j* [6 e+ h/ E" |- n+ b4 [7 X& p: W- a- {
三、遗传算法的基本流程及实现技术
6 _( S+ N# @7 f, `
1 [3 Q0 _* B$ _( |: G, z2 k' t  w8 D1 Y/ S' r! b  K
3.1 遗传算法的基本流程
& d7 Q" n$ j/ a, j1 h1 f7 ^; f
9 p  y5 |5 R' U2 E+ S& d/ I6 x4 X+ x. R9 H( j+ ^
3.2 遗传算法的实现技术/ n4 c8 B2 m# G4 d( w

7 I" i9 W" [4 Q7 p# ^  B7 ]3 U
1 i8 R% C) b' @; [0 p( c! [+ O1.编码
, Y+ G1 s7 `+ I/ d4 `/ q9 @( C9 v( @! }# P; Z+ a

% G/ @& y, u. f1 s! C2.适应度函数2 Z: u$ b$ L5 j1 S/ l
5 x6 W* @' s: B7 S
% N1 e- k" B$ r1 {7 ~$ N
3.选择算子
" Z/ ]: N) d' z  s3 U2 n
# E2 I* j4 T  z" |0 A& _. ]
/ N, r3 v. I# u+ `8 ]0 U7 ~* j4.交叉算子
5 o0 o- G+ l' Q; a, v6 Z" f  D) h9 h8 Z9 n) Z/ t! j$ u

$ H* z% Z" B$ O1 q* E/ w0 l5 M3 J1 n1 L5.变异算子
7 }* f1 ^& Y3 C& h- W- a  W6 @* ?$ b* w( @4 W
# w, R  a7 ?2 Y2 r! c2 m* G* ^. C
6.运行参数# K% ]) g% E* b2 S" v1 n- q
/ Y& }" H6 W$ u

, v1 m' E7 z0 \% U3 \# A" {四、遗传算法的基本原理
( [* {; D: A$ h1 Q2 J2 ]( e7 h; ]3 _9 c$ \6 Z/ n3 k9 |
; D& k- ~  n  y1 G
4.1 模式定理$ ]9 Q3 W/ [$ M  i) X0 ~# V
$ m! N5 p+ K, T, k/ _2 F; Z: _. V
& Y+ u: ?5 S7 T5 @0 i
4.2 积木块假设
+ p4 y% C. S, h' w+ Q' O7 X8 v( o* ]) [, `) N/ k1 y$ P! i; g

/ v. M3 T4 U  f5 S五、遗传算法编程实例（MATLAB）
/ s  X/ k) o3 T4 Q7 c% M6 j9 x- _1 q
8 b7 M$ H6 t) y
一、遗传算法概述6 E" E# B9 E0 u/ _2 m8 c( W! C
        遗传算法（Genetic Algorithm，GA）是进化计算的一部分，是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。该算法简单、通用，鲁棒性强，适于并行处理。/ c$ |" O) {6 D- n/ `8 _: ^
' o8 u% P- k: x2 Q8 M5 {

* \1 z$ K4 U! |1 B* W二、遗传算法的特点和应用
$ V1 s3 d1 ^* T9 }   遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，具有以下特点：5 v+ O" U& K2 U- F7 Q  w7 Z

/ B0 N( A: [* F
( a8 x1 J' [/ M% ]# R. v% R1. 以决策变量的编码作为运算对象。; }0 z$ |2 _' q6 F9 H- y

) V/ |+ Q% V3 ~
; u. \( X, R' N; y    传统的优化算法往往直接利用决策变量的实际值本身来进行优化计算，但遗传算法是使用决策变量的某种形式的编码作为运算对象。这种对决策变量的编码处理方式，使得我们在优化计算中可借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化激励，也可以很方便地应用遗传操作算子。
# j8 ]8 ~8 B; R$ f% O$ S8 I0 ^$ T
8 B7 r2 H0 Z; D
5 p0 {6 @0 U+ v! |5 T3 n' m2. 直接以适应度作为搜索信息。8 N; t7 `$ |8 f

$ \; A. N4 m" i7 h. ^7 y( J& K& K/ b. z6 _$ h. D5 Z, n
    传统的优化算法不仅需要利用目标函数值，而且搜索过程往往受目标函数的连续性约束，有可能还需要满足“目标函数的导数必须存在”的要求以确定搜索方向。
$ H5 F, ?& K0 l9 S
% V( B% d) q* y" \# ~( J' Z
' @$ E1 ]# u8 K9 Y# m    遗传算法仅使用由目标函数值变换来的适应度函数值就可确定进一步的搜索范围，无需目标函数的导数值等其他辅助信息。直接利用目标函数值或个体适应度值也可以将搜索范围集中到适应度较高部分的搜索空间中，从而提高搜索效率。2 S/ S' @- f1 a$ @( t* c" m

3 k7 U8 @* Z# e5 B% a8 R5 t" i8 L9 D% @& f0 V( U! {
3. 使用多个点的搜索信息，具有隐含并行性。* B- {! b. r/ N- n# T' [' A: K  Q

" P( ~- ?2 |# ~) W- s: b7 N( T% Q* R" I' K
    传统的优化算法往往是从解空间的一个初始点开始最优解的迭代搜索过程。单个点所提供的搜索信息不多，所以搜索效率不高，还有可能陷入局部最优解而停滞；: Z9 p- z; }) e- u
! u( y) q. {$ j& L( F; x
' j/ r: t- z1 _; E
    遗传算法从由很多个体组成的初始种群开始最优解的搜索过程，而不是从单个个体开始搜索。对初始群体进行的、选择、交叉、变异等运算，产生出新一代群体，其中包括了许多群体信息。这些信息可以避免搜索一些不必要的点，从而避免陷入局部最优，逐步逼近全局最优解。
/ J$ [; C! }3 Q7 Q
; o6 g2 d7 l& O: |$ c. e5 _, g$ g% f. z5 v
4. 使用概率搜索而非确定性规则。+ R  A& C$ N* I1 X( i" M
" }  l& @: o. z

' \  g) @! i. h  a, E- k   传统的优化算法往往使用确定性的搜索方法，一个搜索点到另一个搜索点的转移有确定的转移方向和转移关系，这种确定性可能使得搜索达不到最优店，限制了算法的应用范围。5 p8 Z3 S- V7 V# c# R3 w
& ?+ F: t5 {# [$ n
" \# j$ h/ N, c+ S6 `
   遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式进行的，增加了搜索过程的灵活性，而且能以较大概率收敛于最优解，具有较好的全局优化求解能力。但，交叉概率、变异概率等参数也会影响算法的搜索结果和搜索效率，所以如何选择遗传算法的参数在其应用中是一个比较重要的问题。6 h8 n. _, G- ~; N% p

# r* e' q( Z; T4 o4 S3 f2 W( ^* s+ f/ l1 Z1 p1 B- D
综上，由于遗传算法的整体搜索策略和优化搜索方式在计算时不依赖于梯度信息或其他辅助知识，只需要求解影响搜索方向的目标函数和相应的适应度函数，所以遗传算法提供了一种求解复杂系统问题的通用框架。它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性，所以广泛应用于各种领域，包括：
) Y& F2 o$ ?& e2 j' M4 U5 g1 u
& Z$ s5 P* V, |" G* j6 G
函数优化
4 S+ j" C0 L# ]5 T  ^组合优化生产调度问题
) M2 E  @0 f! ]- C7 ~0 @自动控制6 x: M7 y( v5 |6 a; D6 L2 l+ ?9 G
机器人学8 n( E+ Y7 q! _9 ]8 B
图像处理（图像恢复、图像边缘特征提取......)4 Z( W" A7 ^. L  P; s
人工生命; m/ M  U& r0 @
遗传编程& C) G0 ~3 T8 ?' I3 Z
机器学习7 j0 N! q) [' a3 G
三、遗传算法的基本流程及实现技术$ B$ b: u7 b6 H5 z, V; C
   基本遗传算法（Simple Genetic Algorithms,SGA）只使用选择算子、交叉算子和变异算子这三种遗传算子，进化过程简单，是其他遗传算法的基础。4 d4 L  O4 ?+ B: e; b4 i9 L

! r" O, {; t6 Y' y0 M/ j" R  Q+ ~" y1 o; B8 l
3.1 遗传算法的基本流程' b7 G+ D; ^" T% o2 E- W
通过随机方式产生若干由确定长度（长度与待求解问题的精度有关）编码的初始群体；
  Y8 v! I" P) u- O% _9 U通过适应度函数对每个个体进行评价，选择适应度值高的个体参与遗传操作，适应度低的个体被淘汰；8 G( T0 D; B0 s7 j; h9 }: E/ i  H
经遗传操作（复制、交叉、变异）的个体集合形成新一代种群，直到满足停止准则（进化代数GEN>=?）；
) d  [4 @1 {, z! j" p/ w5 d. z9 K( ]1 m将后代中变现最好的个体作为遗传算法的执行结果。7 i( \" }3 y1 T5 M/ o
                                                   4 l/ ~9 i5 @! \# u* Y4 q
0 n1 o7 p; A, k1 B, F8 H& \
& I: M! ?  z% s
其中，GEN是当前代数；M是种群规模，i代表种群数量。
$ `5 o* o+ Z* c2 s
/ X6 ]( N# I% C/ L4 M; p) f/ j( H) K8 G6 [2 E
3.2 遗传算法的实现技术! w+ K, D$ U8 j5 V, n. h
基本遗传算法（SGA）由编码、适应度函数、遗传算子（选择、交叉、变异）及运行参数组成。
# W( A/ U+ [) r1 `% z9 p# y$ x. ^2 t1 q7 `
* v5 S, ?# L: J2 E+ ^8 k
1.编码
- [2 @: o- V, q# e（1）二进制编码$ Z' E2 _0 [; O

; y# K8 f9 o  ?5 W. e) E1 B4 M9 W: Q8 T& N) i3 J
二进制编码的字符串长度与问题所求解的精度有关。需要保证所求解空间内的每一个个体都可以被编码。
) E2 e6 t7 u& |) }' N8 D  n* M# w

+ Y- r4 v& ?& ?8 p5 I- Z优点：编、解码操作简单，遗传、交叉便于实现
7 e, S# w8 [8 [* G. s. M% \& Q* L+ l$ v/ X2 Z! L' n; q
9 ?+ R$ E8 Q( b$ A$ V( x
缺点：长度大
3 N! O( k0 t+ g' N; p. A0 m4 P; q; T
, D! N. W6 r4 U& U- }$ Q
) u" v9 G8 `! C2 G* q（2）其他编码方法
; @% l. `+ |; b: w! x5 A! J& @
7 P. n( ~. |2 j9 R5 m
  I1 O  s5 N/ B0 _6 [7 F2 j格雷码、浮点数编码、符号编码、多参数编码等
, M' N" j0 t7 D# s1 T2 G) L" z% L% J: F9 S( I# Y

9 ?) X% k) d/ R" @: y, R2.适应度函数
) c. P" W, G$ K, I  d适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。
  d0 Y9 f/ E8 Y
! _, h8 G5 A4 m
# G7 k$ ]2 v4 O" k3.选择算子
. T0 `0 F- _$ B" n$ r( V通过选择算子模拟“优胜劣汰”，适应度高的个体被遗传到下一代的概率较大，适应度低的算子被遗传到下一代的概率较小。
! d! y$ n% |8 @5 q/ t# ~6 d+ T/ e2 v7 U5 y/ |: @& }

0 b- r3 b) s9 F, j( a) l常用的选择算法：轮盘赌选择法，即令表示群体的适应度函数值的总和，表示群体中第i个染色体的适应度值，则它产生后代的能力刚好为其适应度值所占的份额" r+ J) n7 j4 C0 y* @6 X0 e
# O0 v. e- N' G- _+ E2 E

/ p" j/ [3 \3 F+ L( e4.交叉算子0 J) H7 A/ b+ j. w
交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体；8 i7 E. c4 X; ^
交叉运算是遗传算法区别于其他进化算法的重要特征，是产生新个体的主要方法。# R! F0 n: J6 f# C: y" K) y
在交叉之前需要将群体中的个体进行配对，一般采取随机配对原则。3 X6 a1 M/ V+ d; b+ R0 ^/ x- H4 Z

) W/ t2 D9 N, k& R1 `  G" V  @+ X( z
常用的交叉方式：, v5 T" i. p+ R& Q. t

$ ^) u5 t3 H. g- ]6 X5 C
9 c- r; l5 I. Z4 H% u, ]( Q/ F单点交叉1 W7 O/ \1 L1 w  [/ {  h
双点交叉（多点交叉，交叉点数越多，个体的结构被破坏的可能性越大，一般不采用多点交叉的方式）
6 I9 V" l0 C5 w0 X" N5 h均匀交叉
, v7 n, K1 L5 ?& {3 S7 V* @" x3 Q算术交叉, S& J9 y; ]6 Z8 K. A' F9 F/ ]7 `; E
5.变异算子
5 Z8 Z/ j8 b" |+ [* |3 p! @9 j遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新的个体。
6 S" u. |( z- j) u: q+ f2 S, j4 O4 ^9 i1 ^* R- T' Z! ?# `* J! b9 P5 k# V8 c
9 @4 W+ \4 M' K" g) g8 k
就遗传算法运算过程中产生新个体的能力方面来说，交叉运算是产生新个体的主要方法，它决定了遗传算法的全局搜索能力；而变异运算只是产生新个体的辅助方法，但也是必不可少的一个运算步骤，它决定了遗传算法的局部搜索能力。交叉算子与变异算子的共同配合完成了其对搜索空间的全局搜索和局部搜索，从而使遗传算法能以良好的搜索性能完成最优化问题的寻优过程。
6 f. E* x2 p8 ]$ N8 l
' w# \# M- ^: M! T4 O
7 t; v3 G+ M/ E2 k0 d- w, A3 _/ W6.运行参数2 W; E+ x, o$ j& i' ^% b
编码长度。编码长度取决于问题解的精度，精度越高，编码越长；( n' z4 C% c! X4 v
种群规模。规模小，收敛快但降低了种群的多样性，；+ p5 H9 q9 R2 H+ h
交叉概率。较大的交叉概率容易破坏种群中已形成的优良结构，使搜索具有太大随机性；较小的交叉概率发现新个体的速度太慢，一般取值为
, R$ N' m! e2 v变异概率。变异概率太小，则变异操作产生新个体的能力和抑制早熟现象的能力会较差；变异概率过高随机性过大，一般建议取值范围为0.005～0.01
  r' r4 t: [7 g$ {& O终止进化代数。算法运行结束的条件之一，一般取100～10004 R" M- s, g" l( Y- ?  H: {$ b
四、遗传算法的基本原理
' ]' J# Q9 J; L* `  E1 r4.1 模式定理
' `) I/ M% H8 \1 a3 r3 z4 V定义1:模式H是由{0,1,*}中的元素组成的一个编码串，其中“*”表示通配符，既能被当作0，也能被当作1。e.g. H=10**1
/ o) j1 G' B9 V' i  L0 @0 M& [# T9 C, Y
: k0 Z8 X! a8 f4 x
定义2:模式的阶，是指模式中所含有0，1的数量，记作O(H)  e.g. O(11*00**)=4
4 U; z" \8 ~- [$ X" \2 l- [" ~# t# x
3 S* H$ x' w5 _& Y% r
定义3:模式的矩，即模式的长度，是指模式中从左到右第一个非*位和最后一个非*位之间的距离，记作( j5 S6 X, k% v" Q) U
& O, `3 x. ~2 @6 T0 ^8 ]
1 z! F4 u" _+ ]  U
          e.g.
* T/ l2 X* o  ?: [. P$ g2 u2 A7 L
( ~, r$ d2 H0 B* v( |) L: G4 ]  F
定义4:模式的适应度值，是群体中所包含的全部个体的适应度值的平均值。6 B6 Y9 P7 P4 z6 m
- Q" }$ f/ \; `! C

% p; G7 g% [! j  d定义5:在选择、交叉、变异遗传算子的作用下，低阶、长度短、超过群体平均适应值的模式的生存数量，将随迭代次数以指数规律增长。
0 O* H4 V' f3 ^: V9 m# K% F3 ]7 d$ `

* }/ y% d$ x# D. k模式定理不仅说明基因块的样本呈指数增长，也说明用遗传算法寻求最优样本的可能性，但它并未指出遗传算法一定能够寻求到最优解，积木块假设说明了遗传算法的寻找最优解的能力。
) D. L0 e" |/ r  a* g# E; e& t: a9 Y0 L; J$ N7 r+ E+ R# B" t
  V" D7 m2 d; j1 T8 i
4.2 积木块假设" i- s2 N2 _9 J  q- }5 G4 |
具有低阶、定义长度短，且适应度值高于群体平均适应度值的模式称为基因块或积木块。* Y& F" g; Y/ S' a
$ b! q3 s! c# `- ^, ^4 R3 H
1 h( Z% W; E8 Z9 E* n# y/ e1 \
积木块假设：个体的基因块通过选择、交叉、变异等遗传算子的作用，能够相互拼接在一起，形成适应度更高的个体编码串。
3 m" \6 K! E: D  y0 W% c
: Y1 d* o  e' [
; D. N. ], X2 \积木块假设说明了用遗传算法求解各类问题的基本思想，即通过积木块直接相互拼接在一起能够产生更好的解。" H. R5 d" m! n8 h
9 Z3 h" F6 `7 W) w8 I6 m

2 }4 ^4 I$ P- ~4 U, {' ^五、遗传算法编程实例（MATLAB）4 P: U* m9 |5 e
https://github.com/strawberry-magic-pocket/Genetic-Algorithm.git+ T" p# A# }. u5 D: K: F/ O
————————————————. D8 m) i% T) \! D. R
版权声明：本文为CSDN博主「草莓酱土司」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
* [0 [( c+ a9 ]' |3 h( V) H原文链接：https://blog.csdn.net/qq_34554039/article/details/90521834
+ n& J  q- V& w9 W. r5 M0 C- v5 c, f: j+ n/ [8 Q9 Q0 M7 T8 _& A

+ h9 n2 f5 K9 W: J, Q



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5