人工智能及其应用蔡自兴第四版.ppt

TSP的目标是路径总长度为最短，路径总长度可作为TSP问题的适应度函数：93.遗传操作w简单遗传算法的遗传操作主要有有三种:选择(selection)、交叉(crossover)、变异(mutation)改进的遗传算法大量扩充了遗传操作，以达到更高的效率w选择操作选择操作也叫复制（reproduction）操作，根据个体的适应度函数值所度量的优劣程度决定它在下一代是被淘汰还是被遗传w一般地说，选择将使适应度较大（优良）个体有较大的存在机会，而适应度较小（低劣）的个体继续存在的机会也较小10交叉操作w交叉操作的简单方式是将被选择出的两个个体P1和P2作为父母个体，将两者的部分码值进行交换w假设有八位长的二个体，产生一个在1到8之间的随机数c，假如现在产生的是3，将P1和P2的低三位交换  1 0  0  0  1  1  1  0  1 1  0  1  1  0  0  1 P1 P2  1  1  0  0  0  111变异操作 返回w变异操作的简单方式是改变数码串的某个位置上的数码w二进制编码表示的简单变异操作是将0与1互换：0变异为1，1变异为0wTSP的变异操作：随机产生一个1至n之间的数k，对回路中的第k个城市的代码wk作变异操作，又产生一个1至n之间的数w，替代wk ，并将wk加到尾部，得到：125.1.2 遗传算法的求解步骤遗传算法的求解步骤 1. 遗传算法的特点遗传算法的特点 (1) 遗遗传传算算法法是是对对参参数数集集合合的的编编码码而而非非针针对对参参数本身进行进化；数本身进行进化；(2) 遗遗传传算算法法是是从从问问题题解解的的编编码码组组开开始始而而非非从从单个解开始搜索；单个解开始搜索；(3) 遗遗传传算算法法利利用用目目标标函函数数的的适适应应度度这这一一信信息息而非利用导数或其它辅助信息来指导搜索；而非利用导数或其它辅助信息来指导搜索；(4) 遗遗传传算算法法利利用用选选择择、、交交叉叉、、变变异异等等算算子子而而不是利用确定性规则进行随机操作。

不是利用确定性规则进行随机操作5.1 遗传算法132. 遗传算法的框图遗传算法的框图(图图5.2) (1)  初始化种群初始化种群;(2)  计算种群上每个个体的适应度值计算种群上每个个体的适应度值;(3)  按由个体适应度值所决定的某个规则选按由个体适应度值所决定的某个规则选           择将进入下一代的个体择将进入下一代的个体;(4)  按概率按概率Pc进行交叉操作进行交叉操作;(5)  按概率按概率Pm进行变异操作进行变异操作;(6) 若没有满足某种停止条件，则转第若没有满足某种停止条件，则转第(2)步，步，        否则进入下一步否则进入下一步7) 输输出出种种群群中中适适应应度度值值最最优优的的染染色色体体作作为为问问题的满意解或最优解题的满意解或最优解 5.1 遗传算法14初始化种群初始化种群变异操作变异操作计算适应度值计算适应度值选择操作选择操作交叉操作交叉操作最优解输出最优解输出   终止条件终止条件？？图图5.2  算法框图算法框图      返回返回5.1 遗传算法 否否 是是 开始开始结束结束(1)(2)(3)(4)(5)(6)(7)15遗传算法的一般结构表示遗传算法的一般结构表示 wProcedure: Genetic Algorithmswbeginw  t ← 0;w  initialize P(t);evaluate P(t);w  while (not termination condition ) do–  begin–    recombine P(t) to yield C(t);–    evaluate C(t);–    select P(t+1) from P(t) and C(t);–    t ← t+1;–  endwend5.1 遗传算法163. 遗传算法求解举例遗传算法求解举例5.1 遗传算法v设 用SGA求 v遗传算法归纳为五个基本组成部份遗传算法归纳为五个基本组成部份v方案表示方案表示 v种群初始化种群初始化 v适应度函数适应度函数 v遗传操作遗传操作 v算法参数算法参数 175.1.3 SGA及其模式定理w回顾回顾：： –（（1））GA的的基本原理与算法框架基本原理与算法框架；；–（（2））GA的的基本遗传算子基本遗传算子；；w问题问题：：–（（1）基本遗传算法（）基本遗传算法（SGA）的算法步骤；）的算法步骤；–（（2）） GA的计算实例；的计算实例；–（（3）） GA有效性的理论证明；有效性的理论证明；5.1 遗传算法18SGA的算法步骤的算法步骤5.1 遗传算法(1)编编码码：： 随随机机产产生生一一个个由由确确定定长长度度的的特特征征字字符符串串组成的初始种群。

