高级人工智能第十三章ppt课件

《高级人工智能第十三章ppt课件》由会员分享，可在线阅读，更多相关《高级人工智能第十三章ppt课件（108页珍藏版）》请在金锄头文库上搜索。

1、 高级人工智能第十三章 进化计算EvolutionaryComputation 2020 4 27 2 内容 13 1概述13 2进化系统理论的形式模型13 3达尔文进化算法13 4遗传算法13 5遗传算法的理论基础13 6遗传算法的改进13 7遗传机器学习 分类器系统13 8桶链算法13 9规则发现系统13 10进化策略13 11进化规划 2020 4 27 3 13 1概述 进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法 2020 4 27 4 发展历史 进化计算的研究起源于20世纪50年代 1965年 Holland首次提出了人工遗传操作的重要性 并把这些应用于自然系统和人工系

2、统中 大约在同一时期 Rechenberg和Schwefel提出了进化策略 Fogel提出了进化规划 2020 4 27 5 发展历史 1967年 Bagley在他的论文中首次提出了遗传算法这一术语 并讨论了遗传算法在自动博弈中的应用 1970年 Cavicchio把遗传算法应用于模式识别中 第一个把遗传算法应用于函数优化的是Hollstien 2020 4 27 6 发展历史 1975年是遗传算法研究的历史上十分重要的一年 这一年 Holland出版了他的著名专著 自然系统和人工系统的适应性 该书系统地阐述了遗传算法的基本理论和方法 并提出了对遗传算法的理论研究和发展极为重要的模式理论 sc

3、hematatheory 该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性 同年 DeJong完成了他的重要论文 遗传自适应系统的行为分析 他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑 这是因为他把Holland的模式理论与他的计算使用结合起来 2020 4 27 7 发展历史 1989Goldberg对遗传算法从理论上 方法上和应用上作了系统的总结 1990年 Koza提出了遗传规划 GeneticProgramming 的概念 用于搜索解决特定问题的最适计算机程序 2020 4 27 8 遗传算法与自然进化的比较 自然界 染色体 基因 等位基因 allele 染

4、色体位置 locus 基因型 genotype 表型 phenotype 遗传算法 字符串 字符 特征 特征值 字符串位置 结构 参数集 译码结构 2020 4 27 9 新达尔文进化理论的主要论点 个体是基本的选择目标 随机过程在进化中起重大作用 遗传变异大部分是偶然现象 基因型变异大部分是重组的产物 特别是突变 逐渐进化可能与表型不连续有关 不是所有表型变化都是自然选择的必然结果 进化是在适应中变化的 形式多样 不仅是基因的变化 选择是概率型的 而不是决定型的 2020 4 27 10 进化计算的三大主流板块 Holland提出的遗传算法 GeneticAlgorithm Rechenbe

5、rg和Schwefel提出的进化策略 EvolutionaryStrategies Fogel提出的进化规划 EvolutionaryProgramming 又称为进化程序设计 本章将着重介绍遗传算法 对进化策略和进化规划只作简单介绍 2020 4 27 11 13 2进化系统理论的形式模型 进化在个体群体中起作用 瓦铤顿 Waddington 指出基因型和表型之间关系的重要性 Waddington1974 群体禁止异构环境 但是 后生环境 是多维空间 表型是基因型和环境的产物 然后表型通过异构 选择环境 发生作用 注意 这种多维选择环境与后生环境空间是不同的 现在 适应性是表型空间和选择环境

6、空间的产物 它经常被取作一维 表示多少子孙对下一代作出贡献 基于这种想法 莫楞贝 Muhlenbein 和肯德曼 Kindermann 提出了一种称为进化系统理论的形式模型 Muhlenbein1989 2020 4 27 12 进化系统理论的形式模型 进化的主要过程 后生环境 遗传操作符 选择环境 g p 2020 4 27 13 进化系统理论的形式模型 其中 g是基因型p是表型 基因gi的可能值称为等位基因 在门德尔 Mendel 遗传学中 假设每个基因有有限数的等位基因 2020 4 27 14 进化系统理论的形式模型 这个变换函数给出了模型 说明表型的发展是通过基因与环境的交互作用 变

