高级人工智能课件4.pptx

《高级人工智能课件4.pptx》由会员分享，可在线阅读，更多相关《高级人工智能课件4.pptx（85页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、5/13/20231第四章第四章 计算智能计算智能n4.1概述概述n4.2神经计算神经计算n4.3模糊计算模糊计算n4.4粗糙集理论粗糙集理论n4.5遗传算法遗传算法n4.6进化策略进化策略4.7进化编程进化编程4.8人工生命人工生命4.9粒群优化粒群优化4.10蚂群算法蚂群算法4.11自然计算自然计算4.12免疫算法免疫算法5/13/202324.1 概述概述n信息科学与生命科学的相互交叉、相互渗透和相互促进是现代科学技术发展的一个显著特点。n计算智能涉及神经网络、模糊逻辑、进化计算和人工生命等领域，它的研究和发展正反映了当代科学技术多学科交叉与集成的重要发展趋势。5/13/20233什么是

2、计算智能n把神经网络（NN）归类于传统人工智能（AI）可能不大合适，而归类于计算智能（CI）更能说明问题实质。进化计算、人工生命和模糊逻辑系统的某些课题，也都归类于计算智能。n计算智能取决于制造者（manufacturers）提供的数值数据，不依赖于知识；另一方面，传统人工智能应用知识精品（knowledgetidbits）。人工神经网络应当称为计算神经网络。5/13/20234计算智能与人工智能的区别和关系nAArtificial，表示人工的（非生物的）；BBiological，表示物理的化学的（？）生物的；CComputational，表示数学计算机n计算智能是一种智力方式的低层认知，它与

3、传统人工智能的区别只是认知层次从中层下降至低层而已。中层系统含有知识（精品），低层系统则没有。5/13/20235计算智能与人工智能的区别和关系输入输入人类知识人类知识()传感输入传感输入知识知识()传感数据传感数据计算计算()传感器传感器C数值的数值的A符号的符号的B生物的生物的层次层次复杂性复杂性复杂性复杂性BNNBPRBIANNAPRAICNNCPRCI5/13/20236n当一个系统只涉及数值（低层）数据，含有模式识别部分，不应用人工智能意义上的知识，而且能够呈现出：（1）计算适应性；（2）计算容错性；（3）接近人的速度；（4）误差率与人相近，则该系统就是计算智能系统。n当一个智能计算

4、系统以非数值方式加上知识（精品）值，即成为人工智能系统。5/13/20237n1960年威德罗和霍夫率先把神经网络用于自年威德罗和霍夫率先把神经网络用于自动控制研究。动控制研究。n60年代末期至年代末期至80年代中期，神经网络控制与年代中期，神经网络控制与整个神经网络研究一样，处于低潮。整个神经网络研究一样，处于低潮。n80年代后期以来，随着人工神经网络研究的年代后期以来，随着人工神经网络研究的复苏和发展，对神经网络控制的研究也十分复苏和发展，对神经网络控制的研究也十分活跃。这方面的研究进展主要在神经网络自活跃。这方面的研究进展主要在神经网络自适应控制和模糊神经网络控制及其在机器人适应控制和模

5、糊神经网络控制及其在机器人控制中的应用上。控制中的应用上。4.2神经计算神经计算4.2.1人工神经网络研究的进展人工神经网络研究的进展5/13/20238人工神经网络的特性n并行分布处理n非线性映射n通过训练进行学习n适应与集成n硬件实现5/13/202394.2.2人工神经网络的结构-1 Wj1X1X2Wj2XnWjn ()Yi图图4.2神经元模型神经元模型5/13/202310 图图4.2中的神经元单元由多个输入中的神经元单元由多个输入xi，i=1,2,.,n和一个输出和一个输出y组成。中间状态由输入信号的权组成。中间状态由输入信号的权和表示，而输出为和表示，而输出为（4.1）式中，式中，

6、j为神经元单元的偏置，为神经元单元的偏置，wji为连接权系为连接权系数。数。n为输入信号数目，为输入信号数目，yj为神经元输出，为神经元输出，t为为时间，时间，f()为输出变换函数，如图为输出变换函数，如图4.3。5/13/202311(a)xf(x)1x00图图4.3神经元中的某些变换（激发）函数神经元中的某些变换（激发）函数(a)二值函数二值函数(b)S形函数形函数(c)双曲正切函数双曲正切函数(c)xf(x)1-1(b)f(x)x1 05/13/202312人工神经网络的基本特性和结构n人工神经网络是具有下列特性的有向图：n对于每个节点i存在一个状态变量xi；n从节点j至节点i，存在一个