组成的初始种群2)进进化化：：对对该该字字符符串串种种群群迭迭代代的的执执行行下下面面的的步步①①和步和步②② ，直到满足停止标准：，直到满足停止标准：①① 计算种群中每个个体字符串的计算种群中每个个体字符串的适应值适应值；；②② 应用应用复制、交叉和变异复制、交叉和变异等遗传算子产生下一代种群等遗传算子产生下一代种群3)解解码码：：把把在在后后代代中中出出现现的的最最好好的的个个体体字字符符串串指指定定为为遗遗传传算算法法的的执执行行结结果果，，这这个个结结果果可可以以表表示示问问题的一个解题的一个解 19产生初始种群产生初始种群计算每个个体的适应值计算每个个体的适应值GEN:=GEN+1依概率选择遗传操作依概率选择遗传操作执行复制执行复制选择一个个体选择一个个体i:=i+1选择两个个体选择两个个体选择一个个体选择一个个体执行变异执行变异i:=0复制到新种群复制到新种群i:=i+1将两个后代插入新种群将两个后代插入新种群插入到新种群插入到新种群执行杂交执行杂交指定结果指定结果是是否否是是否否变异变异复制复制交叉交叉结束结束 GEN:=0 是否满足停止准则是否满足停止准则i=M?5.1 遗传算法20SGA的伪代码描述Procedure: Simple Genetic Algorithmsbegin  t ← 0;  initialize P(t);evaluate P(t);  while (not termination condition ) do  begin    recombine P(t) to yield C(t); P(t) ← C(t);  evaluate  P(t); t ← t+1;  endend5.1 遗传算法21一个简单的计算实例一个简单的计算实例例：极大值问题例：极大值问题 max f(x)=x2,x [0,31]1. 编码：编码：5位二进制数；位二进制数；2. 初始群体：群体规模为初始群体：群体规模为4个个体，随机产生；个个体，随机产生； 假设为：假设为：01101，，11000，，01000，，100113. 适应度计算：适应度计算： （适应值直接取（适应值直接取  f(x) ））4. 选择复制产生下一代群体；（选择概率按适应值大小采用轮选择复制产生下一代群体；（选择概率按适应值大小采用轮盘赌的随机策略）盘赌的随机策略） 5.1 5.1 遗传算法遗传算法310f=x2个体个体编号编号初始群初始群体体基因基因译码译码适应度计适应度计算算f(xi)/ f(xi)f(xi)/f下一代群下一代群体复制数体复制数101101131690.140.581211000245760.491.9723010008640.060.220410011193610.311.231225. 个体基因交叉；（一般交叉概率较大个体基因交叉；（一般交叉概率较大0.7～～0.9））6. 个体基因变异（一般变异概率较小个体基因变异（一般变异概率较小0.001～～0.01 ））7. 转转3直至算法终止。

