计算智能概述

第5章计算智能计算智能是信息科学、生命科学、认知科学等不同学科相互交叉的产物。它主要借鉴仿生学的思想，基于人们对生物体智能机理的认识，采用数值计算的方法去模拟和实现人类的智能。计算智能的主要研究领域包括：神经计算、进化计算、模糊计算、免疫计算、DNA计算和人工生命等。本章主要讨论神经计算、进化计算和模糊计算问题。

5.1概述5.2神经计算5.3进化计算5.4模糊计算15.1概述

5.1.1什么是计算智能5.1.2计算智能的产生与发展5.1.3计算智能与人工智能的关系25.1.1什么是计算智能计算智能（ComputationalIntelligence，CI）目前还没有一个统一的的定义，使用较多的是美国科学家贝慈德克（J.C.Bezdek）从计算智能系统角度所给出的定义:如果一个系统仅处理低层的数值数据，含有模式识别部件，没有使用人工智能意义上的知识，且具有计算适应性、计算容错力、接近人的计算速度和近似于人的误差率这4个特性，则它是计算智能的。从学科范畴看，计算智能是在神经网络（NeuralNetworks,NN）、进化计算（EvolutionaryComputation,EC）及模糊系统（FuzzySystem,FS）这3个领域发展相对成熟的基础上形成的一个统一的学科概念。

3

神经网络是一种对人类智能的结构模拟方法，它是通过对大量人工神经元的广泛并行互联，构造人工神经网络系统去模拟生物神经系统的智能机理的。进化计算是一种对人类智能的演化模拟方法，它是通过对生物遗传和演化过程的认识，用进化算法去模拟人类智能的进化规律的。模糊计算是一种对人类智能的逻辑模拟方法，它是通过对人类处理模糊现象的认知能力的认识，用模糊逻辑去模拟人类的智能行为的。从贝慈德克对计算智能的定义和上述计算智能学科范畴的分析，可以看出以下2点：第一，计算智能是借鉴仿生学的思想，基于生物神经系统的结构、进化和认知对自然智能进行模拟的。第二，计算智能是一种以模型（计算模型、数学模型）为基础，以分布、并行计算为特征的自然智能模拟方法。

45.1.2计算智能的产生与发展

