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

高级人工智能第十三章 进化计算EvolutionaryComputation 2020 4 25 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 25 3 13 1概述 进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法 2020 4 25 4 发展历史 进化计算的研究起源于20世纪50年代 1965年 Holland首次提出了人工遗传操作的重要性 并把这些应用于自然系统和人工系统中 大约在同一时期 Rechenberg和Schwefel提出了进化策略 Fogel提出了进化规划 2020 4 25 5 发展历史 1967年 Bagley在他的论文中首次提出了遗传算法这一术语 并讨论了遗传算法在自动博弈中的应用 1970年 Cavicchio把遗传算法应用于模式识别中 第一个把遗传算法应用于函数优化的是Hollstien 2020 4 25 6 发展历史 1975年是遗传算法研究的历史上十分重要的一年 这一年 Holland出版了他的著名专著 自然系统和人工系统的适应性 该书系统地阐述了遗传算法的基本理论和方法 并提出了对遗传算法的理论研究和发展极为重要的模式理论 schematatheory 该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性 同年 DeJong完成了他的重要论文 遗传自适应系统的行为分析 他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑 这是因为他把Holland的模式理论与他的计算使用结合起来 2020 4 25 7 发展历史 1989Goldberg对遗传算法从理论上 方法上和应用上作了系统的总结 1990年 Koza提出了遗传规划 GeneticProgramming 的概念 用于搜索解决特定问题的最适计算机程序 2020 4 25 8 遗传算法与自然进化的比较 自然界 染色体 基因 等位基因 allele 染色体位置 locus 基因型 genotype 表型 phenotype 遗传算法 字符串 字符 特征 特征值 字符串位置 结构 参数集 译码结构 2020 4 25 9 新达尔文进化理论的主要论点 个体是基本的选择目标 随机过程在进化中起重大作用 遗传变异大部分是偶然现象 基因型变异大部分是重组的产物 特别是突变 逐渐进化可能与表型不连续有关 不是所有表型变化都是自然选择的必然结果 进化是在适应中变化的 形式多样 不仅是基因的变化 选择是概率型的 而不是决定型的 2020 4 25 10 进化计算的三大主流板块 Holland提出的遗传算法 GeneticAlgorithm Rechenberg和Schwefel提出的进化策略 EvolutionaryStrategies Fogel提出的进化规划 EvolutionaryProgramming 又称为进化程序设计 本章将着重介绍遗传算法 对进化策略和进化规划只作简单介绍 2020 4 25 11 13 2进化系统理论的形式模型 进化在个体群体中起作用 瓦铤顿 Waddington 指出基因型和表型之间关系的重要性 Waddington1974 群体禁止异构环境 但是 后生环境 是多维空间 表型是基因型和环境的产物 然后表型通过异构 选择环境 发生作用 注意 这种多维选择环境与后生环境空间是不同的 现在 适应性是表型空间和选择环境空间的产物 它经常被取作一维 表示多少子孙对下一代作出贡献 基于这种想法 莫楞贝 Muhlenbein 和肯德曼 Kindermann 提出了一种称为进化系统理论的形式模型 Muhlenbein1989 2020 4 25 12 进化系统理论的形式模型 进化的主要过程 后生环境 遗传操作符 选择环境 g p 2020 4 25 13 进化系统理论的形式模型 其中 g是基因型p是表型 基因gi的可能值称为等位基因 在门德尔 Mendel 遗传学中 假设每个基因有有限数的等位基因 2020 4 25 14 进化系统理论的形式模型 这个变换函数给出了模型 说明表型的发展是通过基因与环境的交互作用 变换过程是高度非线性的 2020 4 25 15 进化系统理论的形式模型 质量函数q给出了具体选择环境ESi下表型的质量 其定义如下 质量定义适应度 用于达尔文选择 至今已有三种具体范例的通用模型 即门德尔遗传学遗传生态学进化配子 2020 4 25 16 门德尔遗传学 在门德尔遗传学中 基因型被详细模型化 而表型和环境几乎被忽略 在遗传生态学中恰好相反 进化配子论是从社会生物学导出的模型 首先让我们讨论门德尔遗传学的选择模型 为了简单起见 我们假设一个基因具有n等位基因a1 an 二倍基因型以元组 ai aj 为特征 我们定义pi j为总群体中基因型 ai aj 的频度 假设基因型与表型相等 质量函数给每个表型赋值 q ai aj qi jqi j可以被解释为出生率减去死亡率 2020 4 25 17 门德尔遗传学 假设p i j是下一代表型 ai aj 的频度 然后达尔文选择根据选择方程调整表型的分布 是群体的平均适应度 2020 4 25 18 门德尔遗传学 设pi是群体中等位基因的频率 如果pi j pipj那么 我们得到在GS中的一个选择方程为 2020 4 25 19 门德尔遗传学 这个离散的选择方程可以用连续方程近似 如果qi j qj i 那么 2020 4 25 20 门德尔遗传学 这个方程很容易被证明 这个结果称作菲希尔 Fisher 基本定理 它说明平均适应度随适应度的差别呈正比例增加 实际上 全部可能的基因型仅有一部分实现 这就是遗传操纵子探索基因型空间的任务 其个体数目相当小 这些操纵子是群体遗传变异性的来源 最重要的操纵子是突变和重组 2020 4 25 21 13 3达尔文进化算法 根据定量遗传学 达尔文进化算法采用简单的突变 选择动力学 达尔文算法的一般形式可以描述如下 是一代的双亲数目 为子孙数目 整数称作 混杂 数 如果两个双亲混合他们的基因 则 2 仅是最好的个体才允许产生子孙 逗号表示双亲们没有选择 加号表示双亲有选择 2020 4 25 22 13 3达尔文进化算法 建立原始种体 通过突变建立子孙 选择 返回到步骤 1 2020 4 25 23 遗传算法思想来源于生物进化过程 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法 以字符串表示状态空间 遗传算法用概率搜索过程在该状态空间中搜索 产生新的样本 13 4遗传算法 2020 4 25 24 遗传算法的特点 特点 通用鲁棒次优解 满意解遗传算法能解决的问题 优化NP完全NP难高度复杂的非线性问题 2020 4 25 25 遗传算法 遗传算法先将搜索结构编码为字符串形式 每个字符串结构被称为个体 然后对一组字符串结构 被称为一个群体 进行循环操作 每次循环被称作一代 包括一个保存字符串中较优结构的过程和一个有结构的 随机的字符串间的信息交换过程 类似于自然进化 遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题 2020 4 25 26 遗传算法 与自然界相似 遗传算法对求解问题的本身一无所知 它所需要的仅是对算法所产生的每个染色体进行评价 并基于适应值来选择染色体 使适应性好的染色体有更多的繁殖机会 在遗传算法中 位字符串扮演染色体的作用 单个位扮演了基因的作用 随机产生一个体字符串的初始群体 每个个体给予一个数值评价 称为适应度 取消低适应度的个体 选择高适应度的个体参加操作 常用的遗传算子有复制 杂交 变异和反转 2020 4 25 27 遗传算法与传统优化算法的主要不同 遗传算法不是直接作用在参变量集上 而是利用参变量集的某种编码 遗传算法不是从单个点 而是在群体中从一个点开始搜索 遗传算法利用适应值信息 无需导数或其它辅助信息 遗传算法利用概率转移规则 而非确定性规则 2020 4 25 28 遗传算法的准备工作 确定表示方案 确定适应值的度量 确定控制该算法的参数和变量 确定怎样指定结果及程序运行结束的标准 2020 4 25 29 基本遗传算法 基本遗传算法 SimpleGeneticAlgorithm SGA 又称为简单遗传算法 只使用选择算子 交叉算子和变异算子这三种基本的遗传算子 其遗传操作简单 容易理解 是其它遗传算法的雏形和基础 基本遗传算法的构成要素 1 染色体编码方法 首先必须对问题的解空间进行编码 使之能用遗传算法进行操作 较常用的是二进制编码方法 现在使用非二进制编码的也逐渐增多 2 适应度函数 fitnessfunction 又称为适应值 适值函数 用来评价一个染色体的好坏 2020 4 25 30 基本遗传算法的构成要素 3 遗传算子 选择算子 selection 又称为复制算子 按照某种策略从父代中挑选个体进入下一代 如使用比例选择 轮盘式选择 交叉算子 crossover 又称为杂交算子 将从群体中选择的两个个体 按照某种策略使两个个体相互交换部分染色体 从而形成两个新的个体 如使用单点一致交叉 变异算子 mutation 按照一定的概率 一般较小 改变染色体中某些基因的值 2020 4 25 31 杂交操作举例 2020 4 25 32 变异操作 简单的变异操作过程如下 每个位置的字符变量都有一个变异概率 各位置互相独立 通过随机过程选择发生变异的位置 产生一个新结构 其中是从对应位置的字符变量的值域中随机选择的一个取值 可以同样得到 2020 4 25 33 反转操作 简单反转操作的步骤如下 从当前群体中随机选择一个结构从中随机选择两个数i 和j 并定义i min i j j max i j 颠倒a中位置i j之间的部分 产生新的结构 2020 4 25 34 基本遗传算法的构成要素 4 运行参数N 群体大小 即群体中包含的个体的数量 T 遗传算法终止的进化代数 Pc 交叉概率 一般取为0 4 0 99 Pm 变异概率 一般取为0 0001 0 1 2020 4 25 35 基本遗传算法 随机产生一个由固定长度字符串组成的初始群体 对于字符串群体 迭代地执行下述步骤 直到选种标准被满足为止 计算群体中的每个个体字符串的适应值 应用下述三种操作 至少前两种 来产生新的群体 复制 把现有的个体字符串复制到新的群体中 杂交 通过遗传重组随机选择两个现有的子字符串 产生新的字符串 变异 将现有字符串中某一位的字符随机变异 把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果 这一结果可以是问题的解 或近似解 2020 4 25 36 基本遗传算法流程图 2020 4 25 37 概率地选择遗传操作 根据适应值选择一个个体 完成交叉 i i 1 i i 1 复制个体 p r 选择 接上页 基于适应值选择两个个体 把新的两个孩子加到群体中 p c 交叉 变异p m 把新的孩子加入到群体中 完成变异 根据适应值选择一个个体 把变异后个体加入到群体中 1 2020 4 25 38 轮盘式选择 首先计算每个个体i被选中的概率然后根据概率的大小将将圆盘分为n个扇形 每个扇形的大小为 选择时转动轮盘 参考点r落到扇形i则选择个体i 2020 4 25 39 单点一致交叉 首先以概率pc从种群中随机地选择两个个体p1 p2 在 1 2 l 内随机选择一个数i 作为交叉的位置 称为交叉点 然后将两个个体交叉点后面的部分交换 例如 0110101100011001100111000110011100101100 2020 4 25 40 一致变异 以概率pm对种群中所有个体的每一位进行变异 对于个体pi的第j位 在 0 1 的范围内随机地生成一个数r 如果r pm 则对第j位取反 否则保持第j位不变 2020 4 25 41 遗传算法举例 问题 求 1 编码 此时取均长为5 每个染色体 2 初始群体生成 群体大小视情况而定 此处设置为4 随机产生四个个体 编码 01101 11000 01000 10011解码 1324819适应度 16957664361 3 适应度评价 2020 4 25 42 4 选择 选择概率个体 01101 11000 01000 10011适应度 16957664361选择概率 0 140 490 060 31选择结果 01101 11000 11000 10011 5 交叉操作 发生交叉的概率较大哪两个个体配对交叉是随机的交叉点位置的选取是随机的 单点交叉 0110101100110001101111000110011001110000 遗传算法举例 2020 4 25 43 6 变异 发生变异的概率很小 7 新群体的产生 保留上一代最优个体 一般为10 左右 至少1个用新个体取代旧个体 随机取代或择优取代 11000 11011 11001 10011 8 重复上述操作 说明 GA的终止条件一般人为设置 GA只能求次优解或满意解 分析 按第二代新群体进行遗传操作 若无变异 永远也找不到最优解 择优取代有问题 若随机的将个体01101选入新群体中 有可能找到最优解 遗传算法举例 2020 4 25 44 13 5遗传算法的理论基础 13 5 1模式的定义遗传算法的理论基础是遗传算法的二进制表达式及模式的含义 模式是能对染色体之间的相似性进行解释的模板 定义1 设GA的个体 记集合则称为一个模式 其中 是通配符 即模式 schema 是含有通配符 的一类字符串的通式表达 每个 可以取 1 或者 0 2020 4 25 45 模式举例 模式 10101110与以下两个字符串匹配 010101110110101110而模式 1010 110与以下四个字符串匹配 010100110010101110110100110110101110 2020 4 25 46 模式的定义 定义2 一个模式s的阶是出现在模式中的 0 和 1 的数目 记为o s 如 模式 0 的阶为1 模式 10 1 的阶为3 定义3 一个模式s的长度是出现在模式中第一个确定位置和最后一个确定位置之间的距离 记为 如 模式 01 的长度为1 模式 0 1 的长度为3 2020 4 25 47 模式定理 假定在给定的时间步t 一个特定的模式s在群体P t 中包含由m个代表串 记为m m s t 首先 我们暂不考虑交叉和变异操作 每个串根据适应值的大小获得不同的复制概率 串i的复制概率为 1 2020 4 25 48 模式定理 则在群体P t 1 中 模式s的代表串的数量的期望值为 其中 表示模式s在t时刻的所有代表串的适应值的均值 称为模式s的适应值 2 2020 4 25 49 模式定理 若记P t 中所有个体的适应值的平均值为 3 则 2 式可以表示为 2020 4 25 50 模式定理 3 式表明 模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值 即 适应值高于群体平均值的模式在下一代的代表串数目将会增加 而适应值低于群体平均值的模式在下一代的代表串数目将会减少 假设模式的适应值为 其中c是一个常数 则 3 式可写为 2020 4 25 51 模式定理 4 上式表明 在平均适应值之上 之下 的模式 将会按指数增长 衰减 的方式被复制 2020 4 25 52 模式定理 复制的结果并没有生成新的模式 因而 为了探索搜索空间中的未搜索部分 需要利用交叉和变异操作 下面先探索交叉对模式的影响 模式s1 1 0 和s2 10 交叉会改变模式的一部分 模式的长度越长 被破坏的概率越大 2020 4 25 53 模式定理 假定模式s在交叉后不被破坏的概率为ps 则 若交叉概率为pc 则s不被破坏的概率为 2020 4 25 54 模式定理 5 所以 再考虑交叉时 3 式可表示为最后 考虑变异算子对模式的影响 变异算子以概率pm随机地改变个体某一位的值 只有当o s 个确定位的值不被破坏时 模式s才不被破坏 2020 4 25 55 模式定理 模式s在变异后不被破坏的概率 Pm 1 可近似地表示为 2020 4 25 56 模式定理 6 因此 考虑交叉和变异时 3 式可表示为 2020 4 25 57 模式定理 由 6 我们得到一个重要的定理 定理1 模式定理 SchemaTheorem 适应值在群体适应值之上的 长度较短的 低阶的模式在GA的迭代中将按指数增长方式被复制 2020 4 25 58 积木块假设 Holland和Goldberg在模式定理的基础上提出了 积木块假设 BuildingBlockHypothesis 低阶 长度较短 高于平均适应度的模式 积木块 在遗传算子的作用下 相互结合 能生成高阶 长度较长 适应度较高的模式 并得到全局最优解 2020 4 25 59 遗传算法的收敛性分析 算法的收敛性可以定义如下 定义 若算法在t时刻的种群xt满足则称算法收敛到x0 关于遗传算法的收敛性 Michalewicz证明了基于压缩原理的收敛性定理 而Rudolph证明了基于Markov链的收敛性定理 2020 4 25 60 遗传算法的改进 遗传算法的局限性 遗传算法得到了广泛应用 但也暴露了一些问题 如 遗传算法在解决某些问题时速度较慢 遗传算法对编码方案的依赖性较强 算法的鲁棒性不够好等 这些问题主要归结为 1 上位 epistasis 效应上位效应包括两个方面 多基因性和基因多效性 2020 4 25 61 遗传算法的改进 2 编码方案最初使用最多的是二进制位串 但此类编码并不适合一些实际问题 现在人们已经探索了许多其它方案 如浮点表示 树形表示等等 3 积木块假设积木块假设是否成立 是否一定存在短的 低阶的 高适应值的积木块 若构成问题最优解的所有低阶模式的适应值都较低 这是GA很难收敛到最优解 此类问题称为 欺骗问题 2020 4 25 62 遗传算法的改进 4 早熟收敛即GA收敛到一个局部最优解 Schraudolph和Belew提出 动态参数编码 方案来解决早熟收敛问题 关于遗传算法的一些改进措施 有兴趣的同学可查找相关资料 2020 4 25 63 遗传机器学习 分类器系统 机器学习是人工智能的一个重要研究领域 也是人工智能的一个重要的应用领域 遗传机器学习 GeneticsBasedMachineLearning GBML 时将遗传算法与机器学习系统相结合的产物 2020 4 25 64 遗传机器学习系统的一般框架 任务子系统 学习子系统 任务检测器 任务效应器 执行效应器 执行检测器 2020 4 25 65 匹兹堡方法和密西根方法 遗传机器学习有两种重要的实现方法 一种是由匹兹堡 Pittsburgh 大学的DeJong和他的学生Smith提出的 该方法用整个规则集合表示一个个体 GAs维护一个包含一定数目的候选规则集的种群 这种方法称为匹兹堡方法 2020 4 25 66 匹兹堡方法和密西根方法 另一种方法是由密西根 Michigan 大学的Holland和他的学生Reitman提出的 该方法每个个体表示一条规则 而整个种群就是规则集 这种方法称为密西根方法 Holland提出的分类器系统采用的是密西根方法 2020 4 25 67 分类器系统 Holland和他的同事提出了一种分类器系统的认知模型 其中的规则不是规则集 而是遗传算法操纵的内部实体 图11 3给出了分类器系统的一般结构 从分类器系统看学习 它由三层动作构成 即执行子系统 信用赋值子系统和发现子系统 2020 4 25 68 分类器系统 2020 4 25 69 分类器系统 执行子系统处在最低层 直接与环境进行交互 它与专家系统相同 由产生式规则构成 但是 它们是消息传送 高度平行 这类规则称作分类器 分类器系统中的学习 要求环境提供反馈 确认所希望的状态是否达到 系统将评价这些规则的有效性 这些活动常常称作信用赋值 有些特定算法专门用来实现信用赋值 例如 桶链算法 最后一层是发现子系统 该系统必须产生新的规则 取代当前用处不大的规则 通过系统累积的经验产生规则 系统根据适应值 使用遗传算法选择 重组和取代规则 2020 4 25 70 分类器系统 分类器系统是平行执行 消息传递和基于规则的系统 在简单的方案中 消息采用规定的字母 全部为固定长度 全部规则采用条件 动作形式 每个条件规定必须满足的信息 每个动作规定当条件满足时所发送的消息 为了方便 假设消息采用长度为l的二进制字符串记录 字符采用子集 1 0 2020 4 25 71 规则与消息 产生式规则 IFTHEN约定 条件的长度是固定的 用二进制数表示 定义 Ifsj 1orsj 0 thenmj sjIfsj thenmjcanbeeither1or0 2020 4 25 72 规则与消息 满足要求的全部消息构成子集 即每个子集是在消息空间的一个超平面 分类器系统是由一组分类器 C1 C2 CN 一个消息表 输入接口 输出接口构成 每部分的主要功能如下 1 输入接口将当前环境状态翻译成标准消息 2 分类器根据规则 规定系统处理消息的过程 3 消息表包含当前全部消息 4 输出接口将结果消息翻译成效应器动作 修改环境状态 2020 4 25 73 分类器系统的基本结构 2020 4 25 74 分类器基本算法 将输入接口全部消息放入消息表 将消息表中的全部消息与全部分类器所有条件比较 记录所有匹配 满足分类器条件部分的每组匹配 将其动作部分所规定的消息送到新的消息表 用新的消息表取代消息表中的全部消息 将消息表中的消息翻译成输出接口的要求 产生系统当前的输出 返回到步骤 1 2020 4 25 75 简单的视觉分类器系统 2020 4 25 76 性质检测器规定的值 1 如果移动对象 0 其它 0 0 如果对象在视野的中间 1 0 如果对象在中心的左边 0 1 如果对象在中心的右边 1 如果系统是对象的近邻 0 其它 1 如果对象很大 0 其它 1 如果对象是狭长的 0 其它 2020 4 25 77 规则表示 规则 IF如果有 捕食 prey small moving nonstripedobject 处于视野中间 centered 非邻近 nonadjacent THEN迅速移向对象 ALIGN FAST 可以表示为 00 000001 0100000000000000 ALIGN FAST 2020 4 25 78 网络图 MOVING SMALL NOTSTRIPED NEAR FAR 01001 ALERT 10001 TARGET 11001 PORSUE 11010 APPROACH 11011 FLEE 11100 FREEZE 10010 DANGER 2020 4 25 79 网络图的规则表示 MOVING和ALERT之间的箭头 00 1 01001 SMALL NOTSTRIPEDandALERT到TARGET的箭头 00 00 01001 10001 2020 4 25 80 学习机制 分类器系统使用两个学习机制 桶链 bucketbrigade 算法 基于对系统的贡献 对现有规则分配一个信用值 规则发现算法 这包括遗传算法 该算法可产生新规则 用于改善系统的知识库 2020 4 25 81 桶链算法 桶链 bucketbrigade 算法基于对系统的贡献 对现有规则分配一个信用值 主要解决多条规则同时要求被激活时的竞争问题 例如 下面的情况下应该选择哪条规则 0111 01 0000 00 0001 00 0 1100 2020 4 25 82 主要问题 引入信用值后的两个问题 当多条规则同时要求被激活时 如何解决竞争问题对一规则被激活产生过作用的那些规则如何分配信用 2020 4 25 83 桶链算法 为解决上述两个问题 引入拍卖行和票据交易所 当有多个分类器获得匹配时 每个分类器要出一个与其强度成正比的叫价B叫价高的分类器被激活并允许发送消息 同时通过票据交易所 将其叫价B提供给激活的分类器 如此继续下去 一条规则可通过消费者获利 增加了强度 通过规则的不断激活形成一条消费者链 直至最终消费者 达到目标 直接从环境中得到补偿 若链中一条规则导致错误结论 则序列上该规则的强度将减弱 并且沿着序列回溯 从而产生新的消费者链 2020 4 25 84 举例 环境0111 强度为0 叫价系数为0 1 索引号分类器强度101 0000200200 0 1000200311 10002004 00 0001200 2020 4 25 85 第一步 分类器强度消息匹配叫价01 0000200E2000 0 100020011 1000200 00 0001200 2020 4 25 86 第二步 分类器强度消息匹配叫价01 0000180000000 0 100020012011 1000200 00 0001200120两条规则同时激活 2020 4 25 87 第三步 分类器强度消息匹配叫价01 000022000 0 1000180110011 1000200220 00 00011800001218 2020 4 25 88 第四步 分类器强度消息匹配叫价01 000022000 0 100021811 10001801000 00 0001162316 2020 4 25 89 第五步 分类器强度消息匹配叫价强度01 000022022000 0 100021821811 1000196196 00 00011460001206规则4达到目标获得补偿60 2020 4 25 90 投标改变分类器的强度 在时间t满足C送去消息的分类器 对在t 1作用的分类器投标 在时间t对分类器C的支持 2020 4 25 91 分类器中的遗传算法 遗传算法可产生新规则 用于改善系统的知识库 可以在三种情况下应用GA 引入一个参数T 时间间隔 用于控制何时使用GA 特殊情况时 如消息的条件都不能匹配 使用GA 系统的性能太差 2020 4 25 92 算法步骤 t 0 随机生成集合Bt Bt M 大小 计算Bt中全体分类器的平均强度Vt 对每个分类器赋予一个标准强度St Cj Vt 给Bt中的每个分类器Cj赋予一个与其标准强度成正比的概率 并根据Bt中的概率分布 从Bt中选取n个分类器 n M 对每个分类器应用交叉算子 生成2n个分类器 将Bt中的2n个强度最低的分类器用新生成的2n个取代 t t 1 转 2 2020 4 25 93 算法说明 算法中S0 Cj 是预知的 实现时考虑结束条件 该算法是经典GA的变种 其中没有变异算子 新分类器的强度是由旧分类器的强度决定的 2020 4 25 94 分类器强度调整算法 将与所选动作相同的分类器形成子集 M 称作动作集 A 将不在 M 中的其它分类器放在集合NOT A 中 在 A 中的全部分类器强度减少一个分数e 如果系统决策正确 则将赢利量R分配给 A 的强度 如果系统决策错误 则将赢利量R 其中0 R R 分配给 A 的强度 从 A 的强度减少一个分数p 至少R 和p中的一个为0 从NOT A 中的强度减去一个分数t 2020 4 25 95 规则发现系统 在规则发现系统中 学习经常是首先评价系统现有的规则质量 然后进行修改 Grefenstette研制了一种规则发现系统RUDI 问题求解级由简化的分类器系统组成 学习级是对知识结构群体进行遗传算法操作 每一个表示为一组规则表 知识结构的整个行为控制这些结构的复制 在RUDI中 信用赋值方法赢利共享规划 Profit SharingPlan 简称PSP 和桶链算法 BBA 对每个规则提供互补的效用信息 根据期望的外部奖励 PSP 强度对规则效用提供更精确的评估 当问题求解时它被用作冲突消解 与此相反 BBA 强度表示规则之间的动态相关性 规则点火依次会聚到相似水平 这种测度可以用作一组协作规则的聚类 2020 4 25 96 规则发现系统 Grefenstette提出一种强度修改方案称作嬴利共享规划PSP 在这种方案中问题求解划分成情节 按所接受的外部奖励区分 如果任何步情节在投标竞争中获胜 则认为该规则在该情节活动 在情节t PSP修改每个活动规则Ri的强度Si t 如下 Si t 1 Si t bSi t bp t 其中 p t 称作在情节结束时所获得的外部奖励 即当获得外部奖励 从每个活动规则搜集投标 每个活动规则给出一部分外部奖励 考虑PSP对给定规则Ri的影响 它按照方程得到 2020 4 25 97 规则发现系统 其中 t的范围是在该情节规则Ri是活动的 即Si t 基本上外部奖励的权值平均p t 1 b 作为指数衰减因子 如果b足够