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

第八章学习与进化模型本章内容建议自学参考:人工神经网络第八章学习与进化模型本章内容建议自学参考:人工神经网络本章要求掌握ANN的基本原理和思想能够在Swarm和Repast中应用ANN掌遗传算法的基本原理和思想能够在Swarm和Repast中应用GA本章要求掌握ANN的基本原理和思想大纲学习主体ANN遗传算法群体智能粒子群优化算法大纲学习主体大纲学习主体ANN遗传算法群体智能粒子群优化算法大纲学习主体学习Agent一个学习Agent可以被认为既包含决定采取什么动作的执行元件，又包含修改执行元件使其能制定更好决策的学习元件。一个学习元件的设计受到下列三个主要因素的影响：将要学习的是执行元件的哪个组成部分；对学习这些组成部分而言，可得到什么反馈；组成部分是如何表示的。学习Agent一个学习Agent可以被认为既包含学习中可用的反馈类型学习中可用的反馈类型通常是决定智能体所面临的学习问题本质的最重要因素。一般分为三种类型：有监督的从它的输入和输出的实例中学习一个函数。对于完全可观察的环境，智能体总能够观察到它的行动所带来的影响，因此可以采用有监督学习的方法来学习预测它们，对于部分可观察的环境，会困难一些。无监督的在未提供明确的输出值的情况下，学习输入的模式。强化学习从强化事物中进行学习，而不是根据教师所说的应该做什么进行学习。学习系统设计的影响因素：如何表示学习到的知识；先验知识的可用性。学习中可用的反馈类型学习中可用的反馈类型通常是决定智能体所面归纳学习（1）

——确定性的有监督的学习纯归纳推理：给定f的实例集合，返回近似于f的函数h函数h被称为假设，一个好的假设应该是一般化的，也就是说能够正确地预测未见过的实例。例子（见板书）：使一个单变量函数能拟合某些数据点假设空间H：选择最高次数为k的多项式集合一致假设:和所有的实例数据一致。如何在多个一致假设之间进行选择？？？奥卡姆剃刀（Ockham’srazor）原则:优先选择与数据一致的最简单的假设。在假设的复杂度和数据拟合度之间进行折中是不可避免的找到一个简单的一致假设的可能性或不可能性很强地依赖于对假设空间的选择。归纳学习（1）

——确定性的有监督的学习纯归纳推理：给定f的归纳学习（2）

——确定性的有监督的学习找到一个简单的一致假设的可能性或不可能性很强地依赖于对假设空间的选择。（假设空间的重要性）如果假设空间包含真实的函数，那么学习的问题就是可实现的，否则就是不可实现的。不幸的是，这是的函数是未知的，我们不能总是说出一个给定的学习问题是否可实现，一种避开这个障碍的方法是使用先验知识得到一个假设空间，我们可以确定一个真实的函数一定在该假设空间中，另外一种做法是采用最大可能的假设空间。归纳学习（2）

——确定性的有监督的学习找到一个简单的一致假学习决策树决策树归纳是最简单的但是最成功的学习算法形式之一。作为执行元件的决策树一棵决策树将用属性集合描述的事物或情景作为输入，并返回一个“决策”。输入的属性或输出值可以是离散的，也可以是连续的，学习一个离散值函数称为分类，学习一个连续函数称为回归。实例说明：决定是否要等座位的决策树从实例中归纳决策树学习决策树决策树归纳是最简单的但是最成功的学习算法形式之一。强化学习

所谓强化学习是指从环境状态到动作映射的学习，以使动作从环境中获得的累积奖赏值最大。该方法不同于监督学习技术那样通过正例、反例来告知采取何种行动，而是通过试错（trial-and-error）来发现最优行为策略。从20世纪80年代末开始，随着对强化学习的数学基础研究取得突破性进展后，对强化学习的研究和应用日益开展起来，成为目前机器学习领域的研究重点之一。强化学习所谓强化学习是指从环境状态到动作映射的学习，以使强化学习的框架结构Agent由状态感知器I、学习器L和动作选择器P三模块组成。状态感知器I把环境状态s映射成Agent内部感知i；动作选择器P根据当前策略选择动作a作用于环境W；学习器L根据环境状态的奖赏值r以及内部感知i，更新Agent的策略知识。W在动作a的作用下将导致环境状态变迁到s’。

强化学习技术的基本原理是：如果Agent的某个动作导致环境正的奖赏（强化信号），那么Agent以后产生这个动作的趋势便会加强，反之Agent产生这个动作的趋势渐弱。强化学习的框架结构Agent由状态感知器I、学习器L和动作选Q-学习Q-学习是由Watkins提出的一种模型无关的强化学习算法，又称为离策略TD学习（off-policyTD）。

