文档介绍：第8章进化算法
—遗传算法
1
遗传算法简介
遗传算法的发展
发展历史
20世纪60年代初,美国Michigan大学Holland
教授开始研究自然和人工系统的自适应行为,意
识到用群体方法搜索以及选择、交叉、变异等操
作策略的重要性;Bagley发明“遗传算法”一词。
1968—1971年,Holland教授提出重要的模式
理论,并实现了遗传算法进化过程的计算机模拟;
1975年,遗传算法发展史上的两块里程碑诞生:
一是,Holland 教授出版了经典著作《自然系统
2
和人工系统的自适应性》,首次明确提出遗传算
法的概念;二是,DeJong完成了具有指导意义
的博士论文《遗传自适应系统的行为分析》,深
入领会了模式定理,他的研究工作为遗传算法及
其应用打下了坚实的基础,得到的结论至今仍具
普遍的指导意义。
1981年,Bridge在她的博士论文中研究了6种复
制策略,目的是克服DeJong的轮盘赌复制操作
中的随机误差。
1989年,Holland的学生Goldberg出版了专著
《搜索、优化和机器学习中的遗传算法》,系统
总结了遗传算法的主要研究结果,奠定了现代遗
传算法的科学基础。引用率最高。
3
1991年,Davis编辑出版了《遗传算法手册》,
为推广和普及遗传算法的应用起到了重要的指导
作用。
20世纪90年代以来,遗传算法在各领域得到持续
广泛的应用。
遗传算法是一种基于自然选择和基因遗传学原理
的优化搜索方法。
创立目的
抽象和严谨解释自然界的适应过程;
将自然生物系统的进化机理运用到工程系统、计
算机系统或商业系统等人工系统的设计中。
4
遗传算法的生物遗传学基础
生物进化的三个因素
遗传、变异、选择。
遗传:指生物把它的特性、形状传给子代,使得
后代在这些特性、形状上总是和亲代相似;是生
物进化的基础。
变异:指子代和亲代总是存在某些不相似的现象;
是生物个体间相互区别的基础,为生物的进化、
发展创造了条件。
选择:指择优的能力;决定生物进化的方向。
5
遗传算法的基本思想
遗传算法是基于自然选择和基因遗传学原理的搜
索算法,它将“优胜劣汰,适者生存”的生物进
化原理引入能够表征待优化参数的编码串(个体)种
群中,按照一定的适应度函数及一系列遗传操作
对各个体进行筛选,从而使适应度高的个体被保
留下来,组成新的种群,新种群中包含了上一代
的大量信息,并且引入了优于上一代的新个体。
如此周而复始,种群中各个体的适应度不断提高,
直至满足一定的终止条件。此时,种群中适应度
最高的个体即为待优化参数的最优解。
以上工作原理,使其能够在复杂空间进行全局优
化搜索,并且具有较强的鲁棒性;对于搜索空间,
基本无需限制性的假设(如连续、可微、单峰值等)。
6
遗传算法的基本操作
Holland教授的遗传算法,通常称为简单遗传算
法,也称标准遗传算法或基本遗传算法。
操作简单、作用强大。
三个基本操作
复制
交叉
变异。
7
几个基本术语
适配值函数:在生物遗传和进化的过程中,对生
物环境适应程度较高的物种将有更多的繁殖机会。
对于遗传算法而言,度量个体适应程度的函数称
为适应度函数,也称为适配值函数。适应度值也
称为适配值。
目标函数:通常指实际问题中期望优化的性能指
标函数,故也称性能指标(函数)。
在遗传算法中,染色体、位串均等同于个体。
8
复制
从一个初始种群(旧种群)中选择生命力强的个体
(位串)产生新种群的过程。
实现思路
定义一个判别指标(也即适配值函数)作为个体位串
的复制向导,决定每个位串被复制还是被淘汰、
以及被复制的数量。
注:判别指标实际上是一个能够表征种群中每个个体适应能力的
量度函数;通常,可通过人们期望优化的性能指标转化得来;根
据达尔文的适者生存理论,个体位串的复制意味着具有较高适配
值的位串更有可能在下一代中产生一个或多个子孙。
9
初始种群的产生方法
随机产生法。
如:掷硬币20次,可产生大小为𝑛= 4的一个初
始种群(“1”表示正面,“0”表示反面):
位串1:01101
位串2:11000 本代第2个个体(染色体)
位串3:01000 每一位称