直至算法终止个体个体编号编号复制后复制后的群体的群体基因基因译码译码适应度适应度计算计算交叉交叉对象对象交叉交叉位置位置交叉后交叉后的群体的群体适应度适应度计算计算1011011316924011001442110002457614110016253110002457643110117294100111936133100002565.1 5.1 遗传算法遗传算法23模式的定义模式的定义w思考：思考： –（（1））SGA优化搜索中遗传算子的作用？优化搜索中遗传算子的作用？–（（2））怎怎样样从从理理论论上上证证明明SGA能能依依概概率率搜搜索索到到优优良良解答的有效性？解答的有效性？w模模式式：：我我们们将将群群体体中中的的个个体体即即基基因因串串中中的的相相似似样样板板称称为为“模式模式”–模式表示基因串某些特征位相同的结构模式表示基因串某些特征位相同的结构–它它描描述述的的是是一一个个串串中中的的子子集集，，在在二二进进制制编编码码的的串串中中，，模模式式是是基基于于三三个个字字符符集集（（0，，1，，*））的的字字符符串串，，符符号号* 代代表表任任意意字字符符，，即即 0或或 1。

例例 如如 模模 式式 *1*描描 述述 了了 一一 个个 四四 个个 元元 的的 子子 集集{010,011,110,111}–一般一个模式代表了多个个体，一个个体符合多个模式；一般一个模式代表了多个个体，一个个体符合多个模式；5.1 5.1 遗传算法遗传算法24模式的阶与定义距模式的阶与定义距w模模式式阶阶：：模模式式H中中确确定定位位置置的的个个数数成成为为模模式式H的的模模式式阶，记作阶，记作O（（H））–例如例如O（（0 1 1 * 1 * ）＝）＝4 – 模模式式阶阶用用来来反反映映不不同同模模式式间间确确定定性性的的差差异异，，模模式式阶阶数数越越高高，，模式的确定性就越高，所匹配的样本个数就越少模式的确定性就越高，所匹配的样本个数就越少w定义距（长度）：定义距（长度）：模式模式H中的第一个确定位置和最后中的第一个确定位置和最后一个确定位置之间的距离称为模式的定义距，记作一个确定位置之间的距离称为模式的定义距，记作δδ(H)–例如，例如，δδ(0 1 1 * 1 * * )＝＝4–在遗传查找中，即使阶数相同的模式，也会有不同的性质，在遗传查找中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。

而模式的定义距就反映了这种性质的差异5.1 5.1 遗传算法遗传算法25模式定理模式定理w模模式式定定理理（（Schema Theorem）） ：：如如果果在在给给定定的的时时间间步步t，，一一个个特特定定的的模模式式H有有m个个代代表表串串包包含含在在种种群群A(t)中中，，记记为为m(H,t) ，，f(H)表表示示在在时时间间步步t模模式式H的的串串平平均均适适应应度度，，整整个个种种群群的的平平均均适适应应度度为为 f ，，l为为二二进进制制染染色色体体基基因因串串长长，，pc为为交交叉叉概概率率，，pm为变异概率，则在基本遗传算法（为变异概率，则在基本遗传算法（SGA）的机制下有：）的机制下有：–结论结论2.3.1.1  若遗传算法只采用选择复制操作，有下式成立，若遗传算法只采用选择复制操作，有下式成立，–结论结论2.3.1.2  若遗传算法同时考虑选择复制与交叉操作，有下式成立，若遗传算法同时考虑选择复制与交叉操作，有下式成立，–结结论论2.3.1.3  若若遗遗传传算算法法同同时时考考虑虑选选择择复复制制、、交交叉叉与与变变异异操操作作，，有有下下式成立，式成立，5.1 5.1 遗传算法遗传算法26模式定理的意义模式定理的意义w模式定理的意义：模式定理的意义：在遗传算子选择、交叉、变异的作用在遗传算子选择、交叉、变异的作用下，具有低阶、短定义距以及平均适应度高于种群平均适应度下，具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。