7、连接权系统数wij；n对于每个节点i，存在一个阈值i；n对于每个节点i，定义一个变换函数fi；对于最一般的情况，此函数取n形式。5/13/202313n递归（反馈）网络递归（反馈）网络:在递归网络中，在递归网络中，多个神经元互连以多个神经元互连以组织一个互连神经组织一个互连神经网络，如图网络，如图4.4。图图4.4反馈网络反馈网络x1x2xnV1V2Vn输入输入输出输出x1x2xn5/13/202314n前馈网络前馈网络:前馈网前馈网络具有递阶分层络具有递阶分层结构，由同层神结构，由同层神经元间不存在互经元间不存在互连的层级组成，连的层级组成，如图如图4.5。x1x2输入层输入层输出层输出层隐

8、层隐层y1ynw11w1m图图4.5前馈网络前馈网络反向传播反向传播5/13/202315人工神经网络的主要学习算法n有师学习算法：能够根据期望的和实际有师学习算法：能够根据期望的和实际的网络输出（对应于给定输入）间的差的网络输出（对应于给定输入）间的差来调整神经元间连接的强度或权。来调整神经元间连接的强度或权。n无师学习算法：不需要知道期望输出。无师学习算法：不需要知道期望输出。n强化学习算法：采用一个强化学习算法：采用一个“评论员评论员”来来评价与给定输入相对应的神经网络输出评价与给定输入相对应的神经网络输出的优度（质量因数）。强化学习算法的的优度（质量因数）。强化学习算法的一个例子是遗传

9、算法（一个例子是遗传算法（GA）。）。5/13/202316人工神经网络的典型模型5/13/202317续前表：续前表：5/13/2023184.2.5基于神经网络的知识表示与推理基于神经网络的知识表示与推理n基于神经网络的知识表示在这里，知识并不像在产生式系统中那样独立地表示为每一条规则，而是将某一问题的若干知识在同一网络中表示。例如，在有些神经网络系统中，知识是用神经网络所对应的有向权图的邻接矩阵及阈值向量表示的。5/13/202319基于神经网络的推理基于神经网络的推理 n基于神经网络的推理是通过网络计算实现的。把用户提供的初始证据用作网络的输入，通过网络计算最终得到输出结果。n一般来说

10、，正向网络推理的步骤如下：n把已知数据输入网络输入层的各个节点。n利用特性函数分别计算网络中各层的输出。n用阈值函数对输出层的输出进行判定，从而得到输出结果。5/13/202320定义定义4.1模糊集合模糊集合(FuzzySets)论域论域U到到0,1区间的任一映射区间的任一映射，即即，都确定，都确定U的一个模糊子集的一个模糊子集F；称为称为F的隶属函数或隶属度。在论域的隶属函数或隶属度。在论域U中，可中，可把模糊子集表示为元素把模糊子集表示为元素u与其隶属函数与其隶属函数的的序偶集合，记为：序偶集合，记为：(4.12)4.3模糊计算模糊计算4.3.1模糊集合、模糊逻辑及其运算模糊集合、模糊逻

11、辑及其运算5/13/202321定义定义4.2模糊集的截集、支集和核模糊集的截集、支集和核n若模糊集是论域若模糊集是论域U中所有满足中所有满足F(u)的元素的元素u构成的集合，则称该集合为模糊集构成的集合，则称该集合为模糊集F的的截集截集。n若模糊集是论域若模糊集是论域U中所有满足中所有满足F(u)0的元素的元素u构成的集合，则称该集合为模糊集构成的集合，则称该集合为模糊集F的的支集支集。n当当u满足满足F(u)=1，称为，称为核核。也就是。也就是=1的截集。的截集。1核核支集支集截集截集5/13/202322定义定义4.3模糊集的运算模糊集的运算n设设A和和B为论域为论域U中的两个模糊集，其

12、隶属函数分别为中的两个模糊集，其隶属函数分别为A和和B，则对于所有，则对于所有u U，存在下列运算：，存在下列运算：nA与与B的并（逻辑或）记为的并（逻辑或）记为AB，其隶属函数定义为：，其隶属函数定义为：AB(u)=A(u)B(u)=maxA(u),B(u)(4.15)nA与与B的交（逻辑与）记为的交（逻辑与）记为AB，其隶属函数定义为：，其隶属函数定义为：AB(u)=A(u)B(u)=minA(u),B(u)(4.16)nA的补（逻辑非）记为的补（逻辑非）记为，其传递函数定义为：，其传递函数定义为：(u)=1-A(u)(4.17)5/13/202323定义定义4.4直积（笛卡儿乘积，代数积