由于在一定条件Q-学习只需采用贪婪策略即可保证收敛，因此Q-学习是目前最有效的模型无关强化学习算法。

Q-学习Q-学习是由Watkins提出的一种模型无关的强化学Q-学习算法流程对每个初始化为0观察当前状态一直重复做：(1)选择一个动作并执行它(2)接收到立即回报(3)观察新状态(4)按照下式更新表项：

(5)Q-学习算法流程对每个初始化Q-学习（例子）

悬崖步行是由Sutton提出的一个Agent仿真试验环境，如图所示。智能体的任务是从起始点S移动到目标点G。S、G之间的阴影方格为悬崖，智能体移动到这个区域就有坠崖的危险，因此如果进入这个区域，就给它一个大的惩罚r＝－1000；如果到达G，就给它一个大的奖赏r＝100，其它情况给它一个回报r＝-0.1。通过学习，智能体可以找到一条既安全又不浪费移动步数的路径，通过对奖赏值的调整，智能体可以找到最安全或者最短的路径。Q-学习（例子）悬崖步行是由Sutton提出的一个Ag大纲学习主体ANN遗传算法群体智能粒子群优化算法大纲学习主体人工智能的联结主义流派

又称仿生学派，认为人工智能源于仿生学，人思维的基本单元是神经元，而非符号处理过程，主张用大脑工作模式取代符号操作的电脑工作模式；智能的本质是联结机制。神经网络是一个由大量简单的处理单元组成的高度复杂的大规模非线性自适应系统；“结构－功能”的研究方法：认为功能、结构和智能行为是密切相关的；1943年，McCulloch和Pitts从神经元入手研究神经网络模型——MP模型。此为人工神经网络研究之始。人工智能的联结主义流派又称仿生学派，认为人工智能源于仿生人工神经网络（ArtificialNeuralNetwork，ANN）从四个方面刻画人脑的基本特征：（1）物理结构模仿生物神经元的功能，构造人工神经元的联结网络CellbodyAxonNucleusSynapse突触Dendrite树突人工神经网络（ArtificialNeuralNetwo（2）计算模拟人脑神经元既有局部的计算和存储功能，又通过联结构成统一的系统，人脑的计算建立在该系统的大规模并行模拟处理基础之上。ANN以具有局部计算能力的神经元为基础，同样实现信息的大规模并行处理。（3）存储与操作大脑对信息的记忆是通过改变突触的强度来实现并分布存储。ANN模拟信息的大规模分布存储。（4）训练后天的训练使得人脑具有很强的自组织和自适应性。ANN根据人工神经元网络的结构特性，使用不同的训练过程，自动从“实践”（即训练样本）中获取相关知识，并存储在系统中。（2）计算模拟ANN是基于联结主义流派的人工智能

联结主义学派与高速发展的计算机技术相结合，发展为计算智能学派，是人工智能在1980年代后的深化和发展；计算智能：借助现代计算机技术模拟人的智能控制、生命演化过程和人的智能行为，从而进行信息获取、处理、应用的理论和方法；计算智能是以数学模型、计算模型为基础，以分布、并行、仿生计算为特征，包含数据、算法和实现的信息系统；计算智能强调模型的建立和构成，强调系统的自组织、自学习和自适应；计算智能的3个主要分支：

人工神经网络（模拟智能产生与作用赖以存在的结构）

遗传算法（模拟生命生成过程与智能进化过程）

模糊逻辑（模拟智能的表现行为）ANN是基于联结主义流派的人工智能联结主义学派与高速发展人工神经网络概述人工神经网络是受生物神经网络的启发构造而成。James（《心理学》，1890年）：大脑皮层每一点的活力产生于其它点势能释放的综合效能，即其它点的兴奋次数、强度和所接受的能量。大脑含约1011个神经元，它们通过1015个联结构成一个网络。每个神经元具有独立的接受、处理和传递电化学信号的能力，这种传递由神经通道来完成。人工神经网络概述人工神经网络是受生物神经网络的启发构造而成。神经元的结构树突从细胞体伸向其它神经元，神经元之间的接受信号的联结点为突触。通过突触输入的信号起着兴奋/抑制作用。当细胞体接受的累加兴奋作用超过某阈值时，细胞进入兴奋状态，产生冲动，并由轴突输出。CellbodyAxonNucleusSynapse突触Dendrite树突神经元的结构CellbodyAxonNucleusSyna神经元系统的基本特征