7、换过程是高度非线性的 2020 4 27 15 进化系统理论的形式模型 质量函数q给出了具体选择环境ESi下表型的质量 其定义如下 质量定义适应度 用于达尔文选择 至今已有三种具体范例的通用模型 即门德尔遗传学遗传生态学进化配子 2020 4 27 16 门德尔遗传学 在门德尔遗传学中 基因型被详细模型化 而表型和环境几乎被忽略 在遗传生态学中恰好相反 进化配子论是从社会生物学导出的模型 首先让我们讨论门德尔遗传学的选择模型 为了简单起见 我们假设一个基因具有n等位基因a1 an 二倍基因型以元组 ai aj 为特征 我们定义pi j为总群体中基因型 ai aj 的频度 假设基因型与表型相等

8、质量函数给每个表型赋值 q ai aj qi jqi j可以被解释为出生率减去死亡率 2020 4 27 17 门德尔遗传学 假设p i j是下一代表型 ai aj 的频度 然后达尔文选择根据选择方程调整表型的分布 是群体的平均适应度 2020 4 27 18 门德尔遗传学 设pi是群体中等位基因的频率 如果pi j pipj那么 我们得到在GS中的一个选择方程为 2020 4 27 19 门德尔遗传学 这个离散的选择方程可以用连续方程近似 如果qi j qj i 那么 2020 4 27 20 门德尔遗传学 这个方程很容易被证明 这个结果称作菲希尔 Fisher 基本定理 它说明平均适应度随

9、适应度的差别呈正比例增加 实际上 全部可能的基因型仅有一部分实现 这就是遗传操纵子探索基因型空间的任务 其个体数目相当小 这些操纵子是群体遗传变异性的来源 最重要的操纵子是突变和重组 2020 4 27 21 13 3达尔文进化算法 根据定量遗传学 达尔文进化算法采用简单的突变 选择动力学 达尔文算法的一般形式可以描述如下 是一代的双亲数目 为子孙数目 整数称作 混杂 数 如果两个双亲混合他们的基因 则 2 仅是最好的个体才允许产生子孙 逗号表示双亲们没有选择 加号表示双亲有选择 2020 4 27 22 13 3达尔文进化算法 建立原始种体 通过突变建立子孙 选择 返回到步骤 1 2020

10、4 27 23 遗传算法思想来源于生物进化过程 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 以字符串表示状态空间 遗传算法用概率搜索过程在该状态空间中搜索 产生新的样本 13 4遗传算法 2020 4 27 24 遗传算法的特点 特点 通用鲁棒次优解 满意解遗传算法能解决的问题 优化NP完全NP难高度复杂的非线性问题 2020 4 27 25 遗传算法 遗传算法先将搜索结构编码为字符串形式 每个字符串结构被称为个体 然后对一组字符串结构 被称为一个群体 进行循环操作 每次循环被称作一代 包括一个保存字符串中较优结构的过程和一个有结构的 随机的字符串间的信息交换过程 类似

11、于自然进化 遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题 2020 4 27 26 遗传算法 与自然界相似 遗传算法对求解问题的本身一无所知 它所需要的仅是对算法所产生的每个染色体进行评价 并基于适应值来选择染色体 使适应性好的染色体有更多的繁殖机会 在遗传算法中 位字符串扮演染色体的作用 单个位扮演了基因的作用 随机产生一个体字符串的初始群体 每个个体给予一个数值评价 称为适应度 取消低适应度的个体 选择高适应度的个体参加操作 常用的遗传算子有复制 杂交 变异和反转 2020 4 27 27 遗传算法与传统优化算法的主要不同 遗传算法不是直接作用在参变量集上 而是利用参变量集的某