13、）直积（笛卡儿乘积，代数积）若若A1,A2,An分别为论域分别为论域U1,U2,Un中的模糊集中的模糊集合，则这些集合的直积是乘积空间合，则这些集合的直积是乘积空间U1,U2,Un中一个中一个模糊集合，其隶属函数为模糊集合，其隶属函数为：定义定义4.5模糊关系模糊关系若若U，V是两个非空模糊集合，则其直积是两个非空模糊集合，则其直积UV中的模糊子集中的模糊子集R称为从称为从U到到V的模糊关系，表示为：的模糊关系，表示为：(4.19)(4.18)5/13/2023244.3.2模糊逻辑推理模糊逻辑推理n模糊逻辑推理是建立在模糊逻辑基础上的不确模糊逻辑推理是建立在模糊逻辑基础上的不确定性推理方法，

14、是在二值逻辑三段论基础上发定性推理方法，是在二值逻辑三段论基础上发展起来的。这种推理方法以模糊判断为前提，展起来的。这种推理方法以模糊判断为前提，动用模糊语言规则动用模糊语言规则，推导出一个近似的模糊判，推导出一个近似的模糊判断结论。断结论。n广义取式广义取式(肯定前提肯定前提)假言推理法假言推理法(GMP)推理规则推理规则可表示为：可表示为：前提前提1：x为为A前提前提2：若：若x为为A，则，则y为为B结结论：论：y为为B5/13/202325n广义拒式广义拒式(否定结论否定结论)假言推理法假言推理法(GMT,GeneralizedModusTollens)的推理规则的推理规则可表示为：可表

15、示为：前提前提1：y为为B前提前提2：若：若x为为A，则，则y为为B结结论：论：x为为An模糊变量的隐含函数基本上可分为三类，模糊变量的隐含函数基本上可分为三类，即模糊合取、模糊析取和模糊蕴涵。即模糊合取、模糊析取和模糊蕴涵。5/13/2023264.3.3模糊判决方法模糊判决方法n在推理得到的模糊集合中取一个相对最能代在推理得到的模糊集合中取一个相对最能代表这个模糊集合的单值的过程就称作表这个模糊集合的单值的过程就称作解模糊解模糊或模糊判决或模糊判决（Defuzzification）。模糊判决可）。模糊判决可以采用不同的方法：重心法、最大隶属度方以采用不同的方法：重心法、最大隶属度方法、加权

16、平均法、隶属度限幅元素平均法。法、加权平均法、隶属度限幅元素平均法。n下面介绍各种模糊判决方法，并以下面介绍各种模糊判决方法，并以“水温适水温适中中”为例，说明不同方法的计算过程。这里为例，说明不同方法的计算过程。这里假设假设“水温适中水温适中”的隶属函数为：的隶属函数为：=X:0.0/0+0.0/10+0.33/20+0.67/30+1.0/40+1.0/50+0.75/60+0.5/70+0.25/80+0.0/90+0.0/1005/13/202327重心法就是取模糊隶属函数曲线与横坐标轴重心法就是取模糊隶属函数曲线与横坐标轴围成面积的重心作为代表点。理论上应该计算输围成面积的重心作为代

17、表点。理论上应该计算输出范围内一系列连续点的重心，即出范围内一系列连续点的重心，即(4.40)但实际上是计算输出范围内整个采样点的重心，但实际上是计算输出范围内整个采样点的重心，用足够小的取样间隔来提供所需要的精度，即：用足够小的取样间隔来提供所需要的精度，即：=48.21.重心法5/13/202328这种方法最简单，只要在推理结论的模糊集这种方法最简单，只要在推理结论的模糊集合中取隶属度最大的那个元素作为输出量即可。合中取隶属度最大的那个元素作为输出量即可。要求这种情况下其隶属函数曲线一定是正规凸模要求这种情况下其隶属函数曲线一定是正规凸模糊集合（即其曲线只能是单峰曲线）。糊集合（即其曲线只

18、能是单峰曲线）。例如，对于例如，对于“水温适中水温适中”，按最大隶属度原，按最大隶属度原则，有两个元素则，有两个元素40和和50具有最大隶属度具有最大隶属度1.0，那就，那就对所有取最大隶属度的元素对所有取最大隶属度的元素40和和50求平均值，执求平均值，执行量应取：行量应取：2.最大隶属度法5/13/2023293.系数加权平均法n系数加权平均法的输出执行量由下式决系数加权平均法的输出执行量由下式决定：定：(4.41)式中，系数的选择要根据实际情况式中，系数的选择要根据实际情况而定，不同的系统就决定系统有不同的而定，不同的系统就决定系统有不同的响应特性。响应特性。ki=N(xi)就是重心法。

