《高等运筹学7.ppt》由会员分享,可在线阅读,更多相关《高等运筹学7.ppt(24页珍藏版)》请在三一文库上搜索。
1、第7章 遗传算法 生物进化表现为“适者生存,不适者被淘汰” 一类新型的全局优化技术仿生类算法: 遗传算法(Genetic Algorithms, GA) 仿生过程算法: 演化策略 进化程序 仿生结构算法: 人工神经网络 仿生行为算法: 蚁群优化算法 戌 绎 径 草 蜕 搁 妒 紧 宫 韧 澄 猩 竿 愚 惰 绒 滦 孕 般 碱 贤 瓢 确 进 亡 喻 搜 岳 稚 弱 狡 命 高 等 运 筹 学 7 高 等 运 筹 学 7 1 1 主要内容 7.1 生物进化和遗传学基本知识概述 7.2 遗传算法描述 7.3 遗传算法的关键参数和操作设计 姓 嫁 硼 乙 嘘 僳 哲 旋 代 怨 逾 助 侵 抛 慈
2、 媚 自 涧 这 旷 甭 傣 谢 谰 熔 掀 玫 超 锹 颤 患 滥 高 等 运 筹 学 7 高 等 运 筹 学 7 2 2 7.1 生物进化和遗传学基本知识概述 1.达尔文自然选择学说 自然选择学说主要包括以下三个方面:自然选择学说主要包括以下三个方面: (1)(1)遗传父代通过繁殖把生物信息传给子代,子遗传父代通过繁殖把生物信息传给子代,子 代按照所得信息而发育、分化代按照所得信息而发育、分化 (2)(2)变异随机发生,变异的选择和积累是生命多变异随机发生,变异的选择和积累是生命多 样性的根源样性的根源 (3)(3)生存斗争和适者生存生存斗争和适者生存 繁殖繁殖是现存物种得以生存、延续的必
3、要条件;是现存物种得以生存、延续的必要条件; 变异变异是生物进化的根本保证;是生物进化的根本保证; 在竞争的环境下,自然界不可避免地会对生物的在竞争的环境下,自然界不可避免地会对生物的 生存进行生存进行选择选择 季 闪 绘 踩 脾 赣 钎 稻 抖 滞 嫂 娱 枚 轮 扇 如 真 刃 师 斌 坡 淹 霸 旁 哥 笑 践 偷 礼 姚 何 袭 高 等 运 筹 学 7 高 等 运 筹 学 7 3 3 物种被后代所继承的就是那些更能适应环境的个体 特征 生物进化:是遗传与变异相互作用的结果 遗传的主要物质是细胞核中染色体上的基因 基因结构:基因位置的排列 基因结构的性质及其与物种的关系: 基因结构物种
4、稳健性 差异性 变易性 稳定性 多样性 进化 通过优胜劣汰的自然选择,适应值高的基因结构就 被保存下来 劳 瑞 淋 湿 俯 曰 荷 矽 锁 襟 扔 笼 啄 畴 耕 醛 漆 惨 这 簇 炽 曳 彼 筑 出 坷 钓 膨 臂 绚 乞 苑 高 等 运 筹 学 7 高 等 运 筹 学 7 4 4 2.现代综合进化论 用统计生物学和用统计生物学和种群遗传学种群遗传学的成就重新解释达尔文的成就重新解释达尔文 的自然选择理论的自然选择理论 种群遗传学:研究种群中基因的组成及其变化种群遗传学:研究种群中基因的组成及其变化 种群:在一定地域中,一个物种的全体成员构成一种群:在一定地域中,一个物种的全体成员构成一
5、个种群个种群 生物的进化实际上是种群的进化,个体总是要消亡生物的进化实际上是种群的进化,个体总是要消亡 ,但种群则可以继续保留,但种群则可以继续保留 每一代中个体基因结构的改变会影响种群基因库的每一代中个体基因结构的改变会影响种群基因库的 组成,而种群基因库组成的变化就是这个种群的进组成,而种群基因库组成的变化就是这个种群的进 化化 通过个体繁殖机会的差异,也能造成后代遗传组成通过个体繁殖机会的差异,也能造成后代遗传组成 的改变,自然选择也能够进行的改变,自然选择也能够进行 庙 讨 痉 包 谚 霄 瞬 沼 哩 碳 呛 洲 恫 每 姚 倍 雄 蔚 团 绅 郧 哪 篡 否 式 峭 囤 纱 姚 啦
6、梧 磋 高 等 运 筹 学 7 高 等 运 筹 学 7 5 5 生物进化的基本过程: 种群 被淘汰的 子种群 获繁殖机会 的子种群 子代种群 选择 变异 婚配 (新一代) 陶 处 铃 笑 埋 勘 巫 乓 棕 试 抡 渤 滓 距 质 扯 荤 收 沫 龙 挠 熬 雇 粱 鹏 番 爸 集 啮 瞅 粳 尝 高 等 运 筹 学 7 高 等 运 筹 学 7 6 6 归纳: 生物的进化表现为生物的进化表现为“适者生存,不适者被淘汰适者生存,不适者被淘汰” 最适合自然环境的种群往往产生了更大的后代种群最适合自然环境的种群往往产生了更大的后代种群 生物进化是生物进化是遗传遗传和和变异变异相互作用的结果相互作用的
7、结果 遗传是通过父代对子代的基因传递来实现;遗传是通过父代对子代的基因传递来实现; 某些遗传信息的改变决定了生物的变异某些遗传信息的改变决定了生物的变异 3. 3. 基本概念和术语基本概念和术语 染色体染色体( (chromosome)chromosome): 是遗传物质的主要载体是遗传物质的主要载体 ,由多个基因,由多个基因( (遗传因子遗传因子) )组成组成 DNA(DNA(脱氧核糖核酸脱氧核糖核酸) ):构成染色体的主要物质:构成染色体的主要物质 基因基因( (gene)gene):染色体上具有遗传效应的:染色体上具有遗传效应的DNADNA片段片段. . 委 英 渣 榜 枫 摈 沛 中
8、穿 胆 蝴 搞 列 糙 舱 悄 痢 屁 迫 菊 涌 湛 哪 辱 罩 魏 注 坞 詹 迫 郧 熊 高 等 运 筹 学 7 高 等 运 筹 学 7 7 7 基因型(genotype):基因组合的模型,染色体的 内部表现,它决定了个体的外部表现 表现型(phenotype):由染色体决定的个体的外 部表现,即根据基因型形成的个体 基因座(locus):基因在染色体中所占据的位置 个体(individual):指染色体带有特征的实体 种群(population):个体的集合称为种群该集 合内个体的数目称为种群的规模 进化(evolution):生物在其延续生存的过程中, 逐渐适应其生存环境,使得其品质
9、不断得到改良, 这种生命现象称为进化生物的进化是以种群的形 式进行的 适应度(fitness):度量某个物种对于生存环境的 适应程度 脆 糜 肤 这 妥 给 濒 阀 咏 饰 芯 可 归 的 养 释 偶 葛 渊 铅 搔 牌 酗 挺 靶 炮 途 鸯 护 磺 卧 鸯 高 等 运 筹 学 7 高 等 运 筹 学 7 8 8 选择(selection):指以一定的概率从种群中选择 若干个体的操作 复制(reproduction):生物的繁殖过程是由其基 因的复制过程来完成的 交叉(crossover):指有性生殖生物在繁殖下一 代时,两个同源染色体之间通过交叉而重组 变异(mutation):在细胞进行
10、复制时可能以很小 的概率产生某些复制差错,从而使DNA发生某种变 异 编码(coding):DNA中遗传信息的模式排列遗 传编码可以看作从表现型到基因型的映射 解码(decoding):从基因型到表现型的映射 斟 跨 死 俄 腾 宴 晓 扇 皑 坷 昆 痛 缕 岂 习 哗 告 篓 痢 具 戒 迎 篓 奔 莉 苦 缎 眶 安 换 谓 闭 高 等 运 筹 学 7 高 等 运 筹 学 7 9 9 7.2 遗传算法描述 1.生物遗传概念与优化问题的对应关系 生物遗传概念 在优化问题中表示的概念 个体 染色体 基因 个体适应度 种群 生物进化过程 适者生存 复制 交叉 变异 一个可行解 解的编码(字符串
11、、向量等),即解的表示形式 解中每一分量的特征(如各分量的值) 解的目标函数值或所对应的适应函数值 多个可行解组成的集合,其个数称为种群规模 求解的迭代过程 目标函数值越好的解,被选择作为下一迭代过程的 当前解的可能性越大 根据目标函数值的优劣选取的一组解 将一对解中的部分分量的取值对换 改变一个解中某一分量的取值 艰 扭 脑 注 蹄 邹 敦 湍 竞 流 羡 遭 截 卜 台 预 死 雁 毗 悟 用 痔 你 颓 瘤 韵 耀 厢 茵 所 骆 架 高 等 运 筹 学 7 高 等 运 筹 学 7 1010 2.算法思想 从优化问题的一个种群(一组可行解)开始,按照从优化问题的一个种群(一组可行解)开始
12、,按照 适者生存和优胜劣汰的原理,逐代适者生存和优胜劣汰的原理,逐代(generationgeneration) 演化产生出越来越好的一个种群(一组可行解)演化产生出越来越好的一个种群(一组可行解) 在每一代,根据个体(可行解)的适应度(目标函在每一代,根据个体(可行解)的适应度(目标函 数值)的优劣挑选一部分优良个体复制(繁殖)到数值)的优劣挑选一部分优良个体复制(繁殖)到 下一代,并对其进行交叉和变异操作,产生出代表下一代,并对其进行交叉和变异操作,产生出代表 新的解集合的种群新的解集合的种群 这个过程将导致种群像自然进化一样的子代种群比这个过程将导致种群像自然进化一样的子代种群比 父代更
13、加适应于环境(即新可行解比旧可行解更接父代更加适应于环境(即新可行解比旧可行解更接 近问题的最优解),整个进化过程中的最优个体就近问题的最优解),整个进化过程中的最优个体就 作为问题的最终解作为问题的最终解 宣 邦 韦 涯 淖 鼻 适 奋 疫 响 肚 分 骗 意 伙 慨 怖 试 迢 汕 灿 缀 衬 鼻 师 踌 招 缕 仙 很 樊 赤 高 等 运 筹 学 7 高 等 运 筹 学 7 1111 3.算法步骤 确定解的编码方案 随机产生初始种群 计算各个体的适应度 按适应度大小执行复制操作 random0,1Pc? 执行交叉操作 random0,1Pm? 执行变异操作 终止准则满足否? 输出结果 Y
14、 Y Y N N N 敷 骄 宪 扎 芭 蛙 栗 帽 词 狈 呜 刚 夜 位 伞 给 戮 创 变 散 惮 显 巷 拄 诈 喷 仇 载 孰 裂 逸 饥 高 等 运 筹 学 7 高 等 运 筹 学 7 1212 5.遗传算法的特点 与其它优化算法相比具有如下特点:与其它优化算法相比具有如下特点: (1)(1)GAGA以决策变量的编码作为运算对象以决策变量的编码作为运算对象 (2)(2)GAGA只用适应度函数值作为搜索信息只用适应度函数值作为搜索信息 (3)(3)GAGA同时使用多个搜索点的搜索信息具有隐含同时使用多个搜索点的搜索信息具有隐含 并行性并行性 (4)(4)GAGA使用概率搜索技术使用概
15、率搜索技术 峨 东 匣 蹬 校 耻 修 韦 惑 皆 猛 掩 啃 欧 韩 敌 虚 魁 蜀 尺 债 咋 渭 息 扒 过 婚 赔 种 碳 亡 淬 高 等 运 筹 学 7 高 等 运 筹 学 7 1313 7.3 遗传算法的关键参数和操作设计 1.编码 将问题的可行解用一种编码来表示称一个解的将问题的可行解用一种编码来表示称一个解的 编码为一个编码为一个染色体染色体,组成编码的元素称为,组成编码的元素称为基因基因 编码是设计编码是设计GAGA时要解决的首要问题,是影响算法时要解决的首要问题,是影响算法 性能与效率的重要因素性能与效率的重要因素 决定了个体的染色体排列形式决定了个体的染色体排列形式 决定
16、了个体从搜索空间的基因型变换到解空间的决定了个体从搜索空间的基因型变换到解空间的 表现型时的解码方法表现型时的解码方法 影响到交叉、变异等遗传算子的运算方法影响到交叉、变异等遗传算子的运算方法 如何设计一种完美的编码方案一直是遗传算法的如何设计一种完美的编码方案一直是遗传算法的 应用难点之一应用难点之一 迂 眩 弘 可 相 壤 抨 要 萄 柜 影 福 灌 暴 奠 预 钡 钒 妈 投 彪 粉 冻 侗 疼 品 烁 唁 侩 腺 位 积 高 等 运 筹 学 7 高 等 运 筹 学 7 1414 常用的两种编码方法: 二进制编码方法:是GA中最常用的一种编码方法, 使用的编码符号集是0,1 符号编码方法
17、:染色体编码串中的基因值取自一个 无数值含义、而只有代码含义的符号集如A, B, C, D, ;1, 2, 3, 4, ;A1, A2, A3, 等等 例如,对于例如,对于TSPTSP问题,假设有问题,假设有n n个城市分别记个城市分别记 为为C C 1 1 , , C C 2 2 , , , , C C n n ,将各个城市的代号按其被访问的,将各个城市的代号按其被访问的 顺序连接在一起,就可构成一个表示旅行路线的个顺序连接在一起,就可构成一个表示旅行路线的个 体如体如 X X: C C 1 1 , , C C 2 2 , , , , C C n n 若将各个城市按其代号的下标进行编号,则这
18、个个若将各个城市按其代号的下标进行编号,则这个个 体也可表示为体也可表示为 X X:1, 2, , 1, 2, , n n 沃 痪 轻 生 巍 些 肿 窑 鸟 垦 贯 娟 克 线 织 络 么 屹 羽 牵 鬃 锣 伶 坞 甄 出 雨 唯 秆 援 渣 鬃 高 等 运 筹 学 7 高 等 运 筹 学 7 1515 2.适应度函数 度量个体适应度的函数称为适应度函数度量个体适应度的函数称为适应度函数 GAGA仅使用适应度函数值,就可确定进一步的搜索仅使用适应度函数值,就可确定进一步的搜索 方向和搜索范围方向和搜索范围 适应度函数的值必须为正值适应度函数的值必须为正值 适应度函数的设计要结合问题本身的要
19、求而定:适应度函数的设计要结合问题本身的要求而定: 可以直接利用目标函数作为适应度函数;可以直接利用目标函数作为适应度函数; 适应度函数是由目标函数变换而成适应度函数是由目标函数变换而成 3.3.种群设定种群设定 种群的规模:一般建议取种群的规模:一般建议取2020100100之间在优化过之间在优化过 程中可以保持确定不变,也可以是动态变化的程中可以保持确定不变,也可以是动态变化的 初始种群的选取:应随机产生初始种群的选取:应随机产生 脓 晴 坦 掂 郝 炮 羔 巨 她 投 舱 忆 玛 磕 允 储 神 德 丁 侧 惹 捎 涵 已 豆 瘤 硅 劈 阁 基 诣 物 高 等 运 筹 学 7 高 等
20、运 筹 学 7 1616 4.选择算子 指从种群中选择优良个体、淘汰劣质个体的操作指从种群中选择优良个体、淘汰劣质个体的操作 (1)(1)比例选择算子比例选择算子个体被选中并被复制到下一代种个体被选中并被复制到下一代种 群中的概率与该个体的适应度大小成正比也叫做群中的概率与该个体的适应度大小成正比也叫做 赌盘选择具体执行过程是:赌盘选择具体执行过程是: 计算个体计算个体i i被选中遗传到下一代的概率被选中遗传到下一代的概率 模拟赌盘操作来确定各个个体被选中的次数模拟赌盘操作来确定各个个体被选中的次数 (2)(2)最佳个体最佳个体( (精英精英) )保存策略保存策略把种群中适应度最高把种群中适应
21、度最高 的个体不参与交叉和变异运算,而直接复制到下一的个体不参与交叉和变异运算,而直接复制到下一 代种群中这种选择操作又称为复制代种群中这种选择操作又称为复制 剐 桌 掐 尼 鸳 冗 站 戮 泽 皋 壮 象 及 岛 汰 叙 孰 肩 缎 直 午 庄 掉 滨 例 褒 农 眩 太 才 讯 祖 高 等 运 筹 学 7 高 等 运 筹 学 7 1717 5.交叉概率与交叉算子 生物进化过程中起核心作用的是遗传基因的重组生物进化过程中起核心作用的是遗传基因的重组 遗传算法中起核心作用的是交叉操作,即把两个遗传算法中起核心作用的是交叉操作,即把两个 相互配对的染色体按某种方式相互交换其部分基相互配对的染色体
22、按某种方式相互交换其部分基 因,从而形成两个新个体因,从而形成两个新个体 (1)(1)交叉概率交叉概率( (P P c c ) )用于控制种群中参与交叉操作用于控制种群中参与交叉操作 的个体的数量一般的个体的数量一般P P c c =0.4=0.40.990.99 (2)(2)交叉算子交叉算子一般要求是既不能太多地破坏个体一般要求是既不能太多地破坏个体 编码串中表示优良性状的基因结构,又要能够有编码串中表示优良性状的基因结构,又要能够有 效地产生出一些较多的新个体效地产生出一些较多的新个体 对由选择操作形成的种群中的个体进行随机配对对由选择操作形成的种群中的个体进行随机配对 按预先设定的交叉概
23、率按预先设定的交叉概率P P c c 来决定每对是否需要进来决定每对是否需要进 行交叉操作行交叉操作 宏 碍 扳 肚 预 臃 港 腿 蹈 义 搭 徽 只 堡 伦 揭 蔚 悦 吁 愉 汹 惭 焚 歇 寇 贺 抗 噬 檬 峰 尸 掷 高 等 运 筹 学 7 高 等 运 筹 学 7 1818 交叉算子的设计包括: 如何确定交叉点的位置:一般是随机设定 如何进行部分基因的交换常用的方法介绍如下: (1)针对二进制编码的交叉方法 单点交叉将交叉点前面或后面的基因相互交换 父个体1: 1011001 子个体1: 1011110 父个体2: 0010110 子个体2: 0010001 双点交叉将两个交叉点之
24、间的基因相互交换 父个体1: 1011011 子个体1: 1001011 父个体2: 0001000 子个体2: 0011000 堂 漫 堂 诺 经 韵 侮 韭 馒 暑 兼 堆 盼 由 摊 贬 叔 蓄 淀 俊 长 阜 桨 殊 愁 烘 颅 包 耕 炼 毛 牡 高 等 运 筹 学 7 高 等 运 筹 学 7 1919 (2)针对符号编码的交叉方法. 符号编码给使用基本的遗传操作带来了新的问题: 交叉操作前: 父代个体1: 0 1 2 | 3 4 5 0 1 2 | 3 4 5 父代个体父代个体2 2: 0 4 3 | 2 5 1 0 4 3 | 2 5 1 交叉操作后(交叉操作后(变为非法变为非法
25、):): 子代个体子代个体1 1: 0 1 2 | 0 1 2 | 2 5 12 5 1 子代个体子代个体2 2: 0 4 3 | 0 4 3 | 3 4 5 3 4 5 逢 只 脱 兹 诬 挥 交 邵 淘 样 孝 芽 告 舶 潮 宣 件 脱 撑 堰 究 薛 台 枪 范 誓 耕 辈 哲 病 溜 劫 高 等 运 筹 学 7 高 等 运 筹 学 7 2020 部分匹配交叉(Partially Matched Crossover, Partially Matched Crossover, PMXPMX ): :交叉操作过程分两步,交叉操作过程分两步, 对个体编码串进行常对个体编码串进行常 规的双点交
26、叉操作,规的双点交叉操作,按交叉区域内各基因值间的按交叉区域内各基因值间的 映射关系来修改交叉区域之外的各个基因座的基因映射关系来修改交叉区域之外的各个基因座的基因 值。值。 交叉前:父代个体交叉前:父代个体1 1: 9 8 4 | 5 6 7 | 1 3 2 0 9 8 4 | 5 6 7 | 1 3 2 0 父代个体父代个体2 2: 8 7 1 | 2 3 0 | 9 5 4 6 8 7 1 | 2 3 0 | 9 5 4 6 交叉后:子代个体交叉后:子代个体1 1: 9 8 4 | 9 8 4 | 2 3 02 3 0 | 1 | 1 3 2 03 2 0 子代个体子代个体2 2: 8
27、8 7 7 1 | 1 | 5 6 75 6 7 | 9 | 9 5 5 4 4 6 6 映射关系映射关系:2-52-5,3-63-6,0-7 0-7 替换替换 :子代个体:子代个体1 1: 9 8 4 | 2 3 0 | 1 9 8 4 | 2 3 0 | 1 6 6 5 5 7 7 子代个体子代个体2 2: 8 8 0 0 1 | 5 6 7 | 9 1 | 5 6 7 | 9 2 2 4 4 3 3 其它交叉方法:顺序交叉(OX),循环交叉(CX)等 芯 沽 努 趴 贪 窍 逢 拳 淀 最 氖 土 照 扑 斤 敢 椎 古 迅 苔 死 师 吭 鞍 傍 臆 淹 趁 企 例 屁 最 高 等 运
28、 筹 学 7 高 等 运 筹 学 7 2121 6.变异概率与变异算子 GAGA中的变异运算,是指对个体染色体编码串中的中的变异运算,是指对个体染色体编码串中的 某些基因值作变动,从而形成一个新的个体某些基因值作变动,从而形成一个新的个体 交叉交叉运算是运算是GAGA中产生新个体的主要方法,决定了中产生新个体的主要方法,决定了 算法的全局搜索能力算法的全局搜索能力 变异变异运算是产生新个体的辅助方法,决定了算法的运算是产生新个体的辅助方法,决定了算法的 局部搜索能力局部搜索能力 (1)(1)变异概率变异概率( (P Pm m) )通常取 通常取P Pm m 0.00010.00010.10.1
29、 (2)(2)变异算子变异算子 变异算子的设计包括:变异算子的设计包括: 如何确定变异点的位置:随机确定如何确定变异点的位置:随机确定 如何进行基因值的替换:以如何进行基因值的替换:以P Pm m对这些基因座的基 对这些基因座的基 因值进行变异常用的方法如下:因值进行变异常用的方法如下: 车 绚 仔 罐 呸 突 啮 赌 斜 觉 泳 挂 田 劝 景 狞 拧 冬 桔 逃 琴 疙 垮 陆 惜 谰 钨 介 捉 疆 鸳 荒 高 等 运 筹 学 7 高 等 运 筹 学 7 2222 基本位变异把选定的基因座上的基因值取反 父个体父个体: : 10101 11011 1011 子个体子个体: : 10100
30、 01011 1011 逆转逆转变异变异将两个逆转点间的基因值逆向排序将两个逆转点间的基因值逆向排序 父个体父个体: 10: 101 11011010 000 00 子个体子个体: 10: 100 01011011 100 00 对于符号编码的个体,有对于符号编码的个体,有 父个体父个体: 12: 123 34564567 789 89 子个体子个体: 12: 127 76546543 389 89 交换变异相互交换两个随机选取的基因座上的交换变异相互交换两个随机选取的基因座上的 基因值基因值 父个体父个体: :BCABCAD DEJHEJHI IFGFG 子个体子个体: :BCABCAI I
31、EJHEJHD DFGFG 插入变异将一个基因座上的基因插入到另一个插入变异将一个基因座上的基因插入到另一个 基因座之后基因座之后 父个体父个体: :BCABCAD DEJHEJHI IFGFG 子个体子个体: :BCABCAD DI IEJHFGEJHFG 甸 窝 违 渤 马 蓟 慈 迭 烤 拷 纬 给 誓 怠 蛔 纫 碱 售 佐 沛 暗 淫 互 首 仿 乌 塔 萨 彭 涯 豫 则 高 等 运 筹 学 7 高 等 运 筹 学 7 2323 7.算法的终止条件 (1)给定一个最大的进化代数,一般是1001000代 (2)当前的最好解连续若干代没有变化 (3)连续几代个体平均适应度的差异小于某一个极小 的值 榨 涅 哦 货 橱 侗 镶 峙 破 疗 渍 诵 刁 宣 焰 嫩 诫 纯 抱 申 甥 砒 槛 求 寓 怜 少 月 劲 线 揽 绷 高 等 运 筹 学 7 高 等 运 筹 学 7 2424
链接地址:https://www.31doc.com/p-5931979.html