遗传算法原理与应用课件

输出结果并结束
是否满足停止准则
否
计算个体适应度值
比例选择运算
单点交叉运算
基本位突变运算
产生新一代群体
2、基本遗传算法的组成
（1）（产1）生编初始码种群 （2）（产2）生编初码始种群 （（33））适适应值度函函数数
（4）遗传算子 （5）选择策略 （6）停止准则
（1）编 码
遗传算法是通过某种编码机制把 对象抽象为由特定符号按一定顺序排 成的串。正如研究生物遗传是从染色 体着手，而染色体则是由基因排成的 串。SGA使用二进制串进行编码。
一、生物学知识点 二、遗传算法概述 三、遗传算法原理 四、遗传算法应用
一、生物学知识点
1.1达尔文的自然选择说(the theory of natural selection )
➢ 遗传（heredity）：子代和父代具有相同或相似 的性状，保证物种的稳定性；
➢ 变异（variation）：子代与父代，子代不同个体 之间总有差异，是生命多样性的根源；
2.4 遗传算法的操作
基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传 算法或标准遗传算法），是由Goldberg 总结出的一种最基本的遗传算法，其遗 传进化操作过程简单，容易理解，是其 它一些遗传算法的雏形和基础。
1、SGA的基本流程框图
产生初始群体
是
长链结构中占有一定位置的基本遗传单位； ➢ 基因型（genotype）：遗传因子组合的模型； ➢ 表现型（phenotype）：由染色体决定性状的外
部表现；
➢ 个体（individual）：指染色体带有特征的实体； ➢ 种群（population）：生活在一定区域的同种生
物的全部个体； ➢ 进化（evolution）：生物在其延续生存的过程中
（4）遗传算子
即遗传操作，是关于染色体的运算。遗传 算法中有三种遗传操作: ● 选择-复制(selection-reproduction) ● 交叉(crossover，有单切点和双切点交叉) ● 变异(mutation，亦称突变)
1）选择算子
➢ 遗传算法使用选择运算来实现对群体中的 个体进行优胜劣汰操作：适应度高的个体 被遗传到下一代群体中的概率大；适应度 低的个体，被遗传到下一代群体中的概率 小。
，逐渐适应其生存环境，使得其品质不断得到改良 ，这种生命现象称为进化； ➢ 适应度（fitness）：度量某个物种对于生存环境的 适应程度。对生存环境适应程度较高的物种将获得 更多的繁殖机会，而对生存环境适应程度较低的物 种，其繁殖机会就会相对较少，甚至逐渐灭绝;
➢ 选择（selection）：指决定以一定的概率从种群中选择 若干个体的操作 ；
二、遗传算法概述
2.1 遗传算法的产生
遗传算法的发展
2.2 遗传算法的基本思想
（1）产生初始种群 （2）根据问题的目标函数构造适值函数 （3）根据适值的好坏不断选择和繁殖 （4）若干代后得到适应值最好的个体即为
最优解
2.3 遗传算法的本质
遗传算法本质上是对染色体模式 所进行的一系列运算，即通过选择算 子将当前种群中的优良模式遗传到下 一代种群中，利用交叉算子进行模式 重组，利用突变算子进行模式突变。 通过这些遗传操作，模式逐步向较好 的方向进化，最终得到问题的最优解。
➢ 生存斗争和适者生存：具有适应性变异的个体被 保留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。
1.2 遗传学基本概念与术语
➢ 染色体（chromosome）：遗传物质的载体； ➢ 脱氧核糖核酸（DNA）：大分子有机聚合物，
双螺旋结构； ➢ 遗传因子（gene）数范围大。
有关术语
个体（染色体）
基因型： 解码
001000111 基因
编码
表现型： 71
在遗传算法运行时，遗传运算是对编码后的染色 体进行操作，即在编码空间操作。而染色体进行评 估与选择要在解空间进行。
（2）产生初始种群
初始种群是随机产生的，具体的 产生方式依赖于编码方法，种群的大 小依赖于计算机的计算能力和计算复 杂度。 例如：随机产生ζi∈U(0,1)
➢ 选择操作的任务就是按某种方法从父代群 体中选取一些个体，遗传到下一代群体。
2）交叉算子
所谓交叉运算，是指对两个相互配对的染 色体依据交叉概率Pc按某种方式相互交换其
部 分基因，从而形成两个新的个体。SGA中交
叉 算子采用单点交叉算子。
交叉率(crossover rate) Pc是指参加交
单点交叉运算 随机选择一个切点： 交叉前： 00000|01110000000010000 11100|00000111111000101 交叉后： 00000|00000111111000101 11100|01110000000010000
➢ 复制（reproduction）：细胞在分裂时，遗传物质DNA 通过复制而转移到新产生的细胞中，新的细胞就继承了 旧细胞的基因;
➢ 交叉（crossover）：在两个染色体的某一相同位置处 DNA被切断，其前后两串分别交叉组合形成两个新的染 色体;
➢ 变异（mutation）：在细胞进行复制时可能以很小的概 率产生某些复制差错，从而使DNA发生某种变异，产生 出新的染色体，这些新的染色体表现出新的性状;
交叉点
注：并不是所有 的被选中的父代 都有进行交叉操 作，要设定一个 交叉概率Pc，一 般取为一个较大 的数，比如0.9。
SGA二进制编码
➢ 染色体表示为：X=(x1,x2,…xn),1≤i ≤n 染色体的每一位，即xi是一个基因。每位的取值 称 为 位 值 。 n 为 染 色 体 的 长 度 。 如 ： X=
（0010010）表示一个染色体，长度为
。
➢ 适用n于三7种情况：背包问题、实优化问题、指
派问题。
➢ 缺点：编码长不利于计算。
若ζi>0.5，则xi=1 若ζi≤0.5，则xi=0
（3）适值函数
在遗传算法中，使用适值函数来表征种 群中每个个体对其生存环境的适应能力，每 个个体具有一个适应值。适应值是群体中个 体生存机会的唯一确定性指标。个体的适应 值越大，该个体被遗传到下一代的概率越大； 反之，均越小。
目标函数 f (x) 适值函数 F (x)