人工智能AI4章计算智能

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,计算智能是信息科学、生命科学、认知科学等不同学科相互交叉的产物。它主要借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法去模拟和实现人类的智能。,计算智能主要研究领域包括：神经计算、进化计算、模糊计算、免疫计算、DNA计算、粗糙集等。,4.1 概述,4.1.1 什么是计算智能,4.1.2 计算智能的产生与发展,4.1.3 计算智能与人工智能的关系,4.2 神经计算,4.3 进化计算,4.4 模糊计算,4.5 粗糙集,第4章 计算智能,1,4.1.1 什么是计算智能,概念解释,计算智能,（Computational Intelligence，CI）目前还没有一个统一的的定义，使用较多的是美国科学家贝慈德克（）从计算智能系统角度所给出的定义。,从计算智能系统角度,如果一个系统仅处理低层的数值数据，含有模式识别部件，没有使用人工智能意义上的知识，且具有计算适应性、计算容错力、接近人的计算速度和近似于人的误差率这4个特性，则它是计算智能的。,从学科范畴看,计算智能是在神经网络（Neural Networks,NN）、进化计算（Evolutionary Computation, EC）及模糊系统（Fuzzy System,FS）这3个领域发展相对成熟的基础上形成的一个统一的学科概念。,2,4.1.1 什么是计算智能,研究领域,神经网络,是一种对人类智能的结构模拟方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理的。,进化计算,是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。,模糊计算,是一种对人类智能的逻辑模拟方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。,综合解释,从贝慈德克的定义和上述学科范畴可以看出以下两点：,第一，,计算智能是借鉴仿生学的思想，基于生物神经系统的结构、进化和认知对自然智能进行模拟的。,第二，,计算智能是一种以模型（计算模型、数学模型）为基础，以分布、并行计算为特征的自然智能模拟方法。,3,4.1.2 计算智能的产生与发展,1992年，贝慈德克在Approximate Reasoning学报上首次 提出了“计算智能”的概念。,1994年6月底到7月初，IEEE在美国佛罗里达州的奥兰多市召开了首届国际计算智能大会(简称WCCI94)。会议第一次将神经网络、进化计算和模糊系统这三个领域合并在一起，形成了“计算智能”这个统一的学科范畴。,在此之后，WCCI大会就成了IEEE的一个系列性学术会议，每4年举办一次。1998年5月，在美国阿拉斯加州的安克雷奇市又召开了第2届计算智能国际会议WCCI98。2002年5月，在美国州夏威夷州首府火奴鲁鲁市又召开了第3届计算智能国际会议WCCI02。此外，IEEE还出版了一些与计算智能有关的刊物。,目前，计算智能的发展得到了国内外众多的学术组织和研究机构的高度重视，并已成为智能科学技术一个重要的研究领域。,4,4.1.3 计算智能与人工智能的关系,目前，对计算智能与人工智能的关系有2种观点，一种认为计算智能是人工智能的一个子集，另一种认为计算智能和人工智能是不同的范畴。,第一种观点,的代表人物是贝慈德克。他把智能（Intelligence，I）和神经网络（Neural Network，NN）都分为,计算的,（Computational，C）、,人工的,（Artificial，A）和,生物的,（Biological,B）3个层次，并以,模式识别,（PR）为例，给出了下图所示的智能的层次结构。,在该图中，,底层是计算智能（CI）,，它通过数值计算来实现，其基础是CNN；,中间层是人工智能（AI）,，它通过人造的符号系统实现，其基础是ANN；,顶层是生物智能（BI）,，它通过生物神经系统来实现，其基础是BNN。,按照贝慈德克的观点，,CNN,是指按生物激励模型构造的NN，,ANN,是指CNN+知识，,BNN,是指人脑，即ANN包含了CNN，BNN又包含了ANN。对智能也一样，贝慈德克认为,AI包含了CI，BI又包含了AI,，即计算智能是人工智能的一个子集。,5,CNN,CPR,CI,ANN,APR,AI,BNN,BPR,BI,人类知识,(+)传感输入,知识,(+)传感数据,计算,(+)传感器,B生物的,A符号的,C数值的,复杂性,复杂性,输入,层次,贝慈德克的智能的3个层次,4.1.3 计算智能与人工智能的关系,6,第二种观点,是大多数学者所持有的观点，其代表人物是艾伯哈特（）。他们认为：,虽然人工智能与计算智能之间有重合，但计算智能是一个全新的学科领域，无论是生物智能还是机器智能，计算智能都是其最核心的部分，而人工智能则是外层。,事实上，CI和传统的AI只是智能的两个不同层次，各自都有自身的优势和局限性，相互之间只应该互补，而不能取代。,大量实践证明，只有把AI和CI很好地结合起来，才能更好地模拟人类智能，才是智能科学技术发展的正确方向。,4.1.3 计算智能与人工智能的关系,7,4.1 概述,4.2 神经计算,4.2.1 神经计算基础,4.2.2 人工神经网络的互连结构,4.2.3 人工神经网络的典型模型,4.3 进化计算,4.4 模糊计算,4.5 粗糙集,第4章 计算智能,神经计算或叫神经网络，是计算智能的重要基础和核心。,基于神经网络的连接学习机制放到机器学习部分讨论。,8,4.2.1 神经计算基础,生物神经系统是人工神经网络的基础。人工神经网络是对人脑神经系统的简化、抽象和模拟，具有人脑功能的许多基本特征。,1. 生物神经系统简介,(1) 生物神经元的结构,(2) 生物神经细胞及工作方式,(3) 突触联结,(4) 突触传递方式,2. 人工神经网络简介,9,结构：,胞体,轴突,树突,突触,长度：,最长1米,状态：,抑制,兴奋,细胞体,轴突,树突,突触,1. 生物神经系统简介,生物神经元的结构,10,细胞结构,细胞膜，细胞质，细胞核,神经递质传递,乙酰胆碱、儿茶酚胺类、氨基酸等,信号跨膜转导,离子通道,基本状态：,抑制：-70毫伏,兴奋：+40 毫伏,静息膜电位：,-70毫伏,动作电位：,+40 毫伏,工作方式：,刺激叠加,瞬间冲动,细胞膜,细胞质,细胞核,1. 生物神经系统简介,神经细胞及工作方式,11,1. 生物神经系统简介,突触联结方式,12,1. 生物神经系统简介,突触传导,突触后膜,突触间隙,突触前膜,神经微管,线粒体,突触小泡,存储颗粒,突触传导由电变化和化学变化两个过程完成。,当一个神经冲动传到神经末梢时，促使小泡前移与突触前膜融合，并在融合处出现裂口，使其所含神经递质释放，释放出来的神经递质通过突触前膜的张口进入突出间隙。,进入突触间隙的神经递质又迅速作用于突触后膜，改变突触后膜的通透性，引起突触后成分中的电位变化，实现神经冲动的传递。,由于神经末梢所释放的递质不同（兴奋作用和抑制作用），因此突触可分为兴奋性突触和抑制性突触。,13,4.2.1 神经计算基础,生物神经系统是人工神经网络的基础。人工神经网络是对人脑神经系统的简化、抽象和模拟，具有人脑功能的许多基本特征。,1. 生物神经系统简介,2. 人工神经网络简介,(1) 人工神经元的结构,(2) 常用的人工神经元模型,(3) 人工神经网络及其分类,14,x,1,x,2,x,n,w,1,w,2,w,n,y,MP模型是美国心理学家麦克洛奇(W.McM ulloch)和数理逻辑学家皮茨(W.Pitts) 根据生物神经元的功能和结构，于1943年提出的一种将神经元看作二进制阈值元件的简单模型。,图中的x,1, x,2, ,x,n,表示某一神经元的n个输入；w,i,表示第i个输入的连接强度，称为连接权值；为神经元的阈值；y为神经元的输出。,2. 人工神经网络简介,人工神经元的结构,图4.3 MP神经元模型,人工神经元是一个具有多输入，单输出的非线性器件。其输入为：,其输出为：,15,根据功能函数的不同，可得不同的神经元模型。,阈值型(Threshold),这种模型的神经元没有内部状态，作用函数f是一个阶跃函数，他表示激活值和输出之间的关系。,分段线性强饱和型(Linear Saturation),这种模型又称为伪线性，其输入/输出之间在一定范围内满足线性关系，一直延续到输出为最大值1为止。但当达到最大值后，输出就不再增。,S型(Sibmoid),这是一种连续的神经元模型，其输入输出特性常用指数、对数或双曲正切等S型函数表示。它反映的是神经元的饱和特性.,子阈累积型(Subthreshold Summation),也是一个非线性函数，当产生的激活值超过T值时，该神经元被激活产生个反响。在线性范围内，系统的反响是线性的。,f(,),1,T,1,2. 人工神经网络简介,常用的人工神经元模型,f(,),1,0,0,f(,),1,0,f(,),0,16,人工神经网络是一种对人工神经元进行互联所形成的网络，它是对生物神经网络的模拟。反映的是神经元的饱和特性.,2. 人工神经网络简介,人工神经网络及其分类,人工神经网络的概念,人工神经网络的分类,按学习方法,前馈网络,反馈网络,按拓扑结构,有导师指导,无导师指导,按网络性能,连续型网络,离散型网络,17,4.2.2 人工神经网络的互联结构,人工神经网络的互连结构（或称拓扑结构）是指单个神经元之间的连接模式，它是构造神经网络的基础，也是神经网络诱发偏差的主要来源。从互连结构的角度：,1. 前馈网络,2. 反馈网络,单层前馈网络,多层前馈网络,单层反馈网络,多层反馈网络,仅含输入层和输出层，且只有输出层的神经元是可计算节点,除拥有输入、输出层外，还至少含有一个、或更多个隐含层的前向网络,指不拥有隐含层的反馈网络,指拥有隐含层的反馈网络,（可含有反馈联结）,（只包含前向联结）,18,单层前馈网络,是指那种只拥有单层计算节点的前向网络。它仅含有输入层和输出层，且只有输出层的神经元是可计算节点，如下图所示,x,1,X,2,X,3,x,n,y,1,Y,2,y,m,权值,w,ij,输出层,输入层,图4.8 单层前馈网络结构,1. 前馈网络,单层前馈网络(1/3),其中，输入向量为X=(x,1,x,2,x,n,)；输出向量为Y=(y,1,y,2,y,m,)；输入层各个输入到相应神经元的连接权值分别是w,ij,，i=1,2,.,n，j=1,2,., m。,19,若假设各神经元的阈值分别是,j,，j=1,2,m，则各神经元的输出y,j, j=1,2,.,m分别为：,1. 前馈网络,单层前馈网络(2/3),其中，由所有连接权值w,ij,构成的连接权值矩阵W为：,在实际应用中，该矩阵是通过大量的训练示例学习而形成的。,20,多层前馈网络,是指那种除拥有输入、输出层外，还至少含有一个、或更多个隐含层的前馈网络。,隐含层是指由那些既不属于输入层又不属于输出层的神经元所构成的处理层,也被称为中间层。隐含层的作用是通过对输入层信号的加权处理，将其转移成更能被输出层接受的形式。,x,1,X,2,X,n,y,1,Y,m,隐含层,输出层,输入层,图4.9 多层前馈网络结构,权值,权值,1. 前馈网络,多层前馈网络(3/3),多层前馈网络的输入层的输出向量是第一隐含层的输入信号，而第一隐含层的输出则是第二隐含层的输入信号，以此类推，直到输出层。,多层前馈网络的典型代表是BP网络。,21,2. 反馈经网络,反馈网络是指允许采用反馈联结方式所形成的神经网络。所谓反馈联结方式是指一个神经元的输出可以被反馈至同层或前层的神经元。,反馈网络和前向网络不同：,前向网络,属于非循环连接模式，它的每个神经元的输入都没有包含该神经元先前的输出，因此不具有“短期记忆”的性质。,反馈网络,则不同，它的每个神经元的输入都有可能包含有该神经元先前输出的反馈信息，即一个神经元的输出是由该神经元当前的输入和先前的输出这两者来决定的，这就有点类似于人类的短期记忆的性质。,反馈网络的典型例子是后面将要介绍的Hopfield网络,22,人工神经网络模型,人工神经网络模型是指对网络结构、联结权值和学习能力的总括。常用的网络模型已有数十种。例如：,传统的感知机模型；具有误差反向传播功能的反向传播网络模型；采用多变量插值的径向基函数网络模型；建立在统计学习理论基础上的支撑向量机网络模型；采用反馈联接方式的反馈网络模型；基于模拟退火算法的随机网络模型。,重点讨论,1. 感知器（Perceptron）模型,2. 反向传播（BP）模型,3. 反馈网络（Hopfield）模型,4.2.3 人工神经网络的典型模型,23,感知器,是美国学者罗森勃拉特（Rosenblatt）于1957年为研究大脑的存储、学习和认知过程而提出的一类具有自学习能力的神经网络模型，其拓扑结构是一种分层前向网络。它包括：单层感知器和多层感知器。,单层感知器,是一种只具有单层可调节连接权值神经元的前向网络，这些神经元构成了单层感知器的输出层，是感知器的可计算节点。,在单层感知器中，每个可计算节点都是一个线性阈值神经元。当输入信息的加权和大于或等于阈值时，输出为1，否则输出为0或-1。,单层感知器的输出层的每个神经元都只有一个输出，且该输出仅与本神经元的输入及联接权值有关，而与其他神经元无关。,1. 感知器模型,单层 感知器(1/7),24,单层感知器的结构如下图,x,1,x,2,x,n,y,1,y,m,输入层,输出层,权值 w,i,j,输入向量为X=(x,1,x,2,x,n,)；,输出向量为Y=(y,1,y,2,y,m,)；,输入层各个输入到相应神经元的连接权值分别是w,ij,，i=1,2,.,n，j=1,2,., m。,若假设各神经元的阈值分别是,j,，j=1,2,m，则各神经元的输出y,j, j=1,2,.,m分别为,其中，由所有连接权值w,ji,构成的连接权值矩阵W为：,在实际应用中，该矩阵是通过大量的训练示例学习而形成的,1. 感知器模型,单层感知器(2/7),25,使用感知器的主要目的是为了对外部输入进行,分类,。,罗森勃拉特已经证明，如果外部输入是线性可分的（指存在一个超平面可以将它们分开），则单层感知器一定能够把它划分为两类。其判别超平面由如下判别式确定：,1.感知器模型,单层感知器(3/7),作为例子，下面讨论用单个感知器实现逻辑运算的问题。事实上，单层感知器可以很好地实现“与”、“或”、“非”运算，但却不能解决“异或”问题。,26,例4.1 “与”运算（x,1,x,2,）,(0,0),(1,1),(0,1),(1,0),图4.10 与运算问题图示,输入,输出,超平面,阈值条件,x,1,x,2,x,1,x,2,w,1,*x,1,+ w,2,* x,2,-=0,0,0,0,w,1,*0+ w,2,*0 -0,0,0,1,0,w,1,*0+ w,2,*1,-0,w,2,1,0,0,w,1,*1+ w,2,*0 -0,w,1,1,1,1,w,1,*1+ w,2,*1-0,w,1,+ w,2,可以证明此表有解，例如取w,1,=1，w,2,=1，=1.5，其分类结果如右图所示。,其中，输出为1的用实心圆，输出为0的用空心圆。后面约定相同。,1. 感知器模型,单层感知器(4/7),27,例4.2 “或”运算（x,1,x,2,）,输入,输出,超平面,阈值条件,x,1,x,2,x,1,x,2,w,1,*x,1,+ w,2,* x,2,-=0,0,0,0,w,1,*0+ w,2,*0 -0,0,0,1,1,w,1,*0+ w,2,*1,-0,w,2,1,0,1,w,1,*1+ w,2,*0 -0,w,1,1,1,1,w,1,*1+ w,2,*1-0,w,1,+ w,2,此表也有解，例如取w,1,=1，w,2,=1，=0.5，其分类结果如右图所示。,(,0,1),(0,0),(1,0),图4.11 或运算问题图示,(1,1),1. 感知器模型,单层感知器(5/7),28,例4.3 “非”运算（x,1,）,输入,输出,超平面,阈值条件,x,1,x,1,w,1,*x,1,-=0,0,1,w,1,*0 - 0,0,1,0,w,1,*1,w,1,此表也有解，例如取w,1,=-1，=-0.5，其分类结果如右图所示。,图4.12 非运算问题图示,0,1,1. 感知器模型,单层感知器(6/7),29,例4.4 “异或”运算（x,1,XOR x,2,）,输入,输出,超平面,阈值条件,x,1,x,2,x,1,XOR x,2,w,1,*x,1,+ w,2,* x,2,-=0,0,0,0,w,1,*0+ w,2,*0 -0,0,0,1,1,w,1,*0+ w,2,*,1,-0,w,2,1,0,1,w,1,*1+ w,2,*0 -0,w,1,1,1,0,w,1,*1+ w,2,*1-w,1,+ w,2,此表无解，即无法找到满足条件的w,1,、w,2,和，如右图所示。因为异或问题是一个非线性可分问题，需要用多层感知器来解决。,(0,1),(0,0),(1,0),图4.13 异或运算问题图示,(1,1),1. 感知器模型,单层感知器(77),30,(2) 多层感知器,多层感知器是通过在单层感知器的输入、输出层之间加入一层或多层处理单元所构成的。其拓扑结构与图5.9所示的多层前向网络相似，差别也在于其计算节点的连接权值是可变的。,多层感知器的输入与输出之间是一种高度非线性的映射关系，如图4.9所示的多层前向网络，若采用多层感知器模型，则该网络就是一个从n维欧氏空间到m维欧氏空间的非线性映射。因此，多层感知器可以实现非线性可分问题的分类。例如，对“异或”运算，用图4.14所示的多层感知器即可解决。,1. 感知器模型,多层 感知器(1/2),31,x,11,y=x,1,XOR x,2,x,1,X,2,x,12,1,-1,1,1,1,-1,输入层,隐层,输出层,权值,权值,图4.14 “异或”问题的多层感知器,阈值0.5,阈值-1.5,阈值1.5,(0,1),(0,0),(1,0),图4.15异或问题的解决,(1,1),在图4.14中，隐层神经元x,11,所确定的直线方程为,它可以识别一个半平面。隐层神经元x,12,所确定的直线方程为,它也可以识别一个半平面。,输出层神经元所确定的直线方程为,它相当于对隐层神经元x,11,和x,12,的输出作“逻辑与”运算，因此可识别由隐层已识别的两个半平面的交集所构成的一个凸多边形，如图4.15所示。,1. 感知器模型,多层 感知器(2/2),32,误差反向传播(Error Back Propagation)网络通常简称为BP(Back Propagation)网络，是由美国加州大学的鲁梅尔哈特和麦克莱兰在研究并行分布式信息处理方法，探索人类认知微结构的过程中，于1985年提出的一种网络模型。,BP网络的网络拓扑结构是多层前向网络，如图4.16所示。在BP网络中，同层节点之间不存在相互连接，层与层之间多采用全互连方式，且各层的连接权值可调。BP网络实现了明斯基的多层网络的设想，是当今神经网络模型中使用最广泛的一种。,y,1,y,2,y,m,x,1,x,2,x,n,输出层,隐含层,输入层,权可调,权可调,图4.16 一个多层BP网络的结构,2. BP网络模型,模型结构,33,对BP网络需说明以下两点：,第一，,BP网络的每个处理单元均为非线性输入/输出关系，其作用函数通常采用的是可微的Sigmoid函数，如：,2. BP网络模型,模型说明,第二，,BP网络的学习过程是由工作信号的正向传播和误差信号的反向传播组成的。所谓正向传播，是指输入模式经隐层到输出层，最后形成输出模式；所谓误差反向传播，是指从输出层开始逐层将误差传到输入层，并修改各层联接权值，使误差信号为最小的过程,。,34,Hopfield网络是由美国加州工学院物理学家霍普菲尔特1982年提出来的一种单层全互连的对称反馈网络模型。它可分为离散Hopfield网络和连续Hopfield网络，限于篇幅，本书重点讨论离散Hopfield网络。,离散Hopfield网络的结构,离散Hopfield网络是在非线性动力学的基础上由若干基本神经元构成的一种单层全互连网络，其任意神经元之间均有连接，并且是一种对称连接结构。一个典型的离散 Hopfidld网络结构如图4-17所示。离散Hopfield网络模型是一个离散时间系统，每个神经元只有0和1（或-1和1）两种状态，任意神经元i和j之间的连接权值为wij。由于神经元之间为对称连接，且神经元自身无连接，因此有,3. Hopfield网络模型,离散,Hopfield,网络模型(1/2),由该连接权值所构成的连接矩阵是一个零对角的对称矩阵。,35,图 417 离散Hopfield网络的结构,y,m,Y,2,Y,1,x,1,x,2,x,n,输入层,输出层,在 Hopfidld网络中，虽然神经元自身无连接，但由于每个神经元都与其他神经元相连，即每个神经元的输出都将通过突触连接权值传递给别的神经元，同时每个神经元又都接受其他神经元传来的信息，这样对每个神经元来说，其输出经过其他神经元后又有可能反馈给自己，因此Hopfidld网络是一种反馈神经网络,3.,Hopfield网络模型,离散,Hopfield,网络模型(2/2),36,4.1 概述,4.2 神经计算,4.3 进化计算,4.3.1 进化计算概述,4.3.2 遗传算法,4.4 模糊计算,4.5 粗糙集,第4章 计算智能,37,进化计算（Evolutionary Computation,EC）是在达尔文（Darwin）的进化论和孟德尔（Mendel）的遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制的问题求解技术。它主要包括,遗传算法（Genetic Algorithm，GA）,进化策略（Evolutionary Strategy,ES）,进化规划（Evolutionary Programming,EP）,遗传规划（Genetic Programming,GP）四大分支。,其中，第一个分支是进化计算中最初形成的一种具有普遍影响的模拟进化优化算法。因此我们主要讨论遗传算法。,4.3 进化计算,38,进化计算是一种模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。它以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的,繁殖（Reproduction）,变异（Mutation）,竞争（Competition）,选择（Selection）,引入到了算法中。,4.3.1 进化计算概述,1. 进化计算及其生物学基础(1/3),(,1) 什么是进化计算,39,(2) 进化计算的生物学基础,自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。, 遗传理论,遗传,是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象。正是由于遗传的作用，自然界才能有稳定的物种。,在自然界，构成生物基本结构与功能的单位是,细胞,（Cell）。,细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为,染色体,（Chromosome）。,在染色体中，遗传信息由,基因,（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。,染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做,脱氧核糖核酸(DNA),，每个基因都在DNA长链中占有一定的位置。,一个细胞中的所有染色体所携带的遗传信息的全体称为一个,基因组,(Genome)。,细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。,4.3.1 进化计算概述,1. 进化计算及其生物学基础(2/3),40, 变异理论,变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是一种随机、不可逆现象，是生物多样性的基础。,引起变异的主要原因：,杂交，,是指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组，即两个染色体在某一相同处的DNA被切断后再进行交配重组，形成两个新的染色体。,复制差错，,是指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体。, 进化论,进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。,达尔文的自然选择学说：,在生物进化中，一种基因有可能发生变异而产生出另一种新的基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。通常，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。,4.3.1 进化计算概述,1. 进化计算及其生物学基础(3/3),41,进化计算自20世纪50年代以来，其发展过程大致可分为三个阶段。,(1) 萌芽阶段,这一阶段是从20世纪50年代后期到70年代中期。20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了,遗传算法,的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的,进化策略,。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的,进化规划,。1969年美国密执安（Michigan）大学的霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的,三大分支基本形成,。,(2) 成长阶段,这一阶段是从20世纪70年代中期到80年代后期。1975年，霍兰德出版专著自然和人工系统的适应性（Adaptation in Natural and Artificial System），全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著遗传算法-搜索、优化及机器学习（Genetic Algorithm-in Search Optimization and Machine Learning），使遗传算法得到了普及与推广。,4.3.1 进化计算概述,2. 进化计算的产生与发展(1/2),42,(3) 发展阶段,这一阶段是从20世纪90年代至今。1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著遗传规划-应用自然选择法则的计算机程序设计（Genetic Programming :on the Programming of Computer by Means of Natural Selection）该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。,进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。目前，进化计算已成为人工智能领域的又一个新的研究热点。,4.3.1 进化计算概述,2. 进化计算的产生与发展(2/2),43,进化计算尽管有多个重要分支，并且不同分支的编码方案、选择策略和进化操作也有可能不同，但它们却有着共同的进化框架。若假设P为种群(Population，或称为群体)，t为进化代数， P(t)为第t代种群 , 则进化计算的基本结构可粗略描述如下：, 确定编码形式并生成搜索空间；,初始化各个进化参数，并设置进化代数t=0；,初始化种群P(0);,对初始种群进行评价（即适应度计算）；,while（不满足终止条件）do,t=t+1;,利用选择操作从P(t-1)代中选出P(t)代群体；,对P(t)代种群执行进化操作；,对执行完进化操作后的种群进行评价（即适应度计算）；,可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。,4.3.1 进化计算概述,3. 进化计算的基本结构,44,遗传算法的基本思想是从初始种群出发，采用优胜劣汰、适者生存的自然法则选择个体，并通过杂交、变异来产生新一代种群，如此逐代进化，直到满足目标为止。遗传算法所涉及到的基本概念主要有以下几个：,种群,（,Population,）：种群是指用遗传算法求解问题时，初始给定的多个解的集合。遗传算法的求解过程是从这个子集开始的。,个体,（Individual）：个体是指种群中的单个元素，它通常由一个用于描述其基本遗传结构的数据结构来表示。例如，可以用0、1组成的长度为l的串来表示个体。,染色体,（Chromos）：染色体是指对个体进行编码后所得到的编码串。染色体中的每1位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。,适应度（Fitness）函数,：适应度函数是一种用来对种群中各个个体的环境适应性进行度量的函数。其函数值是遗传算法实现优胜劣汰的主要依据,遗传操作,（Genetic Operator）：遗传操作是指作用于种群而产生新的种群的操作。,标准的遗传操作包括以下3种基本形式：,选择,（Selection）,交叉,（Crosssover）,变异,（Mutation）,4.3.2 遗传算法,1. 遗传算法的基本概念,45,遗传算法主要由染色体编码、初始种群设定、适应度函数设定、遗传操作设计等几大部分所组成，其算法主要内容和基本步骤可描述如下：,(1) 选择编码策略，将问题搜索空间中每个可能的点用相应的编码策略表示出来，即形成染色体；,(2) 定义遗传策略，包括种群规模N，交叉、变异方法，以及选择概率P,r,、交叉概率P,c,、变异概率P,m,等遗传参数；,(3) 令t=0，随机选择N个染色体初始化种群P(0)；,(4) 定义适应度函数f（f0）；,(5) 计算P(t)中每个染色体的适应值；,(6) t=t+1；,(7) 运用选择算子，从P(t-1)中得到P(t)；,(8) 对P(t)中的每个染色体，按概率P,c,参与交叉；,(9) 对染色体中的基因，以概率P,m,参与变异运算；,(10) 判断群体性能是否满足预先设定的终止标准，若不满足则返回(5)。,4.3.2 遗传算法,2. 遗传算法的基本过程(1/2),46,计算种群中各个个体的适应度，并进行评价,满足终止条件吗？,终止,选择,交叉,变异,Y,图4-18 基本遗传算法的算法流程图,编码和生成初始种群,N,选择,其算法流程如图4-18所示。,45.3.2 遗传算法,2. 遗传算法的基本结构(2/2),47,常用的遗传编码算法有霍兰德二进制码、格雷码（Gray Code）、实数编码和字符编码等。,(1)二进制编码（Binary encoding）,二进制编码是将原问题的结构变换为染色体的位串结构。在二进制编码中，首先要确定二进制字符串的长度l，该长度与变量的定义域和所求问题的计算精度有关。,例5.5,假设变量x的定义域为5，10，要求的计算精度为10,-5,，则需要将5，10至少分为600000个等长小区间，每个小区间用一个二进制串表示。于是，串长至少等于20，原因是：,524288=2,19,6000002,20,=1048576,这样，对应于区间5，10内满足精度要求的每个值x，都可用一个20位编码的二进制串来表示。,二进制编码存在的主要缺点,是汉明（Hamming）悬崖。,例如，7和8的二进制数分别为0111和1000，当算法从7改进到8时，就必须改变所有的位。,4.3.2 遗传算法,3. 遗传编码(1/3),48,4.3.2 遗传算法,3. 遗传编码(2/3),(2) 格雷编码（Gray encoding）,格雷编码是对二进制编码进行变换后所得到的一种编码方法。这种编码方法要求两个连续整数的编码之间只能有一个码位不同，其余码位都是完全相同的。它有效地解决了汉明悬崖问题，其基本原理如下：,设有二进制串b,1,b,2,b,n,，对应的格雷串为a,1,a,2,a,n,，则从二进制编码到格雷编码的变换为：,(4.9),其中，表示模2加法。而从一个格雷串到二进制串的变换为：,(4.10),例4.6,十进制数7和8的二进制编码分别为0111和1000，而其格雷编码分别为0100和1100。,49,(3) 实数编码（Real encoding）,实数编码是将每个个体的染色体都用某一范围的一个实数（浮点数）来表示，其编码长度等于该问题变量的个数。,这种编码方法是将问题的解空间映射到实数空间上，然后在实数空间上进行遗传操作。由于实数编码使用的是变量的真实值，因此这种编码方法也叫做真值编码方法。,实数编码适应于那种多维、高精度要求的连续函数优化问题。,4.3.2 遗传算法,3. 遗传编码(3/3),50,适应度函数是一个用于对个体的适应性进行度量的函数。通常，一个个体的适应度值越大，它被遗传到下一代种群中的概率也就越大。,(1) 常用的适应度函数,在遗传算法中，有许多计算适应度的方法，其中最常用的适应度函数有以下两种：, 原始适应度函数,它是直接将待求解问题的目标函数f(x)定义为遗传算法的适应度函数。例如，在求解极值问题,时，f(x)即为x的原始适应度函数。,采用原始适应度函数的,优点,是能够直接反映出待求解问题的最初求解目标，其,缺点,是有可能出现适应度值为负的情况。,4.3.2 遗传算法,4. 适应度函数(1/5),51, 标准适应度函数,在遗传算法中，一般要求适应度函数非负，并其适应度值越大越好。这就往往需要对原始适应函数进行某种变换，将其转换为标准的度量方式，以满足进化操作的要求，这样所得到的适应度函数被称为标准适应度函数f,Normal,(x)。例如下面的极小化和极大化问题：,极小化问题,对极小化问题，其标准适应度函数可定义为,(4.11),其中，f,max,(x),是原始适应函数,f(x),的一个上界。如果f,max,(x),未知，则可用当前代或到目前为止各演化代中的,f(x),的最大值来代替。可见， f,max,(x),是会随着进化代数的增加而不断变化的。,4.3.2 遗传算法,4. 适应度函数(2/5),52,极大化问题,对极大化问题，其标准适应度函数可定义为,(4.12),其中，f,min,(x),是原始适应函数,f(x),的一个下界。如果f,min,(x),未知，则可用当前代或到目前为止各演化代中的,f(x),的最小值来代替。,4.3.2 遗传算法,4. 适应度函数(3/5),53,(2),适应度函数的加速变换,在某些情况下，适应度函数在极值附近的变化可能会非常小，以至于不同个体的适应值非常接近，使得难以区分出哪个染色体更占优势。对此，最好能定义新的适应度函数，使该适应度函数既与问题的目标函数具有相同的变化趋势，又有更快的变化速度。,适应度函数的加速变换有两种基本方法,线性加速,的适应度函数的定义如下：,f(x)=f(x)+,其中，,f(x),是加速转换前的适应度函数；,f(x),是加速转换后的适应度函数；,和,是转换系数,它们应满足如下条件：, 变化后得到的新的适应度函数平均值要等于原适应度函数的平均值。即,（,4.13,）,其中，x,i,(i=1,n)为当前代中的染色体。,4.3.2 遗传算法,4. 适应度函数(4/5),54, 变换后所得到的新的种群个体所具有的最大适应度要等于其平均适应度的指数倍数。即有关系：,（,4.14,）,式中，,x,i,(i=1,n),为当前代中的染色体，,M,是指将当前的最大适应度放大为平均值的,M,倍。目的是通过,M,拉开不同染色体适应度值的差距。,非线性加速,幂函数变换方法,f(x)=f(x),k,(4.15),指数变换方法,f(x)=exp(-f(x) (4.16),4.3.2 遗传算法,4. 适应度函数(5/5),55,遗传算法中的基本遗传操作包括选择、交叉和变异3种，而每种操作又包括多种不同的方法，下面分别对它们进行介绍。,(1). 选择操作,选择（Selection）操作是指根据选择概率按某种策略从当前种群中挑选出一定数目的个体，使它们能够有更多的机会被遗传到下一代中。,常用的选择策略可分为比例选择、排序选择和竞技选择三种类型。, 比例选择,比例选择方法（Proportional Model）的基本思想是：各个个体被选中的概率与其适应度大小成正比。,常用的比例选择策略包括,轮盘赌选择,繁殖池选择,4.3.2 遗传算法,5. 基本遗传操作(1/11),56,轮盘赌选择,轮盘赌选择法又被称为转盘赌选择法或轮盘选择法。在这种方法中，个体被选中的概率取决于该个体的相对适应度。而相对适应度的定义为：,其中，P(x,i,)是个体x,i,的相对适应度，即个体x,i,被选中的概率；f(x,i,)是个体x,i,的原始适应度；是种群的累加适应度。,轮盘赌选择算法的基本思想是：根据每个个体的选择概率P(x,i,)将一个圆盘分成N个扇区，其中第i个扇区的中心角为：,再设立一个移动指针，将圆盘的转动等价为指针的移动。选择时，假想转动圆盘，若静止时指针指向第i个扇区，则选择个体i。其物理意义如图5-19所示。,4.3.2 遗传算法,5. 基本遗传操作,(2/11),57,P(x,1,),P(x,2,),P(x,N,),P(x,i,),2,p(x,i,),图4-19 轮盘赌选择,从统计角度看，个体的适应度值越大，其对应的扇区的面积越大，被选中的可能性也越大。这种方法有点类似于发放奖品使用的轮盘，并带有某种赌博的意思，因此亦被称为轮盘赌选择。,4.3.2 遗传算法,5. 基本遗传操作(3/11),58,(2)交叉操作,交叉（Crossover）操作是指按照某种方式对选择的父代个体的染色体的部分基因进行交配重组，从而形成新的个体。交配重组是自然界中生物遗传进化的一个主要环节，也是遗传算法中产生新的个体的最主要方法。根据个体编码方法的不同，遗传算法中的交叉操作可分为二进制交叉和实值交叉两种类型,。,二进制交叉,二进制交叉（Binary Valued Crossover）是指二进制编码情况下所采用的交叉操作，它主要包括,单点交叉、两点交叉、多点交叉和均匀交叉,等方法。,4.3.2 遗传算法,5. 基本遗传操作(4/11),59,单点交叉,单点交叉也称简单交叉，它是先在两个父代个体的编码串中随机设定一个交叉点，然后对这两个父代个体交叉点前面或后面部分的基因进行交换，并生成子代中的两个新的个体。假设两个父代的个体串分别是：,X=x,1,x,2, x,k,x,k+1, x,n,Y=y,1,y,2, y,k,y,k+1, y,n,随机选择第k位为交叉点，若采用对交叉点后面的基因进行交换的方法，但点交叉是将X中的x,k+1,到x,n,部分与Y中的y,k+1,到y,n,部分进行交叉，交叉后生成的两个新的个体是：,X= x,1,x,2, x,k,y,k+1, y,n,Y= y,1,y,2, y,k,x,k+1,x,n,例,4.7,设有两个父代的个体串,A=0 0 1 1,0 1,和,B=1 1 0 0,1 0,，若随机交叉点为,4,，则交叉后生成的两个新的个体是：,A= 0 0 1 1,1 0,B= 1 1 0 0,0 1,4.3.2 遗传算法,5. 基本遗传操作(5/11),60,两点交叉,两点交叉是指先在两个父代个体的编码串中随机设定两个交叉点，然后再按这两个交叉点进行部分基因交换，生成子代中的两个新的个体。,假设两个父代的个体串分别是：,X=x,1,x,2, x,i, x,j, x,n,Y=y,1,y,2, y,i, y,j,y,n,随机设定第i、j位为两个交叉点（其中ijn），两点交叉是将X中的x,i+1,到x,j,部分与Y中的y,i+1,到y,j,部分进行交换，交叉后生成的两个新的个体是：,X= x,1,x,2, x,i,y,i+1,y,j,x,j+1, x,n,Y= y,1,y,2, y,i,x,i+1,x,j,y,j+1, y,n,例,4.8,设有两个父代的个体串,A= 0 0 1,1 0,1,和,B= 1 1 0,0 1,0,，若随机交叉点为,3,和,5,，则交叉后的两个新的个体是：,A= 0 0 1,0 1,1,B= 1 1 0,1 0,0,4.3.2 遗传算法,5. 基本遗传操作(6/11),61,多点交叉,多点交是指先随机生成多个交叉点，然后再按这些交叉点分段地进行部分基因交换，生成子代中的两个新的个体。,假设交叉点个数为m，则可将个体串划分为m+1个分段，其划分方法是：,当m为偶数时，对全部交叉点依次进行两两配对，构成m/2个交叉段。,当m为奇数时，对前(m-1)个交叉点依次进行两两配对，构成(m-1)/2个交叉段，而第m个交叉点则按单点交叉方法构成一个交叉段。,下面以m=3为例进行讨论。假设两个父代的个体串分别是,X=x,1,x,2, x,i, x,j, x,k, x,n,和,Y=y,1,y,2, y,i, y,j, y,k, y,n,，,随机设定第i、j、k位为三个交叉点（其中ijkn），则将构成两个交叉段。交叉后生成的两个新的个体是：,X= x,1,x,2, x,i,y,i+1, y,j,x,j+1, x,k,y,k+1, y,n,Y= y,1,y,2, y,i,x,i+1, x,j,y,j+1, y,k,x,k+1, x,n,例,4.9,设有两个父代的个体串,A= 0 0 1 1 0 1,和,B= 1 1 0 0 1 0,，若随机交叉点为,1,、,3,和,5,，则交叉后的两个新的个体是：,A= 0,1 0,1 0,0,B= 1,0 1,0 1,1,4.3.2 遗传算法,5. 基本遗传操作(7/11),62,均匀交叉,均匀交叉（Uniform Crossover）是先随机生成一个与父串具有相同长度，并被称为交叉模版（或交叉掩码）的二进制串，然后再利用该模版对两个父串进行交叉，即将模版中,1对应的位进行交换,，而0对应的位不交换，依此生成子代中的两个新的个体。事实上，这种方法对父串中的每一位都是以相同的概率随机进行交叉的。,例,4.10,设有两个父代的个体串,A=001101,和,B=110010,，若随机生成的,模版,T=010011,，则交叉后的两个新的个体是,A=011010,和,B=100101,。即,A： 0 0 1 1 0 1,B： 1 1 0 0 1 0,T： 0 1 0 0 1 1,A：0,1,1 1,1,0,B：1,0,0 0,0,1,4.3.2 遗传算法,5. 基本遗传操作(8/11),63,实值交叉,实值交叉是在实数编码情况下所采用的交叉操作，主要包括离散交叉和算术交叉，下面主要讨论离散交叉（部分离散交叉和整体离散交叉） 。,部分离散交叉,是先在两个父代个体的编码向量中随机选择一部分分量，然后对这部分分量进行交换，生成子代中的两个新的个体。,整体交叉,则是对两个父代个体的编码向量中的所有分量，都以1/2的概率进行交换，从而生成子代中的两个新的个体。,以部分离散交叉为例，,假设两个父代个体的n维实向量分别是 X=x,1,x,2, x,i,x,k,x,n,和Y=y,1,y,2,y,i,y,k,y,n,，若随机选择对,第k个分量,以后的所有分量进行交换，则生成的两个新的个体向量是：,X= x,1,x,2, x,k,y,k+1,y,n,Y= y,1,y,2, y,k,x,k+1,x,n,例,4.11,设有两个父代个体向量,A=20 16 19 32 18 26,和,B=36 25 38 12 21 30,，若随机选择对,第,3,个分量,以后的所有分量进行交叉，则交叉后两个新的个体向量是：,A= 20 16 19,12,21,30,B= 36 25 38,32,18,26,4.3.2 遗传算法,5. 基本遗传操作(9/11),64,(3) 变异操作,变异（Mutation）是指对选中个体的染色体中的某些基因进行变动，以形成新的个体。变异也是生物遗传和自然进化中的一种基本现象，它可增强种群的多样性。遗传算法中的变异操作增加了算法的局部随机搜索能力，从而可以维持种群的多样性。根据个体编码方式的不同，变异操作可分为二进制变异和实值变异两种类型。, 二进制变异,当个体的染色体采用二进制编码表示时，其变异操作应采用二进制变异方法。该变异方法是先随机地产生一个变异位，然后将该变异位置上的基因值由“0”变为“1”，或由“1”变为“0”，产生一个新的个体。,例4.12,设变异前的个体为A=,0 0 1 1 0 1,，若随机产生的变异,位置是,2,，则该个体的第,2,位由“,0”,变为“,1”,。,变异后的新的个体是,A= 0,1,1 1 0 1,。,4.3.2 遗传算法,5. 基本遗传操作(10/11),65,实值变异,当个体的染色体采用实数编码表示时，其变异操作应采用实值变异方法。该方法是用另外一个在规定范围内的随机实数去替换原变异位置上的基因值，产生一个新的个体。最常用的实值变异操作有:,基于位置的变异方法,该方法是先随机地产生两个变异位置，然后将第二个变异位置上的基因移动到第一个变异位置的前面。,例,4.13,设选中的个体向量,C=20 16 19 12 21 30,，若随机产生的两个变异位置分别时,2,和,4