19、就是重心法。5/13/2023304.4 粗糙集理论粗糙集理论粗糙集理论粗糙集理论(RoughSettheory)是是1982年由波兰数学家年由波兰数学家Z.Pawlak提出的，当时没提出的，当时没有引起国际计算机学界和数学界的重视，研究仅限于东欧的一些国家，直到有引起国际计算机学界和数学界的重视，研究仅限于东欧的一些国家，直到20世纪世纪80年代末才逐渐引起各国学者的注意。年代末才逐渐引起各国学者的注意。1991年，年，Pawlak发表了专著发表了专著RoughSet：TheoreticalAspectsofReasoningaboutData，奠定了粗糙集理论的基础。，奠定了粗糙集理论的基

20、础。1992年，在波兰召开了第一届国际年，在波兰召开了第一届国际粗糙集研讨会，这次会议着重讨论了集合近似的基本思想及其应用，其中粗糙粗糙集研讨会，这次会议着重讨论了集合近似的基本思想及其应用，其中粗糙环境下的机器学习的基础研究是这次会议的四个专题之一。环境下的机器学习的基础研究是这次会议的四个专题之一。1993年在加拿大召年在加拿大召开了第二届国际粗糙集与知识发现研讨会，这次会议积极推动了国际上对粗糙开了第二届国际粗糙集与知识发现研讨会，这次会议积极推动了国际上对粗糙集应用的研究。由于这次会议正值知识发现成为热门研究话题，一些著名的知集应用的研究。由于这次会议正值知识发现成为热门研究话题，一些

21、著名的知识发现学者参加了这次会议，并且介绍了许多应用扩展粗糙集理论的数据挖掘识发现学者参加了这次会议，并且介绍了许多应用扩展粗糙集理论的数据挖掘的方法与系统。的方法与系统。1996年在日本东京召开了第五届国际粗糙集研讨会以及年在日本东京召开了第五届国际粗糙集研讨会以及2001年年在我国举行的研讨会推动了亚洲地区和我国对粗糙集理论与应用的研究。现在，在我国举行的研讨会推动了亚洲地区和我国对粗糙集理论与应用的研究。现在，美国、加拿大、波兰、日本都有粗糙集研究的专门机构。美国、加拿大、波兰、日本都有粗糙集研究的专门机构。5/13/2023314.4 粗糙集理论粗糙集理论1.粗糙集理论的基本概念粗糙集

22、理论的基本概念Rough集的基础概念集的基础概念有一个表示文献资料的对象集合有一个表示文献资料的对象集合U和和U上的等上的等价关系价关系R，R是由对象的属性是由对象的属性(这里是指标引词这里是指标引词)集集派生的派生的U集合的集合的划分，划分，R=X1,X2,Xn。我们称。我们称为近似空间为近似空间(Approximationspace)。对于。对于P R并且并且P，这是指，这是指P是由是由的子集的子集派生的，那么派生的，那么P(所有所有P中等价关系的交集中等价关系的交集)也是一种等价关系，在也是一种等价关系，在Rough集中，我们常称集中，我们常称P为为P上的不可分辨关系上的不可分辨关系(I

23、ndiscernibilityrelation)，记作，记作Ind(P)。按照按照形状形状分类分类4.4.1 粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点5/13/2023324.4 粗糙集理论粗糙集理论按照按照大小大小分类分类按照按照颜色颜色分类分类5/13/2023334.4 粗糙集理论粗糙集理论按照按照“形形状状”和和“大小大小”分分类类按照按照“颜颜色色”和和“大小大小”分分类类5/13/2023344.4.1粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点n定义4.17对于每个集合XU和一个等价关系R，A=(U,R)称为知识库，定义两个子集:nX=x|xX=xU|xX为X

24、的下近似空间(Lowerapproximation)。nX=x|xX=xU|xX为X的上近似空间(Upperapproximation)。nBN(X)=5/13/2023354.4.1粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点甲甲甲甲甲甲甲甲甲甲甲甲甲甲按照按照“形形状状”和和“大小大小”分分类类甲甲甲甲甲甲甲甲甲甲甲甲甲甲5/13/2023364.4.1粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点 5/13/2023374.4.1粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点 n定义4.18X关于A的近似质量，定义为:n定义4.19X关于A的粗糙性测度，定义为:0A(

25、X)1；A(X)=0时，X是可以确定的；A(X)0时，X是可以粗糙的，A(X)是粗糙程度。5/13/2023384.4.1粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点 n定义4.20设F=X1,X2,Xn，XiU，则F关于近似空间A的下近似和上近似，定义为:n定义4.21F关于A的近似精度A(X)和近似质量A(X)分别定义为:5/13/2023394.4.1粗糙集理论的基本概念和特点粗糙集理论的基本概念和特点 2.粗糙集理论的特点粗糙集理论的特点n不需要先验知识不需要先验知识n强大的数据分析和约简能力：求知识的最小表达；强大的数据分析和约简能力：求知识的最小表达；识别数据之间的依赖关系

