1、第八章第八章 学习与进化模型本章内容建议自学参考:人工神经网络本章要求F掌握ANN的基本原理和思想F能够在Swarm和Repast中应用ANNF掌遗传算法的基本原理和思想F能够在Swarm和Repast中应用GA大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法学习Agent 一个学习Agent可以被认为既包含决定采取什么动作的执行元件执行元件，又包含修改执行元件使其能制定更好决策的学习元件学习元件。一个学习元件的设计受到下列三个主要因素的影响：w将要学习的是执行元件的哪个组成部分；w对学习这些组成部分而言，可得到什么反馈；w组
2、成部分是如何表示的。学习中可用的反馈类型学习中可用的反馈类型通常是决定智能体所面临的学习问题本质的最重要因素。一般分为三种类型：w有监督的从它的输入和输出的实例中学习一个函数。对于完全可观察的环境，智能体总能够观察到它的行动所带来的影响，因此可以采用有监督学习的方法来学习预测它们，对于部分可观察的环境，会困难一些。w无监督的在未提供明确的输出值的情况下，学习输入的模式。w强化学习从强化事物中进行学习，而不是根据教师所说的应该做什么进行学习。F学习系统设计的影响因素：如何表示学习到的知识；先验知识学习系统设计的影响因素：如何表示学习到的知识；先验知识的可用性。的可用性。归纳学习（1）确定性的有监
3、督的学习F纯归纳推理：给定f的实例集合，返回近似于f的函数hF函数h被称为假设，一个好的假设应该是一般化的，也就是说能够正确地预测未见过的实例。F例子（见板书）：使一个单变量函数能拟合某些数据点F假设空间H：选择最高次数为k的多项式集合F一致假设:和所有的实例数据一致。F如何在多个一致假设之间进行选择？F奥卡姆剃刀（Ockhams razor）原则:优先选择与数据一致的最简单的假设。F在假设的复杂度和数据拟合度之间进行折中是不可避免的F找到一个简单的一致假设的可能性或不可能性很强地依赖于对假设空间的选择。归纳学习（2）确定性的有监督的学习F找到一个简单的一致假设的可能性或不可能性很强地依赖于对
4、假设空间的选择。（假设空间的重要性）F如果假设空间包含真实的函数，那么学习的问题就是可实现的，否则就是不可实现的。F不幸的是，这是的函数是未知的，我们不能总是说出一个给定的学习问题是否可实现，一种避开这个障碍的方法是使用先验知识得到一个假设空间，我们可以确定一个真实的函数一定在该假设空间中，另外一种做法是采用最大可能的假设空间。学习决策树F决策树归纳是最简单的但是最成功的学习算法形式之一。F作为执行元件的决策树一棵决策树将用属性集合描述的事物或情景作为输入，并返回一个“决策”。输入的属性或输出值可以是离散的，也可以是连续的，学习一个离散值函数称为分类，学习一个连续函数称为回归。实例说明：决定是
5、否要等座位的决策树F从实例中归纳决策树强化学习 所谓强化学习是指从环境状态到动作映射的学习，以使动作从环境中获得的累积奖赏值最大。该方法不同于监督学习技术那样通过正例、反例来告知采取何种行动，而是通过试错（trial-and-error）来发现最优行为策略。从20世纪80年代末开始，随着对强化学习的数学基础研究取得突破性进展后，对强化学习的研究和应用日益开展起来，成为目前机器学习领域的研究重点之一。强化学习的框架结构Agent由状态感知器I、学习器L和动作选择器P三模块组成。F状态感知器I把环境状态s映射成Agent内部感知i；F动作选择器P根据当前策略选择动作a作用于环境W；F学习器L根据环
6、境状态的奖赏值r以及内部感知i，更新Agent的策略知识。W在动作a的作用下将导致环境状态变迁到s。强化学习技术的基本原理是：如果Agent的某个动作导致环境正的奖赏（强化信号），那么Agent以后产生这个动作的趋势便会加强，反之Agent产生这个动作的趋势渐弱。Q-学习FQ-学习是由Watkins提出的一种模型无关的强化学习算法，又称为离策略TD学习（off-policy TD）。F由于在一定条件Q-学习只需采用贪婪策略即可保证收敛，因此Q-学习是目前最有效的模型无关强化学习算法。Q-学习算法流程F对每个 初始化 为0),(asQas,F观察当前状态sF一直重复做：F(1)选择一个动作 并执
7、行它F(2)接收到立即回报F(3)观察新状态F(4)按照下式更新表项：F ar s ss),(max),(asQrasQaF(5)Q-学习（例子）悬崖步行是由Sutton提出的一个Agent仿真试验环境，如图所示。智能体的任务是从起始点S移动到目标点G。S、G之间的阴影方格为悬崖，智能体移动到这个区域就有坠崖的危险，因此如果进入这个区域，就给它一个大的惩罚r1000；如果到达G，就给它一个大的奖赏r100，其它情况给它一个回报r-0.1。通过学习，智能体可以找到一条既安全又不浪费移动步数的路径，通过对奖赏值的调整，智能体可以找到最安全或者最短的路径。大纲F学习主体FANNF遗传算法F群体智能F
8、粒子群优化算法人工智能的联结主义流派F 又称仿生学派，认为人工智能源于仿生学，人思维的基本单元是神经元，而非符号处理过程，主张用大脑工作模式取代符号操作的电脑工作模式；F 智能的本质是联结机制。神经网络是一个由大量简单的处理单元组成的高度复杂的大规模非线性自适应系统；F “结构功能”的研究方法：认为功能、结构和智能行为是密切相关的；F1943年，McCulloch和Pitts从神经元入手研究神经网络模型MP模型。此为人工神经网络研究之始。F人工神经网络（Artificial Neural Network，ANN）从四个方面刻画人脑的基本特征：F（1）F模仿生物神经元的功能，构造人工神经元的联结
9、网络FCell bodyFAxonFNucleusFSynapseF突触FDendriteF树突F（2）F人脑神经元既有局部的计算和存储功能，又通过联结构成统一的系统，人脑的计算建立在该系统的大规模并行模拟处理基础之上。FANN以具有局部计算能力的神经元为基础，同样实现信息的大规模并行处理。F（3）F大脑对信息的记忆是通过改变突触的强度来实现并分布存储。FANN模拟信息的大规模分布存储。F后天的训练使得人脑具有很强的自组织和自适应性。FANN根据人工神经元网络的结构特性，使用不同的训练过程，自动从“实践”（即训练样本）中获取相关知识，并存储在系统中。ANN是基于联结主义流派的人工智能F 联结主
10、义学派与高速发展的计算机技术相结合，发展为计算智能学派，是人工智能在1980年代后的深化和发展；F 计算智能：借助现代计算机技术模拟人的智能控制、生命演化过程和人的智能行为，从而进行信息获取、处理、应用的理论和方法；F 计算智能是以数学模型、计算模型为基础，以分布、并行、仿生计算为特征，包含数据、算法和实现的信息系统；F 计算智能强调模型的建立和构成，强调系统的自组织、自学习和自适应；F 计算智能的3个主要分支：F （模拟智能产生与作用赖以存在的结构）F （模拟生命生成过程与智能进化过程）F （模拟智能的表现行为）人工神经网络概述F人工神经网络是受生物神经网络的启发构造而成。FJames（心理
11、学，1890年）：大脑皮层每一点的活力产生于其它点势能释放的综合效能，即其它点的兴奋次数、强度和所接受的能量。F大脑含约1011个神经元，它们通过1015个联结构成一个网络。每个神经元具有独立的接受、处理和传递电化学信号的能力，这种传递由神经通道来完成。F树突从细胞体伸向其它神经元，神经元之间的接受信号的联结点为突触。通过突触输入的信号起着兴奋/抑制作用。当细胞体接受的累加兴奋作用超过某阈值时，细胞进入兴奋状态，产生冲动，并由轴突输出。FCell bodyFAxonFNucleusFSynapseF突触FDendriteF树突神经元系统的基本特征F 神经元及其联结F 神经元之间的联结强度决定信
12、号传递的强弱F 神经元之间的联结强度可以随训练而改变F 信号分为兴奋型和抑制型F 一个神经元接受的信号的累计效果决定该神经元的状态F 每个神经元有一个阈值人工神经网络的几种形式无反馈前向网F多输入、多输出的多层无环图，同一层间无联结F神经元分层排列，组成输入层、中间层（隐层）、输出层有反馈前向网F从输出层到输入层存在反馈的前向网。层内有联结的前向网F在无反馈前向网中同一层内存在神经元间的联结回路有向网F任意两个神经元间都可能存在有向联结。F网络处在动态中，直至达到某一平衡态、周期态或者混沌状态F感知器（Perceptron）是最早被设计并实现的人工神经网络。FW.McCulloch和W.Pit
13、ts总结生物神经元的基本生理特征，提出一种简单的数学模型与构造方法，建立了阈值加权和模型，简称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 神经元及其联结F 神经元之间的联结强度决定信号传递的强弱F 神经元之间的联结强度可以随训练而改变F 信号分为兴
14、奋型和抑制型F 一个神经元接受的信号的累计效果决定该神经元的状态 每个神经元有一个阈值F突触F树突F突触F树突F内核F轴突F模拟神经元的首要目标：输入信号的加权和F人工神经元可以接受一组来自系统中其它神经元的输入信号，每个输入对应一个权，所有输入的加权和决定该神经元的激活状态。每个权就相当于突触的联结强度。Fw1Fwi xiFw2FwnFx1Fx2FxnXWxwXuii)(F多输入、单输出的加权和结构F设X=(x1,x2,xn)表示n个输入，W=(w1,w2,wn)表示它们对应的联结权重。F故神经元所获得的输入信号累计效果为：xwxwxuniii,1Fw1Fwi xiFw2FwnFx1Fx2F
15、xnXWxwXuii)(F称u(x)为整合函数神经元获得网络输入信号后，信号累计效果整合函数u(x)大于某阈值 时，神经元处于激发状态；反之，神经元处于抑制状态构造激活函数，用于表示这一转换过程。要求是-1,1之间的单调递增函数激活函数通常为3种类型，由此决定了神经元的输出特征F（1）激活函数为符号函数：0,10,1)sgn()(uuuuF1F-1FuFF（2）激活函数为分段线性函数：21,12121,21,1)(uuuuuF1F-1FuFF（3）激活函数为Sigmoid函数，其特点是单调递增、光滑且具有渐近值，具有解析上的优点和神经生理学特征。112)(ueuuueeu11)(FF1F-1F
16、uF将人工神经元的基本模型与激活函数结合，即McCulloch Pitts模型。Fw1F Fu=wixiFw2FwnFx1Fx2Fxny=(u(x)-)niiixwxuy1FANN可以学会它表达的任何东西。（Rosenblatt，1962年）FANN的表达能力有限，其学习能力也受到限制。FANN的学习过程就是训练过程，在将训练样本集输入到网络的过程中，按照一定的方式来调整神经元之间的联结权重值，使得网络能够将训练样本集的内涵以联结权重矩阵的方式存储起来，从而使得网络在接受输入时，能够给出适当的输出。F有监督的学习（Supervised learning）F无监督的学习（Unsupervised
17、 learning）F感知器的学习是有监督的学习。学习的问题归结为求权重系数W=(w1,w2,wn)和阈值的问题。F基本思想：逐步将训练集中的样本输入到网络中，根据输出结果和理想输出之间的差别来调整网络中的权重值。Fw1F Fu=wixiFw2FwnFx1Fx2FxnFy=(u(x)-)F设X=(x1,x2,xn)表示n个输入，W=(w1,w2,wn)表示它们对应的联结权重。假设取符号函数为激活函数，F此为经典的M-P模型：0,10,1)sgn()(uuuuFw1FFu=wixiFw2FwnFx1Fx2FxnF+1 or-10,10,1),sgn()(sgn(uuxwxuy训练集的样本（输入向
18、量、输出值）为：txxxX,.,21tyyyY,.,21t为样本数目。其中，tkxxxxknkkk,.,2,1,.,21tkyk,.,2,11FMarvin 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年代
19、处于低潮。othersyxifyxf,1,0),(f(x,y)y01x001110F是一个双输入、单输出问题。对应的单层感知器为：FxFyFaFbFzFax+by=FxFyF无论如何选择参数a，b，都无法满足划分。这种由单层感知器不能表达的问题称为线性不可分问题。F考虑n个自变量的二值函数，当n4时，线性不可分的函数个数远远超过线性可分函数的个数。自变量个数 函数的个数 线性可分函数的个数144216143256104465,5361,88254.3 10994,57261.8 10195,028,134F（R.O.Windner,1960）F表明单层感知器不能表达的问题的数量远远超过它可以表
20、达的问题的数量。F一个单层网络可以将空间划分成两部分，用多个单层网络组合在一起，并用其中的一个去综合其它单层网络的结果，构成一个二层网络，即可用来在空间划分出一个封闭或开放的凸域（子空间）。Fx1Fz0FxnFz1FznF取权重函数为非线性函数的单级传感器系统。其学习过程涉及到求解非线性方程组的方法。F可线性化的非线性传感器系统。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一个单层
21、前向网可表示为：ckxuwxuwxykkkdjjkjk,.,2,1)(,1F：激活函数；Fwk=(wk1,wk2,wkd)：第k个感知器的权重系数；Fk：第k个感知器的阈值；Fu=(u1,u2,ud)：基函数FxRn，u(x)RnF若记wk0=k，u0=1，则上式变换为：ckxuwxydjjkjk,.,2,10F 记yk(wk;x)为第k个感知器当权重系数为wkRd，输入为x Rn时的输出。F 设训练集为A=(x,t)|=1,2,N，其中 表示训练集数据编号，xRn为输入，tRc为输出，tk为第k个感知器的期望输出。F 基于训练集A的误差函数定义为：NckkkktxwywE112;21)(F学
22、习的目标就是求wk，k=1,2,c，使得误差函数E(w)取最小值：)(minwEAF这就是F单层前向网的学习原理本质上仍是感知器的学习原理。F关于基函数u(x),对学习集的每一个数据，记：dduuuxuxuxuu,.,)(),.,(),(2121F其中=1,2,N。由此，定义学习集A的扩展集B：NtuB,.,2,1),(F不妨假设激活函数为恒等函数，此时网络为线性单层前向网。由此写出误差函数：NckkkdjjkjNckkdjjkjtuwtuwwE112111202121)(F优化的目标函数为：)(minwEBF根据最小二乘法求解目标函数。F由多元函数取极值的必要条件，有：djckwwEkj,.
23、,1,0;,.,10)(jNdikikikjutuwwwE 10)(010 jNdikikiutuwNjkdiNjikiutuuw101写成矩阵形式UTUUWTTcdccddwwwwwwwwwW.102212011110NdNNdduuuuuuuuuU.102212011110NcNNcctttttttttT.212222111211解的形式为：1UUUTWTT双层前向网F多层前向网的结构特点：F1、允许网络具有数层相连的处理单元；F2、联结是从前一层的每一个节点到下一层所有节点，不存在其它联结；F3、同一层内的节点之间不存在联结；F4、不含任何反馈，故输出可以用输入和权重来表示。FL层神经网
24、络：具有L层可调节权重参数F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)F双层前向网模型：具有两层可调节参数且同层无联结的不含反馈的人工神经网络。FX层输入层FY层输出层FZ层隐层F两层可调节权重参数：W(1)、W(2)F设输入层的输入为(x1,x2,xn)Rn。F首先考察隐层，设隐层神经元的激活函数为。第j个隐层神经元的整合函数为aj、输出值为zj：MjazxwxwajjNiijiNijijij,.,2,10)1(1)1()1()1(jiwF第1层（隐层）权重矩阵中第i个输入联结到第j个隐神经元的权重
25、)1(jF第j个隐神经元的阈值F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)F同样考察输出层，设输出层神经元的激活函数为。第k个输出神经元以z=(z1,z2,zM)RM为输入，其整合函数为bk、输出值为yk：ckbyzwzwbkkMjjkjMjkjkjk,.,2,10)2(1)2()2()2(kjwF第2层（输出层）权重矩阵中第j个隐神经元联结到第k个输出神经元的权重F第k个输出神经元的阈值)2(kF1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X
26、)F隐层F(Z)F输出层F(Y)F联合得到双层前向网的输出表达式：F1F2FMF2F1Fx1FxNFNFx2Fy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)ckxwwxwwyMjNiijikjMjkNijijikjk,.,2,1,00)1()2(1)2(1)1()1()2(F记为：xWWTy;,)2()1()2()1(F为简化计，考虑两类的分类问题。F设A、B是分类空间Rd中两个不相交的集合。考虑离散型双层前向网T(W(1),W(2),(1),(2);x)，取其激活函数、为符号函数sgn(u)。BxAxxWWT,1,1);,()2()1()2()
27、1(F该双层前向网的学习目标是，对(A,B)求(W(1),W(2),(1),(2)使得：F求解上述方程。F多层前向网的学习原理：基于适当定义的误差函数，在网络中调整权重矩阵和阈值等参数，使得误差函数极小化。F与单层前向网和感知器相比较，多层前向网由于隐层的存在，无法判别隐层神经元对输入误差的直接影响（无法知道隐层神经元的理想输出值）。因此，对参数权重矩阵和阈值的调整遇到困难。F1F2FMF2F1Fx1FNFy1F1F2FcFy2FycFW(1)FW(2)F输入层F(X)F隐层F(Z)F输出层F(Y)Fx2FxNF解决方案计算两个传播方向：F“前向传播(Forward propagation)”
28、：输入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设学习集有T个样本，记为x,t，=1,2,T，其中：ccNNRttttRxxxx,.,.,212
29、1F输入F理想输出ccRyyyy,.,21F计算实际输出，记为：F实际输出显然有：2,11)()(lwEwETlijlij因此只需讨论某一个样本点的误差传播，以下略去上标 故误差函数为：TckkkTcTtyyyyEEE112121121,.,MjazxwxwajjNiijiNijijij,.,2,10)1(1)1()1(ckbyzwzwbkkMjjkjMjkjkjk,.,2,10)2(1)2()2(F已知下列记号：F又定义第k个输出神经元和第j个隐层神经元的为：MjaEckbEjjkk,.,2,1,.,2,1,)1()2(F输出层误差率F隐层误差率F由微分链式法则，计算可得：ckkkjjjjc
30、kjkkkkjjwaazzbbyyEaE1)2()2(1)1(F输出层误差率F隐层误差率kkkkkkkyEbbyyEbE)2(F因此得到：ijjijjjijkkjkkkjxwaaEwEzwbbEwE)1()1()1()2()2()2()2(k)1(j)1()2(jikjwEwE)2()1(ijijwEwEF取步长因子为固定步长，得到学习规则：TijjiTjkkjxwzw1)1()1(1)2()2(F其中k(2)、k(1)均与有关，k=1,2,c；j=0,1,M；i=0,1,N。大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法遗传算法F遗传算法的基本理论是借鉴自然界生物从简单到复杂、低
31、级到高级的优胜劣汰、适者生存的进化机制，其本质是一种求解优化问题的高效并行全局搜索方法。F遗传算法的主要计算过程是：从随机产生的一个初始种群开始，通过一些算子（选择、交叉、变异）的作用，产生下一代种群，再以新产生的种群为出发点，重复上述过程，直到满足结束准则为止。F遗传算法（GA）把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适
32、应环境的一个“染色体”上，它就是问题的最优解。遗传算法流程F（3）依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；F（4）按照一定的交叉概率和交叉方法，生成新的个体；F（5）按照一定的变异概率和变异方法，生成新的个体；F（6）由交叉和变异产生新一代的种群，返回第2步。F（1）随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；F（2）计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3步；交叉算子和变异算子单点交叉：交叉掩码以连续的n个1开始，后面跟随必要个数的0直至结束。两点交叉：交叉掩码以n0个
33、0开始，后面跟随n1个1，再跟随必要数量的0结束。均匀交叉：产生一个随机的位串，每一位的选区都是随机的并且独立于其他位。F点变异：某一点取反基本遗传算法 基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数 编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色
34、体则是由基因排成的串。SGA使用二进制串进行编码。函数优化示例 F求下列一元函数的最大值：F 0.2)10sin()(xxxfSGA对于本例的编码 F 由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3106等份。又因为221 3106 222，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间-1，2内对应的实数值转化为一个二进制串（b21b20b0）。几个术语 F基因型：1000101110110101000111 F编码F解码F个体（染色体）F基因初始种群 F SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群
35、规模。适应度函数 F 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。选择算子F 遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。轮盘赌选择方法F 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为
36、n，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为：niiiiFFP1/轮盘赌选择方法的实现步骤F（1）计算群体中所有个体的适应度函数值（需要解码）；F（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；F（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。交叉算子 F 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。S
37、GA中交叉算子采用单点交叉算子。单点交叉运算 F交叉前：F00000|01110000000010000F11100|00000111111000101F交叉后：F00000|00000111111000101F11100|01110000000010000F交叉点变异算子 F 所谓变异运算，是指依据变异概率 Pm 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。基本位变异
38、算子 F 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。基本位变异算子的执行过程 F变异前：F000001110000000010000F变异后：F000001110001000010000F变异点运行参数 F（1）M ：种群规模 F（2）T ：遗传运算的终止进化代数 F（3）Pc ：交叉概率 F（4）Pm：变异概率 SGA的框图 F产生初始群体F是否满足停止准则F是F输出结果并结束F计算个体适应度值F比
39、例选择运算F单点交叉运算F基本位变异运算F否F产生新一代群体F执行M/2次大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法Swarm Intelligence Swarm Intelligence(SI)的概念最早由Beni、Hackwood和在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz 在他们的著作Swarm Intelligence:From Natural to Artificial Systems中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：
40、任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。Swarm Intelligence(续)Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。蚂蚁成群则有利于寻找食物，因为任一只蚂蚁发现食物都可带领蚁群来共同搬运和进食。一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很
41、好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。Swarm Intelligence(续)信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能（关于适应性与智能之间的关系存在着一些争议，Fogel认为智能就是具备适应的能力），也就是说动物个体通过聚集成群而涌现出了智能。因此，Bonabeau 将SI的定义进一步推
42、广为：无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。这里我们关心的不是个体之间的竞争，而是它们之间的协同。Swarm Intelligence(续)James Kennedy和Russell C.Eberhart在2001年出版了Swarm Intelligence，是群智能发展的一个重要历程碑，因为此时已有一些群智能理论和方法得到了应用。他们不反对Bonabeau关于SI定义，赞同其定义的基本精神，但反对定义中使用“主体”一词。其理由是“主体”所带有自治性和特殊性是许多Swarm的个体所不具备和拥有的，这将大大限制Swarm的定义范围。他们认为暂时无法给出合适的定义，赞
43、同由Mark Millonas（1994）提出的构建一个SI系统所应满足的五条基本原则：Swarm Intelligence(续)1 Proximity Principle:群内个体具有能执行简单的时间或空间上的评估和计算的能力。2 Quality Principle:群内个体能对环境（包括群内其它个体）的关键性因素的变化做出响应。3 Principle of Diverse Response:群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。4 Stability Principle:不是每次环境的变化都会导致整个群体的行为模式的改变。5 Adaptability Principl
44、e:环境所发生的变化中，若出现群体值得付出代价的改变机遇，群体必须能够改变其行为模式。Swarm Intelligence(续)Swarm Intelligence最重要的观点是：Mind is social，也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已取得成功的两种基于SI的优化算法是蚁群算法和粒子群算法。Swarm Intellig
45、ence(续)目前，已有的基于SI的优化算法都是源于对动物社会通过协作解决问题行为的模拟，它主要强调对社会系统中个体之间相互协同作用的模拟。这一点与EC不同，EC是对生物演化中适者生存的模拟。与EC一样的是，SI的目的并不是为了忠实地模拟自然现象，而是利用他们的某些特点去解决实际问题。另一个与EC的相同点是,基于SI的优化算法也是概率搜索算法。Swarm Intelligence(续)目前，已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法，更重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度
46、分析,群智能理论及应用研究都是具有重要学术意义和现实价值的。Swarm Intelligence(续)由于SI的理论依据是源于对生物群落社会性的模拟，因此其相关数学分析还比较薄弱，这就导致了现有研究还存在一些问题。首先，群智能算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论性分析，算法中涉及的各种参数设置一直没有确切的理论依据，通常都是按照经验型方法确定，对具体问题和应用环境的依赖性比较大。其次，同其它的自适应问题处理方法一样，群智能也不具备绝对的可信性，当处理突发事件时,系统的反应可能是不可测的,这在一定程度上增加了其应用风险。另外,群智能与其它各种先进技术(如:神经网络、模糊逻辑、禁忌搜
47、索和支持向量机等)的融合还不足。蚁群算法 蚁群算法（Ant Colony Optimization,ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法(续)ACO算法设计虚
48、拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。蚁群算法(续)大纲F学习主体FANNF遗传算法F群体智能F粒子群优化算法 粒子群算法(particle swarm optimization，
49、PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。PSO算法简介 PSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以概述如下理论的最基本的思想可以概述如下：我们把系统中的成员称为具有适应性的主体(Adaptive Agen
50、t)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。复杂适应系统（CAS）续CAS的四个基本特点：的四个基本特点：F首先，首先，主体(Adaptive Agent)是主动的、活的实体；F其次，其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；F再次，再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起