神经元及其联结神经元之间的联结强度决定信号传递的强弱神经元之间的联结强度可以随训练而改变信号分为兴奋型和抑制型一个神经元接受的信号的累计效果决定该神经元的状态每个神经元有一个阈值神经元系统的基本特征人工神经网络的几种形式无反馈前向网多输入、多输出的多层无环图，同一层间无联结神经元分层排列，组成输入层、中间层（隐层）、输出层人工神经网络的几种形式无反馈前向网有反馈前向网从输出层到输入层存在反馈的前向网。有反馈前向网层内有联结的前向网在无反馈前向网中同一层内存在神经元间的联结回路层内有联结的前向网人工神经网络方法简介有向网任意两个神经元间都可能存在有向联结。网络处在动态中，直至达到某一平衡态、周期态或者混沌状态人工神经网络方法简介有向网感知器（Perceptron）——人工神经网络的基本构件7-第七章-学习与进化模型ANN课件感知器（Perceptron）是最早被设计并实现的人工神经网络。W.McCulloch和W.Pitts总结生物神经元的基本生理特征，提出一种简单的数学模型与构造方法，建立了阈值加权和模型，简称M-P模型(“ALogicalCalculusImmanentinNervousActivity”,BulletinofMathematicalBiophysics,1943(5):115~133）。人工神经元模型是M-P模型的基础。感知器的数学模型WarrenMcCulloch（1898－1969）WalterPitts(1923－1969)感知器（Perceptron）是最早被设计并实现的人工神经网生物神经元的基本特征神经元及其联结神经元之间的联结强度决定信号传递的强弱神经元之间的联结强度可以随训练而改变信号分为兴奋型和抑制型一个神经元接受的信号的累计效果决定该神经元的状态每个神经元有一个阈值突触树突轴突突触树突内核轴突生物神经元的基本特征树突轴突突触树突内核轴突人工神经网络方法简介模拟神经元的首要目标：输入信号的加权和人工神经元可以接受一组来自系统中其它神经元的输入信号，每个输入对应一个权，所有输入的加权和决定该神经元的激活状态。每个权就相当于突触的联结强度。w1

wixiw2wnx1x2xn人工神经元数学模型——多输入、单输出的加权和结构人工神经网络方法简介模拟神经元的首要目标：输入信号的加权和w设X=(x1,x2,…,xn)表示n个输入，W=(w1,w2,…,wn)表示它们对应的联结权重。故神经元所获得的输入信号累计效果为：w1

wixiw2wnx1x2xn称u(x)为整合函数设X=(x1,x2,…,xn)表示n个输入，W=人工神经网络方法简介感知器的激活函数神经元获得网络输入信号后，信号累计效果整合函数u(x)大于某阈值

时，神经元处于激发状态；反之，神经元处于抑制状态构造激活函数

，用于表示这一转换过程。要求

是[-1,1]之间的单调递增函数激活函数

通常为3种类型，由此决定了神经元的输出特征人工神经网络方法简介感知器的激活函数神经元获得网络输入信号后（1）激活函数

为符号函数：1-1u

（1）激活函数为符号函数：1-1u（2）激活函数

为分段线性函数：1-1u

（2）激活函数为分段线性函数：1-1u人工神经网络方法简介（3）激活函数

为Sigmoid函数，其特点是单调递增、光滑且具有渐近值，具有解析上的优点和神经生理学特征。

1-1u人工神经网络方法简介（3）激活函数为Sigmoid函数，其人工神经网络方法简介2.M-P模型将人工神经元的基本模型与激活函数

结合，即McCulloch–Pitts模型。w1

u=

wixiw2wnx1x2xny=

(u(x)-

)人工神经网络方法简介2.M-P模型w1u=wixiwANN可以学会它表达的任何东西。（Rosenblatt，1962年）ANN的表达能力有限，其学习能力也受到限制。ANN的学习过程就是训练过程，在将训练样本集输入到网络的过程中，按照一定的方式来调整神经元之间的联结权重值，使得网络能够将训练样本集的内涵以联结权重矩阵的方式存储起来，从而使得网络在接受输入时，能够给出适当的输出。有监督的学习（Supervisedlearning）无监督的学习（Unsupervisedlearning）感知器的学习算法ANN可以学会它表达的任何东西。（Rosenblatt，19感知器的学习是有监督的学习。学习的问题归结为求权重系数W=(w1,w2,…,wn)和阈值

的问题。基本思想：逐步将训练集中的样本输入到网络中，根据输出结果和理想输出之间的差别来调整网络中的权重值。w1

u=

wixiw2wnx1x2xny=

(u(x)-

)感知器的学习是有监督的学习。学习的问题归结为求权重系数W=设X=(x1,x2,…,xn)表示n个输入，W=(w1,w2,…,wn)表示它们对应的联结权重。假设取符号函数为激活函数

，此为经典的M-P模型：w1

u=

wixiw2wnx1x2xn+1or-1设X=(x1,x2,…,xn)表示n个输入，W=训练集的样本（输入向量、输出值）为：t为样本数目。其中，训练集的样本（输入向量、输出值）为：t为样本数目。其中，感知器的基本理论“线性不可分”问题的困境及其解决MarvinMinskyMITMediaLabandMITAILab

ToshibaProfessorofMediaArtsandSciences

ProfessorofE.E.andC.S.,M.I.T

minsky@1969年，Minsky和Papert在“Perceptron”一书中从理论上证明单层感知器无法解决许多简单的问题，包括“异或(XOR)”问题。使得ANN理论的发展在1970～80年代处于低潮。感知器的基本理论“线性不可分”问题的困境及其解决Marvin“异或(Exclusive-OR)”运算f(x,y)y01x001110是一个双输入、单输出问题。对应的单层感知器为：xyabzax+by=

xy无论如何选择参数a，b，

，都无法满足划分。这种由单层感知器不能表达的问题称为线性不可分问题。“异或(Exclusive-OR)”运算f(x,y)y0考虑n个自变量的二值函数，当n4时，线性不可分的函数个数远远超过线性可分函数的个数。自变量个数函数的个数线性可分函数的个数144216143256104465,5361,88254.310994,57261.810195,028,134（R.O.Windner,1960）表明单层感知器不能表达的问题的数量远远超过它可以表达的问题的数量。考虑n个自变量的二值函数，当n4时，线性不可分的函数个数远解决途径——多层网络一个单层网络可以将空间划分成两部分，用多个单层网络组合在一起，并用其中的一个去综合其它单层网络的结果，构成一个二层网络，即可用来在空间划分出一个封闭或开放的凸域（子空间）。x1z0xnz1zn解决途径——多层网络一个单层网络可以将空间划分成两部分，用多非线性感知器取权重函数为非线性函数的单级传感器系统。其学习过程涉及到求解非线性方程组的方法。高阶感知器可线性化的非线性传感器系统。非线性感知器高阶感知器单层前向网、多层前向网与BP学习算法简介单层前向网、多层前向网一、单层前向网络单层前向网模型

设有c

1个感知器，其中第k个感知器的输出为yk；对于输入信号x=(x1,x2,…,xn)，每个感知器有d个输入uj(x)，j=1,2,…,d。1kcx1xnx2u1(x)u2(x)ud(x)x3wk1wk2wk3yk输入层输出层一、单层前向网络单层前向网模型设有c1一个单层前向网可表示为：

：激活函数；wk=(wk1,wk2,…,wkd)：第k个感知器的权重系数；

k：第k个感知器的阈值；u=(u1,u2,…,ud)：基函数x

Rn，u(x)Rn若记wk0=

k

，u0=－1，则上式变换为：一个单层前向网可表示为：：激活函数；

记yk(wk;x)为第k个感知器当权重系数为wk

Rd，输入为x

Rn时的输出。设训练集为A={(x

,t

)|=1,2,…,N}，其中

表示训练集数据编号，x

Rn为输入，t

Rc为输出，tk

为第k个感知器的期望输出。基于训练集A的误差函数定义为：单层前向网的学习目标函数记yk(wk;x)为第k个感知器当权重系数为wkRd学习的目标就是求wk

，k=1,2,…,c，使得误差函数E(w)取最小值：这就是目标函数单层前向网的学习原理本质上仍是感知器的学习原理。学习的目标就是求wk，k=1,2,…,c，使得误差函数E(线性单层前向网的解关于基函数u(x),对学习集的每一个数据，记：其中

=1,2,…,N。由此，定义学习集A的扩展集B：线性单层前向网的解关于基函数u(x),对学习集的每一个数据，不妨假设激活函数

为恒等函数，此时网络为线性单层前向网。由此写出误差函数：优化的目标函数为：不妨假设激活函数为恒等函数，此时网络为线性单层前向网。由此根据最小二乘法求解目标函数。由多元函数取极值的必要条件，有：根据最小二乘法求解目标函数。写成矩阵形式W:c(d1)U:N(d1)T:N

c写成矩阵形式W:c(d1)解的形式为：解的形式为：层前向网络、BP学习算法双层前向网多层前向网的结构特点：1、允许网络具有数层相连的处理单元；2、联结是从前一层的每一个节点到下一层所有节点，不存在其它联结；3、同一层内的节点之间不存在联结；4、不含任何反馈，故输出可以用输入和权重来表示。L层神经网络：具有L层可调节权重参数层前向网络、BP学习算法双层前向网多层前向网的结构特点：12M21x1xNNx2y112cy2ycW(1)W(2)输入层(X)隐层(Z)输出层(Y)双层前向网模型：具有两层可调节参数且同层无联结的不含反馈的人工神经网络。X层——输入层Y层——输出层Z层——隐层两层可调节权重参数：W(1)、W(2)12M21x1xNNx2y112cy2ycW(1)W(2)输设输入层的输入为(x1,x2,…,xn)

Rn。首先考察隐层，设隐层神经元的激活函数为

。第j个隐层神经元的整合函数为aj、输出值为zj：第1层（隐层）权重矩阵中第i个输入联结到第j个隐神经元的权重第j个隐神经元的阈值12M21x1xNNx2y112cy2ycW(1)W(2)输入层(X)隐层(Z)输出层(Y)设输入层的输入为(x1,x2,…,xn)Rn。首先考同样考察输出层，设输出层神经元的激活函数为

。第k个输出神经元以z=(z1,z2,…,zM)RM为输入，其整合函数为bk、输出值为yk：第2层（输出层）权重矩阵中第j个隐神经元联结到第k个输出神经元的权重第k个输出神经元的阈值12M21x1xNNx2y112cy2ycW(1)W(2)输入层(X)隐层(Z)输出层(Y)同样考察输出层，设输出层神经元的激活函数为。第k个输出神经联合得到双层前向网的输出表达式：12M21x1xNNx2y112cy2ycW(1)W(2)输入层(X)隐层(Z)输出层(Y)记为：联合得到双层前向网的输出表达式：12M21x1xNNx2y1学习的目标函数为简化计，考虑两类的分类问题。设A、B是分类空间Rd中两个不相交的集合。考虑离散型双层前向网T(W(1),W(2),

(1),

(2);x)，取其激活函数

、

为符号函数sgn(u)。该双层前向网的学习目标是，对(A,B)求(W(1),W(2),

(1),

(2))使得：求解上述方程。学习的目标函数为简化计，考虑两类的分类问题。该双层前向网的学误差的后向传播多层前向网的学习原理：基于适当定义的误差函数，在网络中调整权重矩阵和阈值等参数，使得误差函数极小化。与单层前向网和感知器相比较，多层前向网由于隐层的存在，无法判别隐层神经元对输入误差的直接影响（无法知道隐层神经元的理想输出值）。因此，对参数权重矩阵和阈值的调整遇到困难。12M21

x1N

y112c

y2

yc

W(1)

W(2)输入层(X)隐层(Z)输出层(Y)

x2

xN误差的后向传播多层前向网的学习原理：基于适当定义的误差函数，解决方案——计算两个传播方向：“前向传播(Forwardpropagation)”：输入{xi}进入网络，按照信息在网络中前进移动的方向，逐次计算aj，zj直至输出{yk}的过程；（输入向输出方向的前向传播）“后向传播(Backpropagation)”：利用输出层的误差来估计输出层的直接前导层的误差，再依次估计更前一层的误差，获得所有各层的误差估计。（输出误差向输入方向的后向传播）（Rumelhart,Hinton&Williams,1986）12M21

x1N

y112c

y2

yc

W(1)

W(2)输入层(X)隐层(Z)输出层(Y)

x2

xN解决方案——计算两个传播方向：12M21x1Ny112c设学习集有T个样本，记为{x

,t

}，

=1,2,…,T，其中：输入理想输出计算实际输出，记为：实际输出设学习集有T个样本，记为{x,t}，=1,2,显然有：因此只需讨论某一个样本点的误差传播，以下略去上标

故误差函数为：显然有：因此只需讨论某一个样本点的误差传播，以下略去上标已知下列记号：又定义第k个输出神经元和第j个隐层神经元的误差率为：输出层误差率隐层误差率已知下列记号：又定义第k个输出神经元和第j个隐层神经元的误差由微分链式法则，计算可得：输出层误差率隐层误差率由微分链式法则，计算可得：输出层误差率隐层误差率因此得到：因此得到：梯度法求解wij(l)取步长因子为固定步长

，得到学习规则：其中

k(2)、

k(1)均与

有关，k=1,2,…,c；j=0,1,…,M；i=0,1,…,N。梯度法求解wij(l)其中k(2)、k(1)均与有关，大纲学习主体ANN遗传算法群体智能粒子群优化算法大纲学习主体遗传算法遗传算法的基本理论是借鉴自然界生物从简单到复杂、低级到高级的优胜劣汰、适者生存的进化机制，其本质是一种求解优化问题的高效并行全局搜索方法。遗传算法的主要计算过程是：从随机产生的一个初始种群开始，通过一些算子（选择、交叉、变异）的作用，产生下一代种群，再以新产生的种群为出发点，重复上述过程，直到满足结束准则为止。遗传算法（GA）把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。

遗传算法遗传算法的基本理论是借鉴自然界生物从简单到复杂、低级遗传算法流程（3）依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰；（4）按照一定的交叉概率和交叉方法，生成新的个体；（5）按照一定的变异概率和变异方法，生成新的个体；（6）由交叉和变异产生新一代的种群，返回第2步。（1）随机产生初始种群，个体数目一定，每个个体表示为染色体的基因编码；（2）计算个体的适应度，并判断是否符合优化准则，若符合，输出最佳个体及其代表的最优解，并结束计算；否则转向第3步；遗传算法流程（3）依据适应度选择再生个体，适应度高的个体被选交叉算子和变异算子单点交叉：交叉掩码以连续的n个1开始，后面跟随必要个数的0直至结束。两点交叉：交叉掩码以n0个0开始，后面跟随n1个1，再跟随必要数量的0结束。均匀交叉：产生一个随机的位串，每一位的选区都是随机的并且独立于其他位。点变异：某一点取反交叉算子和变异算子单点交叉：交叉掩码以连续的n个1开始，后面基本遗传算法

基本遗传算法（SimpleGeneticAlgorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。基本遗传算法基本遗传算法（Simple基本遗传算法的组成（1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数基本遗传算法的组成（1）编码（产生初始种群）

编码GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手，而染色体则是由基因排成的串。SGA使用二进制串进行编码。编码GA是通过某种编码机制把对函数优化示例求下列一元函数的最大值：

x∈[-1,2]，求解结果精确到6位小数。函数优化示例求下列一元函数的最大值：x∈[-1,2]，SGA对于本例的编码

由于区间长度为3，求解结果精确到6位小数，因此可将自变量定义区间划分为3×106等份。又因为221<3×106<222

，所以本例的二进制编码长度至少需要22位，本例的编码过程实质上是将区间[-1，2]内对应的实数值转化为一个二进制串（b21b20…b0）。SGA对于本例的编码由于区间长度为几个术语基因型：1000101110110101000111表现型：0.637197编码解码个体（染色体）基因几个术语基因型：100010111011010100011初始种群SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。初始种群SGA采用随机方法生成若干

适应度函数

遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。适应度函数遗传算法对一个个体（解选择算子

遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。选择算子遗传算法使用选择运算来实现对轮盘赌选择方法

轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n，个体i的适应度为Fi，则个体i被选中遗传到下一代群体的概率为：轮盘赌选择方法轮盘赌选择又称比例选择算子，它轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函数值（需要解码）；（2）利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3）采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体的概率进行匹配）来确定各个个体是否遗传到下一代群体中。轮盘赌选择方法的实现步骤（1）计算群体中所有个体的适应度函交叉算子

所谓交叉运算，是指对两个相互配对的染色体依据交叉概率Pc按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。SGA中交叉算子采用单点交叉算子。交叉算子所谓交叉运算，是指对两个相单点交叉运算交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉点单点交叉运算交叉前：交叉点变异算子

所谓变异运算，是指依据变异概率Pm将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。SGA中变异算子采用基本位变异算子。变异算子所谓变异运算，是指依据变异基本位变异算子

基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0。基本位变异算子基本位变异算子是指对基本位变异算子的执行过程变异前：000001110000000010000变异后：000001110001000010000变异点基本位变异算子的执行过程变异前：变异点运行参数（1）M：种群规模（2）T：遗传运算的终止进化代数（3）Pc：交叉概率（4）Pm：变异概率运行参数（1）M：种群规模SGA的框图产生初始群体是否满足停止准则是输出结果并结束计算个体适应度值比例选择运算单点交叉运算基本位变异运算否产生新一代群体执行M/2次SGA的框图产生初始群体是否满足停止准则是输出结果并结束计大纲学习主体ANN遗传算法群体智能粒子群优化算法大纲学习主体SwarmIntelligenceSwarmIntelligence(SI)的概念最早由Beni、Hackwood和在分子自动机系统中提出。分子自动机中的主体在一维或二维网格空间中与相邻个体相互作用，从而实现自组织。1999年，Bonabeau、Dorigo和Theraulaz在他们的著作《SwarmIntelligence:FromNaturaltoArtificialSystems中对群智能进行了详细的论述和分析，给出了群智能的一种不严格定义：任何一种由昆虫群体或其它动物社会行为机制而激发设计出的算法或分布式解决问题的策略均属于群智能。SwarmIntelligenceSwaSwarmIntelligence(续)Swarm可被描述为一些相互作用相邻个体的集合体，蜂群、蚁群、鸟群都是Swarm的典型例子。鱼聚集成群可以有效地逃避捕食者，因为任何一只鱼发现异常都可带动整个鱼群逃避。蚂蚁成群则有利于寻找食物，因为任一只蚂蚁发现食物都可带领蚁群来共同搬运和进食。一只蜜蜂或蚂蚁的行为能力非常有限，它几乎不可能独立存在于自然世界中，而多个蜜蜂或蚂蚁形成的Swarm则具有非常强的生存能力，且这种能力不是通过多个个体之间能力简单叠加所获得的。社会性动物群体所拥有的这种特性能帮助个体很好地适应环境，个体所能获得的信息远比它通过自身感觉器官所取得的多，其根本原因在于个体之间存在着信息交互能力。SwarmIntelligence(续)SwarSwarmIntelligence(续)

信息的交互过程不仅仅在群体内传播了信息，而且群内个体还能处理信息，并根据所获得的信息（包括环境信息和附近其它个体的信息）改变自身的一些行为模式和规范，这样就使得群体涌现出一些单个个体所不具备的能力和特性，尤其是对环境的适应能力。这种对环境变化所具有适应的能力可以被认为是一种智能（关于适应性与智能之间的关系存在着一些争议，Fogel认为智能就是具备适应的能力），也就是说动物个体通过聚集成群而涌现出了智能。因此，Bonabeau将SI的定义进一步推广为：无智能或简单智能的主体通过任何形式的聚集协同而表现出智能行为的特性。这里我们关心的不是个体之间的竞争，而是它们之间的协同。SwarmIntelligence(续)信息的交互SwarmIntelligence(续)JamesKennedy和RussellC.Eberhart在2001年出版了《SwarmIntelligence》，是群智能发展的一个重要历程碑，因为此时已有一些群智能理论和方法得到了应用。他们不反对Bonabeau关于SI定义，赞同其定义的基本精神，但反对定义中使用“主体”一词。其理由是“主体”所带有自治性和特殊性是许多Swarm的个体所不具备和拥有的，这将大大限制Swarm的定义范围。他们认为暂时无法给出合适的定义，赞同由MarkMillonas（1994）提出的构建一个SI系统所应满足的五条基本原则：SwarmIntelligence(续)JamesSwarmIntelligence(续)[1]ProximityPrinciple:群内个体具有能执行简单的时间或空间上的评估和计算的能力。[2]QualityPrinciple:群内个体能对环境（包括群内其它个体）的关键性因素的变化做出响应。[3]PrincipleofDiverseResponse:群内不同个体对环境中的某一变化所表现出的响应行为具有多样性。[4]StabilityPrinciple:不是每次环境的变化都会导致整个群体的行为模式的改变。[5]AdaptabilityPrinciple:环境所发生的变化中，若出现群体值得付出代价的改变机遇，群体必须能够改变其行为模式。SwarmIntelligence(续)[1]ProSwarmIntelligence(续)《SwarmIntelligence》最重要的观点是：Mindissocial，也就是认为人的智能是源于社会性的相互作用，文化和认知是人类社会性不可分割的重要部分，这一观点成为了群智能发展的基石。群智能已成为有别于传统人工智能中连接主义和符号主义的一种新的关于智能的描述方法。群智能的思路，为在没有集中控制且不提供全局模型的前提下寻找复杂的分布式问题求解方案提供了基础。在计算智能领域已取得成功的两种基于SI的优化算法是蚁群算法和粒子群算法。SwarmIntelligence(续)《SwarmIntelligence(续)

目前，已有的基于SI的优化算法都是源于对动物社会通过协作解决问题行为的模拟，它主要强调对社会系统中个体之间相互协同作用的模拟。这一点与EC不同，EC是对生物演化中适者生存的模拟。与EC一样的是，SI的目的并不是为了忠实地模拟自然现象，而是利用他们的某些特点去解决实际问题。另一个与EC的相同点是,基于SI的优化算法也是概率搜索算法。SwarmIntelligence(续)目前，已SwarmIntelligence(续)

目前，已有的群智能理论和应用研究证明群智能方法是一种能够有效解决大多数优化问题的新方法，更重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析,群智能理论及应用研究都是具有重要学术意义和现实价值的。SwarmIntelligence(续)目前，已SwarmIntelligence(续)

由于SI的理论依据是源于对生物群落社会性的模拟，因此其相关数学分析还比较薄弱，这就导致了现有研究还存在一些问题。首先，群智能算法的数学理论基础相对薄弱，缺乏具备普遍意义的理论性分析，算法中涉及的各种参数设置一直没有确切的理论依据，通常都是按照经验型方法确定，对具体问题和应用环境的依赖性比较大。其次，同其它的自适应问题处理方法一样，群智能也不具备绝对的可信性，当处理突发事件时,系统的反应可能是不可测的,这在一定程度上增加了其应用风险。另外,群智能与其它各种先进技术(如:神经网络、模糊逻辑、禁忌搜索和支持向量机等)的融合还不足。SwarmIntelligence(续)由于SI的蚁群算法

蚁群算法（AntColonyOptimization,ACO）由Colorni，Dorigo和Maniezzo在1991年提出，它是通过模拟自然界蚂蚁社会的寻找食物的方式而得出的一种仿生优化算法。自然界种蚁群寻找食物时会派出一些蚂蚁分头在四周游荡，如果一只蚂蚁找到食物，它就返回巢中通知同伴并沿途留下“信息素”（pheromone）作为蚁群前往食物所在地的标记。信息素会逐渐挥发，如果两只蚂蚁同时找到同一食物，又采取不同路线回到巢中，那么比较绕弯的一条路上信息素的气味会比较淡，蚁群将倾向于沿另一条更近的路线前往食物所在地。蚁群算法蚁群算法（AntColonyOptimiz蚁群算法(续)ACO算法设计虚拟的“蚂蚁”，让它们摸索不同路线，并留下会随时间逐渐消失的虚拟“信息素”。根据“信息素较浓的路线更近”的原则，即可选择出最佳路线。目前，ACO算法已被广泛应用于组合优化问题中，在图着色问题、车间流问题、车辆调度问题、机器人路径规划问题、路由算法设计等领域均取得了良好的效果。也有研究者尝试将ACO算法应用于连续问题的优化中。由于ACO算法具有广泛实用价值，成为了群智能领域第一个取得成功的实例，曾一度成为群智能的代名词，相应理论研究及改进算法近年来层出不穷。蚁群算法(续)ACO算法设计虚拟的“蚂蚁”，让它们摸索蚁群算法(续)蚁群算法(续)大纲学习主体ANN遗传算法群体智能粒子群优化算法大纲学习主体

粒子群算法(particleswarmoptimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于SwarmIntelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。PSO算法简介粒子群算法(particleswarmoptimiPSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以概述如下：

我们把系统中的成员称为具有适应性的主体(AdaptiveAgent)，简称为主体。所谓具有适应性，就是指它能够与环境以及其它主体进行交流，在这种交流的过程中“学习”或“积累经验”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。PSO产生背景之一：复杂适应系统CAS理论的最基本的思想可以复杂适应系统（CAS）续CAS的四个基本特点：首先，主体(AdaptiveAgent)是主动的、活的实体；其次，个体与环境(包括个体之间)的相互影响，相互作用，是系统演变和进化的主要动力；再次，这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。复杂适应系统（CAS）续CAS的四个基本特点：PSO产生背景之二:人工生命

人工生命“是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容：①研究如何利用计算技术研究生物现象；②研究如何利用生物技术研究计算问题(NatureComputation)。我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧，例如,人工神经网络是简化的大脑模型.遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统：社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做"群智能"。PSO产生背景之二:人工生命人工生命“基本PSO算法

粒子群优化算法源于1987年Reynolds对鸟群社会系统boids的仿真研究，boids是一个CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。仅通过使用这三条规则，boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。基本PSO算法粒子群优化算法源于1987年Rey基本PSO算法（续）Reynolds仅仅将其作为CAS的一个实例作仿真研究，而并未将它用于优化计算中。

Kennedy和Eberhart在中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。基本PSO算法（续）Reynolds仅仅将其作基本PSO算法(续)PSO中，每个优化问题的解都是搜索空间中的一只鸟。称之为“粒子(Particle)”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他