26、识别数据之间的依赖关系n粗糙集侧重分类；模糊集侧重个体的含糊性粗糙集侧重分类；模糊集侧重个体的含糊性5/13/2023404.5遗传算法遗传算法n遗传算法是模仿生物遗传学和自然选择机遗传算法是模仿生物遗传学和自然选择机理，通过人工方式所构造的一类优化搜索理，通过人工方式所构造的一类优化搜索算法，是对生物进化过程进行的一种数学算法，是对生物进化过程进行的一种数学仿真，是进化计算的最重要的形式。仿真，是进化计算的最重要的形式。n遗传算法为那些难以找到传统数学模型的遗传算法为那些难以找到传统数学模型的难题指出了一个解决方法。难题指出了一个解决方法。n进化计算和遗传算法借鉴了生物科学中的进化计算和遗传

27、算法借鉴了生物科学中的某些知识，这也体现了人工智能这一交叉某些知识，这也体现了人工智能这一交叉学科的特点。学科的特点。5/13/2023414.5.1遗传算法的基本机理遗传算法的基本机理n霍兰德的遗传算法通常称为简单遗传算霍兰德的遗传算法通常称为简单遗传算法法(SGA)。现以此作为讨论主要对象，加。现以此作为讨论主要对象，加上适应的改进，来分析遗传算法的结构上适应的改进，来分析遗传算法的结构和机理。和机理。n编码与解码编码与解码n适应度函数适应度函数 n遗传操作遗传操作 5/13/2023424.5.1遗传算法的基本机理遗传算法的基本机理n编码与解码编码与解码将问题结构变换为位串形式编码表示的

28、过程叫将问题结构变换为位串形式编码表示的过程叫编码编码；而相反将位串形式编码表示变换为原问；而相反将位串形式编码表示变换为原问题结构的过程叫题结构的过程叫解码解码或译码。或译码。把位串形式编码表示叫把位串形式编码表示叫染色体染色体(chromosome)(chromosome)，有时也叫有时也叫个体个体。“甲甲”的编码：的编码：01001 111010100011 染色体的每位称为染色体的每位称为基因基因(gene)(gene)。“甲甲”染色体的第染色体的第5 5个基因取值为个基因取值为1 1 1 1。5/13/2023434.5.1遗传算法的基本机理遗传算法的基本机理n适应度函数适应度函数

29、为了体现染色体的适应能力，引入了对问题中的每一个为了体现染色体的适应能力，引入了对问题中的每一个染色体都能进行度量的函数，叫染色体都能进行度量的函数，叫适应度函数适应度函数(fitness fitness function)function)。适应度函数要有效反映每一个染色体与问题的最优解染适应度函数要有效反映每一个染色体与问题的最优解染色体之间的差距。适应度函数的取值大小与求解问题对色体之间的差距。适应度函数的取值大小与求解问题对象的意义有很大的关系。象的意义有很大的关系。TSPTSP的目标是路径总长度为最短，自然地，由路径总长度的目标是路径总长度为最短，自然地，由路径总长度就可就可导出导出

30、TSPTSP问题的适应度函数。问题的适应度函数。f(wf(w1 1,w,w2 2,w,wn n)=)=5/13/2023444.5.1遗传算法的基本机理遗传算法的基本机理n遗传操作遗传操作:选择、交叉、变异选择、交叉、变异1.1.选择选择(selection)(selection)适应度较大的个体有较大的生存机会适应度较大的个体有较大的生存机会。赌轮选择机制：赌轮选择机制：f fi i/f fj j 5/13/2023454.5.1遗传算法的基本机理遗传算法的基本机理n遗传操作遗传操作:选择、交叉、变异选择、交叉、变异2.2.交叉交叉(crossover)(crossover)将两个个体的部分

31、编码进行交换将两个个体的部分编码进行交换。10001110P111011001P2100011101000100111011001110111103.变异变异(mutation)改变某位的值。改变某位的值。例如：例如：10100110 10100110101101105/13/2023464.5.2遗传算法的求解步骤遗传算法的求解步骤1.遗传算法的特点遗传算法的特点(1)遗遗传传算算法法是是对对参参数数集集合合的的编编码码而而非非针针对对参参数本身进行进化；数本身进行进化；(2)遗遗传传算算法法是是从从问问题题解解的的编编码码组组(群群体体)开开始而非从单个解开始搜索；始而非从单个解开始搜索；

