第七章学习与进化模型课件

第八章第八章 学习与进化模型本章内容建议自学参考:人工神经网络F第八章 学习与进化模型本章内容建议自学参考:人工神经网络本章要求F掌握ANN的基本原理和思想F能够在Swarm和Repast中应用ANNF掌遗传算法的基本原理和思想F能够在Swarm和Repast中应用GAF本章要求掌握ANN的基本原理和思想大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法F大纲学习主体大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法F大纲学习主体学习Agent 一个学习Agent可以被认为既包含决定采取什么动作的执行元件执行元件，又包含修改执行元件使其能制定更好决策的学习元件学习元件。一个学习元件的设计受到下列三个主要因素的影响：w将要学习的是执行元件的哪个组成部分；w对学习这些组成部分而言，可得到什么反馈；w组成部分是如何表示的。F学习Agent 一个学习Agent可以被认为既包含学习中可用的反馈类型学习中可用的反馈类型通常是决定智能体所面临的学习问题本质的最重要因素。一般分为三种类型：w有监督的从它的输入和输出的实例中学习一个函数。对于完全可观察的环境，智能体总能够观察到它的行动所带来的影响，因此可以采用有监督学习的方法来学习预测它们，对于部分可观察的环境，会困难一些。w无监督的在未提供明确的输出值的情况下，学习输入的模式。w强化学习从强化事物中进行学习，而不是根据教师所说的应该做什么进行学习。F学习系统设计的影响因素：如何表示学习到的知识；先验知识学习系统设计的影响因素：如何表示学习到的知识；先验知识的可用性。的可用性。F学习中可用的反馈类型学习中可用的反馈类型通常是决定智能体所面归纳学习（1）确定性的有监督的学习F纯归纳推理：给定f的实例集合，返回近似于f的函数hF函数h被称为假设，一个好的假设应该是一般化的，也就是说能够正确地预测未见过的实例。F例子（见板书）：使一个单变量函数能拟合某些数据点F假设空间H：选择最高次数为k的多项式集合F一致假设:和所有的实例数据一致。F如何在多个一致假设之间进行选择？F奥卡姆剃刀（Ockhams razor）原则:优先选择与数据一致的最简单的假设。F在假设的复杂度和数据拟合度之间进行折中是不可避免的F找到一个简单的一致假设的可能性或不可能性很强地依赖于对假设空间的选择。F归纳学习（1）确定性的有监督的学习纯归纳推理：给定f的归纳学习（2）确定性的有监督的学习F找到一个简单的一致假设的可能性或不可能性很强地依赖于对假设空间的选择。（假设空间的重要性）F如果假设空间包含真实的函数，那么学习的问题就是可实现的，否则就是不可实现的。F不幸的是，这是的函数是未知的，我们不能总是说出一个给定的学习问题是否可实现，一种避开这个障碍的方法是使用先验知识得到一个假设空间，我们可以确定一个真实的函数一定在该假设空间中，另外一种做法是采用最大可能的假设空间。F归纳学习（2）确定性的有监督的学习找到一个简单的一致假学习决策树F决策树归纳是最简单的但是最成功的学习算法形式之一。F作为执行元件的决策树一棵决策树将用属性集合描述的事物或情景作为输入，并返回一个“决策”。输入的属性或输出值可以是离散的，也可以是连续的，学习一个离散值函数称为分类，学习一个连续函数称为回归。实例说明：决定是否要等座位的决策树F从实例中归纳决策树F学习决策树决策树归纳是最简单的但是最成功的学习算法形式之一。强化学习所谓强化学习是指从环境状态到动作映射的学习，以使动作从环境中获得的累积奖赏值最大。该方法不同于监督学习技术那样通过正例、反例来告知采取何种行动，而是通过试错（trial-and-error）来发现最优行为策略。从20世纪80年代末开始，随着对强化学习的数学基础研究取得突破性进展后，对强化学习的研究和应用日益开展起来，成为目前机器学习领域的研究重点之一。F强化学习 所谓强化学习是指从环境状态到动作映射的学习，以使强化学习的框架结构Agent由状态感知器I、学习器L和动作选择器P三模块组成。状态感知器I把环境状态s映射成Agent内部感知i；动作选择器P根据当前策略选择动作a作用于环境W；学习器L根据环境状态的奖赏值r以及内部感知i，更新Agent的策略知识。W在动作a的作用下将导致环境状态变迁到s。强化学习技术的基本原理是：如果Agent的某个动作导致环境正的奖赏（强化信号），那么Agent以后产生这个动作的趋势便会加强，反之Agent产生这个动作的趋势渐弱。F强化学习的框架结构Agent由状态感知器I、学习器L和动作选Q-学习FQ-学习是由Watkins提出的一种模型无关的强化学习算法，又称为离策略TD学习（off-policy TD）。F由于在一定条件Q-学习只需采用贪婪策略即可保证收敛，因此Q-学习是目前最有效的模型无关强化学习算法。FQ-学习Q-学习是由Watkins提出的一种模型无关的强化学Q-学习算法流程F对每个 初始化 为0F观察当前状态F一直重复做：F(1)选择一个动作 并执行它F(2)接收到立即回报F(3)观察新状态F(4)按照下式更新表项：F F(5)FQ-学习算法流程对每个 初始化 Q-学习（例子）悬崖步行是由Sutton提出的一个Agent仿真试验环境，如图所示。智能体的任务是从起始点S移动到目标点G。S、G之间的阴影方格为悬崖，智能体移动到这个区域就有坠崖的危险，因此如果进入这个区域，就给它一个大的惩罚r1000；如果到达G，就给它一个大的奖赏r100，其它情况给它一个回报r-0.1。通过学习，智能体可以找到一条既安全又不浪费移动步数的路径，通过对奖赏值的调整，智能体可以找到最安全或者最短的路径。FQ-学习（例子）悬崖步行是由Sutton提出的一个Ag大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法F大纲学习主体人工智能的联结主义流派 又称仿生学派，认为人工智能源于仿生学，人思维的基本单元是神经元，而非符号处理过程，主张用大脑工作模式取代符号操作的电脑工作模式；智能的本质是联结机制。神经网络是一个由大量简单的处理单元组成的高度复杂的大规模非线性自适应系统；“结构功能”的研究方法：认为功能、结构和智能行为是密切相关的；F1943年，McCulloch和Pitts从神经元入手研究神经网络模型MP模型。此为人工神经网络研究之始。F人工智能的联结主义流派 又称仿生学派，认为人工智能源于仿生F人工神经网络（Artificial Neural Network，ANN）从四个方面刻画人脑的基本特征：F（1）物理结构物理结构F模仿生物神经元的功能，构造人工神经元的联结网络FCell bodyFAxonFNucleusFSynapseF突触FDendriteF树突F人工神经网络（Artificial Neural NetwoF（2）计算模拟F人脑神经元既有局部的计算和存储功能，又通过联结构成统一的系统，人脑的计算建立在该系统的大规模并行模拟处理基础之上。FANN以具有局部计算能力的神经元为基础，同样实现信息的大规模并行处理。F（3）存储与操作F大脑对信息的记忆是通过改变突触的强度来实现并分布存储。FANN模拟信息的大规模分布存储。FF（4）训练F后天的训练使得人脑具有很强的自组织和自适应性。FANN根据人工神经元网络的结构特性，使用不同的训练过程，自动从“实践”（即训练样本）中获取相关知识，并存储在系统中。F（2）计算模拟ANN是基于联结主义流派的人工智能 联结主义学派与高速发展的计算机技术相结合，发展为计算智能学派，是人工智能在1980年代后的深化和发展；计算智能：借助现代计算机技术模拟人的智能控制、生命演化过程和人的智能行为，从而进行信息获取、处理、应用的理论和方法；计算智能是以数学模型、计算模型为基础，以分布、并行、仿生计算为特征，包含数据、算法和实现的信息系统；计算智能强调模型的建立和构成，强调系统的自组织、自学习和自适应；计算智能的3个主要分支：F 人工神经网络人工神经网络（模拟智能产生与作用赖以存在的结构）F 遗传算法遗传算法（模拟生命生成过程与智能进化过程）F 模糊逻辑模糊逻辑（模拟智能的表现行为）FANN是基于联结主义流派的人工智能 联结主义学派与高速发展人工神经网络概述F人工神经网络是受生物神经网络的启发构造而成。FJames（心理学，1890年）：大脑皮层每一点的活力产生于其它点势能释放的综合效能，即其它点的兴奋次数、强度和所接受的能量。F大脑含约1011个神经元，它们通过1015个联结构成一个网络。每个神经元具有独立的接受、处理和传递电化学信号的能力，这种传递由神经通道来完成。F人工神经网络概述人工神经网络是受生物神经网络的启发构造而成。神经元的结构F树突从细胞体伸向其它神经元，神经元之间的接受信号的联结点为突触。通过突触输入的信号起着兴奋/抑制作用。当细胞体接受的累加兴奋作用超过某阈值时，细胞进入兴奋状态，产生冲动，并由轴突输出。FCell bodyFAxonFNucleusFSynapseF突触FDendriteF树突F神经元的结构Cell bodyAxonNucleusSyna神经元系统的基本特征 神经元及其联结 神经元之间的联结强度决定信号传递的强弱 神经元之间的联结强度可以随训练而改变 信号分为兴奋型和抑制型 一个神经元接受的信号的累计效果决定该神经元的状态 每个神经元有一个阈值F神经元系统的基本特征人工神经网络的几种形式无反馈前向网F多输入、多输出的多层无环图，同一层间无联结F神经元分层排列，组成输入层、中间层（隐层）、输出层F人工神经网络的几种形式无反馈前向网有反馈前向网F从输出层到输入层存在反馈的前向网。F有反馈前向网层内有联结的前向网F在无反馈前向网中同一层内存在神经元间的联结回路F层内有联结的前向网FF人工神经网络方法简介人工神经网络方法简介有向网F任意两个神经元间都可能存在有向联结。F网络处在动态中，直至达到某一平衡态、周期态或者混沌状态F人工神经网络方法简介有向网F感知器（Perceptron）F人工神经网络的基本构件F第七章学习与进化模型课件F感知器（Perceptron）是最早被设计并实现的人工神经网络。FW.McCulloch和W.Pitts总结生物神经元的基本生理特征，提出一种简单的数学模型与构造方法，建立了阈值加权和模型，简称M-P模型(“A Logical Calculus Immanent in Nervous Activity”,Bulletin of Mathematical Biophysics,1943(5):115133）。F人工神经元模型是M-P模型的基础。感知器的数学模型FWarren McCullochF（18981969）FWalter PittsF(19231969)F感知器（Perceptron）是最早被设计并实现的人工神经网生物神经元的基本特征 神经元及其联结 神经元之间的联结强度决定信号传递的强弱 神经元之间的联结强度可以随训练而改变 信号分为兴奋型和抑制型 一个神经元接受的信号的累计效果决定该神经元的状态 每个神经元有一个阈值F突触F树突FF轴突轴突F突触F树突F内核F轴突F生物神经元的基本特征树突轴突突触树突内核轴突FF人工神经网络方法简介人工神经网络方法简介F模拟神经元的首要目标：输入信号的加权和F人工神经元可以接受一组来自系统中其它神经元的输入信号，每个输入对应一个权，所有输入的加权和决定该神经元的激活状态。每个权就相当于突触的联结强度。Fw1Fwi xiFw2FwnFx1Fx2FxnFF人工神经元数学模型人工神经元数学模型F多输入、单输出的加权和结构F人工神经网络方法简介模拟神经元的首要目标：输入信号的加权和wF设X=(x1,x2,xn)表示n个输入，W=(w1,w2,wn)表示它们对应的联结权重。F故神经元所获得的输入信号累计效果为：Fw1Fwi xiFw2FwnFx1Fx2FxnF称u(x)为整合函数F设X=(x1,x2,xn)表示n个输入，W=FF人工神经网络方法简介人工神经网络方法简介FF感知器的激活函数感知器的激活函数神经元获得网络输入信号后，信号累计效果整合函数u(x)大于某阈值 时，神经元处于激发状态；反之，神经元处于抑制状态构造激活函数，用于表示这一转换过程。要求是-1,1之间的单调递增函数激活函数通常为3种类型，由此决定了神经元的输出特征F人工神经网络方法简介感知器的激活函数神经元获得网络输入信号后F（1）激活函数为符号函数：F1F-1FuFF（1）激活函数为符号函数：1-1uF（2）激活函数为分段线性函数：F1F-1FuFF（2）激活函数为分段线性函数：1-1uFF人工神经网络方法简介人工神经网络方法简介F（3）激活函数为Sigmoid函数，其特点是单调递增、光滑且具有渐近值，具有解析上的优点和神经生理学特征。FF1F-1FuF人工神经网络方法简介（3）激活函数为Sigmoid函数，其FF人工神经网络方法简介人工神经网络方法简介FF2.M-P2.M-P模型模型F将人工神经元的基本模型与激活函数结合，即McCulloch Pitts模型。Fw1F Fu=wixiFw2FwnFx1Fx2Fxny=(u(x)-)F人工神经网络方法简介2.M-P模型w1 u=wixiwFANN可以学会它表达的任何东西。（Rosenblatt，1962年）FANN的表达能力有限，其学习能力也受到限制。FANN的学习过程就是训练过程，在将训练样本集输入到网络的过程中，按照一定的方式来调整神经元之间的联结权重值，使得网络能够将训练样本集的内涵以联结权重矩阵的方式存储起来，从而使得网络在接受输入时，能够给出适当的输出。F有监督的学习（Supervised learning）F无监督的学习（Unsupervised learning）感知器的学习算法FANN可以学会它表达的任何东西。（Rosenblatt，19F感知器的学习是有监督的学习。学习的问题归结为求权重系数W=(w1,w2,wn)和阈值的问题。F基本思想：逐步将训练集中的样本输入到网络中，根据输出结果和理想输出之间的差别来调整网络中的权重值。Fw1F Fu=wixiFw2FwnFx1Fx2FxnFy=(u(x)-)F感知器的学习是有监督的学习。学习的问题归结为求权重系数W=F设X=(x1,x2,xn)表示n个输入，W=(w1,w2,wn)表示它们对应的联结权重。假设取符号函数为激活函数，F此为经典的M-P模型：Fw1FFu=wixiFw2FwnFx1Fx2FxnF+1 or-1F设X=(x1,x2,xn)表示n个输入，W=训练集的样本（输入向量、输出值）为：t为样本数目。其中，F训练集的样本（输入向量、输出值）为：t为样本数目。其中，FF感知器的基本理论FF“线性不可分线性不可分”问题的困境及其解决问题的困境及其解决FMarvin MinskyFMIT Media Lab and MIT AI LabToshiba Professor of Media Arts and SciencesProfessor of E.E.and C.S.,M.I.Tminskymedia.mit.eduF1969年，Minsky和Papert在“Perceptron”一书中从理论上证明单层感知器无法解决许多简单的问题，包括“异或(XOR)”问题。使得ANN理论的发展在197080年代处于低潮。F感知器的基本理论“线性不可分”问题的困境及其解决MarvinFF“异或(Exclusive-OR)”运算f(x,y)y01x001110F是一个双输入、单输出问题。对应的单层感知器为：FxFyFaFbFzFax+by=FxFyF无论如何选择参数a，b，都无法满足划分。这种由单层感知器不能表达的问题称为线性不可分问题。F“异或(Exclusive-OR)”运算f(x,y)y0F考虑n个自变量的二值函数，当n4时，线性不可分的函数个数远远超过线性可分函数的个数。自变量个数 函数的个数 线性可分函数的个数144216143256104465,5361,88254.3 10994,57261.8 10195,028,134F（R.O.Windner,1960）F表明单层感知器不能表达的问题的数量远远超过它可以表达的问题的数量。F考虑n个自变量的二值函数，当n4时，线性不可分的函数个数远FF解决途径多层网络F一个单层网络可以将空间划分成两部分，用多个单层网络组合在一起，并用其中的一个去综合其它单层网络的结果，构成一个二层网络，即可用来在空间划分出一个封闭或开放的凸域（子空间）。Fx1Fz0FxnFz1FznF解决途径多层网络一个单层网络可以将空间划分成两部分，用多FF非线性感知器非线性感知器F取权重函数为非线性函数的单级传感器系统。其学习过程涉及到求解非线性方程组的方法。FF高阶感知器高阶感知器F可线性化的非线性传感器系统。F非线性感知器高阶感知器F单层前向网、多层前向网与BP学习算法简介F单层前向网、多层前向网FF一、单层前向网络FF单层前向网模型单层前向网模型F 设有c 1个感知器，其中第k个感知器的输出为yk；对于输入信号x=(x1,x2,xn)，每个感知器有d个输入uj(x)，j=1,2,d。F1FkFcFx1FxnFx2Fu1(x)Fu2(x)Fud(x)Fx3Fwk1Fwk2Fwk3FykF输入层F输出层F一、单层前向网络单层前向网模型 设有c 1F一个单层前向网可表示为：F：激活函数；Fwk=(wk1,wk2,wkd)：第k个感知器的权重系数；Fk：第k个感知器的阈值；Fu=(u1,u2,ud)：基函数FxRn，u(x)RnF若记wk0=k，u0=1，则上式变换为：F一个单层前向网可表示为：激活函数；F 记yk(wk;x)为第k个感知器当权重系数为wkRd，输入为x Rn时的输出。F 设训练集为A=(x,t)|=1,2,N，其中 表示训练集数据编号，xRn为输入，tRc为输出，tk为第k个感知器的期望输出。F 基于训练集A的误差函数定义为：FF单层前向网的学习目标函数单层前向网的学习目标函数F 记yk(wk;x)为第k个感知器当权重系数为wkRdF学习的目标就是求wk，k=1,2,c，使得误差函数E(w)取最小值：F这就是目标函数F单层前向网的学习原理本质上仍是感知器的学习原理。F学习的目标就是求wk，k=1,2,c，使得误差函数E(FF线性单层前向网的解线性单层前向网的解F关于基函数u(x),对学习集的每一个数据，记：F其中=1,2,N。由此，定义学习集A的扩展集B：F线性单层前向网的解关于基函数u(x),对学习集的每一个数据，F不妨假设激活函数为恒等函数，此时网络为线性单层前向网。由此写出误差函数：F优化的目标函数为：F不妨假设激活函数为恒等函数，此时网络为线性单层前向网。由此F根据最小二乘法求解目标函数。F由多元函数取极值的必要条件，有：F根据最小二乘法求解目标函数。写成矩阵形式FFWW:c c(d d 1)1)FFU U:N N(d d 1)1)FFT:T:N N c cF写成矩阵形式W:c(d1)解的形式为：F解的形式为：层前向网络、BP学习算法双层前向网F多层前向网的结构特点：F1、允许网络具有数层相连的处理单元；F2、联结是从前一层的每一个节点到下一层所有节点，不存在其它联结；F3、同一层内的节点之间不存在联结；F4、不含任何反馈，故输出可以用输入和权重来表示。FL层神经网络：具有L层可调节权重参数F层前向网络、BP学习算法双层前向网多层前向网的结构特点：F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)F双层前向网模型：具有两层可调节参数且同层无联结的不含反馈的人工神经网络。FX层输入层FY层输出层FZ层隐层F两层可调节权重参数：W(1)、W(2)F12M21x1xNNx2y112cy2ycW(1)W(2)输F设输入层的输入为(x1,x2,xn)Rn。F首先考察隐层，设隐层神经元的激活函数为。第j个隐层神经元的整合函数为aj、输出值为zj：F第1层（隐层）权重矩阵中第i个输入联结到第j个隐神经元的权重F第j个隐神经元的阈值F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)F设输入层的输入为(x1,x2,xn)Rn。首先考F同样考察输出层，设输出层神经元的激活函数为。第k个输出神经元以z=(z1,z2,zM)RM为输入，其整合函数为bk、输出值为yk：F第2层（输出层）权重矩阵中第j个隐神经元联结到第k个输出神经元的权重F第k个输出神经元的阈值F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)F同样考察输出层，设输出层神经元的激活函数为。第k个输出神经F联合得到双层前向网的输出表达式：F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)F记为：F联合得到双层前向网的输出表达式：12M21x1xNNx2y1FF学习的目标函数学习的目标函数F为简化计，考虑两类的分类问题。F设A、B是分类空间Rd中两个不相交的集合。考虑离散型双层前向网T(W(1),W(2),(1),(2);x)，取其激活函数、为符号函数sgn(u)。F该双层前向网的学习目标是，对(A,B)求(W(1),W(2),(1),(2)使得：F求解上述方程。F学习的目标函数为简化计，考虑两类的分类问题。该双层前向网的学FF误差的后向传播误差的后向传播F多层前向网的学习原理：基于适当定义的误差函数，在网络中调整权重矩阵和阈值等参数，使得误差函数极小化。F与单层前向网和感知器相比较，多层前向网由于隐层的存在，无法判别隐层神经元对输入误差的直接影响（无法知道隐层神经元的理想输出值）。因此，对参数权重矩阵和阈值的调整遇到困难。F1F2FMF2F1Fx1FNFy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)Fx2FxNF误差的后向传播多层前向网的学习原理：基于适当定义的误差函数，F解决方案计算两个传播方向：F“前向传播(Forward propagation)”：输入xi进入网络，按照信息在网络中前进移动的方向，逐次计算aj，zj直至输出yk的过程；（输入向输出方向的前向传播）F“后向传播(Back propagation)”：利用输出层的误差来估计输出层的直接前导层的误差，再依次估计更前一层的误差，获得所有各层的误差估计。（输出误差向输入方向的后向传播）（Rumelhart,Hinton&Williams,1986）F1F2FMF2F1Fx1FNFy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)Fx2FxNF解决方案计算两个传播方向：12M21x1Ny112cF设学习集有T个样本，记为x,t，=1,2,T，其中：F输入F理想输出F计算实际输出，记为：F实际输出F设学习集有T个样本，记为x,t，=1,2,显然有：因此只需讨论某一个样本点的误差传播，以下略去上标 故误差函数为：F显然有：因此只需讨论某一个样本点的误差传播，以下略去上标 F已知下列记号：F又定义第k个输出神经元和第j个隐层神经元的误差率为：F输出层误差率F隐层误差率F已知下列记号：又定义第k个输出神经元和第j个隐层神经元的误差F由微分链式法则，计算可得：F输出层误差率F隐层误差率F由微分链式法则，计算可得：输出层误差率隐层误差率F因此得到：F因此得到：FF梯度法求解wij(l)F取步长因子为固定步长，得到学习规则：F其中k(2)、k(1)均与有关，k=1,2,c；j=0,1,M；i=0,1,N。F梯度法求解wij(l)其中k(2)、k(1)均与有关，大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法F大纲学习主体遗传算法F遗传算法的基本理论是借鉴自然界生物从简单到复杂、低级到高级的优胜劣汰、适者生存的进化机制，其本质是一种求解优化问题的高效并行全局搜索方法。F遗传算法的主要计算过程是：从随机产生的一个初始种群开始，通过一些算子（选择、交叉、变异）的作用，产生下一代种群，再以新产生的种群为出发点，重复上述过程，直到满足结束准则为止。F遗传算法（GA）把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。F遗传算法遗传算法的基本理论是借鉴自然界生物从简单到复杂、低级遗传算法流程F（3）依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；F（4）按照一定的交叉概率和交叉方法，生成新的个体；F（5）按照一定的变异概率和变异方法，生成新的个体；F（6）由交叉和变异产生新一代的种群，返回第2步。F（1）随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；F（2）计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3步；F遗传算法流程（3）依据适应度选择再生个体，适应度高的个体被选交叉算子和变异算子F单点交叉：交叉掩码以连续的n个1开始，后面跟随必要个数的0直至结束。F两点交叉：交叉掩码以n0个0开始，后面跟随n1个1，再跟随必要数量的0结束。F均匀交叉：产生一个随机的位串，每一位的选区都是随机的并且独立于其他位。F点变异：某一点取反F交叉算子和变异算子单点交叉：交叉掩码以连续的n个1开始，后面基本遗传算法 基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。F基本遗传算法 基本遗传算法（Simple 基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数F基本遗传算法的组成（1）编码（产生初始种群）编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。F 编码 GA是通过某种编码机制把对函数优化示例 F求下列一元函数的最大值：F FFx-1,2 ，求解结果精确到6位小数。F函数优化示例 求下列一元函数的最大值：x-1,2 ，SGA对于本例的编码 F 由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。FSGA对于本例的编码 由于区间长度为几个术语 F基因型：1000101110110101000111 表现型：0.637197 F编码F解码F个体（染色体）F基因F几个术语 基因型：100010111011010100011初始种群 F SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。F初始种群 SGA采用随机方法生成若干 适应度函数 F 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。F 适应度函数 遗传算法对一个个体（解选择算子F 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。F选择算子 遗传算法使用选择运算来实现对轮盘赌选择方法F 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：F轮盘赌选择方法 轮盘赌选择又称比例选择算子，它轮盘赌选择方法的实现步骤F（1）计算群体中所有个体的适应度函数值（需要解码）；F（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；F（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。F轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函交叉算子 F 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。F交叉算子 所谓交叉运算，是指对两个相单点交叉运算 F交叉前：F00000|01110000000010000F11100|00000111111000101F交叉后：F00000|00000111111000101F11100|01110000000010000F交叉点F单点交叉运算 交叉前：交叉点变异算子 F 所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。F变异算子 所谓变异运算，是指依据变异基本位变异算子 F 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。F基本位变异算子 基本位变异算子是指对基本位变异算子的执行过程 F变异前：F000001110000000010000F变异后：F000001110001000010000F变异点F基本位变异算子的执行过程 变异前：变异点运行参数 F（1）M ：种群规模 F（2）T ：遗传运算的终止进化代数 F（3）Pc ：交叉概率 F（4）Pm：变异概率 F运行参数（1）M ：种群规模 SGA的框图 F产生初始群体F是否满足停止准则F是F输出结果并结束F计算个体适应度值F比例选择运算F单点交叉运算F基本位变异运算F否F产生新一代群体F执行M/2次FSGA的框图 产生初始群体是否满足停止准则是输出结果并结束计大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法F大纲学习主体Swarm Intelligence Swarm Intelligence(SI)的概念最早由Beni、Hackwood和在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz 在他们的著作Swarm Intelligence:From Natural to Artificial Systems中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。FSwarm Intelligence SwaSwarm Intelligence(续)Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。蚂蚁成群则有利于寻找食物，因为任一只蚂蚁发现食物都可带领蚁群来共同搬运和进食。一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。FSwarm Intelligence(续)SwarSwarm Intelligence(续)信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能（关于适应性与智能之间的关系存在着一些争议，Fogel认为智能就是具备适应的能力），也就是说动物个体通过聚集成群而涌现出了智能。因此，Bonabeau 将SI的定义进一步推广为：无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。这里我们关心的不是个体之间的竞争，而是它们之间的协同。FSwarm Intelligence(续)信息的交互Swarm Intelligence(续)James Kennedy和Russell C.Eberhart在2001年出版了Swarm Intelligence，是群智能发展的一个重要历程碑，因为此时已有一些群智能理论和方法得到了应用。他们不反对Bonabeau关于SI定义，赞同其定义的基本精神，但反对定义中使用“主体”一词。其理由是“主体”所带有自治性和特殊性是许多Swarm的个体所不具备和拥有的，这将大大限制Swarm的定义范围。他们认为暂时无法给出合适的定义，赞同由Mark Millonas（1994）提出的构建一个SI系统所应满足的五条基本原则：FSwarm Intelligence(续)James Swarm Intelligence(续)1 Proximity Principle:群内个体具有能执行简单的时间或空间上的评估和计算的能力。2 Quality Principle:群内个体能对环境（包括群内其它个体）的关键性因素的变化做出响应。3 Principle of Diverse Response:群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。4 Stability Principle:不是每次环境的变化都会导致整个群体的行为模式的改变。5 Adaptability Principle:环境所发生的变化中，若出现群体值得付出代价的改变机遇，群体必须能够改变其行为模式。FSwarm Intelligence(续)1 ProSwarm Intelligence(续)Swarm Intelligence最重要的观点是：Mind is social，也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已取得成功的两种基于SI的优化算法是蚁群算法和粒子群算法。FSwarm Intelligence(续)Swarm Intelligence(续)目前，已有的基于SI的优化算法都是源于对动物社会通过协作解决问题行为的模拟，它主要强调对社会系统中个体之间相互协同作用的模拟。这一点与EC不同，EC是对生物演化中适者生存的模拟。与EC一样的是，SI的目的并不是为了忠实地模拟自然现象，而是利用他们的某些特点去解决实际问题。另一个与EC的相同点是,基于SI的优化算法也是概率搜索算法。FSwarm Intelligence(续)目前，已Swarm Intelligence(续)目前，已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法，更重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析,群智能理论及应用研究都是具有重要学术意义和现实价值的。FSwarm Intelligence(续)目前，已Swarm Intelligence(续)由于SI的理论依据是源于对生物群落社会性的模拟，因此其相关数学分析还比较薄弱，这就导致了现有研究还存在一些问题。首先，群智能算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论性分析，算法中涉及的各种参数设置一直没有确切的理论依据，通常都是按照经验型方法确定，对具体问题和应用环境的依赖性比较大。其次，同其它的自适应问题处理方法一样，群智能也不具备绝对的可信性，当处理突发事件时,系统的反应可能是不可测的,这在一定程度上增加了其应用风险。另外,群智能与其它各种先进技术(如:神经网络、模糊逻辑、禁忌搜索和支持向量机等)的融合还不足。FSwarm Intelligence(续)由于SI的蚁群算法 蚁群算法（Ant Colony Optimization,ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。F蚁群算法 蚁群算法（Ant Colony Optimiz蚁群算法(续)ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。F蚁群算法(续)ACO算法设计虚拟的“蚂蚁”，让它们摸索蚁群算法(续)F蚁群算法(续)大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法F大纲学习主体 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。PSO算法简介 F 粒子群算法(particle swarm optimiPSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以概述如下理论的最基本的思想可以概述如下：我们把系统中的成员称为具有适应性的主体(Adaptive Agent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。FPSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以复杂适应系统（CAS）续CAS的四个基本特点：的四个基本特点：首先，首先，主体(Adaptive Agent)是主动的、活的实体；其次，其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；再次，再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；最后，最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。F复杂适应系统（CAS）续CAS的四个基本特点：PSO产生背景之二:人工生命 人工生命“是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容：研究如何利用计算技术研究生物现象；研究如何利用生物技术研究计算问题(Nature Computation)。我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧，例如,人工神经网络是简化的大脑模型.遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统：社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做群智能。FPSO产生背景之二:人工生命 人工生命“基本PSO算法 粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。F基本PSO算法 粒子群优化算法源于1987年Rey基本PSO算法（续）Reynolds仅仅将其作为CAS的一个实例作仿真研究，而并未将它用于优化计算中。Kennedy和Eberhart在中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。F基本PSO算法（续）Reynolds仅仅将其作基本PSO算法(续)PSO中，每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子(Particle)”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索.PSO 初始化为一群随机粒子。然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值pBest.另一个极值是整个种群目前找到的最优解。这个极值是全局极值gBest。另外,也可以不用整个种群而只是用其中一部分的邻居。F基本PSO算法(续)PSO中，每个优化问题的解都基本PSO算法(续)PSO算法数学表示如下：设搜索空间为D维，总粒子数为n。第i个粒子位置表示为向量Xi=(xi1,xi2,xiD)；第i个粒子“飞行”历史中的过去最优位置（即该位置对应解最优）为Pi=(pi1,pi2,piD)，其中第g个粒子的过去最优位置Pg为所有Pi(i=1,n)中的最优；第i个粒子的位置变化率（速度）为向量Vi=(vi1,vi2,viD)。每个粒子的位置按如下公式进行变化（“飞行”）：F基本PSO算法(续)PSO算法数学表示如下：基本PSO算法(续)F（1）F（2）F其中，C1,C2为正常数，称为加速因子；rand()为0，1之间的随机数；w称惯性因子，w较大适于对解空间进行大范围探查(exploration)，w较小适于进行小范围开挖(exploitation)。第d（1dD）维的位置变化范围为-XMAXd,XMAXd，速度变化范围为-VMAXd,VMAXd，迭代中若位置和速度超过边界范围则取边界值。F基本PSO算法(续)（1）其中，C1,C2为正常数，称为加速基本PSO算法(续)粒子群初始位置和速度随机产生，然后按公式(1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群(Local)内历史最优Pl调整位置，即公式(2)中Pgd换为Pld。F基本PSO算法(续)粒子群初始位置和速度随机产生，然后PSO与与EC的异同的异同 首先，PSO和EC所模拟的自然随机系统不一样。EC是模拟生物系统进化过程，其最基本单位是基因，它在生物体的每一代之间传播；而PSO模拟的是社会系统的变化，其最基本单位是“敏因”（Meme），这一词由Dawkin在The Selfish Gene一书中提出，它是指思想文化传播中的基本单位，个体在社会中会根据环境来改变自身的思想，Meme的传播途径是在个体与个体之间，在实际人类社会中它还可以在人脑与书本之间、人脑与计算机、计算机与计算机之间传播。FPSO与EC的异同 首先，PSO和EC所模拟的自然随机PSO与与EC的异同（续）的异同（续）其次，EC中强调“适者生存”，不好的个体在竞争中被淘汰；PSO强调“协同合作”，不好的个体通过学习向好的方向转变，不好的个体被保留还可以增强群体的多样性。EC中最好的个体通过产生更多的后代来传播自己的基因，而PSO中的最佳个体通过吸引其它个体向它靠近来传播自己的敏因。FPSO与EC的异同（续）其次，EC中强调“适者生存”，不好PSO与与EC的异同（续）的异同（续）再次，EC中的上一代到下一代转移概率只与上一代的状态相关，而与历史无关，它的个体只包含当前信息，其群体的信息变化过程是一个Markov链过程；而PSO中的个体除了有着位置和速度外，还有着过去的历史信息（pBest、gBest），也就是具有记忆能力，上一代到下一代转移概率不仅与上一代的状态相关，而且与过去的历史相关，如果仅从群体的位置及速度信息来看，群体的信息变化过程不是一个Markov链过程。FPSO与EC的异同（续）再次，EC中的上一代到下一代转PSO与与EC的异同（续）的异同（续）最后，EC的迭代由选择、变异和交叉重组操作组成，而PSO的迭代中的操作是“飞行”。在某种程度上看，PSO的操作中隐含了选择、变异和交叉重组操作，gBest和pBest的更新可以类似一种弱选择；而粒子位置更新则类似于3个父代：Xi、gBest和pBest的之间重组，其中还包含了变异的成分。PSO中所隐含的变异是有偏好的，而并非通常的完全随机变异，这与最近对实际生物系统变异行为的新研究成果相符。FPSO与EC的异同（续）最后，EC的迭代由选择、变异和PSO与与EC的异同（续）的异同（续）EC和PSO所分别模拟的两个伟大的自然随机系统：Evolution和Mind之间存在着显著的差异，尽管它们都是基于群体的，都是由其中的随机成分带来创新，但其本质是不同的，因此不能将PSO简单地归类于EC中。FPSO与EC的异同（续）EC和PSO所分别模拟的两个本章完F本章完