《AI0512进化计算与遗传算法人工智能课程浙江大学研究生》由会员分享，可在线阅读，更多相关《AI0512进化计算与遗传算法人工智能课程浙江大学研究生（88页珍藏版）》请在金锄头文库上搜索。
1、AI-05-12-AI-05-12-进化计算与遗进化计算与遗传算法传算法-人工智能课人工智能课程程-浙江大学研究生浙江大学研究生本章主要参考文献：本章主要参考文献：1 陈国良陈国良, 王煦法王煦法 等等. 遗传算法及其应用遗传算法及其应用. 人民邮电出版社人民邮电出版社, 1996.2 王正志王正志, 薄涛薄涛. 进化计算进化计算. 国防科技大学出版社国防科技大学出版社, 2000.3 张颖张颖, 刘艳秋刘艳秋. 软计算方法软计算方法. 科学出版社科学出版社, 2002. pp69-108.4 史忠植史忠植. 高级人工智能高级人工智能. 科学出版社科学出版社, 1998. pp249-270.
2、5 史忠植史忠植. 知识发现知识发现. 清华大学出版社清华大学出版社, 2002. pp265-294.6 Mitchell, T. M.著著, 曾华军等译曾华军等译. 机器学习机器学习. 机械工业出版社机械工业出版社, 2003. pp179-196.7 贺前华贺前华, 韦岗韦岗, 陆以勤陆以勤. 基因算法研究进展基因算法研究进展. 电子学报电子学报, 1998, 26(10): 118-122, 103.2内容12.1 概述12.2 进化系统理论的形式模型12.3 达尔文进化算法12.4 分类器系统12.5 桶链算法12.6 遗传算法12.7 并行遗传算法12.8 分类器系统Boole12
3、.9 规则发现系统12.10 进化策略12.11 进化程序设计312.1 概述12.1.1 背景背景 人们对很多高度非线性问题的内部机理还很不清楚： 智能模拟智能模拟 非线性优化非线性优化 图像识别图像识别，等等。 要解决上述问题，就需要一些具有自组织、自适具有自组织、自适应能力的大规模并行算法应能力的大规模并行算法，模拟生物或自然现象就成为AI中的一种自然而又重要的研究方向。因此产生了如下新方法： 人工神经网络人工神经网络 遗传算法、进化计算遗传算法、进化计算，等等。4 生物进化的主要特点：生物进化的主要特点：进化的结果非常复杂进化的结果非常复杂 进化的过程非常简单：繁殖、变异、竞争、选择进
4、化的过程非常简单：繁殖、变异、竞争、选择 基于自然选择的软件设计方法解决传统方法中存在的如下最大障碍：需要事先描述问题的全部特点，需要事先描述问题的全部特点，并说明针对问题的特点，程序应采取的措施并说明针对问题的特点，程序应采取的措施。 利用进化机理，人们可以“培育培育”程序，去解决那些结构尚不清楚的问题。12.1.1 背景（续）背景（续）5 遗传算法和进化计算的基本思想基本思想：来源于生物进化过程, 它是基于进化过程中的信息遗传机制信息遗传机制和优胜劣汰的自然选择原则自然选择原则的搜索算法搜索算法（以字符串表示状态空间）。遗传算法用概率搜索概率搜索过程在该状态空间中搜索，产生新的样本。 遗传
5、算法和进化计算是一种通用的问题求解方法，它采用某种编码技术来表示各种复杂的结构采用某种编码技术来表示各种复杂的结构，并将每个编码称为一个个体个体。算法维持一个一定数目的编码集合，称为种群种群，并通过对种群中的每个个体进行某些遗传操作（如变异、交叉、选择等）遗传操作（如变异、交叉、选择等）来模拟进化过程，最终获得一些具有较高性能指标的编码。 12.1.3 基本思想基本思想6发展历史发展历史遗传算法的发展历史： 1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。1967年，Bagley在他的论文中首次提出了遗传算法遗传算法（Genetic Algorit
6、hm，简称GA）这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。 7发展历史（续）1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著“Adaptation in Natural and Artificial Systems”(自然和人工系统的自然和人工系统的自适应性自适应性)该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理模式理论（Schemata Theory），该理论首次确认了结构重组遗传操作对于获得
7、隐并行性的重要性。同年，DeJong完成了他的重要论文“An Analysis of the Behavior of a Class of Genetic Adaptive Systems”(遗传自适自适应系系统的行的行为分析分析)。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑里程碑，这是因为他把Holland的模式理论与他自己的实验结合起来。 8发展历史（续）1988年Mayr提出新达尔文进化理论新达尔文进化理论。1989年Goldberg对遗传算法从理论、方法和应用上作了系统的总结.9特 点特点：特点：通用通用鲁棒鲁棒次优解、满意解次优解、满意解遗传算法能解决的问题：遗
8、传算法能解决的问题：优化优化NP完全问题完全问题NP难解问题难解问题高度复杂的非线性问题高度复杂的非线性问题10进化计算和遗传算法的主要应用领域：进化计算和遗传算法的主要应用领域：应用领域应用领域说说 明明控制控制规划规划设计设计组合优化组合优化图像处理图像处理信号处理信号处理机器人机器人人工生命人工生命瓦斯管道控制、防避导弹控制、机器人控瓦斯管道控制、防避导弹控制、机器人控制制生产规划、并行机任务分配生产规划、并行机任务分配VLSI部局、通信网络设计、喷气发动机设部局、通信网络设计、喷气发动机设计计TSP问题、背包问题、图划分问题问题、背包问题、图划分问题模式识别、特征抽取模式识别、特征抽取
9、滤波器设计滤波器设计路径规划路径规划生命的遗传进化生命的遗传进化11遗传算法与自然进化的比较自然界自然界染色体染色体基因基因等位基因等位基因(allele)染色体位置染色体位置(locus)基因型基因型(genotype)表型表型(phenotype)遗传算法遗传算法字符串字符串字符，特征字符，特征特征值特征值字符串位置字符串位置结构结构参数集，译码结构参数集，译码结构12面向执行的学习系统面向执行的学习系统任务子系统学习子系统任务检测器任务效应器执行效应器执行检测器13新达尔文进化理论的主要论点新达尔文进化理论的主要论点1)个体个体是基本的选择目标;2)随机过程随机过程在进化中起重大作用,
10、遗传变异大部分是偶然现象;3)基因型变异基因型变异大部分是重组的产物, 特别是突变;4)逐渐进化可能与表型不连续有关;5)不是所有表型变化都是自然选择的必然结果;6)进化是在适应中变化的, 形式多样, 不仅是基因的变化;7)选择是概率型的选择是概率型的, 而不是决定型的。而不是决定型的。1412.2 进化系统理论的形式模型 进化在个体群体中起作用。1974年Waddington指出基因型基因型和表型表型之间关系的重要性。群体禁止异构环境。但是“后成环境后成环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境选择环境”发生作用。 【注】：这种多维选择环境与后成环境空间是不同的。
11、现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代作出贡献。 基于上述思想，1989年Muhlenbein和Kindermann提出了一种称为进化系统理论进化系统理论的形式模型。15 进化系统理论的形式模型进化的主要过程后生环境遗传操作符选择环境gp16进化系统理论的形式模型其中，g 是基因型基因型 p 是表型表型 基因gi的可能值称为等位基因等位基因。 在门德尔(Mendel)遗传学中，假设每个基因有有限个等位基因。17进化系统理论的形式模型 这个变换函数给出了模型，说明表型的发展是通过基因与环境的交互作用而实现的。 变换过程是高度非线性的变换过程是高度非线性
12、的。18进化系统理论的形式模型 质质量函数量函数q给出了具体选择环境ESi下表型的质量，其定义如下： 质量函数定义适适应应度度，用于达尔文选择。目前主要有三种通用模型，即 门门德德尔尔遗传遗传学学 遗传遗传生生态态学学 进进化配子化配子19 门德尔遗传学 在门门德德尔尔遗遗传传学学中，基因型被详细模型化，而表型和环境几乎被忽略；在遗遗传传生生态态学学中恰好相反；进进化配子论化配子论是从社会生物学导出的模型。 首先，讨论门德尔遗传学的选择模型。为简单起见，假设一个基因具有n个等位基因a1,an。二倍基因型以元组(ai, aj)为特征。定义pi,j为总群体中基因型(ai, aj)的频频度度。假设基
13、因型与表型相等。质量函数给每个表型赋值。 q (ai, aj) = qi,j qi,j可被解释为出生率减去死亡率出生率减去死亡率。 20 门德尔遗传学 假设 pi,j是下一代表型(ai, aj)的频度。然后达达尔尔文文选择选择根据选择方程调整表型的分布: 其中，Q是群体的平均适应度平均适应度。21 门德尔遗传学设 pi 是群体中等位基因的频率。如果 pi,j = pi pj那么，可得基因型空间GS中的一个选择方程选择方程为：22 门德尔遗传学 这个离散的选择方程可以用连续方程近似: 如果 qi,j = qj,i, 那么这个离散的选择方程可以用连续方程近似: 23 门德尔遗传学 这个方程很容易被
14、证明: 这个结果称作Fisher基基本本定定理理。它说明平平均均适适应应度度随随适适应应度度的的差差别别呈呈正正比比例例增增加加。实际上，全部可能的基因型仅有一部分实现。这就是遗遗传传操操纵纵子子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最最重重要要的的操操纵纵子子是是突突变变和和重重组组。2412.3 达尔文进化算法 根据定量遗传学，达尔文进化算法达尔文进化算法采用简单的突突变变/ /选择动力学选择动力学。达尔文算法的一般形式可以描述如下：其中，：是一代的双亲数目双亲数目，：为子孙数目子孙数目，：称作“混混杂杂”数，若双亲混合其基因，则 = 2。【注】：仅当是
15、最好的个体才允许产生子孙。 逗号“, ,”表示双亲们没没有有选选择择，加号“+ +”表 示双亲有选择有选择。 2512.3 达尔文进化算法1)建立原始种体。2)通过突变建立子孙。3)选择：4)返回到步骤(1)。2612.4 分类器系统 Holland和他的同事提出了一种分类器系统分类器系统的认知模型,其中的规则不是规则集, 而是遗传算法操纵的内部实体。 下图给出了分类器系统的一般结构, 它由三层动三层动作作构成,即执行子系统执行子系统、信用赋值子系统信用赋值子系统和发现子系发现子系统统。27 分类器系统 （1）执执行子系行子系统统处在最低层, 直接与环境进行交互。它与专家系统相同,由产生式规则
16、构成。但是, 它们是通过消息消息传传送送, ,高度高度并行并行工作。这类规则称作分分类类器器。 （2）分类器系统中的学习, 要求环境提供反馈, 确认所希望的状态是否达到。系统将评价这些规则的有效性, 这些活动常常称作信用信用赋值赋值。有些特定算法专门用来实现信用赋值, 例如, 桶链算法桶链算法。 （3 3）最后一最后一层层是是发现发现子系子系统统, , 该该系系统统必必须产须产生新的生新的规则规则, , 取代当前用取代当前用处处不大的不大的规则规则。通。通过过系系统统累累积积的的经验产经验产生生规则规则。系。系统统根据适根据适应值应值, , 使用使用遗传遗传算法算法选择选择、重组和取代规则。重
17、组和取代规则。28 分类器系统分类器系统的一般结构发现遗传算法信用赋值桶链执行分类器系统消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息29 分类器系统 分类器系统是平行执行、消息传递和基于规则的系统。在简单的方案中,消息采用规定的字母, 全部为固定长度。全部规则采用条件/动作形式。每个条件规定必须满足的信息, 每个动作规定当条件满足时所发送的消息。 为了方便, 假设消息采用长度为l的二进制字符串记录, 字符采用子集1, 0, #。30规则与消息产生式规则：IF THEN 约定：条件的长度是固定的，用二进制数表示。定义： If sj = 1 or sj = 0, then mj
18、 = sj If sj = #, then mj can be either 1 or 0. 31规则与消息 满足要求的全部消息构成子集, 即每个子集是在消息空间的一个超平面。分类器系统是由一组分类器 C1, C2, CN、一个消息表、输入接口、输出接口构成。每部分的主要功能如下: (1) 输入接口将当前环境状态翻译成标准消息。(2) 分类器根据规则, 规定系统处理消息的过程。(3) 消息表包含当前全部消息。(4) 输出接口将结果消息翻译成效应器动作, 修改环境状态。32分类器系统的基本结构分类器消息表(a)全部消息进行条件测试条件消息规约输出接口送到环境输入接口来自环境(a)(b)(b)选中
19、分类器产生新消息33分类器基本算法1)将输入接口全部消息放入消息表。2)将消息表中的全部消息与全部分类器所有条件比较, 记录所有匹配。3)满足分类器条件部分的每组匹配, 将其动作部分所规定的消息送到新的消息表。4)用新的消息表取代消息表中的全部消息。5)将消息表中的消息翻译成输出接口的要求, 产生系统当前的输出。6)返回到步骤(1)。34简单的视觉分类器系统视觉向量视野运动向量对象检测器11110消息35性质检测器规定的值1，如果移动对象0，其它(0,0)，如果对象在视野的中间(1,0)，如果对象在中心的左边(0,1)，如果对象在中心的右边1，如果系统是对象的近邻0，其它1，如果对象很大0，其
20、它1，如果对象是狭长的0，其它36规则表示规则：IF 如果有“捕食(prey)”(small, moving,nonstriped object), 处于视野中间(centered), 非邻近 (nonadjacent),THEN 迅速移向对象 (ALIGN), (FAST).可以表示为：00#000001 / 0100000000000000, ALIGN, FAST.37网络图MOVINGSMALL NOT STRPEDNEARFAR01001ALERT10001TARGET11001PORSUE11010APPROACH11011FLEE11100FREEZE10010DANGER38网
21、络图的规则表示MOVING和ALERT之间的箭头：00#1/01001#SMALL，NOT STRIPED and ALERT到TARGET的箭头：00#00#，01001#/10001#39学习机制分类器系统使用两个学习机制，桶链(bucket brigade) 算法。基于对系统的贡献, 对现有规则分配一个信用值。规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。4012.5 桶链算法 桶链桶链(bucket brigade) 算法算法基于对系统的贡献, 对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问题竞争问题。 例如：下面的情况下应该选择哪条规则。
22、011101# #：0000# #00：000100# 0：110041主要问题引入信用值后的两个问题：当多条规则同时要求被激活时，如何解决竞争问题对一规则被激活产生过作用的那些规则如何分配信用42桶链算法为解决上述两个问题，引入拍卖行和票据交易所：当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价B叫价高的分类器被激活并允许发送消息，同时通过票据交易所,将其叫价B提供给激活的分类器。如此继续下去，一条规则可通过消费者获利（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。若链中一条规则导致错误结论，则序列上该规则的强度将减弱，并且
23、沿着序列回溯，从而产生新的消费者链43举例环境0111，强度为0，叫价系数为0.1。索引号分类器强度 101# #：0000200 200# 0：1000200 311# #：1000200 4# #00：000120044第一步分类器 强度 消息 匹配 叫价01# #：0000 200 E 2000# 0：1000 20011# #：1000 200# #00：0001 20045第二步分类器 强度 消息 匹配 叫价01# #：0000 180 000000# 0：1000 200 1 2011# #：1000 200# #00：0001 200 1 20两条规则同时激活46第三步分类器 强
24、度 消息 匹配 叫价01# #：0000 22000# 0：1000 180 110011# #：1000 200 2 20# #00：0001 180 0001 2 1847第四步分类器 强度 消息 匹配 叫价01# #：0000 22000# 0：1000 21811# #：1000 180 1000# #00：0001 162 3 1648第五步分类器 强度 消息 匹配 叫价 强度01# #：0000 220 22000# 0：1000 218 21811# #：1000 196 196# #00：0001 146 0001 206规则4达到目标获得补偿60。49投标改变分类器的强度在时
25、间t满足C送去消息的分类器对在t-1作用的分类器投标在时间t对分类器C的支持50分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。可以在三种情况下应用GA：1)引入一个参数T（时间间隔），用于控制何时使用GA。2)特殊情况时（如消息的条件都不能匹配）使用GA。3)系统的性能太差。51算法步骤1)t=0，随机生成集合Bt，|Bt|=M（大小）；2)计算Bt中全体分类器的平均强度Vt，对每个分类器赋予一个标准强度St(Cj)/Vt；3)给Bt中的每个分类器Cj赋予一个与其标准强度成正比的概率，并根据Bt中的概率分布，从Bt中选取n个分类器，nM；4)对每个分类器应用交叉算子，生成2n个
26、分类器；5)将Bt中的2n个强度最低的分类器用新生成的2n个取代；6)t=t+1，转(2)。52算法说明1)算法中S0(Cj)是预知的；2)实现时考虑结束条件；3)该算法是经典GA的变种，其中没有变异算子；4)新分类器的强度是由旧分类器的强度决定的。5312.6 遗传算法遗传算法先将搜索结构编码为字符串形式, 每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。54 遗传算法与自然界相似，遗传算法
27、对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有复制、杂交、变异和反转。55遗传算法与传统优化算法的主要不同1)遗传算法不是直接作用在参变量集上, 而是利用参变量集的某种编码;2)遗传算法不是从单个点, 而是在群体中从一个点开始搜索;3)遗传算法利用适应值信息, 无需导数或其它辅助信息;4)遗传算法利用概率转移规
28、则, 而非确定性规则。56遗传算法的准备工作1)确定表示方案;2)确定适应值的度量;3)确定控制该算法的参数和变量;4)确定怎样指定结果及程序运行结束的标准。57基本的遗传算法1.随机产生一个由固定长度字符串组成的初始群体;2.对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：1)计算群体中的每个个体字符串的适应值;2)应用下述三种操作(至少前两种)来产生新的群体:复制: 把现有的个体字符串复制到新的群体中。杂交: 通过遗传重组随机选择两个现有的子字符串, 产生新的字符串。变异: 将现有字符串中某一位的字符随机变异。3.把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。
29、这一结果可以是问题的解(或近似解)。58基本遗传算法的流程图GEN=0概率地选择遗传操作随机创建初始群体是否满足选中标准？计算群体中每个个体的适应值i:=0i:=M指定结果结束GEN:=GEN+1是是否（转下页）59概率地选择遗传操作根据适应值选择一个个体完成杂交i:=i+1i:=i+1完成繁殖p(r)繁殖（接上页）基于适应值选择两个个体把新的两个孩子加到群体中p(c)杂交变异p(m)把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中60表示模式 所谓模式就是一个相同的构形, 它描述的是一个串的子集, 这个集合中的串之间在某些位上相同。 模式的复制生长方程： 这表明,
30、 一个特定的模式按照其平均适应值与群体的平均适应值之间的比率生长。61杂交操作杂交操作是个有结构、随机的字符串间信息交换过程。简单的杂交操作分为三步从当前群体B(t)中选择两个结构：随机选择一个整数交换a和a中位置x左边的元素, 产生两个新的结构：62具有强度的遗传算法1.在t = 0时随机产生M字符串的群体B(t)。计算群体B(t)中字符串的平均强度 v(t), 给群体B(t)中的每个字符串赋以规范值 S(Cj, t)/v(t)。2.对群体B(t)中的每个字符串赋与一个概率值, 其值与规范值成正比。然后, 使用概率分布, 从B(t)中选择n对字符串, nM, 并且将它们复制。3.对每对复制字
31、符串进行杂交操作, 形成2n个新的字符串。4.用步骤(3)中生成的2n个新的字符串取代群体B(t)中2n个强度最低的字符串。5.时间 t 变为 t + 1, 返回步骤(1)。63杂交操作举例10220201No OffspringPt. of interchangeCrossoverParentsOffspring1110#0#1#0111#0001#11#010#1000#00#110#01#10#100100100#011161711110#11#0001#0#0001#11#00#11#00#110#01#10#000#01111#01#10#64变异操作简单的变异操作过程如下:每个位置
32、的字符变量都有一个变异概率, 各位置互相独立。通过随机过程选择发生变异的位置：产生一个新结构 , 其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。65反转操作简单反转操作的步骤如下:1)从当前群体中随机选择一个结构2)从中随机选择两个数i和j, 并定义3) i = mini,j, j=maxi,j;3)颠倒a中位置i、j之间的部分, 产生新的结构66遗传算法举例问题：求（1）编码： 此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体： 编码： 01101，11000，01000，10011 解码： 13 24 8 19 适
33、应度： 169 576 64 361（3）适应度评价：67（4）选择：选择概率 个体： 01101，11000，01000，10011 适应度： 169 576 64 361 选择概率：0.14 0.49 0.06 0.31选择结果：01101，11000，11000，10011（5）交叉操作：发生交叉的概率较大 哪两个个体配对交叉是随机的 交叉点位置的选取是随机的（单点交叉） 0110 1 01100 11 000 11011 1100 0 11001 10 011 1000068（6）变异：发生变异的概率很小（7）新群体的产生： 保留上一代最优个体，一般为10%左右，至少1个 用新个体取代
34、旧个体，随机取代或择优取代。 11000，11011，11001，10011（8）重复上述操作：说明：GA的终止条件一般人为设置； GA只能求次优解或满意解。分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解择优取代有问题。 若随机的将个体01101选入新群体中，有可能找到最优解。6912.7 并行遗传算法基于离散门德尔模型的遗传算法由六部分组成：1)对给定问题求解的染色体表示；2)求解的原始物种；3)起环境作用的品质函数；4)可以生成子孙的个体的选择过程；5)一种遗传操纵子，如变异、重组；6)控制算法本身的参数。70并行遗传算法并行遗传算法：1)给定具有不同开始表型的N个个体；2
35、)每个个体计算局部最大；3)选择在“近邻”中选择配对；4)用重组和突变创建子孙；5)返回步骤2。7112.8 分类器系统Boole Wilson 于1987年开发了一个布尔问题的分类器系统 Boole(Wilson 1987)。一个布尔函数变量L 是从长度为L的字符串到 0, 1的映射。学习函数意味获得对任何输入字符串能给出正确输出0 或 1的能力。72分类器强度调整算法1)将与所选动作相同的分类器形成子集 M，称作动作集 A。将不在 M中的其它分类器放在集合 NOTA中。2)在A中的全部分类器强度减少一个分数e。3)如果系统决策正确，则将赢利量R分配给A的强度;4)如果系统决策错误，则将赢利
36、量R(其中0RR)分配给 A的强度，从A的强度减少一个分数p。至少R和p中的一个为0。5)从 NOTA中的强度减去一个分数t。73Boole的遗传算法1)根据P中分类器的强度，通过概率选择第一个分类器 。2)根据概率 , 与步骤(1)相同，选择分类器 ，并对 和 进行杂交；从结果中选择一个作为子孙，另一个被抛弃。3)如果步骤 (2) 未完成，则复制 形成子孙。4)对子孙应用变异操作，以概率 改变每个分类的等位基因。5)如果通过杂交生成子孙，每个父母的强度减少三分之一，子孙的初始强度等于父母减少的总和；否则减少 的一半，而子孙的初始强度等于减少的量。6)将子孙加到P中。7)根据P中分类器强度的概
37、率分布，删除最小的一个分类器。7412.9 规则发现系统 在规则发现系统中, 学习经常是首先评价系统现有的规则质量, 然后进行修改。Grefenstette 研制了一种规则发现系统RUDI。问题求解级由简化的分类器系统组成。学习级是对知识结构群体进行遗传算法操作, 每一个表示为一组规则表。知识结构的整个行为控制这些结构的复制。 在RUDI中, 信用赋值方法赢利共享规划(Profit-Sharing Plan, 简称PSP) 和桶链算法(BBA) 对每个规则提供互补的效用信息。根据期望的外部奖励, PSP-强度对规则效用提供更精确的评估。当问题求解时它被用作冲突消解。与此相反, BBA-强度表示
38、规则之间的动态相关性, 规则点火依次会聚到相似水平。这种测度可以用作一组协作规则的聚类。 75 规则发现系统 Grefenstette 提出一种强度修改方案称作嬴利共享规划PSP。在这种方案中问题求解划分成情节, 按所接受的外部奖励区分。如果任何步情节在投标竞争中获胜, 则认为该规则在该情节活动。在情节t, PSP 修改每个活动规则Ri的强度 Si(t) 如下: Si(t + 1) = Si(t) -bSi(t) + bp(t), 其中, p(t) 称作在情节结束时所获得的外部奖励, 即当获得外部奖励,从每个活动规则搜集投标, 每个活动规则给出一部分外部奖励。考虑PSP 对给定规则Ri 的影响
39、, 它按照方程得到:76 规则发现系统其中, t 的范围是在该情节规则 Ri 是活动的, 即Si(t) 基本上外部奖励的权值平均p(t), (1 - b) 作为指数衰减因子。如果 b 足够小,那么 S(t) 具有 p(t) 的平均值。如果外部奖励 p(t)是常数,p*, 那么Si 收敛到一个平衡值 Si*:77 规则发现系统在常数赢利下, PSP 将以下列速率减少误差 Ei(t) = p* - Si(t)强度每次改变, 以因子b减少当前强度与平衡强度之差。 78 规则发现系统我们看出, 奖励相当是常数情况下, 在PSP下每个规则强度很快收敛到一个平衡强度, 可以预测情节结束时将接收的奖励水平。
40、PSP的一种可能的限制是它取决于这种前提, 成功外部奖励区分的情节所对应的合适区间, 在这个区间里进行信用赋值。情节的选择非常重要。79 规则发现系统在桶链算法BBA中, 是基于规则之间单独处理的, 可以避免有关情节的假设。假设规则 Ri 在tau 步点火, 规则 Rj 在 tau + 1点火, 那么BBA 按照下面公式修改规则 Ri的强度 Si:第一个改变意味BBA 在给定的情节修改规则强度多于一次。第二个改变导致PSP与BBA基本的不同。PSP强度预测所期望的情节结束获得的外部奖励是在规则点火, BBA的强度预测所期望的内部奖励是在规则的下一步。 8012.9 规则发现系统RUDI的控制结
41、构问题求解BBA/PSP遗传算法任务执行强度新规则信用奖励81PSP与BBA比较奖励：10000300初始状态结束状态82不同的强度修改方案规则PSP强度BBA强度1000648299567100064546443003009995313003008312.10 进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下:(1)定义的问题是寻找n维的实数向量x, 它使函数(2) 双亲向量的初始群体从每维可行范围内随机选择。(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。(4) 根据最小误差选择向量为下一代新的双亲。(5) 向量的标准偏差保持不变, 或者
42、没有可用的计算方法, 那么处理结束。8412.11 进化程序设计 进化程序设计(evolutionary programming)的过程, 可理解为从所有可能的计算机程序形成的空间中, 搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。85进化程序设计步骤1.产生出初始群体, 它由关于问题(计算机程序)的函数随机组合而成。2.迭代完成下述子步骤，直至满足选种标准为止:1)执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值2)应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序, 创造出新的计算机程序个体。3. 在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。86Thanks！87结束结束
