高级人工智能第十三章.ppt_第1页
高级人工智能第十三章.ppt_第2页
高级人工智能第十三章.ppt_第3页
高级人工智能第十三章.ppt_第4页
高级人工智能第十三章.ppt_第5页
已阅读5页,还剩102页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

高级人工智能 第十三章 进化计算 Evolutionary Computation *史忠植 高级人工智能2 内 容 13.1 概述 13.2 进化系统理论的形式模型 13.3 达尔文进化算法 13.4 遗传算法 13.5 遗传算法的理论基础 13.6 遗传算法的改进 13.7 遗传机器学习分类器系统 13.8 桶链算法 13.9 规则发现系统 13.10 进化策略 13.11 进化规划 *史忠植 高级人工智能3 13.1 概 述 进化计算是通过模拟自然界中生物进化 机制进行搜索的一种算法。 *史忠植 高级人工智能4 发展历史 进化计算的研究起源于20世纪50年代。 1965年,Holland首次提出了人工遗传操作 的重要性,并把这些应用于自然系统和人 工系统中。 大约在同一时期: Rechenberg和Schwefel提出了进化策略。 Fogel提出了进化规划。 *史忠植 高级人工智能5 发展历史 1967年,Bagley在他的论文中首次提出了 遗传算法这一术语,并讨论了遗传算法在 自动博弈中的应用。 1970年,Cavicchio把遗传算法应用于模式 识别中。第一个把遗传算法应用于函数优 化的是Hollstien。 *史忠植 高级人工智能6 发展历史 1975年是遗传算法研究的历史上十分重要的一年。这 一年,Holland出版了他的著名专著自然系统和人 工系统的适应性该书系统地阐述了遗传算法的基 本理论和方法,并提出了对遗传 算法的理论研究和 发展极为重要的模式理论(schemata theory),该 理论首次确认了结构重组遗传 操作对于获得隐并行 性的重要性。 同年,DeJong完成了他的重要论文遗传自适应系 统的行为分析。他在该论文中所做的研究工作可 看作是遗传算法发展过程中的一个里程碑,这是因 为他把Holland的模式理论与他的计算使用结合起来 。 *史忠植 高级人工智能7 发展历史 1989 Goldberg对遗传 算法从理论上,方法上 和应用上作了系统的总结。 1990年,Koza提出了遗传规划(Genetic Programming)的概念。(用于搜索解决特定 问题的最适计算机程序) *史忠植 高级人工智能8 遗传算法与自然进化的比较 自然界 染色体 基因 等位基因(allele) 染色体位置(locus) 基因型(genotype) 表型(phenotype) 遗传算法 字符串 字符,特征 特征值 字符串位置 结构 参数集,译码结构 *史忠植 高级人工智能9 新达尔文进化理论的主要论点 1) 个体是基本的选择目标; 2) 随机过程在进化中起重大作用, 遗传变异大部 分是偶然现象; 3) 基因型变异大部分是重组的产物, 特别是突变; 4) 逐渐进化可能与表型不连续有关; 5) 不是所有表型变化都是自然选择的必然结果; 6) 进化是在适应中变化的, 形式多样, 不仅是基因 的变化; 7) 选择是概率型的, 而不是决定型的。 *史忠植 高级人工智能10 进化计算的三大主流板块 lHolland提出的遗传算法(Genetic Algorithm)。 lRechenberg和Schwefel提出的进化策略 (Evolutionary Strategies)。 lFogel提出的进化规划(Evolutionary Programming),又称为进化程序设计。 l本章将着重介绍遗传算法,对进化策略和进化规 划只作简单介绍。 *史忠植 高级人工智能11 13.2 进化系统理论的形式模型 进化在个体群体中起作用。瓦铤顿(Waddington) 指出基因型和表型之间关系的重要性(Waddington 1974)。群体禁止异构环境。但是“后生环境”是多维空 间。表型是基因型和环境的产物。然后表型通过异构“ 选择环境“发生作用。注意,这种多维选择环境与后生 环境空间是不同的。现在,适应性是表型空间和选择 环境空间的产物。它经常被取作一维,表示多少子孙 对下一代作出贡献。 基于这种想法,莫楞贝(Muhlenbein) 和肯德曼 (Kindermann)提出了一种称为进化系统理论的形式模 型(Muhlenbein 1989)。 *史忠植 高级人工智能12 进化系统理论的形式模型 进化的主要过程 后生环境遗传操作符选择环境 gp *史忠植 高级人工智能13 进化系统理论的形式模型 其中,g 是基因型 p 是表型。 基因gi的可能值称为等位基因。 在门德尔(Mendel)遗传学中,假设每个基因 有有限数的等位基因。 *史忠植 高级人工智能14 进化系统理论的形式模型 这个变换函数给出了模型,说明表型的发展是通过基 因与环境的交互作用。 变换过程是高度非线性的。 *史忠植 高级人工智能15 进化系统理论的形式模型 质量函数q给出了具体选择环 境ESi下表型的质量 , 其定义如下: 质量定义适应度,用于达尔文选择。至今已有三种 具体范例的通用模型,即 门德尔遗传学 遗传生态学 进化配子 *史忠植 高级人工智能16 门德尔遗传学 在门德尔遗传学中,基因型被详细模型化,而表型 和 环境几乎被忽略。在遗传生态学中恰好相反。 进化配子论是从社会生物学导出的模型。 首先让我们讨论门 德尔遗传学的选择模型。为 了简单起见,我们假设一个基因具有n 等位基因 a1,an。 二倍基因型以元组(ai,aj)为特征。 我们定 义 pi,j 为总群体中基因型(ai,aj) 的频度。假设基因 型与表型相等。质量函数给每个表型赋值。 q(ai,aj) = qi,j qi,j 可以被解释为出生率减去死亡率 *史忠植 高级人工智能17 门德尔遗传学 假设 pi,j是下一代表型(ai,aj) 的频度。然后达尔文 选择根据选择方程调整表型的分布: 是群体的平均适应度。 *史忠植 高级人工智能18 门德尔遗传学 设 pi 是群体中等位基因的频率。如果 pi,j = pi pj 那么,我们得到在 GS中的一个选择方程为 *史忠植 高级人工智能19 门德尔遗传学 这个离散的选择方程可以用连续方程近似: 如果 qi,j = qj,i, 那么 *史忠植 高级人工智能20 门德尔遗传学 这个方程很容易被证明: 这个结果称作菲希尔(Fisher)基本定理。它说明平 均适应度随适应度的差别呈正比例增加。实际上, 全部可能的基因型仅有一部分实现。这就是遗传操 纵子探索基因型空间的任务,其个体数目相当小。 这些操纵子是群体遗传变 异性的来源。最重要的操 纵子是突变和重组。 *史忠植 高级人工智能21 13.3 达尔文进化算法 根据定量遗传学,达尔文进化算法采用简单 的突变/选择动力学。 达尔文算法的一般形式可以描述如下: 是一代的双亲数目, 为子孙数目。 整数 称作“混杂”数。 如果两个双亲混合他们的基因,则 = 2。仅 是最好的个体才允许产生子孙。 逗号表示双亲们没有选择,加号表示双亲有选择。 *史忠植 高级人工智能22 13.3 达尔文进化算法 1) 建立原始种体。 2) 通过突变建立子孙。 3) 选择: 4) 返回到步骤(1)。 *史忠植 高级人工智能23 遗传算法思想来源于生物进化过程, 它 是基于进化过程中的信息遗传机制和优胜 劣汰的自然选择原则的搜索算法(以字符串 表示状态空间)。遗传算法用概率搜索过程 在该状态空间中搜索,产生新的样本。 13.4 遗传算法 *史忠植 高级人工智能24 遗传算法的特点 特点: 通用 鲁棒 次优解、满意解 遗传算法能解决的问题: 优化 NP完全 NP难 高度复杂的非线性问题 *史忠植 高级人工智能25 遗传算法 遗传算法先将搜索结构编码为字符串形式, 每个字 符串结构被称为个体。 然后对一组字符串结构(被称为一个群体)进行循环 操作。每次循环被称作一代,包括一个保存字符串 中较优结构的过程和一个有结构的、随机的字符 串间的信息交换过程。 类似于自然进化,遗传算法通过作用于染色体上 的基因寻找好的染色体来求解问题。 *史忠植 高级人工智能26 遗传算法 与自然界相似,遗传算法对求解问题的本身一无 所知,它所需要的仅是对算法所产生的每个染色 体进行评价,并基于适应值来选择染色体,使适 应性好的染色体有更多的繁殖机会。 在遗传算法中,位字符串扮演染色体的作用,单 个位扮演了基因的作用,随机产生一个体字符串 的初始群体,每个个体给予一个数值评价,称为 适应度,取消低适应度的个体,选择高适应度的 个体参加操作。 常用的遗传算子有复制、杂交、变异和反转。 *史忠植 高级人工智能27 遗传算法与传统优化算法的主要不同 1) 遗传算法不是直接作用在参变量集上, 而 是利用参变量集的某种编码; 2) 遗传算法不是从单个点, 而是在群体中从一 个点开始搜索; 3) 遗传算法利用适应值信息, 无需导数或其它 辅助信息; 4) 遗传算法利用概率转移规则, 而非确定性规 则。 *史忠植 高级人工智能28 遗传算法的准备工作 1) 确定表示方案; 2) 确定适应值的度量; 3) 确定控制该算法的参数和变量; 4) 确定怎样指定结果及程序运行结束的标准 。 *史忠植 高级人工智能29 基本遗传算法 基本遗传算法(Simple Genetic Algorithm:SGA)又称为简单 遗传算法,只使用选择算子、交叉算子和变异算子这三 种基本的遗传算子。其遗传操作简单、容易理解,是其 它遗传算法的雏形和基础。 基本遗传算法的构成要素: 1、染色体编码方法:首先必须对问题的解空间进行编码 ,使之能用遗传算法进行操作。较常用的是二进制编码 方法,现在使用非二进制编码的也逐渐增多。 2、适应度函数(fitness function,又称为适应值适值函 数)用来评价一个染色体的好坏。 *史忠植 高级人工智能30 基本遗传算法的构成要素 3、遗传算子 选择算子(selection) :又称为复制算子。按照某种策略 从父代中挑选个体进入下一代,如使用比例选择、轮盘 式选择。 交叉算子(crossover):又称为杂交算子。将从群体中选 择的两个个体,按照某种策略使两个个体相互交换部分 染色体,从而形成两个新的个体。如使用单点一致交叉 。 变异算子(mutation):按照一定的概率(一般较小),改 变染色体中某些基因的值。 *史忠植 高级人工智能31 杂交操作举例 1 0 2 2 0 2 0 1 No Offspring Pt. of interchange CrossoverParentsOffspring 1110#0# 1#0111# 0001#11# 010#1000 #00#11 0#01#10# #100100 100#0111 6 17 1 1110#11# 0001#0# 0001#11# #00#11 #00#11 0#01#10# 000#0111 1#01#10# *史忠植 高级人工智能32 变异操作 简单的变异操作过程如下: 每个位置的字符变量都有一个变异概率, 各位置互 相独立。通过随机过程选择发生变异的位置: 产生一个新结构 , 其 中 是从对应位置 的字符变量的值域中随机选 择的一个取值。 可以同样得到。 *史忠植 高级人工智能33 反转操作 简单反转操作的步骤如下: 1) 从当前群体中随机选择一个结构 1) 从中随机选择两个数i和j, 并定义 i = mini,j, j=maxi,j; 3) 颠倒a中位置i、j之间的部分, 产生新的结构 *史忠植 高级人工智能34 基本遗传算法的构成要素 4、运行参数 N:群体大小,即群体中包含的个体的数量。 T:遗传算法终止的进化代数。 Pc:交叉概率,一般取为 0.40.99。 Pm:变异概率,一般取为 0.00010.1 。 *史忠植 高级人工智能35 基本遗传算法 1. 随机产生一个由固定长度字符串组成的初始群体; 2. 对于字符串群体,迭代地执行下述步骤,直到选种标准被 满足为止: 1) 计算群体中的每个个体字符串的适应值; 2) 应用下述三种操作(至少前两种)来产生新的群体: 复制: 把现有的个体字符串复制到新的群体中。 杂交: 通过遗传重组随机选择两个现有的子字符串, 产生新的字符串。 变异: 将现有字符串中某一位的字符随机变异。 3. 把在后代中出现的最高适应值的个体字符串指定为遗传算 法运行的结果。这一结果可以是问题的解(或近似解)。 *史忠植 高级人工智能36 基本遗传算法流程图 GEN=0 概率地选择遗传操作 随机创建初始群体 计算群体中每个个体的适应值 i:=0 显示结果 结束 GEN:=GEN+1 是 是 否 (转下页) i=N? GEN=M? 1 *史忠植 高级人工智能37 概率地选择遗传操作 根据适应值选 择一个个体 完成交叉 i:=i+1 i:=i+1复制个体 p(r)选择 (接上页) 基于适应值选 择两个个体 把新的两个孩 子加到群体中 p(c)交叉变异p(m) 把新的孩子加 入到群体中 完成变异 根据适应值选 择一个个体 把变异后个体 加入到群体中 1 *史忠植 高级人工智能38 轮盘式选择 l首先计算每个个体 i 被选中的 概率 l然后根据概率的大小将将圆盘 分为 n个扇形,每个扇形的大 小为 。选择时转动轮盘 ,参考点r落到扇形i则选择个 体i 。 . . . . . . p1 p2 pi r *史忠植 高级人工智能39 单点一致交叉 l首先以概率pc从种群中随机地选择两个个体 p1、p2。在1, 2, . . . ,l内随机选择一个数i,作为交叉的位置 ,称为交叉点。然后将两个个体交叉点后面 的部分交换。 l例如: 0110 101100 0110 011001 1100 011001 1100 101100 *史忠植 高级人工智能40 一致变异 以概率pm对种群中所有个体的每一位进行变 异。 对于个体pi的第j位,在0,1的范围内随机地生 成一个数r, 如果 r THEN 约定:条件的长度是固定的,用二进制数表示。 定义: If sj = 1 or sj = 0, then mj = sj If sj = #, then mj can be either 1 or 0. *史忠植 高级人工智能72 规则与消息 满足要求的全部消息构成子集, 即每个子集是在消 息空间的一个超平面。分类器系统是由一组分类器 C1, C2, CN、一个消息表、输入接口、输出接 口构成。每部分的主要功能如下: (1) 输入接口将当前环境状态翻译成标准消息。 (2) 分类器根据规则, 规定系统处理消息的过程。 (3) 消息表包含当前全部消息。 (4) 输出接口将结果消息翻译成效应器动作, 修改环境 状态。 *史忠植 高级人工智能73 分类器系统的基本结构 分类器 消息表 (a)全部消息进行条件测试 条件消息规约 输出接口 送到环境 输入接口 来自环境 (a) (b) (b)选中分类器产生新消息 *史忠植 高级人工智能74 分类器基本算法 1) 将输入接口全部消息放入消息表。 2) 将消息表中的全部消息与全部分类器所有 条件比较, 记录所有匹配。 3) 满足分类器条件部分的每组匹配, 将其动作 部分所规定的消息送到新的消息表。 4) 用新的消息表取代消息表中的全部消息。 5) 将消息表中的消息翻译成输出接口的要求, 产生系统当前的输出。 6) 返回到步骤(1)。 *史忠植 高级人工智能75 简单的视觉分类器系统 视觉向量 视野 运动向量 对象 检测器 11110 消息 *史忠植 高级人工智能76 性质检测器规定的值 1,如果移动对象 0,其它 (0,0),如果对象在视野的中间 (1,0),如果对象在中心的左边 (0,1),如果对象在中心的右边 1,如果系统是对象的近邻 0,其它 1,如果对象很大 0,其它 1,如果对象是狭长的 0,其它 *史忠植 高级人工智能77 规则表示 规则: IF 如果有“捕食(prey)”(small, moving,nonstriped object), 处于视野中间(centered), 非邻近 (nonadjacent), THEN 迅速移向对象 (ALIGN), (FAST). 可以表示为: 00#000001 / 0100000000000000, ALIGN, FAST. *史忠植 高级人工智能78 网络图 MOVINGSMALL NOT STRIPEDNEARFAR 01001 ALERT 10001 TARGET 11001 PORSUE 11010 APPROACH 11011 FLEE 11100 FREEZE 10010 DANGER *史忠植 高级人工智能79 网络图的规则表示 MOVING和ALERT之间的箭头: 00#1/01001# SMALL,NOT STRIPED and ALERT到 TARGET的箭头: 00#00#,01001#/ 10001# *史忠植 高级人工智能80 学习机制 分类器系统使用两个学习机制, 桶链(bucket brigade) 算法。基于对系统的贡 献, 对现有规则分配一个信用值。 规则发现算法。这包括遗传算法,该算法可 产生新规则,用于改善系统的知识库。 *史忠植 高级人工智能81 桶链算法 桶链(bucket brigade) 算法基于对系统的贡献, 对现有规则分配一个信用值。主要解决多条 规则同时要求被激活时的竞争问题。 例如:下面的情况下应该选择哪条规则。 011101# #:0000 # #00:0001 00# 0:1100 *史忠植 高级人工智能82 主要问题 引入信用值后的两个问题: 当多条规则同时要求被激活时,如何解 决竞争问题 对一规则被激活产生过作用的那些规则 如何分配信用 *史忠植 高级人工智能83 桶链算法 为解决上述两个问题,引入拍卖行和票据交易所: 当有多个分类器获得匹配时,每个分类器要出一个与 其强度成正比的叫价B 叫价高的分类器被激活并允许发送消息,同时通过票 据交易所,将其叫价B提供给激活的分类器。 如此继续下去,一条规则可通过消费者获利(增加了 强度),通过规则的不断激活形成一条消费者链,直 至最终消费者(达到目标)直接从环境中得到补偿。 若链中一条规则导致错误结论,则序列上该规则的强 度将减弱,并且沿着序列回溯,从而产生新的消费者 链 *史忠植 高级人工智能84 举 例 环境0111,强度为0,叫价系数为0.1。 索引号分类器强度 101# #:0000200 200# 0:1000200 311# #:1000200 4# #00:0001200 *史忠植 高级人工智能85 第一步 分类器 强度 消息 匹配 叫价 01# #:0000 200 E 20 00# 0:1000 200 11# #:1000 200 # #00:0001 200 *史忠植 高级人工智能86 第二步 分类器 强度 消息 匹配 叫价 01# #:0000 180 0000 00# 0:1000 200 1 20 11# #:1000 200 # #00:0001 200 1 20 两条规则同时激活 *史忠植 高级人工智能87 第三步 分类器 强度 消息 匹配 叫价 01# #:0000 220 00# 0:1000 180 1100 11# #:1000 200 2 20 # #00:0001 180 0001 2 18 *史忠植 高级人工智能88 第四步 分类器 强度 消息 匹配 叫价 01# #:0000 220 00# 0:1000 218 11# #:1000 180 1000 # #00:0001 162 3 16 *史忠植 高级人工智能89 第五步 分类器 强度 消息 匹配 叫价 强度 01# #:0000 220 220 00# 0:1000 218 218 11# #:1000 196 196 # #00:0001 146 0001 206 规则4达到目标获得补偿60。 *史忠植 高级人工智能90 投标改变分类器的强度 在时间t满足C 送去消息的分 类器 对在t-1作 用的分类 器投标 在时间t对分类器C的支持 *史忠植 高级人工智能91 分类器中的遗传算法 遗传算法可产生新规则,用于改善系统的知 识库。 可以在三种情况下应用GA: 1) 引入一个参数T(时间间隔),用于控制何 时使用GA。 2) 特殊情况时(如消息的条件都不能匹配) 使用GA。 3) 系统的性能太差。 *史忠植 高级人工智能92 算法步骤 1) t=0,随机生成集合Bt,|Bt|=M(大小); 2) 计算Bt中全体分类器的平均强度Vt,对每个分类 器赋予一个标准强度St(Cj)/Vt; 3) 给Bt中的每个分类器Cj赋予一个与其标准强度成 正比的概率,并根据Bt中的概率分布,从Bt中选 取n个分类器,nM; 4) 对每个分类器应用交叉算子,生成2n个分类器; 5) 将Bt中的2n个强度最低的分类器用新生成的2n个 取代; 6) t=t+1,转(2)。 *史忠植 高级人工智能93 算法说明 1) 算法中S0(Cj)是预知的; 2) 实现时考虑结束条件; 3) 该算法是经典GA的变种,其中没有变异 算子; 4) 新分类器的强度是由旧分类器的强度决 定的。 *史忠植 高级人工智能94 分类器强度调整算法 1) 将与所选动作相同的分类器形成子集 M,称作动作集 A。将不在 M中的其它分类器放在集合 NOTA中。 2) 在A中的全部分类器强度减少一个分数e。 3) 如果系统决策正确,则将赢利量R分配给A的强度; 4) 如果系统决策错误,则将赢利量R(其中0RR)分配给 A 的强度,从A的强度减少一个分数p。至少R和p中的一个 为0。 5) 从 NOTA中的强度减去一个分数t。 *史忠植 高级人工智能95 规则发现系统 在规则发现系统中, 学习经常是首先评价系统现有的规则 质量, 然后进行修改。Grefenstette 研制了一种规则发现系 统RUDI。问题求解级由简化的分类器系统组成。学习级是对知 识结构群体进行遗传算法操作, 每一个表示为一组规则表。知 识结构的整个行为控制这些结构的复制。 在RUDI中, 信用赋值方法赢利共享规划(Profit-Sharing Plan,简称PSP) 和桶链算法(BBA) 对每个规则提供互补的效用 信息。根据期望的外部奖励, PSP-强度对规则效用提供更精确 的评估。当问题求解时它被用作冲突消解。与此相反, BBA-强 度表示规则之间的动态相关性, 规则点火依次会聚到相似水平 。这种测度可以用作一组协作规则的聚类。 *史忠植 高级人工智能96 规则发现系统 Grefenstette 提出一种强度修改方案称作嬴利共享规划PSP 。在这种方案中问题求解划分成情节, 按所接受的外部奖励区 分。如果任何步情节在投标竞争中获胜, 则认为该规则 在该情 节活动。在情节t, PSP 修改每个活动规则 Ri的强度 Si(t) 如 下: Si(t + 1) = Si(t) -bSi(t) + bp(t), 其中, p(t) 称作在情节结束时所获得的外部奖励, 即当获 得外部奖励,从每个活动规则 搜集投标, 每个活动规则给 出 一部分外部奖励。考虑PSP 对给定规则Ri 的影响, 它按照 方程得到: *史忠植 高级人工智能97 规则发现系统 其中, t 的范围是在该情节规则 Ri 是活动的, 即 Si(t) 基本上外部奖励的权值平均p(t), (1 - b) 作为 指数衰减因子。如果 b 足够小,那么 S(t) 具有 p(t) 的平均值。如果外部奖励 p(t)是常数,p*, 那么Si 收敛到 一个平衡值 Si*: *史忠植 高级人工智能98 规则发现系统 在常数赢利下, PSP 将以下列速率减少误差 Ei(t) = p* - Si(t) 强度每次改变, 以因子b减少当前强度与平衡强度之差。 *史忠植 高级人工智能99 规则发现系统 我们看出, 奖励相当是常数情况下, 在PSP下每 个规则强度很快收敛到一个平衡强度, 可以预 测情节结束时将接收的奖励水平。 PSP的一种可能的限制是它取决于这种前提, 成 功外部奖励区分的情节所对应的合适区间, 在 这个区间里进行信用赋值。情节的选择非常重 要。 *史忠植 高级人工智能100 规则发现系统

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论