32、(3)遗遗传传算算法法利利用用目目标标函函数数的的适适应应度度这这一一信信息而非利用导数或其它辅助信息来指导搜索；息而非利用导数或其它辅助信息来指导搜索；(4)遗遗传传算算法法利利用用选选择择、交交叉叉、变变异异等等算算子子而不是利用确定性规则进行随机操作。而不是利用确定性规则进行随机操作。5/13/202347一般遗传算法的主要步骤如下：一般遗传算法的主要步骤如下：(1)随随机机产产生生一一个个由由确确定定长长度度的的特特征征字字符串组成的初始群体。符串组成的初始群体。(2)对对该该字字符符串串群群体体迭迭代代的的执执行行下下面面的的和和步，直到满足停止标准：步，直到满足停止标准：计算群体中

33、每个个体字符串的适应值；计算群体中每个个体字符串的适应值；应应用用复复制制、交交叉叉和和变变异异等等遗遗传传算算子子产产生生下一代群体。下一代群体。(3)把把在在后后代代中中出出现现的的最最好好的的个个体体字字符符串串指指定定为为遗遗传传算算法法的的执执行行结结果果，这这个结果可以表示问题的一个解。个结果可以表示问题的一个解。5/13/2023482.遗传算法的流程图遗传算法的流程图(图图4.18)(1)初始化群体初始化群体;(2)计算群体上每个个体的适应度值计算群体上每个个体的适应度值;(3)按按由由个个体体适适应应度度值值所所决决定定的的某某个个规规则则选选择择将将进入下一代的个体进入下一

34、代的个体;(4)按概率按概率Pc进行交叉操作进行交叉操作;(5)按概率按概率Pm进行突变操作进行突变操作;(6)若若没没有有满满足足某某种种停停止止条条件件，则则转转第第(2)步步，否则进入下一步。否则进入下一步。(7)输输出出群群体体中中适适应应度度值值最最优优的的染染色色体体作作为为问问题题的的满意解或最优解。满意解或最优解。5/13/202349初始化种群初始化种群变异操作变异操作计算适应度值计算适应度值选择操作选择操作交叉操作交叉操作输出适应度最优个体输出适应度最优个体终止条件终止条件开始开始图图4.18遗传算法流程图遗传算法流程图是是否否结束结束5/13/202350产生初始群体产生

35、初始群体是否满足停止准则是否满足停止准则计算每个个体的适应值计算每个个体的适应值i=M?GEN:=GEN+1依概率选择遗传操作依概率选择遗传操作执行复制执行复制选择一个个体选择一个个体选择交叉位置选择交叉位置选择两个个体选择两个个体选择一个个体选择一个个体执行变异执行变异i:=0GEN:=0复制到新群体复制到新群体i:=i+1将两个后代插入新群体将两个后代插入新群体插入到新群体插入到新群体执行杂交执行杂交指定结果指定结果结束结束是是否否是是否否变异变异复制复制交叉交叉5/13/2023513.遗传算法求解举例遗传算法求解举例v设，用SGA求v参数设置v二进制编码v种群大小为4v染色体长为4位5

36、/13/202352遗传算法归纳为五个基本组成部分遗传算法归纳为五个基本组成部分 方案表示方案表示用用一一个个二二进进制制矢矢量量表表示示一一个个染染色色体体，由由染染色色体体来来代代表表变变量量x x的的实实数数值值，每每个个染色体的每一位二进制数称为遗传因子。染色体的每一位二进制数称为遗传因子。群体初始化群体初始化随机产生一定数量的染色体，每个染色体为若干位字节的二进制数。随机产生一定数量的染色体，每个染色体为若干位字节的二进制数。适应度函数适应度函数适适应应度度函函数数必必须须有有能能力力计计算算搜搜索索空空间间中中每每个个确确定定长长度度的的特特征征字字符符串串的的适适应应值。值。遗传

37、操作遗传操作采采用用的的遗遗传传操操作作分分别别是是复复制制、交交叉叉和和变变异异。交交叉叉相相对对于于复复制制和和变变异异的的不不同同之之处处在在于于：交交叉叉需需要要两两个个父父代代染染色色体体配配合合进进行行，而而复复制制和和变变异异只只需需要要一一个个父父代代染染色色体体即即可可进进行行。变变异异可可根根据据一一定定的的变变异异率率来来改改变变一一个个或或多多个个遗遗传传基基因。因。算法参数算法参数遗遗传传算算法法的的主主要要参参数数有有群群体体规规模模和和算算法法执执行行的的最最大大代代数数目目，次次要要参参数数有有复复制概率、杂交概率和变异概率等参数。制概率、杂交概率和变异概率等参

38、数。5/13/2023534.6进化策略进化策略n进化策略进化策略(EvolutionStrategies，ES)是是一类模仿自然进化原理以一类模仿自然进化原理以求解参数优化求解参数优化问题的算法。问题的算法。n它是由雷切伯格（它是由雷切伯格（Rechenberg）、施韦）、施韦费尔（费尔（Schwefel）和彼得）和彼得比纳特比纳特（PeterBienert）于）于1964年提出的，并在年提出的，并在德国共同建立的。德国共同建立的。5/13/2023544.6.1进化策略的算法模型n寻求与函数极值关联的实数寻求与函数极值关联的实数n维矢量维矢量x，F(x):RnR。n随机选择父矢量的初始群体