的模式在子代中呈指数增长w积木块假说；积木块假说；wSGA最新的理论研究：最新的理论研究：–（（1）浓度模型；）浓度模型；–（（2）概率模型；）概率模型；5.1 5.1 遗传算法遗传算法27GA与与进化计算的发展w进化计算（进化计算（Evolutionary computing ））w灵感计算（灵感计算（inspired computing ））w自然计算（自然计算（Nature computing ））–进进化化计计算算–蚁蚁群系群系统统–量子量子遗传遗传算法算法 –人工免疫系人工免疫系统统 –人工内分泌系人工内分泌系统统 –复复杂杂自适自适应应系系统统 285.2  进化策略进化策略w进化策略进化策略(Evolution Strategies，，ES)是是一类模仿自然进化原理以求解参数优化一类模仿自然进化原理以求解参数优化问题的算法问题的算法w它是由雷切伯格（它是由雷切伯格（Rechenberg）、施韦）、施韦费尔（费尔（Schwefel）和彼得）和彼得·比纳特（比纳特（Peter Bienert）于）于1964年提出的，并在德国共年提出的，并在德国共同建立的同建立的295.2.1 进化策略的算法模型 w寻求与函数极值关联的实寻求与函数极值关联的实n维矢量维矢量x。

w随机选择父矢量的初始种群随机选择父矢量的初始种群w父矢量父矢量xi, i=1,…,p产生子代矢量产生子代矢量xiw对误差对误差 (i=1,…,p)排序以选择和决定保排序以选择和决定保持哪些矢量持哪些矢量w继续产生新的试验数据以及选择最小继续产生新的试验数据以及选择最小误差矢量误差矢量 5.2 进化策略305.2.2 进化策略和遗传算法的进化策略和遗传算法的区别区别 w进化策略和遗传算法有着很强的相似性，它进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原理的算法们都是一类模仿自然进化原理的算法w两者也存在着区别，其中最基本的区别是它两者也存在着区别，其中最基本的区别是它们的研究领域不同们的研究领域不同–进化策略是一种数值优化的方法，它采用一个具进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法有自适应步长和倾角的特定爬山方法–遗传算法从广义上说是一种自适应搜索技术遗传算法从广义上说是一种自适应搜索技术5.2 进化策略315.3  进化编程进化编程w进化编程进化编程(Evolutionary Programming，，EP)，又称为进化规划（，又称为进化规划（Evolutionary Planning），是由福格尔（），是由福格尔（Fogel）在）在1962年提出的一种模仿人类智能的方法。

年提出的一种模仿人类智能的方法w进化编程根据正确预测的符号数来度量适进化编程根据正确预测的符号数来度量适应值通过变异，为父代种群中的每个机应值通过变异，为父代种群中的每个机器状态产生一个子代父代和子代中最好器状态产生一个子代父代和子代中最好的部分被选择生存下来的部分被选择生存下来w它的提出是受自然生物进化机制的启发它的提出是受自然生物进化机制的启发325.3.1 进化编程的机理与表示进化编程的机理与表示w进进化化编编程程的的过过程程，，可可理理解解为为从从所所有有可可能能的的计计算算机机程程序序形形成成的的空空间间中中，，搜搜索索具具有有高的适应度的计算机程序个体高的适应度的计算机程序个体w进进化化编编程程设设计计强强调调种种群群行行为为的的变变化化进进化化编编程程系系统统的的表表示示自自然然地地面面向向任任务务级级一一旦旦选选定定一一种种适适应应性性表表示示，，就就可可以以定定义义依依赖赖于于该该表表示示的的变变异异操操作作，，在在具具体体的的父父辈行为上创建后代辈行为上创建后代 5.3 进化编程335.3.2 进化编程的步骤进化编程的步骤 进化编程分为三个步骤：进化编程分为三个步骤：w产生出初始种群。

