优化算法之遗传算法-pyy
• 70年代初,Holland提出了“模式定理”(Schema Theorem),一般认为是“遗传算法的基本定理”, 从而奠定了遗传算法研究的理论基础;
1985年,在美国召开了第一届遗传算法国际会议, 并且成立了国际遗传算法学会(ISGA, International Society of Genetic Algorithms);
• 遗传学基本概念与术语
基因型(genotype):遗传因子组合的模型,染 色体的内部表现;
表现型(phenotype):由染色体决定性状的外 部表现,基因型形成的个体;
A T C G T A
A T C A T A
• 遗传学基本概念与术语
个体(individual):指染色体带有特征的实体; 种群(population):个体的集合,该集合内个体 数称为种群的大小; 种群大小:种群中个体的数量,也叫群体规模。
遗传算法是什么? 遗传算法的思想来源是怎样的? 它由谁提出的?
遗传算法 (Genetic Algorithm,GA) 是进化计算的一个分支, GA思想源于自然界“自然选择”和“优胜劣汰”的进化规律, 是一种模拟自然界生物进化过程的随机搜索算法。 通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。 它最早由美国密歇根大学教授John H. Holland提出, 现在已经广泛应用于各种工程领域的优化问题之中。
• 达尔文 (Darwin) 的进化论
– 进化论是生物学最基本的理论之一。生物学上的所谓 进化或者演化(Evolution),旧称“天演”,是指生 物在变异、遗传与自然选择作用下的演变发展,物种 淘汰和物种产生过程。地球上原来无生命,大约在30 多亿年前,在一定的条件下,形成了原始生命,其后, 生物不断的进化,直至今天世界上存在着170多万个物 种。 – 达尔文用自然选择来解释生物进化。自然选择就是指 生物由于环境中某些因素的影响而使得有利于一些个 体的生存,而不利于另外一些个体生存的演化过程。 – 简而言之——物竞天择,适者生存
假设[Umin,Umax ]为[1, 64 ],采用 6 位二进制符号串进行编码, 则某个二进制符号串 010101 代表了数值 22 L 位二进制编码的精度为: 二进制编码的最大缺点是长度较大,当要求采用较高的精度
群体
淘汰
遗传基因重组过程
淘汰的 个体
变异
选择
新种群 交配
种群
父代染色体1 父代染色体2
生物进化过程
子代染色体1
子代染色体2
生物遗传学基础
群体
竞争
变异
子群
婚配
淘汰的 群 体
种群
• 遗传学基本概念与术语
染色体(chromosome):遗传物质的载体; 脱氧核糖核酸(DNA):大分子有机聚合物, 双螺旋结构; 遗传因子(gene):DNA或RNA长链结构中占 有一定位置的基本遗传单位;
遗传算法原理
• Holland 的模式定理提出,遗传算法的实质是通过选择、 交叉、变异的遗传算子对模式进行搜索。
• 低阶、定义长度较小且平均适应值高于群体平均适应值 的模式在群体中的比例将呈指数级增长。 • 随着进化的不断进行,较优染色体的个数将快速增加。
• 模式定理证明了遗传算法寻求全局最优解的可能性,但 不能保证算法一定能找到全局最优解。
遗传算法原理
• 积木块假设 (Building Block Hypothesi s) ,对模 式定理做了补充,说明遗传算法具有能够找到全局 最优解的能力。 • 积木块(building block) 是指低阶、定义长度较小且 平均适应值高于群体平均适应值的模式。 • 积木块假设认为在遗传算法运行过程中,积木块在 遗传算子的影响下能够相互结合,产生新的更加优 秀的积木块,最终接近全局最优解。
遗传空间
解空间
群体p(t) 选择运算 交叉运算 变异运算
编
码
个体评价
群体p(t+1)
解
码
解集合
遗传算法原理
• 在遗传算法中,问题的每个有效解被称为一个“染色体 (chromosome)” ,也称为“串”,对应于群体中的每 个生物个体( individual) 。 • 染色体的具体形式是一个使用特定编码方式生成的编码 串,编码串中的每一个编码单元称为"基因(gene)"
遗传算法
Genetic Algorithm (GA)
主要内容
• 遗传算法简介
– 基本原理 – 研究进展
• 遗传算法的流程
– 流程结构 – 应用举例
• 遗传算法的改进
– – – – 算子选择 参数设置 混合遗传算法 并行遗传算法
• 遗传算法的应用
– 遗传算法在生物信息学中的应用
遗传算法简介
1930~1947年,达尔文进化论与遗传学走向融合, Th. Dobzhansky1937年发表的《遗传学与物种起 源》是融合进化论与遗传学的代表作。 • 生物进化与智能学的关系
生物物种作为复杂系统,具有奇妙的自适应、自 组织和自优化能力,这是一种生物在进化过程中 体现的智能,也是人工系统梦寐以求的功能。
遗传算法原理
• Holland 给出了著名的模式定理 (Schema Theory) , 为遗传算法提供了理论支持。
• 模式(schema) 是指群体中编码的某些位置具有相似 结构的染色体集合。
假设染色体的编码是由 0 或 1 组成的二进制符号序列, 模式 01***0 则表示以 01 开头且以 0 结尾的编码串对应的染 色体的集合,即 {010000, 010010, 010100, 010110, 011000 , 011010 ,0 11100 , 011110} 。
• 孟德尔(Mendel) 的遗传学
– 遗传学是研究基因及它们在生物遗传中的作用的科学 分支。遗传学最早的应用在有历史记载之初就已经出 现了,即驯养动物及植物的选择育种。遗传信息以化 学方法被编码在DNA(脱氧核糖核酸)中。 – 1865年,孟德尔首先记录了豌豆某些特性的遗传模式, 表明它们遵守简单的统计学规律。由他的统计分析中, 孟德尔定义了一个概念:遗传的基本单位——等位基 因。他描述的等位基因类于现在的基因。直到孟德尔 死后,20世纪初另外的科学家重新发现这个定律之后, 孟德尔的工作的重要性才被大家了解。 – 改变一个生物的DNA从而达到某种目的被称为基因工 程。
研究内容和方向
遗传算法的流程
• 七个重要问题:
– – – – – – – 染色体的编码 群体的初始化 适应值评价 选择群体 种群交配 种群变异 算法流程 遗传空间 群体p(t)
选择运算
交叉运算 变异运算 个体评价
解空间
编
码
群体p(t+1)
解
码
解集合
染色体的编码
• 原因:遗传算法只能处理染色体,不能直接在问 题解集上进行相应操作。
遗传算法原理
• 遗传算法类似于自然进化,通过作用于染色体上的基因寻找 好的染色体来求解问题 。 • 遗传算法对求解问题的本身一无所知,它所需要的仅仅是对 算法所产生的每个染色体进行评价,并基于适应值来选择染 色体,使适应性好的染色体有更多的繁殖机会。 • 在遗传算法中,通过随机方式产生若干个所求解问题的数字 编码,即染色体,形成初始种群;通过适应度函数给每个个 体一个数值评价,淘汰低适应度的个体,选择高适应度的个 体参加遗传操作,经过遗传操作后的个体集合形成下一代新 的种群。再对这个新种群进行下一轮进化。这就是遗传算法 的基本原理。
• 应用遗传算法,需要解决问题解的表示,即染色体 的编码 • 编码:将问题结构变换为位串形式编码表示的过程;
• 解码或译码:将位串形式编码表示变换为原问题结 构的过程。
解空间
解 码
编 码
一个解的编码 染色体(chromosome)
• 编码方法
– – – – 二进制编码方法 浮点数编码方法 格雷码(Gray) 符号编码
遗传算法原理
• 模式的阶(schema order) : 模式中具有确定取值的
基因个数。
如模式 01***0 的阶为 3
• 模式的定义长度(schemad defining length) 是指
模式中第一个具有确定取值的基因到最后一个具有
确定取值的基因的距离,
例如模式 01***0的定义长度为5 而模式*1****的定义长度为 0
• 二进制编码方法
二进制编码方法产 生的染色体是一个 二进制符号序列, 染色体的每一个基 因只能取值 0 或 1 。 假定问题定义的有效解取值空间为 [Umin,Umax ], 其中 D为有 效解的变量维数,使用 L 位二进制符号串表示解的一维变 量 ,则我们可以得到如表 4. 2 所示的编码方式:
• 产生
60年代中期,美国Michigan大学的J. H. Holland教 授提出借鉴生物自然遗传的基本原理用于自然 和人工系统的自适应行为研究和串编码技术;
1967年,他的学生J. D. Bagley在博士论文中首次提 出“遗传算法(Genetic Algorit版了著名的“Adaptation in Natural and Artificial Systems”,标志遗传算法的 诞生。
• 遗传学基本概念与术语
进化(evolution):生物在其延续生存的过程 中,逐渐适应其生存环境,使得其品质不断得 到改良,这种生命现象称为进化; 适应度(fitness):个体性能的数量值,度量某 个物种对于生存环境的适应程度。对生存环境 适应程度较高的物种将获得更多的繁殖机会, 而对生存环境适应程度较低的物种,其繁殖机 会就会相对较少,甚至逐渐灭绝;
• 遗传算法通过比较适应值(fitness value) 区分染色体的 优劣,适应值越大的染色体越优秀。