39、。随机选择父矢量的初始群体。n父矢量父矢量xi,i=1,p通过算法产生子代矢量通过算法产生子代矢量xi。n对误差对误差F(xi)(i=1,p)排序以选择和决定排序以选择和决定保持哪些矢量。保持哪些矢量。拥有最小误差的拥有最小误差的P矢量成为矢量成为下一代的新的父代。下一代的新的父代。n继续产生新的试验数据以及选择最小误差矢继续产生新的试验数据以及选择最小误差矢量，找到符合条件的误差为止。量，找到符合条件的误差为止。5/13/2023554.6.2进化策略和遗传算法的区别进化策略和遗传算法的区别n进化策略和遗传算法有着很强的相似性，它们都是一类模仿自然进化原进化策略和遗传算法有着很强的相似性，它

40、们都是一类模仿自然进化原理的算法。理的算法。n两者也存在着区别，其中最基本的区别是它们的研究领域不同。进化策两者也存在着区别，其中最基本的区别是它们的研究领域不同。进化策略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬略是一种数值优化的方法，它采用一个具有自适应步长和倾角的特定爬山方法。遗传算法从广义上说是一种自适应搜索技术。山方法。遗传算法从广义上说是一种自适应搜索技术。(1)(1)进进化化策策略略和和遗遗传传算算法法表表示示个个体体的的方方式式不不同同，进进化化策策略略在在浮浮点点矢矢量量上上运运行行，而而遗遗传传算算法法一一般般运运行行在在二二进进制制矢矢量量上上。GAGA

41、是是对对变变量量的的编编码码串串操操作作,而而ESES是对变量本身操作。是对变量本身操作。(2)(2)进化策略和遗传算法的选择过程不同。进化策略优等个体机会均等进化策略和遗传算法的选择过程不同。进化策略优等个体机会均等(3)(3)进进化化策策略略和和遗遗传传算算法法的的复复制制参参数数不不同同，遗遗传传算算法法的的复复制制参参数数(交交叉叉和和变变异异的可能性的可能性)在进化过程中保持恒定，而进化策略时时改变它们。在进化过程中保持恒定，而进化策略时时改变它们。5/13/2023564.7进化编程进化编程n进化编程进化编程(EvolutionaryProgramming，EP)，又称为进化规划（

42、，又称为进化规划（EvolutionaryPlanning），），是由福格尔（是由福格尔（Fogel）在）在1962年提出的一种模年提出的一种模仿人类智能的方法。仿人类智能的方法。n进化编程根据正确预测的符号数来度量适应值。进化编程根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状态产生通过变异，为父代群体中的每个机器状态产生一个子代。父代和子代中最好的部分被选择生一个子代。父代和子代中最好的部分被选择生存下来。存下来。n它的提出是受自然生物进化机制的启发。它的提出是受自然生物进化机制的启发。5/13/2023574.7.1进化编程的机理与表示进化编程的机理与表示n进进化化编

43、编程程的的过过程程，可可理理解解为为从从所所有有可可能能的的计计算算机机程程序序形形成成的的空空间间中中，搜搜索索具具有有高的适应度的计算机程序个体。高的适应度的计算机程序个体。n进进化化编编程程设设计计强强调调群群体体行行为为的的变变化化。进进化化编编程程系系统统的的表表示示自自然然地地面面向向任任务务级级。一一旦旦选选定定一一种种适适应应性性表表示示，就就可可以以定定义义依依赖赖于于该该表表示示的的变变异异操操作作，在在具具体体的的父父辈行为上创建后代。辈行为上创建后代。5/13/2023584.7.2进化编程的步骤进化编程的步骤进化编程分为三个步骤：进化编程分为三个步骤：n产生出初始群体

44、。产生出初始群体。n迭迭代代完完成成下下述述子子步步骤骤，直直至至满满足足选选种种标标准准为止：为止：n执行群体中的每个程序。执行群体中的每个程序。n应用变异等操作创造新程序群体。应用变异等操作创造新程序群体。n在在后后代代中中适适应应值值最最高高的的计计算算机机程程序序个个体体被被指定为进化编程的结果。指定为进化编程的结果。5/13/202359变异和创造子代变异和创造子代评估已存在的评估已存在的FSM用最好的状态机用最好的状态机预测和添加符号预测和添加符号选择父代选择父代初始化观测顺序初始化观测顺序是是否否是否预测是否预测初始化群体初始化群体图图5.6进化编程的基本过程进化编程的基本过程有

