【人工智能_人工智能导论课件】第6章遗传算法及其应用导论.ppt
《【人工智能_人工智能导论课件】第6章遗传算法及其应用导论.ppt》由会员分享,可在线阅读,更多相关《【人工智能_人工智能导论课件】第6章遗传算法及其应用导论.ppt(63页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、第 6 章 遗传算法及其应用,教材: 王万良人工智能导论(第3版) 高等教育出版社,第6章 遗传算法及其应用,遗传算法(GA)是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域,是21世纪有关智能计算中的重要技术之一。 本章首先详细介绍遗传算法的基本算法,然后介绍双倍体、双种群、自适应等比较典型的改进遗传算法,最后简单介绍了遗传算法在生产调度中的应用。在此基础上,读者可以进一步学习遗传算法以及其他进化算法的内容。,2,第6章 遗传算法及其应用,6.1 遗传算
2、法的产生与发展 6.2 遗传算法的基本算法 6.3 遗传算法的改进算法 6.4 遗传算法的应用,3,第6章 遗传算法及其应用,6.1 遗传算法的产生与发展 6.2 遗传算法的基本算法 6.3 遗传算法的改进算法 6.4 遗传算法的应用,4,6.1 遗传算法的产生与发展,遗传算法(genetic algorithms,GA):一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。 遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域。,5,6.1 遗传算法的产生与发展,6.1.1 遗传算法的生物背景 6.1.2 遗产
3、算法的基本思想 6.1.3 遗产算法的发展历史 6.1.4 设计遗产算法的基本原则与内容,6,6.1.1 遗传算法的生物学背景,适者生存:最适合自然环境的群体往往产生了更大的后代群体。 生物进化的基本过程:,染色体(chromosome):生物的遗传物质的主要载体。 基因(gene):扩展生物性状的遗传物质的功能单元和结构单位。 基因座(locus):染色体中基因的位置。 等位基因(alleles):基因所取的值。,7,6.1.2 遗传算法的基本思想,8,6.1.2 遗传算法的基本思想,遗传算法的基本思想: 在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解。,9,6.1.3
4、 遗传算法的发展历史,1962年,Fraser提出了自然遗传算法。 1965年,Holland首次提出了人工遗传操作的重要性。 1967年,Bagley首次提出了遗传算法这一术语。 1970年,Cavicchio把遗传算法应用于模式识别中。 1971年,Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。 1975年,美国J. Holland出版了自然系统和人工系统的适配;DeJong完成了重要论文遗传自适应系统的行为分析。 20世纪80年代以后,遗传算法进入兴盛发展时期。,10,6.1.4 遗传算法设计的基本内容,11,第6章 遗传算法及其应用,
5、6.1 遗传算法的产生与发展 6.2 遗传算法的基本算法 6.3 遗传算法的改进算法 6.4 遗传算法的应用,12,6.2 遗传算法的基本算法,遗传算法的五个基本要素: 参数编码 初始群体的设定 适应度函数的设计 遗传操作设计 控制参数设定,13,6.2 遗传算法的基本算法,6.2.1 编码 6.2.2 群体设定 6.2.3 适应度函数 6.2.4 选择 6.2.5 交叉 6.2.6 变异 6.2.7 遗传算法的一般步骤,14,6.2.1 编码,位串编码,一维染色体编码方法:将问题空间的参数编码为一维排列的染色体的方法。,二进制编码:用若干二进制数表示一个个体,将原问题的解空间映射到位串空间
6、B=0,1上,然后在位串空间上进行遗传操作。,(1) 二进制编码,15,6.2.1 编码,(1) 二进制编码(续),优点: 类似于生物染色体的组成,算法易于用生物遗传理论解释,遗传操作如交叉、变异等易实现;算法处理的模式数最多。,缺点: 相邻整数的二进制编码可能具有较大的Hamming距离,降低了遗传算子的搜索效率。 15:01111 16: 10000 要先给出求解的精度。 求解高维优化问题的二进制编码串长,算法的搜索效率低。,16,6.2.1 编码,位串编码 (2) Gray 编码,Gray编码:将二进制编码通过一个变换进行转换得到的编码。,17,6.2.1 编码,2. 实数编码,采用实数
7、表达法不必进行数制转换,可直接在解的表现型上进行遗传操作。 多参数映射编码的基本思想:把每个参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体。 多参数映射编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围。,18,初始种群的产生,6.2.2 群体设定,(1)根据问题固有知识,把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。 (2)随机产生一定数目的个体,从中挑选最好的个体加到初始群体中。这种过程不断迭代,直到初始群体中个体数目达到了预先确定的规模。,19,2. 种群规模的确定,6.2.2 群体设定,模式定理表明:若群体规模
8、为M,则遗传操作可从这M 个个体中生成和检测 个模式,并在此基础上能够不断形成和优化积木块,直到找到最优解。,群体规模太小,遗传算法的优化性能不太好,易陷入局部最优解。 群体规模太大,计算复杂。,20,将目标函数映射成适应度函数的方法,6.2.3 适应度函数,若目标函数为最大化问题,则 若目标函数为最小化问题,则,将目标函数转换为求最大值的形式,且保证函数值非负!,若目标函数为最大化问题,则 若目标函数为最小化问题,则,21,适应度函数的尺度变换,在遗传算法中,将所有妨碍适应度值高的个体产生,从而影响遗传算法正常工作的问题统称为欺骗问题(deceptive problem)。,6.2.3 适应
9、度函数,过早收敛:缩小这些个体的适应度,以降低这些超级个体的竞争力。,停滞现象:改变原始适应值的比例关系,以提高个体之间的竞争力。,适应度函数的尺度变换(fitness scaling)或者定标:对适应度函数值域的某种映射变换。,22,适应度函数的尺度变换(续),(1)线性变换:,6.2.3 适应度函数,满足,23,适应度函数的尺度变换(续),(2)幂函数变换法:,6.2.3 适应度函数,(3)指数变换法:,24,6.2.4 选择,个体选择概率分配方法 选择操作也称为复制(reproduction)操作:从当前群体中按照一定概率选出优良的个体,使它们有机会作为父代繁殖下一代子孙。 判断个体优良
10、与否的准则是各个个体的适应度值:个体适应度越高,其被选择的机会就越多。,25,6.2.4 选择,个体选择概率分配方法 (1)适应度比例方法(fitness proportional model)或蒙特卡罗法(Monte Carlo),各个个体被选择的概率和其适应度值成比例。,个体 被选择的概率为:,26,6.2.4 选择,1. 个体选择概率分配方法 (2) 排序方法 (rank-based model), 线性排序:J. E. Baker,群体成员按适应值大小从好到坏依次排列: 个体 按转盘式选择的方式选择父体,27,6.2.4 选择,1. 个体选择概率分配方法 (2) 排序方法 (rank-
11、based model), 非线性排序: Z. Michalewicz,将群体成员按适应值从好到坏依次排列,并按下式分配选择概率:,28,6.2.4 选择,1.个体选择概率分配方法 (2) 排序方法 (rank-based model),可用其他非线性函数来分配选择概率,只要满足以下条件:,29,6.2.4 选择,2. 选择个体方法 (1)转盘赌选择(roulette wheel selection),按个体的选择概率产生一个轮盘,轮盘每个区的角度与个体的选择概率成比例。 产生一个随机数,它落入转盘的哪个区域就选择相应的个体交叉。,第1轮产生一个随机数:0.81,第2轮产生一个随机数:0.32
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 人工智能_人工智能导论课件 人工智能 导论 课件 遗传 算法 及其 应用
限制150内