1992年，贝慈德克在《ApproximateReasoning》学报上首次提出了“计算智能”的概念。1994年6月底到7月初，IEEE在美国佛罗里达州的奥兰多市召开了首届国际计算智能大会(简称WCCI’94)。会议第一次将神经网络、进化计算和模糊系统这三个领域合并在一起，形成了“计算智能”这个统一的学科范畴。在此之后，WCCI大会就成了IEEE的一个系列性学术会议，每4年举办一次。1998年5月，在美国阿拉斯加州的安克雷奇市又召开了第2届计算智能国际会议WCCI’98。2002年5月，I在美国州夏威夷州首府火奴鲁鲁市又召开了第3届计算智能国际会议WCCI’02。此外，IEEE还出版了一些与计算智能有关的刊物。目前，计算智能的发展得到了国内外众多的学术组织和研究机构的高度重视，并已成为智能科学技术一个重要的研究领域。55.1.3计算智能与人工智能的关系目前，对计算智能与人工智能的关系有2种不同观点，一种点认为计算智能是人工智能的一个子集，另一种观点认为计算智能和人工智能是不同的范畴。第一种观点的代表人物是贝慈德克。他把智能（Intelligence，I）和神经网络（NeuralNetwork，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，即计算智能是人工智能的一个子集。6CNNCPRCIANNAPRAIBNNBPRBI人类知识(+)传感输入知识(+)传感数据计算(+)传感器B~生物的A~符号的C~数值的复杂性复杂性输入层次贝慈德克的智能的3个层次7第二种观点是大多数学者所持有的观点，其代表人物是艾伯哈特（R.C.Eberhart）。他们认为：虽然人工智能与计算智能之间有重合，但计算智能是一个全新的学科领域，无论是生物智能还是机器智能，计算智能都是其最核心的部分，而人工智能则是外层。事实上，CI和传统的AI只是智能的两个不同层次，各自都有自身的优势和局限性，相互之间只应该互补，而不能取代。大量实践证明，只有把AI和CI很好地结合起来，才能更好地模拟人类智能，才是智能科学技术发展的正确方向。85.2神经计算神经计算或叫神经网络，是计算智能的重要基础和核心，也是计算智能乃至智能科学技术的一个重要研究领域。本节的主要内容包括：5.1.1神经计算基础5.1.2人工神经网络的互连结构5.1.3人工神经网络的典型模型至于基于神经网络的连接学习机制放到第7章学习部分讨论。95.2.1神经计算基础1.生物神经系统简介生物神经系统是人工神经网络的基础。人工神经网络是对人脑神经系统的简化、抽象和模拟，具有人脑功能的许多基本特征。为方便对神经网络的进一步讨论，下面先介绍：(1)生物神经元的结构(2)生物神经元的功能(3)人脑神经系统的联结机制10(1)生生物神神经元的的结构神经末梢梢突触轴突树突细胞核细胞体它由细胞胞体(Soma)、轴轴突(Axon)和树树突(Dendrite)三三个主要要部分组组成细胞体由细胞核核、细胞胞质和细细胞膜等等组成，，其直径径大约为为0.5-100μm大小不不等。细细胞体是是神经元元的主体体，用于于处理由由树突接接受的其其它神经经元传来来的信号号,其内内部是细细胞核，，外部是是细胞膜膜，细胞胞膜的外外面是许许多向外外延伸出出的纤维维。11轴突是由细胞胞体向外外延伸出出的所有有纤维中中最长的的一条分分枝，用用来向外外传递神神经元产产生的输输出电信信号。每个神经经元都有有一条轴轴突，其其最大长长度可达达1m以以上。在在轴突的的末端形形成了许许多很细细的分枝枝，这些些分支叫叫神经末末梢。每一条神神经末梢梢可以与与其它神神经元形形成功能能性接触触，该接接触部位位称为突突触。所所谓功能能性接触触，是指指非永久久性的接接触，这这正是神神经元之之间传递递信息的的奥秘之之处树突是指由细细胞体向向外延伸伸的除轴轴突以外外的其它它所有分分支。树树突的长长度一般般较短，，但数量量很多，，它是神神经元的的输入端端，用于于接受从从其它神神经元的的突触传传来的信信号。12(2)生生物神神经元的的功能根据神经经生理学学的研究究，生物物神经元元的2个个主要功功能是:神经元元的兴奋奋与抑制制，神经经元内神神经冲动动的传导导。①神经经元的抑抑制与兴兴奋抑制状态态是指神神经元在在没有产产生冲动动时的工工作状态态。兴奋状态态是指神神经元产产生冲动动时的工工作状态态。通常情况况下，神神经元膜膜电位约约为-70毫毫伏，膜膜内为负负，膜外外为正，，处于抑抑制状态态。当神神经元受受到外部部刺激时时，其膜膜电位随随之发生生变化，，即膜内内电位上上升、膜膜外电位位下降，，当膜内内外的电电位差大大于阈值值电位（（约+40毫伏伏）时，，神经元元产生冲冲动而进进入兴奋奋状态。。说明:神经元每每次冲动动的持续续时间大大约1毫毫秒左右右，在此此期间即即使刺激激强度再再增加也也不会引引起冲动动强度的的增加。。神经元每每次冲动动结束后后，都会会重新回回到抑制制状态。。如果神经经元受到到的刺激激作用不不能使细细胞膜内内外的电电位差大大于阈值值电位，，则神经经元不会会产生冲冲动，将将仍处于于抑制状状态。②神经经元内神神经冲动动的传导导神经冲动动在神经经元内的的传导是是一种电电传导过过程，神神经冲动动沿神经经纤维传传导的速速度却在在3.2---320km/s之间间，且其其传导速速度与纤纤维的粗粗细、髓髓鞘的有有无有一一定关系系。一般般来说，，有髓鞘鞘的纤维维的传导导速度较较快，而而无髓鞘鞘的纤维维的传导导速度较较慢。13(3)人人脑神神经系统统的联结结机制①人脑脑神经系系统的联联结规模模人脑大约约由1011--1012个神经元元所组成成，其中中每个神神经元大大约有3＊104个突触。。小脑中的的每个神神经元大大约有105个突触，，并且每每个突触触都可以以与别的的神经元元的一个个树突相相连。人脑神经经系统就就是由这这些巨量量的生物物神经元元经广泛泛并行互互连所形形成的一一个高度度并行性性、非常常复杂的的神经网网络系统统。②人脑脑神经系系统的分分布功能能人脑神经经系的记记忆和处处理功能能是有机机的结合合在一起起的，每每个神经经元既具具有存储储功能，，同时又又具有处处理能力力。从结构上上看，人人脑神经经系统又又是一种种分布式式系统统统。人们们通过对对脑损坏坏病人所所做的神神经生理理学研究究，没有有发现大大脑中的的哪一部部分可以以决定其其余所有有各部分分的活动动，也没没有发现现在大脑脑中存在在有用于于驱动和和管理整整个智能能处理过过程的任任何中央央控制部部分。即，人类大脑脑的各个部分分是协同工作作、相互影响响的。在大脑脑中，不仅知知识的存储是是分散的，而而且其控制和和决策也是分分散的。14人工神经网络络是由大量的的人工神经元元经广泛互联联所形成的一一种人工网络络系统，用以以模拟人类神神经系统的结结构和功能。。(1)人工工神经元的结结构(2)常用用的人工神经经元模型神神经计算基基础2.人工神神经网络简介介15人工神经元的的结构θ…x1x2xnw1w2wny人工神经元是是对生物神经经元的抽象与与模拟下图是一个MP神经元模模型1943年，，心理学家麦麦克洛奇(W.McMulloch)和数数理逻辑学家家皮茨(W.Pitts)根据生物物神经元的功功能和结构，，提出了一个个将神经元看看作二进制阈阈值元件的简简单模型，即即MP模型。。图中的x1,x2,…,xn表示某一神经经元的n个输输入；wi表示第i个输输入的连接强强度，称为连连接权值；θθ为神经元的的阈值；y为为神经元的输输出。可见，，人工神经元元是一个具有有多输入，单单输出的非线线性器件。其其输入为,输出为其中，f称为为神经元功能能函数（或作作用函数，激激活函数）。。16常用的人工神神经元模型根据功能函数数的不同，可可得到不同的的神经元模型型。常用模型型包括：阈值型(Threshold)θf(θ)1这种模型的神神经元没有内内部状态，作作用函数f是是一个阶跃函函数，他表示示激活值σ和和输出之间的的关系。这是一种连续续的神经元模模型，其输入入输出特性常常用指数、对对数或双曲正正切等S型函函数表示。它它反映的是神神经元的饱和和特性.分段线性强饱饱和型(LinearSaturation)S型(Sibmoid)子阈累积型(SubthresholdSummation)也是一个非线线性函数，当当产生的激活活值超过T值值时，该神经经元被激活产产生个反响。。在线性范围围内，系统的的反响是线性性的。T1这种模型又称称为伪线性，，其输入/输输出之间在一一定范围内满满足线性关系系，一直延续续到输出为最最大值1为止止。但当达到到最大值后，，输出就不再再增。17人人工神经网网络的互联结结构人工神经网络络的互连结构构（或称拓扑扑结构）是指指单个神经元元之间的连接接模式，它是是构造神经网网络的基础，，也是神经网网络诱发偏差差的主要来源源。从互连结结构的角度：：前馈网络反馈网络单层前馈网络络多层前馈网络络单层反馈网络络多层反馈网络络仅含输入层和和输出层，且且只有输出层层的神经元是是可计算节点点除拥有输入、、输出层外，，还至少含有有一个、或更更多个隐含层层的前向网络络指不拥有隐含含层的反馈网网络指拥有隐含层层的反馈网络络可含有反馈联联结只包含前向联联结18包括单层前馈馈网络和多层层前馈网络。。单层前馈网络络是指那种只只拥有单层计计算节点的前前向网络。它它仅含有输入入层和输出层层，且只有输输出层的神经经元是可计算算节点，如下下图所示其中，输入向向量为X=(x1,x2,…,xn)；输出向量量为Y=(y1,y2,…,ym)；输入层各各个输入到相相应神经元的的连接权值分分别是wij，i=1,2,..,n，j=1,2,..,m。……x1X2X3xny1Y2ym权值wij输出层输入层图5.8单层前馈网络结构人人工神经网网络的互联结结构1.前馈馈网络(1/3)19若假设各神经经元的阈值分分别是θj，j=1,2,…,m，，则各神经元元的输出yj,j=1,2,..,m分别为：：其中，由所有有连接权值wij构成的连接权权值矩阵W为为：在实际应用中中，该矩阵是是通过大量的的训练示例学学习而形成的的。人人工神经网网络的互联结结构1.前馈馈网络(2/3)20多层前馈网络络是指那种除除拥有输入、、输出层外，，还至少含有有一个、或更更多个隐含层层的前馈网络络。隐含层是指由由那些既不属属于输入层又又不属于输出出层的神经元元所构成的处处理层,也被被称为中间层层。隐含层的的作用是通过过对输入层信信号的加权处处理，将其转转移成更能被被输出层接受受的形式。多层前馈网络络的输入层的的输出向量是是第一隐含层层的输入信号号，而第一隐隐含层的输出出则是第二隐隐含层的输入入信号，以此此类推，直到到输出层。多层前馈网络络的典型代表表是BP网络络。x1X2Xny1Ym隐含层输出层输入层图5.9多层前馈网络结构………权值权值人人工神经网网络的互联结结构1.前馈馈网络(3/3)21人人工神经网网络的互联结结构2.反馈网网络反馈网络是指指允许采用反反馈联结方式式所形成的神神经网络。所所谓反馈联结结方式是指一一个神经元的的输出可以被被反馈至同层层或前层的神神经元。反馈网络和前前向网络不同同：前向网络属于非循环连连接模式，它它的每个神经经元的输入都都没有包含该该神经元先前前的输出，因因此不具有““短期记忆””的性质。反馈网络则不同，它的的每个神经元元的输入都有有可能包含有有该神经元先先前输出的反反馈信息，即即一个神经元元的输出是由由该神经元当当前的输入和和先前的输出出这两者来决决定的，这就就有点类似于于人类的短期期记忆的性质质。反馈网络的典典型例子是后后面将要介绍绍的Hopfield网网络22人工神经网络络的模型是指指对网络结构构、联结权值值和学习能力力的总括。常用的网络模模型已有数十十种。例如：：传统的感知机机模型，具有误差反向向传播功能的的反向传播网网络模型，采用多变量插插值的径向基基函数网络模模型，建立在统计学学习理论基础础上的支撑向向量机网络模模型，采用反馈联接接方式的反馈馈网络模型，，基于模拟退火火算法的随机机网络模型。。本小节主要讨讨论感知机（Perceptron）模模型反向传播（BP）模型反馈网络（Hopfield）模型型人人工神经网网络的典型模模型23感知器是美国国学者罗森勃勃拉特（Rosenblatt）于于1957年年为研究大脑脑的存储、学学习和认知过过程而提出的的一类具有自自学习能力的的神经网络模模型，其拓扑扑结构是一种种分层前向网网络。它包括括：单层感知器多层感知器人人工神经网网络的典型模模型1.感知器器模型(1/10)24(1)单层层感知器单层感知器器是一种只只具有单层层可调节连连接权值神神经元的前前向网络，，这些神经经元构成了了单层感知知器的输出出层，是感感知器的可可计算节点点。在单层感知知器中，每每个可计算算节点都是是一个线性性阈值神经经元。当输输入信息的的加权和大大于或等于于阈值时，，输出为1，否则输输出为0或或-1。单层感知器器的输出层层的每个神神经元都只只有一个输输出，且该该输出仅与与本神经元元的输入及及联接权值值有关，而而与其他神神经元无关关。3.2.3人工神神经网络的的典型模型型1.感知知器模型(2/10)25单层感知器器的结构如如下图…x1x2xn…y1ym输入层输出层权值wij输入向量为为X=(x1,x2,…,xn)；输出向量为为Y=(y1,y2,…,ym)；输入层各个个输入到相相应神经元元的连接权权值分别是是wij，i=1,2,..,n，j=1,2,..,m。若假设各神神经元的阈阈值分别是是θj，j=1,2,…,m，则各各神经元的的输出yj,j=1,2,..,m分分别为其中，由所所有连接权权值wji构成的连接接权值矩阵阵W为：在实际应用用中，该矩矩阵是通过过大量的训训练示例学学习而形成成的26使用感知器器的主要目目的是为了了对外部输输入进行分分类。罗森森勃拉特已已经证明，，如果外部部输入是线线性可分的的（指存在在一个超平平面可以将将它们分开开），则单单层感知器器一定能够够把它划分分为两类。。其判别超超平面由如如下判别式式确定：作为例子，，下面讨论论用单个感感知器实现现逻辑运算算的问题。。事实上，，单层感知知器可以很很好地实现现“与”、、“或”、、“非”运运算，但却却不能解决决“异或””问题。人人工工神神经经网网络络的的典典型型模模型型1.感感知知器器模模型型(4/10)27例5.1““与与””运运算算（（x1∧x2）(0,0)(1,1)(0,1)(1,0)图5.10与运算问题图示输入输出超平面阈值条件x1x2x1∧x2w1*x1+w2*x2-θ=0000w1*0+w2*0-θ＜0θ＞0010w1*0+w2*1