45、限状态机有限状态机FiniteStateMachineFMS5/13/2023604.8人工生命人工生命n自然界是生命之源。自然生命千千万万，千自然界是生命之源。自然生命千千万万，千姿百态，千差万别，巧夺天工，奇妙无穷。姿百态，千差万别，巧夺天工，奇妙无穷。n人工人工生命（生命（ArtificialLife，AL）试图通过）试图通过人工方法建造具有人工方法建造具有自然生命特征的人造系统。自然生命特征的人造系统。n人工生命是生命科学、信息科学和系统科学人工生命是生命科学、信息科学和系统科学等学科交叉研究的产物，其研究成果必将促等学科交叉研究的产物，其研究成果必将促进人工智能的发展。进人工智能的发

46、展。5/13/2023614.8.1 人工生命研究的起源和发展人工生命研究的起源和发展 n人类长期以来一直力图用科学技术方法模拟自人类长期以来一直力图用科学技术方法模拟自然界，然界，包括人脑本身。包括人脑本身。1943年麦卡络奇和皮茨年麦卡络奇和皮茨提出了提出了MP神经学网络模型。神经学网络模型。n人工生命的许多早期研究工作也源于人工智能。人工生命的许多早期研究工作也源于人工智能。n20世纪世纪70年代以来，康拉德（年代以来，康拉德（Conrad）等提出）等提出不断完善的不断完善的“人工世界人工世界”模型。模型。n80年代，年代，人工神经网络再度兴起促进人工生命人工神经网络再度兴起促进人工生命

47、的发展。正式提出人工生命的概念，建立起人的发展。正式提出人工生命的概念，建立起人工生命新学科。工生命新学科。n90年代，迅速发展年代，迅速发展5/13/2023624.8.2人工生命的定义和研究意义人工生命的定义和研究意义n人工生命是一项抽象地提取控制生物现象人工生命是一项抽象地提取控制生物现象的基本动态原理，并且通过物理媒介（如的基本动态原理，并且通过物理媒介（如计算机）来模拟生命系统动态发展过程的计算机）来模拟生命系统动态发展过程的研究工作。研究工作。n通俗地讲，人工生命即人造的生命，非自通俗地讲，人工生命即人造的生命，非自然的生命。然而，要对人工生命做出严格然的生命。然而，要对人工生命做

48、出严格的定义，却需要对问题进行深入研究。的定义，却需要对问题进行深入研究。5/13/202363人工生命系统人工生命系统 n1987年兰德提出的人工生命定义为：年兰德提出的人工生命定义为：“人工生人工生命是研究能够演示出自然生命系统特征行为的命是研究能够演示出自然生命系统特征行为的人造系统人造系统”。n通过计算机或其它机器对类似生命的行为进行通过计算机或其它机器对类似生命的行为进行综合研究，以便对传统生物科学起互补作用。综合研究，以便对传统生物科学起互补作用。n兰德在计算机上演示了他们研制的具有生命特兰德在计算机上演示了他们研制的具有生命特征的软件系统，并把这类具有生命现象和特征征的软件系统，

49、并把这类具有生命现象和特征的人造系统称为人工生命系统。的人造系统称为人工生命系统。5/13/202364自然生命的共同特征和现象n自繁殖、自进化、自寻优自繁殖、自进化、自寻优n自成长、自学习、自组织自成长、自学习、自组织n自稳定、自适应、自协调自稳定、自适应、自协调n物质构造物质构造n能量转换能量转换n信息处理信息处理5/13/202365研究人工生命的意义研究人工生命的意义 n人工生命是自然生命的模拟、延伸与扩人工生命是自然生命的模拟、延伸与扩展，其研究开发有重大的科学意义和广展，其研究开发有重大的科学意义和广泛的应用价值。泛的应用价值。n开发基于人工生命的工程技术新方法、新开发基于人工生命

50、的工程技术新方法、新系统、新产品系统、新产品 n为自然生命的研究提供新模型、新工具、为自然生命的研究提供新模型、新工具、新环境新环境 n延伸人类寿命、减缓衰老、防治疾病延伸人类寿命、减缓衰老、防治疾病n扩展自然生命，人工进化、优生优育扩展自然生命，人工进化、优生优育 n促进生命、信息、系统科学的交叉与发展促进生命、信息、系统科学的交叉与发展5/13/2023664.8.3人工生命的研究内容和方法人工生命的研究内容和方法1.人工生命的研究内容人工生命的研究内容人工生命的研究内容大致可分为两类：人工生命的研究内容大致可分为两类：(1)构构成成生生物物体体的的内内部部系系统统，包包括括脑脑、神神经经