第7章遗传算法及其应用.ppt
《第7章遗传算法及其应用.ppt》由会员分享,可在线阅读,更多相关《第7章遗传算法及其应用.ppt(79页珍藏版)》请在三一文库上搜索。
1、第 7 章 遗传算法及其应用,2,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,3,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,4,7.1 遗传算法的产生与发展,遗传算法(genetic algorithms,GA):一类借鉴生物界自然选择和自然遗传机制的随机搜索算法,非常适用于处理传统搜索方法难以解决的复杂和非线性优化问题。 遗传算法可广泛应用于组合优化、机器学习、自适应控制、规划设计和人
2、工生命等领域。,5,7.1 遗传算法的产生与发展,7.1.1 遗传算法的生物背景 7.1.2 遗产算法的基本思想 7.1.3 遗产算法的发展历史 7.1.4 设计遗产算法的基本原则与内容,6,7.1.1 遗传算法的生物学背景,适者生存:最适合自然环境的群体往往产生了更大的后代群体。 生物进化的基本过程:,染色体(chromosome):生物的遗传物质的主要载体。 基因(gene):扩展生物性状的遗传物质的功能单元和结构单位。 基因座(locus):染色体中基因的位置。 等位基因(alleles):基因所取的值。,7,7.1.2 遗传算法的基本思想,8,7.1.2 遗传算法的基本思想,遗传算法的
3、基本思想: 在求解问题时从多个解开始,然后通过一定的法则进行逐步迭代以产生新的解。,9,7.1.3 遗传算法的发展历史,1962年,Fraser提出了自然遗传算法。 1965年,Holland首次提出了人工遗传操作的重要性。 1967年,Bagley首次提出了遗传算法这一术语。 1970年,Cavicchio把遗传算法应用于模式识别中。 1971年,Hollstien在论文计算机控制系统中人工遗传自适应方法中阐述了遗传算法用于数字反馈控制的方法。 1975年,美国J. Holland出版了自然系统和人工系统的适配;DeJong完成了重要论文遗传自适应系统的行为分析。 20世纪80年代以后,遗传
4、算法进入兴盛发展时期。,10,7.1.4 设计遗传算法的基本原则与内容,设计的基本原则:,11,设计的基本内容:,7.1.4 设计遗传算法的基本原则与内容,12,第7章 遗传算法及其应用,7.1 遗传算法的产生与发展 7.2 遗传算法的基本算法 7.3 遗传算法的改进算法 7.4 基于遗传算法的生产调度方法,13,7.2 遗传算法的基本算法,遗传算法的五个基本要素: 参数编码 初始群体的设定 适应度函数的设计 遗传操作设计 控制参数设定,14,7.2 遗传算法的基本算法,7.2.1 编码 7.2.2 群体设定 7.2.3 适应度函数 7.2.4 选择 7.2.5 交叉 7.2.6 变异 7.2
5、.7 遗传算法的一般步骤,15,7.2.1 编码,位串编码,一维染色体编码方法:将问题空间的参数编码为一维排列的染色体的方法。,二进制编码:用若干二进制数表示一个个体,将原问题的解空间映射到位串空间 B=0,1上,然后在位串空间上进行遗传操作。,(1) 二进制编码,16,7.2.1 编码,(1) 二进制编码(续),优点: 类似于生物染色体的组成,算法易于用生物遗传理论解释,遗传操作如交叉、变异等易实现;算法处理的模式数最多。,缺点: 相邻整数的二进制编码可能具有较大的Hamming距离,降低了遗传算子的搜索效率。 15:01111 16: 10000 要先给出求解的精度。 求解高维优化问题的二
6、进制编码串长,算法的搜索效率低。,17,7.2.1 编码,位串编码 (2) Gray 编码,Gray编码:将二进制编码通过一个变换进行转换得到的编码。,18,7.2.1 编码,2. 实数编码,采用实数表达法不必进行数制转换,可直接在解的表现型上进行遗传操作。 多参数映射编码的基本思想:把每个参数先进行二进制编码得到子串,再把这些子串连成一个完整的染色体。 多参数映射编码中的每个子串对应各自的编码参数,所以,可以有不同的串长度和参数的取值范围。,19,7.2.1 编码,3. 有序串编码,有序问题:目标函数的值不仅与表示解的字符串的值有关,而且与其所在字符串的位置有关。,4结构式编码,Goldbe
7、rg等提出MessyGA(mGA)的遗传算法编码方法。,20,初始种群的产生,7.2.2 群体设定,(1)根据问题固有知识,把握最优解所占空间在整个问题空间中的分布范围,然后,在此分布范围内设定初始群体。 (2)随机产生一定数目的个体,从中挑选最好的个体加到初始群体中。这种过程不断迭代,直到初始群体中个体数目达到了预先确定的规模。,21,2. 种群规模的确定,7.2.2 群体设定,模式定理表明:若群体规模为M,则遗传操作可从这M 个个体中生成和检测 个模式,并在此基础上能够不断形成和优化积木块,直到找到最优解。,群体规模太小,遗传算法的优化性能不太好,易陷入局部最优解。 群体规模太大,计算复杂
8、。,22,将目标函数映射成适应度函数的方法,7.2.3 适应度函数,若目标函数为最大化问题,则 若目标函数为最小化问题,则,将目标函数转换为求最大值的形式,且保证函数值非负!,若目标函数为最大化问题,则 若目标函数为最小化问题,则,23,将目标函数映射成适应度函数的方法(续),7.2.3 适应度函数,存在界限值预选估计困难或者不能精确估计的问题!,若目标函数为最大化问题,则 若目标函数为最小化问题,则 :目标函数界限的保守估计值。,24,适应度函数的尺度变换,在遗传算法中,将所有妨碍适应度值高的个体产生,从而影响遗传算法正常工作的问题统称为欺骗问题(deceptive problem)。,7.
9、2.3 适应度函数,过早收敛:缩小这些个体的适应度,以降低这些超级个体的竞争力。,停滞现象:改变原始适应值的比例关系,以提高个体之间的竞争力。,适应度函数的尺度变换(fitness scaling)或者定标:对适应度函数值域的某种映射变换。,25,适应度函数的尺度变换(续),(1)线性变换:,7.2.3 适应度函数,满足,26,适应度函数的尺度变换(续),(2)幂函数变换法:,7.2.3 适应度函数,(3)指数变换法:,27,7.2.4 选择,个体选择概率分配方法 选择操作也称为复制(reproduction)操作:从当前群体中按照一定概率选出优良的个体,使它们有机会作为父代繁殖下一代子孙。
10、判断个体优良与否的准则是各个个体的适应度值:个体适应度越高,其被选择的机会就越多。,28,7.2.4 选择,个体选择概率分配方法 (1)适应度比例方法(fitness proportional model)或蒙特卡罗法(Monte Carlo),各个个体被选择的概率和其适应度值成比例。,个体 被选择的概率为:,29,7.2.4 选择,1. 个体选择概率分配方法 (2) 排序方法 (rank-based model), 线性排序:J. E. Baker,群体成员按适应值大小从好到坏依次排列: 个体 按转盘式选择的方式选择父体,30,7.2.4 选择,1. 个体选择概率分配方法 (2) 排序方法
11、(rank-based model), 非线性排序: Z. Michalewicz,将群体成员按适应值从好到坏依次排列,并按下式分配选择概率:,31,7.2.4 选择,1.个体选择概率分配方法 (2) 排序方法 (rank-based model),可用其他非线性函数来分配选择概率,只要满足以下条件:,32,7.2.4 选择,2. 选择个体方法 (1)转盘赌选择(roulette wheel selection),按个体的选择概率产生一个轮盘,轮盘每个区的角度与个体的选择概率成比例。 产生一个随机数,它落入转盘的哪个区域就选择相应的个体交叉。,第1轮产生一个随机数:0.81,第2轮产生一个随机
12、数:0.32,33,7.2.4 选择,2. 选择个体方法 (2)锦标赛选择方法(tournament selection model),锦标赛选择方法:从群体中随机选择个个体,将其中适应度最高的个体保存到下一代。这一过程反复执行,直到保存到下一代的个体数达到预先设定的数量为止。,随机竞争方法(stochastic tournament):每次按赌轮选择方法选取一对个体,然后让这两个个体进行竞争,适应度高者获胜。如此反复,直到选满为止。,34,7.2.4 选择,2. 选择个体方法 (3) 和 选择,从规模为 的群体中随机选取个体通过重组和变异生成 个后代, 再选取 个最优的后代作为新一代种群。,
13、从 个后代与其父体共 中选取 个最优的后代。,35,7.2.4 选择,2. 选择个体方法 (4)Boltzmann锦标赛选择,最佳个体(elitist model)保存方法:把群体中适应度最高的个体不进行交叉而直接复制到下一代中,保证遗传算法终止时得到的最后结果一定是历代出现过的最高适应度的个体。,(5)最佳个体保存方法,随机选取两个个体 ,若 则选择适应值好的作为胜者,否则计算概率 ,若 ,选择差解,否则选择好解。,36,7.2.5 交叉,1. 基本的交叉算子 (1)一点交叉(single-point crossover),一点交叉:在个体串中随机设定一个交叉点,实行交叉时,该点前或后的两个
14、个体的部分结构进行互换,并生成两个新的个体。,二点交叉:随机设置两个交叉点,将两个交叉点之间的码串相互交换。,(2)二点交叉 (two-point crossover),37,7.2.5 交叉,基本的交叉算子(续),均匀交叉:按照均匀概率抽取一些位,每一位是否被选取都是随机的,并且独立于其他位。然后将两个个体被抽取位互换组成两个新个体。,(3)均匀交叉(uniform crossover)或一致交叉,38,7.2.5 交叉,2. 修正的交叉方法 (1)部分匹配交叉PMX:Goldberg D. E.和R. Lingle(1985),39,7.2.5 交叉,2. 修正的交叉方法(续) (2)顺序
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 遗传 算法 及其 应用
链接地址:https://www.31doc.com/p-2987720.html