遗传算法流程图
诸葛亮资料-人才规划
2023年2月20日发(作者：世界十大名酒)遗传算法
第1章遗传算法简介
遗传算法（GeneticAlgorithm）起始于20世纪60年代，主要由美国Michigan⼤学的JohnHolland与其同事和学⽣研究形成了
⼀个较完整的理论和⽅法。从1985年在美国卡耐基梅隆⼤学召开的第5届⽬标遗传算法会议（IntertionalConferenceon
GeneticAlgorithms:ICGA’85）到1997年5⽉IEEE的TransactiononEvolutionaryComputation创刊，遗传算法作为具有系统优
化、适应和学习的⾼性能计算和建模⽅法的研究逐渐成熟。
1.1遗传算法的产⽣与发展（略）
1.2遗传算法概要
1.2.1⽣物进化理论和遗传算法的知识
遗传：
变异：亲代和⼦代之间，⼦代和⼦代的不同个体之间总有些差异，这种现象称为变异，变异是随即发⽣的，变异的选择和积累
是⽣
命多样性的根源
⽣存⽃争和适者⽣存：
下⾯给出⽣物学的⼏个基本概念知识，这对于理解遗传算法很重要。染⾊体：是⽣物细胞中含有的⼀种微⼩的丝状化合物，是
遗传物质的主要载体，由多个遗传因⼦—基因组成。
遗传因⼦（gene）:DNA长链结构中占有⼀定位置的基本遗传单位，也称基因。⽣物的基因根据物种的不同⽽多少不⼀。
个体（individual）:指染⾊体带有特征的实体
种群（population）:染⾊体带有特征的个体的集合
进化（evolution）;⽣物在其延续⽣命的过程中，逐渐适应其⽣存环境使得其品质不断得到改良，这种⽣命现象称为进化。⽣
物的
进化是以种群的形式进⾏的。
适应度（fitness）:度量某个物种对于⽣存环境的适应程度
选择（selection）:指以⼀定的概率从种群中选择若⼲个体的操作
复制(reproduction)
交叉(crossorer)
变异（musation）：复制时很⼩的概率产⽣的某些复制差错
编码（coding）:DNA中遗传信息在⼀个长链上按⼀定的模式排列，也即进⾏了遗传编码。遗传编码可以看成是从表现型到遗
传⼦
型的映射。
解码（decoding）：从遗传⼦型到表现型的映射
1.2.2遗传算法的基本思想
遗传算法是从代表问题可能潜在解集的⼀个种群开始的。该种群是由经过基因编码的⼀定数⽬的个体组成，这需要实现从表现
型到基因型的映射即编码。初代种群产⽣之后，按照适者⽣存、优胜略汰的原理，逐代进化产⽣出越来越好的近似种，即在每
⼀代中，根据问题域中个体适应度⼤⼩挑选个体，并借助⾃然遗传学的遗传算⼦进⾏组合交叉和变异，产⽣出代表解的解集的
种群。这个过程将导致种群像⾃然进化⼀样的后⽣代种群⽐前代更加适应于环境，末代种群中的最优个体经过解码可以作为问
题近似最优解。
采⽤多种群即有⼦种群的算法往往会获得更好的结果。每个⼦种群像单种群遗传算法⼀样独⽴地演算若⼲代后，在⼦种群之间
进⾏个体交换。这种多种群遗传算法更加贴近于⾃然界中种族的进化，称为并⾏遗传算法。
1.2.3遗传算法的特点
*⾃组织，⾃学习，⾃适应性
*本质并⾏性
*不需要求导或其他辅助知识，⽽只要影响搜索⽅向的⽬标函数和相应的适应度函数
*强调概率转换规则，⽽不是确定的转换规则
*对给定问题可产⽣许多的潜存种，最终选择可以由使⽤者确定，因此对于确认可替代解集⽽⾔是特别适合的。（如多⽬标优
化问题）1.3遗传算法的基本操作
遗传算法包括三个基本操作：选择，交叉（基因重组），变异
这些基本操⼜有许多不同的地⽅。
1.选择
按⽐例的适应度算法（proportionalfitnessassigment）
基于排序的适应度算法（rank-basedfitnessassignment）
轮盘赌选择（roulettewheelselection）
随机遍历抽样（stochasticuniversalsampling）
局部选择（lacalselection）
截断选择（tournamentselection）
2.交叉或基因重组（crossorer/recombination）
*实值重组（realvaluerecombination）
离散重组（discrete）、中间(intermediate)重组、线性(linear)
重组、扩展线性(extendedlinear)重组
*⼆进制交叉（binaryvaluelcrossorer）
单点交叉、多点（multiple-poinrt）交叉、均匀(uniform)
交叉、洗牌(shuffle)交叉、缩⼩代理(crossoverwithreduced
surrogate)
3.变异（mutation）
变异实质上是⼦代基因按⼩概率扰动产⽣的变化，有两种算法，分别为实值变异和⼆进制变异
第⼆章基本遗传算法
2.1⼀个简单的遗传算法实例
本节介绍⼀个简单的实例，来考察⼀下⼆进制算法的轮盘赌选择、多点交叉和变异操作，以便对遗传算法的基本过程和基本操
作有所了解。
表1是⼀组⼆进制基因构成的个体组成的初始种群，个体适应度是由某种算法计算得到的。适应度越⼤代表这个个体越好。这
⾥为了能够符合优胜略汰的原则，个体适应度按照⽐例转化为选择概率，进⽽得到累积概率
表1
轮盘赌选择⽅法类似于博彩游戏中的轮盘赌，将轮盘分成10个（即种群个体数⽬）扇区，并进⾏10次选择，从⽽产⽣10个
[0,1]之间的随机书，图1的尖头表⽰被选中的染⾊体。
图1轮盘赌选择
1到10代表染⾊体个体序号，扇区⼤⼩表⽰染⾊体选择概率的⼤⼩假设产⽣的随机数序列为
0.070221，0.545929，0.784567，0.44693，0.507893，0.291198，0.71634，0.272901，0.371435，0.854641，将随机数
序列与计算获得的累积概率⽐较，则依次序号为1，8，9，6，7，5，8，4，6，10个体被选中。显然适应度⾼的个体被选中
的概率⼤，在第⼀次⽣存竞争中，序号为2和3的个体被淘汰，代之以适应度⾼的个体8和6，这个过程被称为再⽣
（reproduction）
再⽣之后重要的遗传操作是交叉，这⾥仅以单点交叉为例。任意挑选经过选择操作后种群中的两个个体（该两个个体应是不同
的）作为交叉对象，随机产⽣⼀个交叉点位置，将交叉点位置之右的部分基因进⾏交叉，如下图2
⽗个体
⽗个体2
⼦个体
⼦个体2
图2单点交叉
如果只考虑交叉操作实现进化机制，在多数情况下是不⾏的，这与⽣物界近亲繁殖影响进化历程是类似的。因为种群的个体数
是有限的，经过若⼲代交叉操作，源于⼀代较好祖先的⼦个体逐渐充斥整个种群，这样就会出现所谓早熟或过早收敛现象。这
样最后获得的个体并⾮真正意义上的最优种群。为避免这种现象，有必要在进化过程中加⼊具有新遗传基因的个体，解决⽅法
是模仿⽣物变异的遗传操作。对于⼆进制基因码组成的个体种群，实现基因码的⼩概率翻转，即可达到此⽬的，如图3（第四
位由1翻转为0）
图3变异
变异总是⼩概率的，即只有个别个体发⽣变异。其翻转的位置及翻转个数可以是随机的，有时也可以是固定的。
遗传算法的⼀般流程如图4所⽰
图4基于遗传算法流程图
2.2简单函数优化的实例
前⼀节所讲的实例是没有真正对象的，只是将遗传算法操作过程结合最简单的轮盘赌选择，单点交叉，单点⼩概率变异介绍了
⼀下，使学⽣对遗传算法有⼀个概要了解，本节结合函数优化问题，使学⽣了解如何对问题实现编码和解码，如何产⽣初始种
群，如何针对函数优化问题确定适应度函数，将遗传算法的操作全过程表⽰出来。
考虑下列⼀元函数求最⼤值的优化问题：
()sin(10*)2.0[1,2]fxxxxπ=+∈-
由于()fx在[-1，2]可微，可⽤微分法先求出其最值：
()sin(10)10cos(10
fxxxxπππ'=+=即
tan(10)10xxππ=-
解得：
,
0,211,2......200211,2...
20iiiiixixixiεε-?=+=??=??+?=+=--?式中(1,2....)iiε=及i=-1,-2...
是⼀列接近于0的实数递减序列。
函数()sin(10*)2.0fxxxπ=+的曲线
最后得到
191919371.8520
xεε=+=+下⾯我们⽤遗传算法解决上述函数的最优问题（即求其最⼤值）
（1）编码
变量x作为实数，可以视为遗传算法的表现形式。从表现型到
基因型的映射称为编码。通常采⽤⼆进制编码形式将某个变量值代表的个体表⽰为⼀个[0、1]⼆进制串。如果设定求解精确到
6位⼩数，由于区间长度为2-（-1）=3，必须将闭区间[-1，2]分为3*106等份。因为2097152=221<3*106<=222=4194304
所以编码的⼆进制串长⾄少需要22位
①将⼀个⼆进制串（b21b20….b0）2代表的⼆进制数化为10进制数：
21
212002100(bb....b)(2)iiibx='==∑g
②x'对应的区间[-1，2]内的实数：
222(1)1.021xx--'=-+-g
串[0………0]和串[1……1]（每个⾥都是22个数）分别表⽰区间的两个端点值-1和2。
（2）产⽣初始种群
⼀个个体由串长为22的随机产⽣的⼆进制串组成染⾊体的基因码，我们可以产⽣⼀定数⽬的个体组成种群，种群的⼤⼩（规
模）就是指种群中的个体数⽬。
（3）计算适应度
适应度⼤的个体其存活和被选中的概率⼤。适应度的计算就是对个体的计算，考虑到本例⽬标函数在定义域内均⼤于0，⽽且
是求函数最⼤值，所以直接引⽤⽬标函数作为适应度函数：
()()fsfx=例如x1=0.637197通过编码得到的⼆进制串是
s1=[1101000111]
这个串就是个体。个体的适应度就是
1111()()sin(10)2.02.286345fsfxxxπ==+=这⾥我们选择种群数量为3，每个个体为：
s1=[1101000111]
s2=[]
s3=[1111000101]
分别对应于数量值x1=0.637197,x2=-0.958973,x3=1.627888,三个个体的适应度计算如下；
1111()()sin(10)2.02.286345fsfxxxπ==+=
2233()()1.078878
()()3.250650fsfxfsfx====
显然3个个体中S3的适应度最⼤，为最佳个体。
（4）遗传操作
下⾯是经过选择操作后的两个个体：
s2=[000001000]
s3=[1111000101]
⾸先执⾏单点交叉，随机选择⼀个交叉点，将之后的串交叉
2
S'=[1111000101]3
S'=[1110010000]这两个个体的适应度分别为：
2
3
()(0.998113)1.940865()(1.666028)3.459245fsffsf'=-='==可以发现2
S'的适应度⽐S2和S3都⾼。（问题：这样选择选出种群中个体数⽬不是越来越少吗）下⾯考察变异操作，假定已经以⼀⼩
概率选择了S3的第5个遗传因⼦（即第5位）变异，遗传因⼦是由原来的0变为1，产⽣新的个体3S'=
[1111000101]，计算该个体的适应度
3
()(1.721638)0.917743fsf'==可见该个体的适应度⽐它的⽗个体的适应度减⼩了，但如果选中第
10个遗传因⼦变异，产⽣新个体为3
S''=[]3
()(1.630818)3.343555fsf''==⼜发现3
S''的适应度⽐其⽗个体的适应度改善了。这说明变异操作的“扰动”作⽤。
（5）模拟结果
设定种群⼤⼩为50，交叉概率PC=0.25，变异概率Pm=0.01,按照上述的基本遗传算法，在进⾏到89代时获得最佳个体：S
max=[1111001111]
Xmax=1.850549f(xmax)=3.850274
由于数学函数优化问题不需要专门领域的知识，且能较好的反映算法本⾝的实际效能，所以常⽤于GA的测试问题。下⾯四个
为具有相当复杂度的常⽤测试函数：
1）Shubert函数
}}55
1
122(,)cos[(1)1]cos[(1)1]0.5[(1.42513)(0.80032)]iifxyiixiiyxy==??=++++++++∑∑
此函数有760个局部极⼩点，其中只有⼀个（-1.42513，-0.80032）为全局最⼩点，最⼩值为186.7309，⾃变量的取值范围-
10
2）Camel函数
42222(,)(4
2.1)(44)3xfxyxxxyyy=-+++-+此函数有6个局部极⼩点，其中有两个（-0.0898，0.7126）和(0.0898,-0.7126)为全局最⼩
点，最⼩值为-1.031628，⾃变量的取值范围为-100
3）DeJones’sF5函数
25526111()0.02()
ijiijifxjxa===++-∑∑
其中22532
01632()32323232321616323232ija?----??=?-------??。⾃变量取值范围为-65535
4）Shsffer’sF6函数
(,)0.5(10.001())fxyxy=-++
此函数有⽆限个局部极⼤点，其中只有⼀个（0，0）为全局最⼤，最⼤值为1。⾃变量的取值范围为-100
2.3遗传基因型
Holland提出的遗传算法是采⽤⼆进制编码来表现个体遗传基因型的，它使⽤的编码符号集由⼆进制符号0和1组成，因此实际
的遗传基因是⼀个⼆进制符号串，其优点在于编码、解码操作简单，交叉、变异等遗传操作便于实现，⽽且便于利⽤模式定理
进⾏理论分析等。其缺点在于，不便于反映所求问题的特定知识，对于⼀些连续函数的优化问题，也由于遗传算法的随机特征
⽽使得其局部搜索能⼒较差，对于⼀些多维、⾼精度要求的连续函数优化，⼆进制编码存在着连续函数离散化时的映射误差，
个体编码串较短时，可能达不到精度要求；⽽个体编码较长时，虽然能提⾼精度，但却会使算法的搜索空间急剧扩⼤，造成遗
传算法的性能降低。为提⾼遗传算法的局部搜索能⼒，后来⼜陆续产⽣了：格雷码（GrayCode）等。为改善遗传算法的计
算复杂性，提⾼算法效率提出了浮点码和符号编码。随着⽣物计算理论研究的兴起，有⼈提出DNA编码法，并在模糊控制器
优化
应⽤中取得很好的效果。
遗传算法的进化过程是建⽴在编码机制基础上的，编码技术对于算法性能如搜索能⼒和种群多样性等影响很⼤，例如⼆进制编
码搜索能⼒强，⽽种群多样性弱，浮点编码则正好相反。⼆进制编码的种群稳定性⽐浮点编码差。
浮点编码对个体itx的第p个基因进⾏变异操作
()()(0,)iipDttxpxNψδ=+（N为⾼斯噪声）
可见浮点数编码操作的变量可以任意地⼩，这样可以保证只要变异量是⾜够的⼩，产⽣的新个体可以与⽗个体充分的接近。⽽
⼆进制编码的变异操作不能保证⽗个体与新个体的充分接近，因此其种群稳定性⽐浮点差。
⼀个好的编码⽅法应具有下⾯9个特征：
！）完整性（completeness）原则上，分布在所有问题域的解都可能被构造出来。
2）封闭性（closure）每个基因编码对应⼀个可接受的个体，封闭性保证系统从不产⽣⽆效的个体。
3）紧致性（compactness）若两种基因编码g1和g2都被解码成相同的个体，若g1⽐g2占的空间⼩，就认为g1⽐g2紧致。
4)可扩展性（scalability）对于具体的问题，编码的⼤⼩确定了解码的时间，两者存在⼀定的函数关系，若增加⼀种表现型，
作为基因的编码⼤⼩也相应增加。
5）多重性（multiplicity）多个基因解码成⼀个表现型，即从基因型到相应的表现型空间是多对⼀的关系，这是基因的多重
性。若相同的基因型被解码成不同的表现型，这是表现型的多重性。
6）个体可塑性（flexibility）决定表现型与相应给定基因是受环境影响的。
7）模块性（modulatity）若表现型的构成中有多个重复的结构，在基因型编码中这种重复应当是避免的。
8）冗余性（redundancy）冗余性能够提⾼可靠性和鲁棒性
9）复杂性（complexity）包括基因型的结构复杂性，解码复杂性，计算时空复杂性（基因解码、适应值、再⽣等）
以上特性有时是相⽭盾的。
2.4适应度函数及其尺度变换
遗传算法在进化搜索中基本不利⽤外部信息，即以适应度函数（fitnessfunction）为依据，利⽤种群中每个个体的适应度值来
进⾏搜索。因此适应度函数的选取⾄关重要，直接影响到遗传算法的收敛速度以及能否找到最优解。⼀般⽽⾔，适应度函数是
由⽬标函数变换
⽽成的。对⽬标函数值域的某种映射变换成为适应度的尺度变换（fitnessscaling）
1.⼏种常见的适应度函数
①直接以待求解的⽬标函数转化为适应度函数，即
若⽬标函数为最⼤化问题Fit(f(x))=f(x)
若⽬标函数为最⼩化问题Fit(f(x))=-f(x)
这种适应度函数简单、直观，但存在两个问题，其⼀是可能不满⾜常⽤的轮盘赌选择中的概率⾮负的要求；其⼆是某些待求解
的函数在函数值分布上相差很⼤，因此得到的平均适应度可能不利于体现种群的平均性，影响算法的性能。
②若⽬标函数为最⼩问题，则
maxmax(),()(())0
cfxfxcFitfx-
式中maxc为f(x)的最⼤值估计。反之，则minmin
(),
()(())0fxcfxcFitfx->?=??其他
minc为f(x)的最⼩值估计
这种⽅法是第⼀种⽅法的改进，称为“界限构造法”，但maxcminc的
构造与选择困难。
③若⽬标函数取为最⼩问题：
1(())0,()01()Fitfxccfxcfx=≥+≥++
若⽬标函数为最⼤问题：
1
(())0,()01()Fitfxccfxcfx=≥-≥+-
这种⽅法与2相似，c为⽬标函数界限的保守估计值
2.适应度函数的作⽤
在选择操作时会出现以下问题：
①在遗传进化的初期，通常会产⽣⼀些超常的个体，若按照⽐例选择法，这些异常个体因竞争⼒太突出⽽控制了选择过程，
影响算法的全局优化进程。
②在遗传进化的后期，即算法接近收敛时由于种群中个体适应度较⼩时，继续优化的潜能降低，可能获得某个局部最优解。
上述问题我们称为遗传算法的欺骗问题。适应度函数设计不当有可能造成这种问题的出现。
3.适应度函数的确定