12、种编码 遗传算法不是从单个点 而是在群体中从一个点开始搜索 遗传算法利用适应值信息 无需导数或其它辅助信息 遗传算法利用概率转移规则 而非确定性规则 2020 4 27 28 遗传算法的准备工作 确定表示方案 确定适应值的度量 确定控制该算法的参数和变量 确定怎样指定结果及程序运行结束的标准 2020 4 27 29 基本遗传算法 基本遗传算法 SimpleGeneticAlgorithm SGA 又称为简单遗传算法 只使用选择算子 交叉算子和变异算子这三种基本的遗传算子 其遗传操作简单 容易理解 是其它遗传算法的雏形和基础 基本遗传算法的构成要素 1 染色体编码方法 首先必须对问题的解空间进

13、行编码 使之能用遗传算法进行操作 较常用的是二进制编码方法 现在使用非二进制编码的也逐渐增多 2 适应度函数 fitnessfunction 又称为适应值 适值函数 用来评价一个染色体的好坏 2020 4 27 30 基本遗传算法的构成要素 3 遗传算子 选择算子 selection 又称为复制算子 按照某种策略从父代中挑选个体进入下一代 如使用比例选择 轮盘式选择 交叉算子 crossover 又称为杂交算子 将从群体中选择的两个个体 按照某种策略使两个个体相互交换部分染色体 从而形成两个新的个体 如使用单点一致交叉 变异算子 mutation 按照一定的概率 一般较小 改变染色体中某些基因

14、的值 2020 4 27 31 杂交操作举例 2020 4 27 32 变异操作 简单的变异操作过程如下 每个位置的字符变量都有一个变异概率 各位置互相独立 通过随机过程选择发生变异的位置 产生一个新结构 其中是从对应位置的字符变量的值域中随机选择的一个取值 可以同样得到 2020 4 27 33 反转操作 简单反转操作的步骤如下 从当前群体中随机选择一个结构从中随机选择两个数i 和j 并定义i min i j j max i j 颠倒a中位置i j之间的部分 产生新的结构 2020 4 27 34 基本遗传算法的构成要素 4 运行参数N 群体大小 即群体中包含的个体的数量 T 遗传算法终止的

15、进化代数 Pc 交叉概率 一般取为0 4 0 99 Pm 变异概率 一般取为0 0001 0 1 2020 4 27 35 基本遗传算法 随机产生一个由固定长度字符串组成的初始群体 对于字符串群体 迭代地执行下述步骤 直到选种标准被满足为止 计算群体中的每个个体字符串的适应值 应用下述三种操作 至少前两种 来产生新的群体 复制 把现有的个体字符串复制到新的群体中 杂交 通过遗传重组随机选择两个现有的子字符串 产生新的字符串 变异 将现有字符串中某一位的字符随机变异 把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果 这一结果可以是问题的解 或近似解 2020 4 27 36 基本遗

16、传算法流程图 2020 4 27 37 概率地选择遗传操作 根据适应值选择一个个体 完成交叉 i i 1 i i 1 复制个体 p r 选择 接上页 基于适应值选择两个个体 把新的两个孩子加到群体中 p c 交叉 变异p m 把新的孩子加入到群体中 完成变异 根据适应值选择一个个体 把变异后个体加入到群体中 1 2020 4 27 38 轮盘式选择 首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇形 每个扇形的大小为 选择时转动轮盘 参考点r落到扇形i则选择个体i 2020 4 27 39 单点一致交叉 首先以概率pc从种群中随机地选择两个个体p1 p2 在 1 2 l 内随机选择一个数i 作为交叉的位置 称为交叉点 然后将两个个体交叉点后面的部分交换 例如 0110101100011001100111000110011100101100 2020 4 27 40 一致变异 以概率pm对种群中所有个体的每一位进行变异 对于个体pi的第j位 在 0 1 的范围内随机地生成一个数r 如果r pm 则对第j位取反 否则保持第j位不变 2020 4 27 41 遗传算法举例