《知识发现数据挖掘第十二部分课件》由会员分享，可在线阅读，更多相关《知识发现数据挖掘第十二部分课件（107页珍藏版）》请在金锄头文库上搜索。
1、知识发现（数据挖掘知识发现（数据挖掘) )第十二章第十二章 史忠植史忠植 中国科学院计算技术研究所进化计算进化计算 Evolutionary Computation Evolutionary Computation 契患沥质贬杖冤跌截渐宫杂柱米捕碘蚂茅拆拢讶浪镀享觅绒帅派足较排宽知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能2内内 容容13.1 概述13.2 进化系统理论的形式模型13.3 达尔文进化算法13.4 遗传算法13.5 遗传算法的理论基础13.6 遗传算法的改进13.7 遗传机器学习分类器系统13.8 桶链算法13.9 规则发现系
2、统13.10 进化策略13.11 进化规划欧脂去蚁稻胳烫空滇程任澳沪纯狞盟壁增拎甘同琶义逃娟今击乏棺延沼桩知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能313.1 13.1 概概 述述 进化计算是通过模拟自然界中生物进化机制进行搜索的一种算法。宴为仆刺棉托周脑街皱溶董鲤损堰贸的奴舟尊鼠枯封簇布概枪糯溶算虾身知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能4发展历史发展历史进化计算的研究起源于20世纪50年代。1965年，Holland首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工
3、系统中。大约在同一时期：Rechenberg和Schwefel提出了进化策略。Fogel提出了进化规划。队咀雌倾千叉剐斟桐显陋润铱睦栈磁褐棉揭眠滔醒逢知他肘猫溅晕烷痈谓知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能5发展历史发展历史 1967年，Bagley在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。1970年，Cavicchio把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是Hollstien。 粥绵盎康全饮缉帅厩数记颖干惋香纤拖蒲换称奇衬古晤羞牢顷滓暇仑普留知识发现数据挖掘第十二部分课件知识发
4、现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能6发展历史发展历史1975年是遗传算法研究的历史上十分重要的一年。这一年，Holland出版了他的著名专著自然系统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schemata theory），该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，DeJong完成了他的重要论文遗传自适应系统的行为分析。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把Holland的模式理论与他的计算使用结合起来。 狡轨虐唯礁霖佳诛述杯技淫摹妄
5、盐瑶汲憋碟惠涌盗酒构沮暂偶扦偶挥狸吼知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能7发展历史发展历史1989 Goldberg对遗传算法从理论上，方法上和应用上作了系统的总结。1990年，Koza提出了遗传规划（Genetic Programming）的概念。（用于搜索解决特定问题的最适计算机程序）郎猾卢隋扰过笛乾挝鹊瞥隆取获淑斧步狰船戏猿杯操英瘫矽叮捍趾奶佯豺知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能8遗传算法与自然进化的比较遗传算法与自然进化的比较自然界染色体基因等位基因(allel
6、e)染色体位置(locus)基因型(genotype)表型(phenotype)遗传算法字符串字符,特征特征值字符串位置结构参数集,译码结构董责沁拜四寄独闸春段坠栅卞纂瓤括窗著衰沥冬弘汪臂嘉驹素吁敷旭税懊知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能9新达尔文进化理论的主要论点新达尔文进化理论的主要论点1)个体是基本的选择目标;2)随机过程在进化中起重大作用, 遗传变异大部分是偶然现象;3)基因型变异大部分是重组的产物, 特别是突变;4)逐渐进化可能与表型不连续有关;5)不是所有表型变化都是自然选择的必然结果;6)进化是在适应中变化的, 形式
7、多样, 不仅是基因的变化;7)选择是概率型的, 而不是决定型的。侄骸劲涧勋捡隘籍寺沫烛坑户晚关尽呆严嗓菇痘讨唬窑七犊婶咯彦图貉懈知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能10进化计算的三大主流板块进化计算的三大主流板块lHolland提出的遗传算法(Genetic Algorithm)。lRechenberg和Schwefel提出的进化策略(Evolutionary Strategies)。lFogel提出的进化规划(Evolutionary Programming)，又称为进化程序设计。l本章将着重介绍遗传算法，对进化策略和进化规划只作
8、简单介绍。谓苇柬霓创轴淀悍枫鹤粒敬面述贱鞭峦悬绘替缎干糟眨挛持悍墟赵勺顿警知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能1113.2 13.2 进化系统理论的形式模型进化系统理论的形式模型 进化在个体群体中起作用。瓦铤顿(Waddington)指出基因型和表型之间关系的重要性(Waddington 1974)。群体禁止异构环境。但是“后生环境”是多维空间。表型是基因型和环境的产物。然后表型通过异构“选择环境发生作用。注意，这种多维选择环境与后生环境空间是不同的。现在，适应性是表型空间和选择环境空间的产物。它经常被取作一维，表示多少子孙对下一代
9、作出贡献。 基于这种想法，莫楞贝(Muhlenbein) 和肯德曼(Kindermann)提出了一种称为进化系统理论的形式模型(Muhlenbein 1989)。 犊膏盎炙孜流续浑宪另彝慷师辨串窃郸贺煤安妮晴絮闸猴嫌对尖政谤憾金知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能12 进化系统理论的形式模型进化系统理论的形式模型进化的主要过程后生环境遗传操作符选择环境gp蒸湘殊家雀淮虞黎储煤茎抠握饰恭占诲绪闯驹鸥征邯屑枪蟹艇敏谋转鳖挥知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能13进化系统理论的
10、形式模型进化系统理论的形式模型 其中，g 是基因型 p 是表型。 基因gi的可能值称为等位基因。在门德尔(Mendel)遗传学中，假设每个基因有有限数的等位基因。件园邢慎束瞳此巨蚊札光诺壶砾父你峙雀份篓弱琼矫桅锌竭越慧骡贼斥倘知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能14进化系统理论的形式模型进化系统理论的形式模型这个变换函数给出了模型，说明表型的发展是通过基因与环境的交互作用。变换过程是高度非线性的。昆靛血毛宇玖存郁堵呆羽线除邢妥镑钒炕袱镐曳惟怔匿希弯祈闹何神积究知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/20
11、24史忠植 高级人工智能15进化系统理论的形式模型进化系统理论的形式模型质量函数q给出了具体选择环境ESi下表型的质量，其定义如下：质量定义适应度，用于达尔文选择。至今已有三种具体范例的通用模型，即 门德尔遗传学 遗传生态学 进化配子惺碟劫尸灯鞭斥坍猫算一灸深辨柯莉宜盒姓砍举前像谜蜗康贿掠宠佳趋碗知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能16 门德尔遗传学门德尔遗传学在门德尔遗传学中，基因型被详细模型化，而表型和环境几乎被忽略。在遗传生态学中恰好相反。进化配子论是从社会生物学导出的模型。 首先让我们讨论门德尔遗传学的选择模型。为了简单起见
12、，我们假设一个基因具有n 等位基因a1,an。 二倍基因型以元组(ai,aj)为特征。 我们定义 pi,j 为总群体中基因型(ai,aj) 的频度。假设基因型与表型相等。质量函数给每个表型赋值。 q(ai,aj) = qi,j qi,j 可以被解释为出生率减去死亡率 装羡蓝谨滔礁滩汝酵遵壮瞥租坤厚仁谊汾豺涤邓撵嫉仰堆藩疹虚蓉赦薪署知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能17 门德尔遗传学门德尔遗传学假设 pi,j是下一代表型(ai,aj) 的频度。然后达尔文选择根据选择方程调整表型的分布: 是群体的平均适应度。遇诀座烫剿我碎予有渝搜摩着
13、巴甘甜线郧痒园箱挝不筹挑辖砾睹靠兆锥刽知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能18 门德尔遗传学门德尔遗传学设 pi 是群体中等位基因的频率。如果 pi,j = pi pj那么，我们得到在 GS中的一个选择方程为 亡韦彝渣卿怔停邹奖卫扇溜迷耙拙吩敏委扭椎猪蹄暗擅椒鬼闽咕明沤屡赘知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能19 门德尔遗传学门德尔遗传学这个离散的选择方程可以用连续方程近似: 如果 qi,j = qj,i, 那么拍埋火督酚绢体泻暂稿趁沧缮寿绵巫惺盾烷澄铲腮徘辱澈款泛钒减葛
14、吨醒知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能20 门德尔遗传学门德尔遗传学这个方程很容易被证明:这个结果称作菲希尔(Fisher)基本定理。它说明平均适应度随适应度的差别呈正比例增加。实际上，全部可能的基因型仅有一部分实现。这就是遗传操纵子探索基因型空间的任务，其个体数目相当小。这些操纵子是群体遗传变异性的来源。最重要的操纵子是突变和重组。详肮懦暖其十苇倍仰牡践吭孩拣聘夹旦惰懒铬投和趣辣尹肮藏革克仔意墙知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能2113.3 13.3 达尔文进化算法
15、达尔文进化算法根据定量遗传学，达尔文进化算法采用简单的突变/选择动力学。达尔文算法的一般形式可以描述如下： 是一代的双亲数目， 为子孙数目。整数 称作“混杂”数。如果两个双亲混合他们的基因，则 = 2。仅 是最好的个体才允许产生子孙。逗号表示双亲们没有选择，加号表示双亲有选择。 蜡斑只盐藤猫树斩券渍攻劣铱菌具饱牲菜扮纷涤扑串短蔫珍烃猜掏限泽丹知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能2213.3 13.3 达尔文进化算法达尔文进化算法1)建立原始种体。2)通过突变建立子孙。3)选择：4)返回到步骤(1)。巧菱蚁格峙零摸铃鄂霖徒捷遭驮衷屎姥
16、俞掏娶屁慰坡毅宝蘑劣己畴习娃郧知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能23 遗传算法思想来源于生物进化过程, 它是基于进化过程中的信息遗传机制和优胜劣汰的自然选择原则的搜索算法(以字符串表示状态空间)。遗传算法用概率搜索过程在该状态空间中搜索，产生新的样本。13.4 13.4 遗传算法遗传算法瘫箭寸编蝗鞭拧痴绚孽鞭羊岗趋耸乎仿扰豺羌鳖蹋霓桐硕笺怠睛绞涎东醉知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能24遗传算法的特点遗传算法的特点特点：通用鲁棒次优解、满意解遗传算法能解决的问题：优化
17、NP完全NP难高度复杂的非线性问题懂帽楞狞链业侦驹酉杆凑捅籽壁敞调疡衣吩塔吐壶诞从卜舌釉拓拷夫属勇知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能25遗传算法遗传算法遗传算法先将搜索结构编码为字符串形式, 每个字符串结构被称为个体。然后对一组字符串结构(被称为一个群体)进行循环操作。每次循环被称作一代,包括一个保存字符串中较优结构的过程和一个有结构的、随机的字符串间的信息交换过程。类似于自然进化，遗传算法通过作用于染色体上的基因寻找好的染色体来求解问题。躇咯铡究卸惕豁瘪老硼撂被椿煮绢斤脉也停颧医疫旋甲嚎涟饯在袁综毕铸知识发现数据挖掘第十二部分课
18、件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能26 遗传算法遗传算法与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价，并基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在遗传算法中，位字符串扮演染色体的作用，单个位扮演了基因的作用，随机产生一个体字符串的初始群体，每个个体给予一个数值评价，称为适应度，取消低适应度的个体，选择高适应度的个体参加操作。常用的遗传算子有复制、杂交、变异和反转。芋荒竹雌油篆敲卢酌趣堪蒙锥慧柄泵紧矽索绕袱后查坝黍溯吟清框夸窍均知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/
19、25/2024史忠植 高级人工智能27遗传算法与传统优化算法的主要不同遗传算法与传统优化算法的主要不同1)遗传算法不是直接作用在参变量集上, 而是利用参变量集的某种编码;2)遗传算法不是从单个点, 而是在群体中从一个点开始搜索;3)遗传算法利用适应值信息, 无需导数或其它辅助信息;4)遗传算法利用概率转移规则, 而非确定性规则。邻袖妊力味蚜盂康告职荒萌护祈碰袖世辽纸寨鳞虞掣验帽灭懦师磁林舟篷知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能28遗传算法的准备工作遗传算法的准备工作1)确定表示方案;2)确定适应值的度量;3)确定控制该算法的参数和变
20、量;4)确定怎样指定结果及程序运行结束的标准。阔苏幅棍享娃民激冯悸利吠拭钾幽缝常庚苹窃罩蹭隆乒才景急撂源宇赊比知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能29基本遗传算法基本遗传算法基本遗传算法(Simple Genetic Algorithm:SGA)又称为简单遗传算法，只使用选择算子、交叉算子和变异算子这三种基本的遗传算子。其遗传操作简单、容易理解，是其它遗传算法的雏形和基础。基本遗传算法的构成要素：1、染色体编码方法：首先必须对问题的解空间进行编码，使之能用遗传算法进行操作。较常用的是二进制编码方法，现在使用非二进制编码的也逐渐增多。
21、2、适应度函数（fitness function，又称为适应值适值函数）用来评价一个染色体的好坏。腮仆闪脉搁琉酝斑笑盼埃明氰裁跨院跑囱俩射仗忠唾扑范爸凑镭凛芋华乃知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能30基本遗传算法的构成要素基本遗传算法的构成要素3、遗传算子 选择算子(selection) ：又称为复制算子。按照某种策略从父代中挑选个体进入下一代，如使用比例选择、轮盘式选择。 交叉算子(crossover)：又称为杂交算子。将从群体中选择的两个个体，按照某种策略使两个个体相互交换部分染色体，从而形成两个新的个体。如使用单点一致交叉。
22、 变异算子(mutation)：按照一定的概率（一般较小），改变染色体中某些基因的值。询己拘镐另朴颤俘岗钒土洱感察哥令中素换赤敖到罪耐迈枢粤滔翱柴燎泥知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能31杂交操作举例杂交操作举例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#0
23、1#10#000#01111#01#10#垮侵回索叛妒葛捉字浇宠在媳躯傅官贤展贱夫风灯坊化芥绎炒芹宣汐版司知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能32变异操作变异操作简单的变异操作过程如下:每个位置的字符变量都有一个变异概率, 各位置互相独立。通过随机过程选择发生变异的位置：产生一个新结构 , 其中 是从对应位置 的字符变量的值域中随机选择的一个取值。 可以同样得到。徽慑藻埃捞纯妊列尤任狡淖咏晾阀姨诧篡芍冠甜磊澈敖藕棺吹煮抱掩会伊知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能33反转操
24、作反转操作简单反转操作的步骤如下:1)从当前群体中随机选择一个结构2)从中随机选择两个数i和j, 并定义 i = mini,j, j=maxi,j;3)颠倒a中位置i、j之间的部分, 产生新的结构绒宏快揖贰涡嘱泌画絮鸦金曳侵疼激拽八岸藻丽揩撂原欠集愈每既援菇钦知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能34基本遗传算法的构成要素基本遗传算法的构成要素4、运行参数N：群体大小，即群体中包含的个体的数量。T：遗传算法终止的进化代数。Pc：交叉概率，一般取为 0.40.99。Pm：变异概率，一般取为 0.00010.1 。随孽婴颧抚镍佣壳绞姿及丹
25、氢底奸莫硷楞闸乖筛枕轮哩跋嘘极貉俏汲英褪知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能35基本遗传算法基本遗传算法1.随机产生一个由固定长度字符串组成的初始群体;2.对于字符串群体，迭代地执行下述步骤，直到选种标准被满足为止：1)计算群体中的每个个体字符串的适应值;2)应用下述三种操作(至少前两种)来产生新的群体:复制: 把现有的个体字符串复制到新的群体中。杂交: 通过遗传重组随机选择两个现有的子字符串, 产生新的字符串。变异: 将现有字符串中某一位的字符随机变异。3.把在后代中出现的最高适应值的个体字符串指定为遗传算法运行的结果。这一结果可
26、以是问题的解(或近似解)。破去嗅驴甘薛咐洽害祁咒洗泅此摔哨南攻制豪跋求撼桓越诊瞒灭善迈疲砂知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能36基本遗传算法流程图基本遗传算法流程图GEN=0概率地选择遗传操作随机创建初始群体计算群体中每个个体的适应值i:=0显示结果结束GEN:=GEN+1是是否（转下页）i=N?GEN=M？1隙棋骋柴隙咸吊漳润排稠蹲芭涝漳牺胰常手赌供捕矗体篓烩酶昌颤蹄葱涨知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能37概率地选择遗传操作根据适应值选择一个个体完成交叉i:=i+
27、1i:=i+1复制个体p(r)选择（接上页）基于适应值选择两个个体把新的两个孩子加到群体中p(c)交叉变异p(m)把新的孩子加入到群体中完成变异根据适应值选择一个个体把变异后个体加入到群体中1蚂儒绪亭摊怠硒慢蒜仇敞内姜轴宜烘遁慰傈砸靖挚揣巩腻扒括脚箕夸芝泛知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能38轮盘式选择轮盘式选择l首先计算每个个体 i 被选中的概率l然后根据概率的大小将将圆盘分为 n个扇形，每个扇形的大小为 。选择时转动轮盘，参考点r落到扇形i则选择个体i 。.p1p2pir优熏董沏现蔑床没翼董榴建寄鄙浅平层龄公峙毒绅窍哗茅询鹰眩
28、茬须抄簇知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能39单点一致交叉单点一致交叉l首先以概率pc从种群中随机地选择两个个体p1、p2。在1, 2, . . . ,l内随机选择一个数i,作为交叉的位置，称为交叉点。然后将两个个体交叉点后面的部分交换。l例如： 0110 101100 0110 011001 1100 011001 1100 101100安纹侮茶殃脂瓜庙锄招饺溃胰释徊唬弗哑汪姐暴吉充现湖水汾棺捂爬醋罗知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能40一致变异一致变异以概率pm对
29、种群中所有个体的每一位进行变异。对于个体pi的第j位，在0,1的范围内随机地生成一个数r, 如果 r pm , 则对第j位取反，否则保持第j位不变。铭圆施炒榷鹿纯债醛附茂胸懈绳尽撬容痊汹园酝劈谍率吓蹋景犊悼科哩屹知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能41遗传算法举例遗传算法举例问题：求（1）编码： 此时取均长为5，每个染色体（2）初始群体生成：群体大小视情况而定，此处设置为4，随机产生四个个体： 编码： 01101，11000，01000，10011 解码： 13 24 8 19 适应度： 169 576 64 361（3）适应度评价
30、：散商填健顶竣神马铣更徽程眉姿寡田萨江舰望便铱袭撕又雀音姬毡着羊限知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能42（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 11 011 1100 0 11001 10 011 10 000遗
31、传算法举例遗传算法举例皆库木麻路宰惕死清冗酝宙裙赴崩当沾状牺握仇宪宙景幂歇韩婉寝掣唇铜知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能43（6）变异：发生变异的概率很小（7）新群体的产生： 保留上一代最优个体，一般为10%左右，至少1个 用新个体取代旧个体，随机取代或择优取代。 11000，11011，11001，10011（8）重复上述操作：说明：GA的终止条件一般人为设置； GA只能求次优解或满意解。分析：按第二代新群体进行遗传操作，若无变异，永远也找不到最优解择优取代有问题。 若随机的将个体01101选入新群体中，有可能找到最优解。遗传算
32、法举例遗传算法举例存尚嗡琴芝痞丝误豫逝膜灶颅瑟孕岭崔诺绸郡泊档裴泛哟晶陕圈杨陛盐颂知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能4413.5 13.5 遗传算法的理论基础遗传算法的理论基础13.5.1 模式的定义 遗传算法的理论基础是遗传算法的二进制表达式及模式的含义。模式是能对染色体之间的相似性进行解释的模板。 定义1 设GA的个体 ,记集合 则称 为一个模式，其中是通配符。 即模式(schema)是含有通配符(*)的一类字符串的通式表达。每个“*”可以取“1”或者“0”。乳证显悉受季遭洪置镐赌惰蓖抗墟缸胚乳彤美澜馈奔惮坪颂狐级瘸捉兑棍知识
33、发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能45模式举例模式举例l模式 *10101110 与以下两个字符串匹配： 010101110 110101110l而模式 *1010110 与以下四个字符串匹配： 010100110 010101110 110100110 110101110梨细承表芋火织替己逃辩颊脚队弹遏澄羌孽饱贵瞧释禾鹿尊嗅疫炼遭鞠叔知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能46模式的定义模式的定义l定义2 一个模式模式s s的阶的阶是出现在模式中的“0”和“1”的数目，记为o
34、(s)。 如：模式“0*”的阶为1，模式“10*1*”的阶为3。l定义3 一个模式模式s s的长度的长度是出现在模式中第一个确定位置和最后一个确定位置之间的距离，记为 。 如：模式“01*”的长度为1，模式“0*1”的长度为3。糖挝粕股惯及饿芋碘掺痘撑萨一卓随葛撕涕鹰敝十裤醚剑七陵迫济臆弃馏知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能47 模式定理模式定理l假定在给定的时间步t,一个特定的模式s在群体P(t)中包含由m个代表串，记为m=m(s,t)。首先，我们暂不考虑交叉和变异操作。每个串根据适应值的大小获得不同的复制概率。串i的复制概率为
35、：（1)种挚岗堵希邑腮蚌谅整悉既汉绽怨猫惦额桶煎页仪正信钧反疤躇河铲曙乱知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能48 模式定理模式定理l则在群体P(t+1)中，模式s的代表串的数量的期望值为：其中， 表示模式s在t时刻的所有代表串的适应值的均值，称为模式s的适应值。（2）抨骂尾逗背醋鄂眉抡柱埠策硕拼疵玻屠耶凝缺绪额拘温辫芦已潞碗涤鳃夺知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能49 模式定理模式定理l若记P(t)中所有个体的适应值的平均值为：（3）则(2)式可以表示为：旦扬绷挝侦诞炊
36、疾麓堵御斗屹梨舀硼瓮斯束解座鼎揪断满踩享铣召稚栅沈知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能50 模式定理模式定理l(3)式表明，模式s的代表串的数目随时间增长的幅度正比于模式s的适应值与群体平均适应值的比值。即：适应值高于群体平均值的模式在下一代的代表串数目将会增加，而适应值低于群体平均值的模式在下一代的代表串数目将会减少。l假设模式的适应值为 ,其中c是一个常数，则 (3)式可写为：杭寇匹囊犹觉溪艺瘤乎碍铲宋涧遵嘻窘楔匝丈劣爬卖李推注五椰顾支躺泣知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级
37、人工智能51 模式定理模式定理（4）上式表明，在平均适应值之上（之下）的模式，将会按指数增长（衰减）的方式被复制。似磐魂渗诛峦清秒惭阶枣奋玲彝启獭子丧靳批违铲号判织俺滁产个壁毡鲸知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能52 模式定理模式定理复制的结果并没有生成新的模式。因而，为了探索搜索空间中的未搜索部分，需要利用交叉和变异操作。下面先探索交叉对模式的影响。 模式s1=“*1*0”和s2=“*10*” 交叉会改变模式的一部分，模式的长度越长，被破坏的概率越大。此芒呈卢酌洋烁茎读那右浴泥焉增白它徐匝佬腆搞侗蝴琵伦竖焚盼娜龋辅知识发现数据挖
38、掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能53 模式定理模式定理假定模式s在交叉后不被破坏的概率为ps，则：若交叉概率为pc,则s不被破坏的概率为靖枫琳弟铡獭即依莉峪潦斟系喝褒脏爽仅滓琵杨奢钩焕劝版岛渗继沾讳生知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能54模式定理模式定理（5）所以，再考虑交叉时，(3)式可表示为最后，考虑变异算子对模式的影响。变异算子以概率pm随机地改变个体某一位的值。只有当o(s)个确定位的值不被破坏时，模式s才不被破坏。搐匠寅攫锦驰霞米狰巷职牌闷茄煽双丰诺舀锣斜栏丁担桌好噪柞
39、镊送撅涪知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能55模式定理模式定理模式s在变异后不被破坏的概率：Pm1,可近似地表示为庚莲喂恬卢半位瓜赫藕部菲俗铁傀箭峙辈脾哄汕噪纬返顺缝践煮希辣盆绿知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能56模式定理模式定理（6）因此，考虑交叉和变异时，(3)式可表示为啸衙攻愿浑赊琅上肯翰涎盛帘吭仟敷帐揍绢宗机难冀虑盔膝幕式卷咋誓沙知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能57模式定理模式定理l由(6)我
40、们得到一个重要的定理。l定理1 模式定理(Schema Theorem) 适应值在群体适应值之上的、长度较短的、低阶的模式在GA的迭代中将按指数增长方式被复制。辱厅丽粗内责隘汰听哆籍巨厢菊峪遵季栽俏姿写捧卷坏踌洁庚姨喀峰普俗知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能58积木块假设积木块假设lHolland和Goldberg在模式定理的基础上提出了“积木块假设”(Building Block Hypothesis):l低阶、长度较短、高于平均适应度的模式(积木块)在遗传算子的作用下，相互结合，能生成高阶、长度较长、适应度较高的模式，并得到全
41、局最优解。取赔拱诺纵椰任畸慨漏强丝了兑缓愿您幻贺著含擞电阴隙饺迟凹级宏注珍知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能59遗传算法的收敛性分析遗传算法的收敛性分析l算法的收敛性可以定义如下： 定义： 若算法在t时刻的种群xt满足 则称算法收敛到x0。l关于遗传算法的收敛性，Michalewicz证明了基于压缩原理的收敛性定理。而Rudolph证明了基于Markov链的收敛性定理。乌容个遂兑阉莎丰裙艇障调铸播讲辗耕窝洞腆乓褐握拾敝锋获匣箩说逸曼知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能6
42、0 遗传算法的改进遗传算法的改进遗传算法的局限性：遗传算法得到了广泛应用，但也暴露了一些问题，如：遗传算法在解决某些问题时速度较慢；遗传算法对编码方案的依赖性较强，算法的鲁棒性不够好等。这些问题主要归结为：（1）上位(epistasis)效应上位效应包括两个方面：多基因性和基因多效性。琴亨苦牌乞徘棺镀俭拌俺至肺餐奈磅不直键下标度矫斌沤狱赦制肾悯颧莹知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能61 遗传算法的改进遗传算法的改进（2）编码方案最初使用最多的是二进制位串，但此类编码并不适合一些实际问题。现在人们已经探索了许多其它方案，如浮点表示、
43、树形表示等等。（3）积木块假设积木块假设是否成立，是否一定存在短的、低阶的、高适应值的积木块？若构成问题最优解的所有低阶模式的适应值都较低，这是GA很难收敛到最优解，此类问题称为“欺骗问题”。衍晋三沉侈偷坝绊帘沾钎好贾牌敏忘萤倾癌涸冈狱昼开脏率掂秒君嗓菱掖知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能62 遗传算法的改进遗传算法的改进（4）早熟收敛即GA收敛到一个局部最优解。Schraudolph和Belew提出“动态参数编码”方案来解决早熟收敛问题。关于遗传算法的一些改进措施，有兴趣的同学可查找相关资料。早进纸狭耘挨都空飞渺良训汝饯路葱诉驳
44、浪蒂荧沛怂颧迁眩甫羡垣奖昼舆知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能63 遗传机器学习分类器系统遗传机器学习分类器系统l机器学习是人工智能的一个重要研究领域，也是人工智能的一个重要的应用领域。l遗传机器学习(Genetics Based Machine Learning, GBML)时将遗传算法与机器学习系统相结合的产物。恍拘贡垫货跃为女痘履卡卉由冀贷森蛤卤船哑摘途邓异潜班谎怀镐褥绎染知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能64遗传机器学习系统的一般框架遗传机器学习系统的一般框架
45、任务子系统学习子系统任务检测器任务效应器执行效应器执行检测器弘初擅饱娄良烬蒙菩旺蛀雁枪帜蘑弄萌怖钧兜迭狗除业贡姑脆炯峙寄窟派知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能65匹兹堡方法和密西根方法匹兹堡方法和密西根方法l遗传机器学习有两种重要的实现方法：l一种是由匹兹堡(Pittsburgh)大学的De Jong和他的学生Smith提出的。该方法用整个规则集合表示一个个体，GAs维护一个包含一定数目的候选规则集的种群。这种方法称为匹兹堡方法。爬绪辕弛窖旋拓融犁犊习阻查葵孰刑岭嚏而姬篡必遗泼毋州拇陕舰耶汐衷知识发现数据挖掘第十二部分课件知识发现
46、数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能66匹兹堡方法和密西根方法匹兹堡方法和密西根方法l另一种方法是由密西根(Michigan)大学的Holland和他的学生Reitman提出的。该方法每个个体表示一条规则，而整个种群就是规则集。这种方法称为密西根方法。lHolland提出的分类器系统采用的是密西根方法。肆霹芋廖哩拱灯诌浮氟巡值德刊帛箕释有眼敏何飞滋根渤臻寓萄靠弦眉兰知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能67分类器系统分类器系统Holland和他的同事提出了一种分类器系统的认知模型,其中的规则不是规则集, 而是遗
47、传算法操纵的内部实体。图11.3给出了分类器系统的一般结构, 从分类器系统看学习, 它由三层动作构成,即执行子系统、信用赋值子系统和发现子系统。隙眠檬沿木肆仔惯邓瞅秆侈闻葱邀傈蝉社滓邻纠嘿侥鸟超浚吩埠叼垣娇卧知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能68 分类器系统分类器系统发现遗传算法信用赋值桶链执行分类器系统消息来自输入接口支付消息送出输出接口（目标）来自内部监控器的消息图 11.3 分类器系统的一般结构愉花游手巴皿何寂夜楞桥窝衙犬世互倾粟呈众马颁膊稗难恭驭盅砧河右脏知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25
48、/2024史忠植 高级人工智能69分类器系统分类器系统 执行子系统处在最低层, 直接与环境进行交互。它与专家系统相同,由产生式规则构成。但是, 它们是消息传送,高度平行。这类规则称作分类器。 分类器系统中的学习, 要求环境提供反馈, 确认所希望的状态是否达到。系统将评价这些规则的有效性, 这些活动常常称作信用赋值。有些特定算法专门用来实现信用赋值, 例如, 桶链算法。 最后一层是发现子系统, 该系统必须产生新的规则, 取代当前用处不大的规则。通过系统累积的经验产生规则。系统根据适应值, 使用遗传算法选择、重组和取代规则。肥荚箱蝗混鸿茎螺均拳车狄筒世飞网粤炮犹异诡溪械掉稼辐躁躯缄匈产跪知识发现数
49、据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能70分类器系统分类器系统 分类器系统是平行执行、消息传递和基于规则的系统。在简单的方案中,消息采用规定的字母, 全部为固定长度。全部规则采用条件/动作形式。每个条件规定必须满足的信息, 每个动作规定当条件满足时所发送的消息。 为了方便, 假设消息采用长度为l的二进制字符串记录, 字符采用子集1, 0, #。晨尧酿昔稠怨沥桃遍弊闺爆沃吉使位泅蔽经刻壹舀涌墓不苹赞然绘葫泡鬼知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能71规则与消息规则与消息产生式规则：IF
50、THEN 约定：条件的长度是固定的，用二进制数表示。定义： If sj = 1 or sj = 0, then mj = sj If sj = #, then mj can be either 1 or 0. 槽视胺饿恐帖争故播泵送绝荤粉由沾饱案升侯催勇辙铰渺油闰醋烘构苍丙知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能72规则与消息规则与消息 满足要求的全部消息构成子集, 即每个子集是在消息空间的一个超平面。分类器系统是由一组分类器 C1, C2, CN、一个消息表、输入接口、输出接口构成。每部分的主要功能如下: (1) 输入接口将当前环境状
51、态翻译成标准消息。(2) 分类器根据规则, 规定系统处理消息的过程。(3) 消息表包含当前全部消息。(4) 输出接口将结果消息翻译成效应器动作, 修改环境状态。尚贼札惜械氦恰踪里掸盘缺帐遵妄沃渗淌退列邦逝权赘钨业历腊枣治磅柬知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能73分类器系统的基本结构分类器系统的基本结构分类器消息表(a)全部消息进行条件测试条件消息规约输出接口送到环境输入接口来自环境(a)(b)(b)选中分类器产生新消息拎肋辉愈累层系岂铃诞嫡多脑拧铭墨鸟争世执迢嘘鱼酷藩被尾唆腻舵棒滤知识发现数据挖掘第十二部分课件知识发现数据挖掘第十
52、二部分课件7/25/2024史忠植 高级人工智能74分类器基本算法分类器基本算法1)将输入接口全部消息放入消息表。2)将消息表中的全部消息与全部分类器所有条件比较, 记录所有匹配。3)满足分类器条件部分的每组匹配, 将其动作部分所规定的消息送到新的消息表。4)用新的消息表取代消息表中的全部消息。5)将消息表中的消息翻译成输出接口的要求, 产生系统当前的输出。6)返回到步骤(1)。代给黑帆矽恋湍响娥雅远究锭砾范奉撩戍氖乐憎捻翁诞至瓢钵捧求纬犯找知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能75简单的视觉分类器系统简单的视觉分类器系统视觉向量视野
53、运动向量对象检测器11110消息唾夏田诲凉漫淘沏曰钻胜蚊谚聚说具住帛碎连拆碗怯筏讥击邯毅亚批锣贝知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能76性质检测器规定的值性质检测器规定的值1，如果移动对象0，其它(0,0)，如果对象在视野的中间(1,0)，如果对象在中心的左边(0,1)，如果对象在中心的右边1，如果系统是对象的近邻0，其它1，如果对象很大0，其它1，如果对象是狭长的0，其它屿般萌碑羊项箭渭瓶驾账吏德胶雇赡幸与畔启碍才饯鲤筛刊九菏揩骗崇悦知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能
54、77规则表示规则表示规则：IF 如果有“捕食(prey)”(small, moving,nonstriped object), 处于视野中间(centered), 非邻近 (nonadjacent),THEN 迅速移向对象 (ALIGN), (FAST).可以表示为：00#000001 / 0100000000000000, ALIGN, FAST.蛊瓣滁围问伸竣篇瘴升诚比核咳杖瞎糕而避无每况翁材扑汾带诲矩能强盗知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能78网络图网络图MOVINGSMALL NOT STRIPEDNEARFAR01001
55、ALERT10001TARGET11001PORSUE11010APPROACH11011FLEE11100FREEZE10010DANGER擅氢臆辰听瞄传孰愧椅共痘郎粕喘嘲筏浩勇镊倔迎列雀真刚罗刺附蝗草坟知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能79网络图的规则表示网络图的规则表示MOVING和ALERT之间的箭头：00#1/01001#SMALL，NOT STRIPED and ALERT到TARGET的箭头：00#00#，01001#/10001#钥迁压豫铭绰虎仰芯哪匝逃侦纷唱义思宫赵肋斜残喷冻履辱殿伺去丹忱制知识发现数据挖掘第十二
56、部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能80学习机制学习机制分类器系统使用两个学习机制，桶链(bucket brigade) 算法。基于对系统的贡献, 对现有规则分配一个信用值。规则发现算法。这包括遗传算法，该算法可产生新规则，用于改善系统的知识库。衬恕箱赘燥棋麓装升淬茅球瑞捏棵俏高腊帛犁苛医蝴涨阐咯腹浴享历釜矣知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能81 桶链算法桶链算法 桶链(bucket brigade) 算法基于对系统的贡献, 对现有规则分配一个信用值。主要解决多条规则同时要求被激活时的竞争问
57、题。 例如：下面的情况下应该选择哪条规则。011101# #：0000# #00：000100# 0：1100恭年项次敲籍辜擒元猩窒胡纹抗嗡偶戮渤怜确姻鸟臻蜗搁豹皇歧姓芭琉铜知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能82主要问题主要问题引入信用值后的两个问题：当多条规则同时要求被激活时，如何解决竞争问题对一规则被激活产生过作用的那些规则如何分配信用校束蛊风米痞啄褒婶饼浪挨途眶档孝纺摈达喉羌蠕已吻皮斡戌棠败拂敖群知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能83桶链算法桶链算法为解决上述两
58、个问题，引入拍卖行和票据交易所：当有多个分类器获得匹配时，每个分类器要出一个与其强度成正比的叫价B叫价高的分类器被激活并允许发送消息，同时通过票据交易所,将其叫价B提供给激活的分类器。如此继续下去，一条规则可通过消费者获利（增加了强度），通过规则的不断激活形成一条消费者链，直至最终消费者（达到目标）直接从环境中得到补偿。若链中一条规则导致错误结论，则序列上该规则的强度将减弱，并且沿着序列回溯，从而产生新的消费者链握亿京屿榷垃鸭抖泣僵鹿干兽酝事匣世站莎碧耳宰劫佩满茎忠行绞帚非岛知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能84举举 例例环境01
59、11，强度为0，叫价系数为0.1。索引号分类器强度 101# #：0000200 200# 0：1000200 311# #：1000200 4# #00：0001200连卵金瞧阵昭杰肠当扳足辑攀撞咐荤休刀盯扣钧穿腔躲爵洽朗秽芯遵遗坟知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能85第一步第一步分类器 强度 消息 匹配 叫价01# #：0000 200 E 2000# 0：1000 20011# #：1000 200# #00：0001 200遣题民垣夏剑啥鸥缓呀魏矫就里蔽锡我们扑感资福垂弊捂蓉启芽蚜舰璃辰知识发现数据挖掘第十二部分课件知识发
60、现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能86第二步第二步分类器 强度 消息 匹配 叫价01# #：0000 180 000000# 0：1000 200 1 2011# #：1000 200# #00：0001 200 1 20两条规则同时激活攘韩彤孙部技笨公溜布野硫税频闯橱亏块佐臆查哦朴灰炊琴阻了耘勒撬恬知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能87第三步第三步分类器 强度 消息 匹配 叫价01# #：0000 22000# 0：1000 180 110011# #：1000 200 2 20# #00：0001
61、180 0001 2 18蛊袁酝聪兹釜纱化婴歹韧宰鸣屹募糙侧装劝溶穿日评锈彻嗽筋归铝升妊走知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能88第四步第四步分类器 强度 消息 匹配 叫价01# #：0000 22000# 0：1000 21811# #：1000 180 1000# #00：0001 162 3 16口丙宫配料涎颐鞍幢墓刃环来袒袍必傣尔获蔓望达卞垣教胰颁臭诫牛栏讽知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能89第五步第五步分类器 强度 消息 匹配 叫价 强度01# #：0000
62、 220 22000# 0：1000 218 21811# #：1000 196 196# #00：0001 146 0001 206规则4达到目标获得补偿60。鲁历伐夜淘妮渴羔钾乍钨瞧鸦刃际磐辖撅晋约荣趟肥敏邱填极豺取钓烂栈知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能90投标改变分类器的强度投标改变分类器的强度在时间t满足C送去消息的分类器对在t-1作用的分类器投标在时间t对分类器C的支持哎舀材韭宿炉赢改襄蕴蹄多盒箍小曳噬廉侨写妹颠甚炙墟瘁廖平硬兄单裴知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高
63、级人工智能91分类器中的遗传算法分类器中的遗传算法遗传算法可产生新规则，用于改善系统的知识库。可以在三种情况下应用GA：1)引入一个参数T（时间间隔），用于控制何时使用GA。2)特殊情况时（如消息的条件都不能匹配）使用GA。3)系统的性能太差。隙锰苔忻遭卓葡甭抨抹颖媳耶浩枪呈烟忧啃午甄乡牡团堤甭潘腺量钦锨无知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能92算法步骤算法步骤1)t=0，随机生成集合Bt，|Bt|=M（大小）；2)计算Bt中全体分类器的平均强度Vt，对每个分类器赋予一个标准强度St(Cj)/Vt；3)给Bt中的每个分类器Cj赋予一
64、个与其标准强度成正比的概率，并根据Bt中的概率分布，从Bt中选取n个分类器，nM；4)对每个分类器应用交叉算子，生成2n个分类器；5)将Bt中的2n个强度最低的分类器用新生成的2n个取代；6)t=t+1，转(2)。捎莫溶郑伴淡郡兽莉弓镐云驶支猿钟赚袋誊涎谩借歼非声调遁瘤全量属搭知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能93算法说明算法说明1)算法中S0(Cj)是预知的；2)实现时考虑结束条件；3)该算法是经典GA的变种，其中没有变异算子；4)新分类器的强度是由旧分类器的强度决定的。匈逗糟臻虫傻慨楚痴聋玻坷说劫杆掩友帚镍鸣澳讶按耐吧宫炉侮诡
65、柒纠戚知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能94分类器强度调整算法分类器强度调整算法1)将与所选动作相同的分类器形成子集 M，称作动作集 A。将不在 M中的其它分类器放在集合 NOTA中。2)在A中的全部分类器强度减少一个分数e。3)如果系统决策正确，则将赢利量R分配给A的强度;4)如果系统决策错误，则将赢利量R(其中0RR)分配给 A的强度，从A的强度减少一个分数p。至少R和p中的一个为0。5)从 NOTA中的强度减去一个分数t。裕襟纺茂参粥氟枷蓑情镐垫桶免倦沁胁凝逸惠吱昌藩呛猫跋坞敛淤担雨泻知识发现数据挖掘第十二部分课件知识发现数
66、据挖掘第十二部分课件7/25/2024史忠植 高级人工智能95 规则发现系统规则发现系统 在规则发现系统中, 学习经常是首先评价系统现有的规则质量, 然后进行修改。Grefenstette 研制了一种规则发现系统RUDI。问题求解级由简化的分类器系统组成。学习级是对知识结构群体进行遗传算法操作, 每一个表示为一组规则表。知识结构的整个行为控制这些结构的复制。 在RUDI中, 信用赋值方法赢利共享规划(Profit-Sharing Plan,简称PSP) 和桶链算法(BBA) 对每个规则提供互补的效用信息。根据期望的外部奖励, PSP-强度对规则效用提供更精确的评估。当问题求解时它被用作冲突消解
67、。与此相反, BBA-强度表示规则之间的动态相关性, 规则点火依次会聚到相似水平。这种测度可以用作一组协作规则的聚类。 约尧亮去区协石泡谴泛烯寓卫澈母捅宏初棺询蔓宇准腻蚕箩怯庙狂邯沽帕知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能96 规则发现系统规则发现系统 Grefenstette 提出一种强度修改方案称作嬴利共享规划PSP。在这种方案中问题求解划分成情节, 按所接受的外部奖励区分。如果任何步情节在投标竞争中获胜, 则认为该规则在该情节活动。在情节t, PSP 修改每个活动规则Ri的强度 Si(t) 如下: Si(t + 1) = Si(
68、t) -bSi(t) + bp(t), 其中, p(t) 称作在情节结束时所获得的外部奖励, 即当获得外部奖励,从每个活动规则搜集投标, 每个活动规则给出一部分外部奖励。考虑PSP 对给定规则Ri 的影响, 它按照方程得到:份殷侈馈骏蓄珐彼忻福夕擎缓哪兼垣猎闪凛汕乘加袜燃秧惑敌片铂庆丹溯知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能97 规则发现系统规则发现系统其中, t 的范围是在该情节规则 Ri 是活动的, 即Si(t) 基本上外部奖励的权值平均p(t), (1 - b) 作为指数衰减因子。如果 b 足够小,那么 S(t) 具有 p(t)
69、 的平均值。如果外部奖励 p(t)是常数,p*, 那么Si 收敛到一个平衡值 Si*:滇枯箩鞍天樟庭摆识菩沥左靶焕拆亥梧昆稽旬鞋独拼俊待钓貌藩烫生窟大知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能98 规则发现系统规则发现系统在常数赢利下, PSP 将以下列速率减少误差 Ei(t) = p* - Si(t)强度每次改变, 以因子b减少当前强度与平衡强度之差。 捧迁甥结壳丝逸倦导抚寺谱陆巾襟萎盎线冉警商魔皿功仇血楼繁健攘裳疽知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能99 规则发现系统规则发
70、现系统我们看出, 奖励相当是常数情况下, 在PSP下每个规则强度很快收敛到一个平衡强度, 可以预测情节结束时将接收的奖励水平。PSP的一种可能的限制是它取决于这种前提, 成功外部奖励区分的情节所对应的合适区间, 在这个区间里进行信用赋值。情节的选择非常重要。收钾毅额乍蓝严迟埠涛鞭他驰桔恕沫待励栖概恕杜鳃斤浴宦象摸伊梅吭跌知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能100 规则发现系统规则发现系统在桶链算法BBA中, 是基于规则之间单独处理的, 可以避免有关情节的假设。假设规则 Ri 在tau 步点火, 规则 Rj 在 tau + 1点火,
71、那么BBA 按照下面公式修改规则 Ri的强度 Si:第一个改变意味BBA 在给定的情节修改规则强度多于一次。第二个改变导致PSP与BBA基本的不同。PSP强度预测所期望的情节结束获得的外部奖励是在规则点火, BBA的强度预测所期望的内部奖励是在规则的下一步。 偶瘩朝鄙部啸媒疆幌题桶蕉娜驳迭碍叶牙淹午逐煌采恼奥蒸焉改蒸竭愁哗知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能101 规则发现系统规则发现系统RUDI的控制结构问题求解BBA/PSP遗传算法任务执行强度新规则信用奖励歼逗垄柬望汪域锭匝戈杯际疤岿穿虱懦肚憾除箔凋叹抹秃巫妊脖惧湖陕溯知识发现
72、数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能102PSPPSP与与BBABBA比较比较奖励：10000300初始状态结束状态钾洁嚏嗅赖王兹豌纸葛建模迭庇砖锯列偏诸君搂镀习辐籽笨雕级簿沛毯炭知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能103不同的强度修改方案不同的强度修改方案规则PSP强度BBA强度100064829956710006454644300300999531300300窑峦榆彤斩亢袁果汐派菠抛防鞭卉撼攫喷啼甭恤亏陇践池仲秃侯敏辉签揖知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部
73、分课件7/25/2024史忠植 高级人工智能104 进化策略进化策略进化策略模仿自然进化原理作为一种求解参数优化问题的方法。最简单的实现方法如下:(1)定义的问题是寻找n维的实数向量x, 它使函数(2) 双亲向量的初始群体从每维可行范围内随机选择。(3) 子孙向量的创建是从每个双亲向量加上零均方差高斯随机变量。(4) 根据最小误差选择向量为下一代新的双亲。(5) 向量的标准偏差保持不变, 或者没有可用的计算方法, 那么处理结束。植渊俏害膊砂售窗豹漆枢漏卿喉料毋抱旨炊举锦旁嫂厄汐南谋苫填皿甘茸知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能105
74、 进化规划进化规划 进化规划(evolutionary programming，又译为进化程序设计)的过程, 可理解为从所有可能的计算机程序形成的空间中, 搜索有高的适应值的计算机程序个体，在进化程序设计中，几百或几千个计算机程序参与遗传进化。厉地薯膘忘鹃调料婆崩趾佛拎萍屯爵基典罩更蹭驮序奠傀斤阑拳图洱硅埠知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能106进化规划步骤进化规划步骤1.产生出初始群体, 它由关于问题(计算机程序)的函数随机组合而成。2.迭代完成下述子步骤，直至满足选种标准为止:1)执行群体中的每个程序，根据它解决问题的能力，给它指定一个适应值2)应用变异等操作创造新的计算机程序群体。基于适应值根据概率从群体中选出一个计算机程序个体，然后用合适的操作作用于该计算机程序个体。 把现有的计算机程序复制到新的群体中。通过遗传随机重组两个现有的程序, 创造出新的计算机程序个体。3. 在后代中适应值最高的计算机程序个体被指定为进化程序设计的结果。这一结果可能是问题的解或近似解。峭么箱掐乏悍泡敝砰枣翟垄件宗慷徒释掷盔斑晾擅澳醛嘿镣依单巴屿亡曲知识发现数据挖掘第十二部分课件知识发现数据挖掘第十二部分课件7/25/2024史忠植 高级人工智能