产生出初始种群w迭迭代代完完成成下下述述子子步步骤骤，，直直至至满满足足选选种种标准为止：标准为止：–执行种群中的每个程序执行种群中的每个程序–应用变异等操作创造新程序种群应用变异等操作创造新程序种群w在在后后代代中中适适应应值值最最高高的的计计算算机机程程序序个个体被指定为进化编程的结果体被指定为进化编程的结果5.3 进化编程34变异和创造子代变异和创造子代评估已存在的评估已存在的FSM用最好的状态机用最好的状态机预测和添加符号预测和添加符号选择父代选择父代初始化观测顺序初始化观测顺序是是否否初始化种群初始化种群图图5.6  进化编程的基本过程进化编程的基本过程5.3 进化编程是否预测是否预测355.4 人工生命人工生命 w自然界是生命之源自然生命千千万万，自然界是生命之源自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无千姿百态，千差万别，巧夺天工，奇妙无穷w人工生命（人工生命（Artificial Life，，AL）试图通过）试图通过人工方法建造具有自然生命特征的人造系人工方法建造具有自然生命特征的人造系统w人工生命是生命科学、信息科学和系统科人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必学等学科交叉研究的产物，其研究成果必将促进人工智能的发展。

将促进人工智能的发展 365.4.1 人工生命研究的起源和发人工生命研究的起源和发展展 w人类长期以来一直力图用科学技术方法模拟自人类长期以来一直力图用科学技术方法模拟自然界，包括人脑本身然界，包括人脑本身19431943年麦卡络奇和皮茨年麦卡络奇和皮茨提出了提出了M M－－P P神经学网络模型神经学网络模型 w人工生命的许多早期研究工作也源于人工智能人工生命的许多早期研究工作也源于人工智能 w20世纪世纪70年代以来，康拉德（年代以来，康拉德（Conrad）等提）等提出不断完善的出不断完善的““人工世界人工世界””模型 w80年代年代w90年代年代5.4 人工生命375.4.2 人工生命的定义和研究意人工生命的定义和研究意义义 w人工生命是一项抽象地提取控制生物现人工生命是一项抽象地提取控制生物现象的基本动态原理，并且通过物理媒介象的基本动态原理，并且通过物理媒介（如计算机）来模拟生命系统动态发展（如计算机）来模拟生命系统动态发展过程的研究工作过程的研究工作w通俗地讲，人工生命即人造的生命，非通俗地讲，人工生命即人造的生命，非自然的生命然而，要对人工生命做出自然的生命然而，要对人工生命做出严格的定义，却需要对问题进行深入研严格的定义，却需要对问题进行深入研究。

究 5.4 人工生命38人工生命系统人工生命系统 w19871987年兰德提出的人工生命定义为：年兰德提出的人工生命定义为：““人工生命是研究能够演示出自然生命系人工生命是研究能够演示出自然生命系统特征行为的人造系统统特征行为的人造系统””w通过计算机或其它机器对类似生命的行通过计算机或其它机器对类似生命的行为进行综合研究，以便对传统生物科学为进行综合研究，以便对传统生物科学起互补作用起互补作用w兰德在计算机上演示了他们研制的具有兰德在计算机上演示了他们研制的具有生命特征的软件系统，并把这类具有生生命特征的软件系统，并把这类具有生命现象和特征的人造系统称为人工生命命现象和特征的人造系统称为人工生命系统 5.4 人工生命39自然生命的共同特征和现象 w自繁殖、自进化、自寻优自繁殖、自进化、自寻优w自成长、自学习、自组织自成长、自学习、自组织w自稳定、自适应、自协调自稳定、自适应、自协调w物质构造物质构造w能量转换能量转换w信息处理信息处理5.4 人工生命40研究人工生命的意义研究人工生命的意义 w人工生命是自然生命的模拟、延伸与扩人工生命是自然生命的模拟、延伸与扩展，其研究开发有重大的科学意义和广展，其研究开发有重大的科学意义和广泛的应用价值。