-θ＜0θ＞w2100w1*1+w2*0-θ＜0θ＞w1

111w1*1+w2*1-θ≥0θ≤w1+w2

可以以证证明明此此表表有有解解，，例例如如取取w1=1，，w2=1，，θθ=1.5，，其其分分类类结结果果如如右右图图所所示示。。其中中，，输输出出为为1的的用用实实心心圆圆，，输输出出为为0的的用用空空心心圆圆。。后后面面约约定定相相同同。。人人工工神神经经网网络络的的典典型型模模型型1.感感知知器器模模型型(5/10)28例5.2““或或””运运算算（（x1∨x2）输入输出超平面阈值条件x1x2x1∨x2w1*x1+w2*x2-θ=0000w1*0+w2*0-θ＜0θ＞0011w1*0+w2*1

-θ≥0θ≤w2101w1*1+w2*0-θ≥0θ≤w1

111w1*1+w2*1-θ≥0θ≤w1+w2

此表表也也有有解解，，例例如如取取w1=1，，w2=1，，θθ=0.5，，其其分分类类结结果果如如右右图图所所示示。。(0,1)(0,0)(1,0)图5.11与运算问题图示(1,1)人人工工神神经经网网络络的的典典型型模模型型1.感感知知器器模模型型(6/10)29例5.3““非非””运运算算（（¬x1）输入输出超平面阈值条件x1¬x1w1*x1-θ=001w1*0-θ≥0θ≤010w1*1