泛的应用价值–开发基于人工生命的工程技术新方法、新开发基于人工生命的工程技术新方法、新系统、新产品系统、新产品 –为自然生命的研究提供新模型、新工具、为自然生命的研究提供新模型、新工具、新环境新环境 –延伸人类寿命、减缓衰老、防治疾病延伸人类寿命、减缓衰老、防治疾病–扩展自然生命，人工进化、优生优育扩展自然生命，人工进化、优生优育 –促进生命、信息、系统科学的交叉与发展促进生命、信息、系统科学的交叉与发展5.4 人工生命415.4.3 人工生命的研究内容人工生命的研究内容和方法和方法 1. 人工生命的研究内容人工生命的研究内容人工生命的研究内容大致可分为两类：人工生命的研究内容大致可分为两类：  (1) 构构成成生生物物体体的的内内部部系系统统，，包包括括脑脑、、神神经经系系统统、、内内分分泌泌系系统统、、免免疫疫系系统统、、遗遗传传系统、酶系统、代谢系统等系统、酶系统、代谢系统等  (2) 在在生生物物体体及及其其种种群群的的外外部部系系统统，，包包括括环境适应系统和遗传进化系统等环境适应系统和遗传进化系统等 5.4 人工生命42人工生命的科学框架 w生命现象仿生系统生命现象仿生系统w生命现象的建模与仿真生命现象的建模与仿真 w进化动力学进化动力学 w人工生命的计算理论和工具人工生命的计算理论和工具 w进化机器人进化机器人 w进化和学习等的结合进化和学习等的结合 w人工生命的应用人工生命的应用5.4 人工生命432. 人工生命的研究方法 （（1）信息模型法）信息模型法        根根据据内内部部和和外外部部系系统统所所表表现现的的生生命命行行为来建造信息模型。

为来建造信息模型2）工作原理法）工作原理法       生生命命行行为为所所显显示示的的自自律律分分数数和和非非线线性性行行为为，，其其工工作作原原理理是是混混沌沌和和分分形形，，以以此此为基础研究人工生命的机理为基础研究人工生命的机理 5.4 人工生命44人工生命的研究技术途径人工生命的研究技术途径  (1)  工程技术途径工程技术途径  利用计算机、自动化、微电子、精密利用计算机、自动化、微电子、精密机械、光电通信、人工智能、神经网络机械、光电通信、人工智能、神经网络等有关工程技术方法和途径，研究开发、等有关工程技术方法和途径，研究开发、设计制造人工生命通过计算机屏幕，设计制造人工生命通过计算机屏幕，以三维动画，虚拟现实的软件方法或采以三维动画，虚拟现实的软件方法或采用光机电一体化的硬件装置来演示和体用光机电一体化的硬件装置来演示和体现人工生命现人工生命 5.4 人工生命45(2) 生物科学途径 w利用生物科学方法和技术，通过人工合成、基因控制，无性繁殖过程，培育生成人工生命w由于伦理学、社会学、人类学等方面的问题，通过生物科学途径生成的人工生命，如克隆人引起了不少争论。

需要研究和制订相应的社会监督、国家法律和国际公约5.4 人工生命465.4.4 人工生命的实例人工生命的实例 w人工脑人工脑 –波兰人工智能和心理学教授安奇波兰人工智能和心理学教授安奇··布勒布勒（（Andrzej Buller）及一些日本学者在日）及一些日本学者在日本现代通讯研究所进化系统研究室对人本现代通讯研究所进化系统研究室对人工脑的研究，已取得重要进展工脑的研究，已取得重要进展 w计算机病毒计算机病毒 w计算机进程计算机进程 w细胞自动机细胞自动机 w人工核苷酸人工核苷酸 5.4 人工生命475.5 小结w进化计算进化计算–遗传算法遗传算法–进化策略进化策略–进化编程进化编程w人工生命人工生命–计算智能研究的最新领域之一计算智能研究的最新领域之一–重要科学意义和社会效益重要科学意义和社会效益–研究内容、发展前景和应用领域研究内容、发展前景和应用领域48个人观点供参考，欢迎讨论。