–θ<0θ>w1此表表也也有有解解，，例例如如取取w1=-1，，θθ=-0.5，，其其分分类类结结果果如如右右图图所所示示。。图5.12非运算问题图示01人人工工神神经经网网络络的的典典型型模模型型1.感感知知器器模模型型(7/10)30例5.4““异异或或””运运算算（（x1XORx2）输入输出超平面阈值条件x1x2X1XORx2w1*x1+w2*x2-θ=0000w1*0+w2*0-θ＜0θ＞0011w1*0+w2*1-θ≥0θ≤w2101w1*1+w2*0-θ≥0θ≤w1

110w1*1+w2*1-θ<0θ>w1+w2

此表表无无解解，，即即无无法法找找到到满满足足条条件件的的w1、w2和θθ，，如如右右图图所所示示。。因因为为异异或或问问题题是是一一个个非非线线性性可可分分问问题题，，需需要要用用多多层层感感知知器器来来解解决决。。(0,1)(0,0)(1,0)图5.13异或运算问题图示(1,1)人人工工神神经经网网络络的的典典型型模模型型1.感感知知器器模模型型(8/10)31(2)多多层层感感知知器器多层层感感知知器器是是通通过过在在单单层层感感知知器器的的输输入入、、输输出出层层之之间间加加入入一一层层或或多多层层处处理理单单元元所所构构成成的的。。其其拓拓扑扑结结构构与与图图5.9所所示示的的多多层层前前向向网网络络相相似似，，差差别别也也在在于于其其计计算算节节点点的的连连接接权权值值是是可可变变的的。。多层感知器的的输入与输出出之间是一种种高度非线性性的映射关系系，如图5.9所示的多多层前向网络络，若采用多多层感知器模模型，则该网网络就是一个个从n维欧氏氏空间到m维维欧氏空间的的非线性映射射。因此，多多层感知器可可以实现非线线性可分问题题的分类。例例如，对“异异或”运算，，用图5.14所示的多多层感知器即即可解决。人人工神经网网络的典型模模型1.感知知器模型(9/10)32x11y=x1XORx2x1X2x121-1111-1输入层隐层输出层权值权值图5.14““异或”问问题的多层感感知器阈值0.5阈值-1.5阈值1.5(0,1)(0,0)(1,0)图5.15异或问题的解决(1,1)在图5.14中，隐层神神经元x11所确定的直线线方程为它可以识别一一个半平面。。隐层神经元元x12所确定的直线线方程为它也可以识别别一个半平面面。输出层神经元元所确定的直直线方程为它相当于对隐隐层神经元x11和x12的输出作“逻逻辑与”运算算，因此可识识别由隐层已已识别的两个个半平面的交交集所构成的的一个凸多边边形，如图5.15所示示。33误差反向传播播(ErrorBackPropagation)网网络通常简称称为BP(BackPropagation)网络，是是由美国加州州大学的鲁梅梅尔哈特和麦麦克莱兰在研研究并行分布布式信息处理理方法，探索索人类认知微微结构的过程程中，于1985年提出出的一种网络络模型。BP网络的网网络拓扑结构构是多层前向向网络，如图图5.16所所示。在BP网络中，同同层节点之间间不存在相互互连接，层与与层之间多采采用全互连方方式，且各层层的连接权值值可调。BP网络实现了了明斯基的多多层网络的设设想，是当今今神经网络模模型中使用最最广泛的一种种。y1y2ymx1x2xn输出层隐含层输入层权可调权可调………图5.16一个多层BP网络的结构人人工神经网网络的典型模模型2.BP网网络模型(1/2)34对BP网络需需说明以下两两点：第一，BP网网络的每个处处理单元均为为非线性输入入/输出关系系，其作用函函数通常采用用的是可微的的Sigmoid函数，，如：第二，BP网网络的学习过过程是由工作作信号的正向向传播和误差差信号的反向向传播组成的的。所谓正向向传播，是指指输入模式经经隐层到输出出层，最后形形成输出模式式；所谓误差差反向传播，，是指从输出出层开始逐层层将误差传到到输入层，并并修改各层联联接权值，使使误差信号为为最小的过程程。人人工神经网网络的典型模模型2.BP网网络模型(2/2)35Hopfield网络是是由美国加州州工学院物理理学家霍普菲菲尔特1982年提出来来的一种单层层全互连的对对称反馈网络络模型。它可可分为离散Hopfield网络和和连续Hopfield网络，限于于篇幅，本书书重点讨论离离散Hopfield网网络。离散Hopfield网网络的结构离散Hopfield网网络是在非线线性动力学的的基础上由若若干基本神经经元构成的一一种单层全互互连网络，其其任意神经元元之间均有连连接，并且是是一种对称连连接结构。一一个典型的离离散Hopfidld网络结构如如图5-17所示。离散散Hopfield网络络模型是一个个离散时间系系统，每个神神经元只有0和1（或-1和1）两两种状态，任任意神经元i和j之间的的连接权值为为wij。由由于神经元之之间为对称连连接，且神经经元自身无连连接，因此有有由该连接权值值所构成的连连接矩阵是一一个零对角的的对称矩阵。。人人工神经网网络的典型模模型2.Hopfield网络模型(1/2)36图5‑17离散Hopfield网络的结构ymY2Y1x1……x2xn输入层输出层在Hopfidld网网络中，虽然然神经元自身身无连接，但但由于每个神神经元都与其其他神经元相相连，即每个个神经元的输输出都将通过过突触连接权权值传递给别别的神经元，，同时每个神神经元又都接接受其他神经经元传来的信信息，这样对对每个神经元元来说，其输输出经过其他他神经元后又又有可能反馈馈给自己，因因此Hopfidld网网络是一种反反馈神经网络络人人工神经网网络的典型模模型2.Hopfield网络模型(2/2)37进化计算（EvolutionaryComputation,EC）是在达达尔文（Darwin））的进化论和和孟德尔（Mendel）的遗传变变异理论的基基础上产生的的一种在基因因和种群层次次上模拟自然然界生物进化化过程与机制制的问题求解解技术。它主主要包括遗传算法（GeneticAlgorithm，GA））进化策略（EvolutionaryStrategy,ES）进化规划（EvolutionaryProgramming,EP）遗传规划（GeneticProgramming,GP）四大分分支。其中，第一个个分支是进化化计算中最初初形成的一种种具有普遍影影响的模拟进进化优化算法法。因此我们们主要讨论遗遗传算法。5.3进化化计算38进化计算是一一种模拟自然然界生物进化化过程与机制制进行问题求求解的自组织织、自适应的的随机搜索技技术。它以达达尔文进化论论的“物竟天天择、适者生生存”作为算算法的进化规规则，并结合合孟德尔的遗遗传变异理论论，将生物进进化过程中的的繁殖（Reproduction））变异（Mutation）竞争（Competition）选择（Selection）引入到了算法法中。进进化计算概概述1.进化计计算及其生物物学基础(1/3)(1)什么是是进化计算39(2)进化化计算的生物物学基础自然界生物进进化过程是进进化计算的生生物学基础，，它主要包括括遗传(Heredity)、变异异(Mutation)和进化(Evolution)理理论。①遗遗传理理论遗传是是指父父代（（或亲亲代））利用用遗传传基因因将自自身的的基因因信息息传递递给下下一代代（或或子代代），，使子子代能能够继继承其其父代代的特特征或或性状状的这这种生生命现现象。。正是是由于于遗传传的作作用，，自然然界才才能有有稳定定的物物种。。在自然然界，，构成成生物物基本本结构构与功功能的的单位位是细细胞（（Cell）。。细胞中中含有有一种种包含含着所所有遗遗传信信息的的复杂杂而又又微小小的丝丝状化化合物物，人人们称称其为为染色色体（（Chromosome）。。在染色色体中中，遗遗传信信息由由基因因（Gene））所组组成，，基因因决定定着生生物的的性状状，是是遗传传的基基本单单位。。染色体体的形形状是是一种种双螺螺旋结结构，，构成成染色色体的的主要要物质质叫做做脱氧氧核糖糖核酸酸(DNA)，，每个个基因因都在在DNA长长链中中占有有一定定的位位置。。一个细细胞中中的所所有染染色体体所携携带的的遗传传信息息的全全体称称为一一个基基因组组(Genome)。细胞在在分裂裂过程程中，，其遗遗传物物质DNA通过过复制制转移移到新新生细细胞中中，从从而实实现了了生物物的遗遗传功功能。。进进化计计算概概述1.进进化化计算算及其其生物物学基基础(2/3)40②变变异理理论变异是是指子子代和和父代代之间间，以以及子子代的的各个个不同同个体体之间间产生生差异异的现现象。。变异异是生生物进进化过过程中中发生生的一一种随随机现现象，，是一一种不不可逆逆过程程，在在生物物多样样性方方面具具有不不可替替代的的作用用。引引起变变异的的主要要原因因有以以下两两种：：杂交，，是指指有性性生殖殖生物物在繁繁殖下下一代代时两两个同同源染染色体体之间间的交交配重重组，，即两两个染染色体体在某某一相相同处处的DNA被切切断后后再进进行交交配重重组，，形成成两个个新的的染色色体。。复制差差错，，是指指在细细胞复复制过过程中中因DNA上某某些基基因结结构的的随机机改变变而产产生出出新的的染色色体。。③进进化论论进化是是指在在生物物延续续生存存过程程中，，逐渐渐适应应其生生存环环境，，使得得其品品质不不断得得到改改良的的这种种生命命现象象。遗遗传和和变异异是生生物进进化的的两种种基本本现象象，优优胜劣劣汰、、适者者生存存是生生物进进化的的基本本规律律。达尔文文的自自然选选择学学说认认为：：在生生物进进化中中，一一种基基因有有可能能发生生变异异而产产生出出另一一种新新的生生物基基因。。这种种新基基因将将依据据其与与生存存环境境的适适应性性而决决定其其增殖殖能力力。一一般情情况下下，适适应性性强的的基因因会不不断增增多，，而适适应性性差的的基因因则会会逐渐渐减少少。通通过这这种自自然选选择，，物种种将逐逐渐向向适应应于生生存环环境的的方向向进化化，甚甚至会会演变变成为为另一一个新新的物物种，，而那那些不不适应应于环环境的的物种种将会会逐渐渐被淘淘汰。。进进化计计算概概述1.进进化化计算算及其其生物物学基基础(3/3)41进化计计算自自20世纪纪50年代代以来来，其其发展展过程程大致致可分分为三三个阶阶段。。①萌萌芽芽阶段段这一阶段段是从20世纪纪50年年代后期期到70年代中中期。20世纪纪50年年代后期期，一些些生物学学家在研研究如何何用计算算机模拟拟生物遗遗传系统统中，产产生了遗传算法法的基本思思想，并并于1962年年由美国国密执安安（Michigan）大学学霍兰德德（Holland））提出。。1965年德德国数学学家雷切切伯格（（Rechenberg）等等人提出出了一种种只有单单个个体体参与进进化，并并且仅有有变异这这一种进进化操作作的进化策略略。同年，，美国学学者弗格格尔（Fogel）提提出了一一种具有有多个个个体和仅仅有变异异一种进进化操作作的进化规划划。1969年美美国密执执安（Michigan）大大学的霍霍兰德（（Holland）提提出了系系统本身身和外部部环境相相互协调调的遗传传算法。。至此，，进化计计算的三大分支支基本形形成。②成长长阶段这一阶段段是从20世纪纪70年年代中期期到80年代后后期。1975年，霍霍兰德出出版专著著《自然然和人工工系统的的适应性性（AdaptationinNaturalandArtificialSystem））》，全全面介绍绍了遗传传算法。。同年，，德国学学者施韦韦费尔（（Schwefel））在其博博士论文文中提出出了一种种由多个个个体组组成的群群体参与与进化的的，并且且包括了了变异和和重组这这两种进进化操作作的进化化策略。。1989年，，霍兰德德的学生生戈尔德德伯格（（Goldberg））博士出出版专著著《遗传传算法----搜索、、优化及及机器学学习（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，，使遗传传算法得得到了普普及与推推广。进进化计算算概述2.进进化计算算的产生生与发展展(1/2)42③发展展阶段这一阶段段是从20世纪纪90年年代至今今。1989年年，美国国斯坦福福（Stanford）大学学的科扎扎（Koza））提出了了遗传规规划的新新概念，，并于1992年出版版了专著著《遗传传规划----应用自自然选择择法则的的计算机机程序设设计（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection））》该书书全面介介绍了遗遗传规划划的基本本原理及及应用实实例，标标志着遗遗传规划划作为计计算智能能的一个个分支已已基本形形成。进入20世纪90年代代以来，，进化计计算得到到了众多多研究机机构和学学者的高高度重视视，新的的研究成成果不断断出现、、应用领领域不断断扩大。。目前，，进化计计算已成成为人工工智能领领域的又又一个新新的研究究热点。。进进化计算算概述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)代种种群执行行进化操操作；对执行完完进化操操作后的的种群进进行评价价（即适适应度计计算）；；}}可以看出出，上述述基本结结构包含含了生物物进化中中所必需需的选择择操作、、进化操操作和适适应度评评价等过过程。进进化计算算概述3.进进化计算算的基本本结构44遗传算法法的基本本思想是是从初始始种群出出发，采采用优胜胜劣汰、、适者生生存的自自然法则则选择个个体，并并通过杂杂交、变变异来产产生新一一代种群群，如此此逐代进进化，直直到满足足目标为为止。遗遗传算法法所涉及及到的基基本概念念主要有有以下几几个：种群（Population）：种群群是指用用遗传算算法求解解问题时时，初始始给定的的多个解解的集合合。遗传传算法的的求解过过程是从从这个子子集开始始的。个体（Individual）：：个体是是指种群群中的单单个元素素，它通通常由一一个用于于描述其其基本遗遗传结构构的数据据结构来来表示。。例如，，可以用用0、1组成的的长度为为l的串串来表示示个体。。染色体（Chromos）：：染色体体是指对对个体进进行编码码后所得得到的编编码串。。染色体体中的每每1位称称为基因因，染色色体上由由若干个个基因构构成的一一个有效效信息段段称为基基因组。。适应度（Fitness）函函数：适适应度函函数是一一种用来来对种群群中各个个个体的的环境适适应性进进行度量量的函数数。其函函数值是是遗传算算法实现现优胜劣劣汰的主主要依据据遗传操作作（GeneticOperator）：：遗传操操作是指指作用于于种群而而产生新新的种群群的操作作。标准的遗遗传操作作包括以以下3种种基本形形式：选择（Selection）交叉（Crosssover）变异（Mutation））遗遗传算法法1.遗遗传算算法的基基本概念念45遗传算法法主要由由染色体体编码、、初始种种群设定定、适应应度函数数设定、、遗传操操作设计计等几大大部分所所组成，，其算法法主要内内容和基基本步骤骤可描述述如下：：(1)选选择编编码策略略，将问问题搜索索空间中中每个可可能的点点用相应应的编码码策略表表示出来来，即形形成染色色体；(2)定定义遗遗传策略略，包括括种群规规模N，，交叉、、变异方方法，以以及选择择概率Pr、交交叉概率率Pc、、变异概概率Pm等遗传传参数；；(3)令令t=0，随随机选择择N个染染色体初初始化种种群P(0)；；(4)定定义适适应度函函数f（（f>0）；(5)计计算P(t)中每个个染色体体的适应应值；(6)t=t+1；；(7)运运用选选择算子子，从P(t-1)中中得到P(t)；(8)对对P(t)中中的每个个染色体体，按概概率Pc参与交交叉；(9)对对染色色体中的的基因，，以概率率Pm参参与变异异运算；；(10)判断断群体性性能是否否满足预预先设定定的终止止标准，，若不满满足则返返回(5)。遗遗传算法法2.遗遗传算算法的基基本结构构(1/2)46计算种群中各个个体的适应度，并进行评价满足终止条件吗？终止选择交叉变异Y图5-18基本遗传算法的算法流程图编码和生成初始种群N选择其算法流流程如图图5-18所示示。遗遗传算法法2.遗遗传算算法的基基本结构构(2/2)47常用的遗遗传编码码算法有有霍兰德德二进制制码、格格雷码（（GrayCode）、实实数编码码和字符符编码等等。(1)二二进制编编码（Binaryencoding））二进制编编码是将将原问题题的结构构变换为为染色体体的位串串结构。。在二进进制编码码中，首首先要确确定二进进制字符符串的长长度l，，该长度度与变量量的定义义域和所所求问题题的计算算精度有有关。例5.5假设变量量x的定定义域为为[5，，10]，要求求的计算算精度为为10-5，则则需要将将[5，，10]至少分分为600000个等等长小区区间，每每个小区区间用一一个二进进制串表表示。于于是，串串长至少少等于20，原原因是：：524288=219<600000<220=1048576这样，对对应于区区间[5，10]内满满足精度度要求的的每个值值x，都都可用一一个20位编码码的二进进制串<b19,b18,……,b0>来表表示。二进制编编码存在在的主要要缺点是汉明（（Hamming）悬悬崖。例如，7和8的的二进制制数分别别为0111和和1000，当当算法从从7改进进到8时时，就必必须改变变所有的的位。遗遗传算法法3.遗遗传编编码(1/3)48遗遗传算法法3.遗遗传编编码(2/3)(2)格格雷编编码（Grayencoding）格雷编码码是对二二进制编编码进行行变换后后所得到到的一种种编码方方法。这这种编码码方法要要求两个个连续整整数的编编码之间间只能有有一个码码位不同同，其余余码位都都是完全全相同的的。它有有效地解解决了汉汉明悬崖崖问题，，其基本本原理如如下：设有二进制制串b1,b2,……,bn，，对应的格格雷串为a1,a2,…,an，则从从二进制编编码到格雷雷编码的变变换为：其中，⊕表表示模2加加法。而从从一个格雷雷串到二进进制串的变变换为：例5.6十进制数7和8的二二进制编码码分别为0111和和1000，而其格格雷编码分分别为0100和1100。。49(3)实实数编码（（Realencoding）实数编码是是将每个个个体的染色色体都用某某一范围的的一个实数数（浮点数数）来表示示，其编码码长度等于于该问题变变量的个数数。这种编码方方法是将问问题的解空空间映射到到实数空间间上，然后后在实数空空间上进行行遗传操作作。由于实实数编码使使用的是变变量的真实实值，因此此这种编码码方法也叫叫做真值编编码方法。。实数编码适适应于那种种多维、高高精度要求求的连续函函数优化问问题。5.3.2遗传算算法3.遗遗传编码(3/3)50适应度函数数是一个用用于对个体体的适应性性进行度量量的函数。。通常，一一个个体的的适应度值值越大，它它被遗传到到下一代种种群中的概概率也就越越大。(1)常常用的适应应度函数在遗传算法法中，有许许多计算适适应度的方方法，其中中最常用的的适应度函函数有以下下两种：①原始适适应度函数数它是直接将将待求解问问题的目标标函数f(x)定义义为遗传算算法的适应应度函数。。例如，在在求解极值值问题时，f(x)即为x的原始适适应度函数数。采用原始适适应度函数数的优点是是能够直接接反映出待待求解问题题的最初求求解目标，，其缺点是是有可能出出现适应度度值为负的的情况。5.3.2遗传算算法4.适适应度函数数(1/4)51②标准适适应度函数数在遗传算法法中，一般般要求适应应度函数非非负，并其其适应度值值越大越好好。这就往往往需要对对原始适应应函数进行行某种变换换，将其转转换为标准准的度量方方式，以满满足进化操操作的要求求，这样所所得到的适适应度函数数被称为标标准适应度度函数fNormal(x)。极小化问题题对极小化问问题，其标标准适应度度函数可定定义为其中，fmax(x)是原始适应应函数f(x)的一个上界界。如果fmax(x)未知，则可可用当前代代或到目前前为止各演演化代中的的f(x)的最大值来来代替。可可见，fmax(x)是会随着进进化代数的的增加而不不断变化的的。5.3.2遗传算算法4.适适应度函数数(2/4)52极大化问题题对极大化问问题，其标标准适应度度函数可定定义为其中，fmin(x)是原始适应应函数f(x)的一个下界界。如果fmin(x)未知，则可可用当前代代或到目前前为止各演演化代中的的f(x)的最小值来来代替。5.3.2遗传算算法4.适适应度函数数(3/4)53(2)适应度函数数的加速变变换在某些情况况下，适应应度函数在在极值附近近的变化可可能会非常常小，以至至于不同个个体的适应应值非常接接近，使得得难以区分分出哪个染染色体更占占优势。对对此，最好好能定义新新的适应度度函数，使使该适应度度函数既与与问题的目目标函数具具有相同的的变化趋势势，又有更更快的变化化速度。适应度函数数的加速变变换有两种种基本方法法①线性加加速适应度函数数的定义如如下：f’(x)=αf(x)+ββ其中，f(x)是加速转换换前的适应应度函数；；f’(x)是加速转换换后的适应应度函数；；α和β是转换系数数。②非线性性加速幂函数变换换方法f’(x)=f(x)k指数变换方方法f’(x)=exp(-βf(x))5.3.2遗传算算法4.适适应度函数数(4/4)54遗传算法中中的基本遗遗传操作包包括选择、、交叉和变变异3种，，而每种操操作又包括括多种不同的方法法，下面分分别对它们们进行介绍绍。(1).选选择操作作选择（Selection））操作是指指根据选择择概率按某某种策略从从当前种群群中挑选出出一定数目目的个体，，使它们能能够有更多多的机会被被遗传到下下一代中。。常用的选择择策略可分分为比例选选择、排序序选择和竞竞技选择三三种类型。。①比例选选择比例选择方方法（ProportionalModel）的基本本思想是：：各个个体体被选中的的概率与其其适应度大大小成正比比。常用的比例例选择策略略包括轮盘赌选择择繁殖池选择择5.3.2遗传算算法5.基基本遗传操操作(1/11)55②轮盘赌选选择轮盘赌选择择法又被称称为转盘赌赌选择法或或轮盘选择择法。在这这种方法中中，个体被被选中的概概率取决于于该个体的的相对适应应度。而相相对适应度度的定义为为：其中，P(xi)是个体xi的相对适应应度，即个个体xi被选中的概概率；f(xi)是个体xi的原始适应应度；是种种群的累加加适应度。。轮盘赌选择择算法的基基本思想是是：根据每每个个体的的选择概率率P(xi)将一个圆圆盘分成N个扇区，，其中第i个扇区的的中心角为为：并再设立一一个固定指指针。当进进行选择时时，可以假假想转动圆圆盘，若圆圆盘静止时时指针指向向第i个扇扇区，则选选择个体i。其物理理意义如图图5-19所示。5.3.2遗传算算法5.基基本遗传操操作(2/11)56P(x1)P(x2)P(xN)……P(xi)2πp(xi)图5-19轮盘赌选择从统计角度度看，个体体的适应度度值越大，，其对应的的扇区的面面积越大，，被选中的的可能性也也越大。这这种方法有有点类似于于发放奖品品使用的轮轮盘，并带带有某种赌赌博的意思思，因此亦亦被称为轮轮盘赌选择择。遗遗传传算算法法5.基基本本遗遗传传操操作作(3/11)57(2)交交叉叉操操作作交叉叉（（Crossover））操操作作是是指指按按照照某某种种方方式式对对选选择择的的父父代代个个体体的的染染色色体体的的部部分分基基因因进进行行交交配配重重组组，，从从而而形形成成新新的的个个体体。。交交配配重重组组是是自自然然界界中中生生物物遗遗传传进进化化的的一一个个主主要要环环节节，，也也是是遗遗传传算算法法中中产产生生新新的的个个体体的的最最主主要要方方法法。。根根据据个个体体编编码码方方法法的的不不同同，，遗遗传传算算法法中中的的交交叉叉操操作作可可分分为为二二进进制制交交叉叉和和实实值值交交叉叉两两种种类类型型。①二二进进制制交交叉叉二进进制制交交叉叉（（BinaryValuedCrossover））是是指指二二进进制制编编码码情情况况下下所所采采用用的的交交叉叉操操作作，，它它主主要要包包括括单点点交交叉叉、、两两点点交交叉叉、、多多点点交交叉叉和和均均匀匀交交叉叉等方方法法。。遗遗传传算算法法5.基基本本遗遗传传操操作作(4/11)58单点点交交叉叉单点点交交叉叉也也称称简简单单交交叉叉，，它它是是先先在在两两个个父父代代个个体体的的编编码码串串中中随随机机设设定定一一个个交交叉叉点点，，然然后后对对这这两两个个父父代代个个体体交交叉叉点点前前面面或或后后面面部部分分的的基基因因进进行行交交换换，，并并生生成成子子代代中中的的两两个个新新的的个个体体。。假假设设两两个个父父代代的的个个体体串串分分别别是是：：X=x1x2…xkxk+1…xnY=y1y2…ykyk+1…yn随机选择第k位为交叉点点，若采用对对交叉点后面面的基因进行行交换的方法法，但点交叉叉是将X中的的xk+1到xn部分与Y中的的yk+1到yn部分进行交叉叉，交叉后生生成的两个新新的个体是：：X’=x1x2…xkyk+1…ynY’=y1y2…ykxk+1…xn例5.7设有两个父代代的个体串A=001101和B=110010，若随机交叉叉点为4，则交叉后生生成的两个新新的个体是：：A’=001110B’=110001遗遗传算法5.基本本遗传操作(5/11)59两点交叉两点交叉是指指先在两个父父代个体的编编码串中随机机设定两个交交叉点，然后后再按这两个个交叉点进行行部分基因交交换，生成子子代中的两个个新的个体。。假设两个父代代的个体串分分别是：X=x1x2…xi…xj…xnY=y1y2…yi…yj…,yn随机设定第i、j位为两两个交叉点（（其中i<j<n），两两点交叉是将将X中的xi+1到xj部分与Y中的的yi+1到yj部分进行交换换，交叉后生生成的两个新新的个体是：：X’=x1x2…xiyi+1…yjxj+1…xnY’=y1y2…yixi+1…xjyj+1…yn例5.8设有两个父代代的个体串A=001101和B=110010，若随机交叉叉点为3和5，则交叉后的的两个新的个个体是：A’=001011B’=110100遗遗传算法5.基本本遗传操作(6/11)60多点交叉多点交是指先先随机生成多多个交叉点，，然后再按这这些交叉点分分段地进行部部分基因交换换，生成子代代中的两