粒子群优化算法概述

计算机辅助工艺课程作业学 生：赵 华 琳学 号: s时 间：09年6月粒子群优化算法概述0.前 言优化是科学研究、工程技术和经济管理等领域的重要研究工具。它所研究的问题是讨论在众多的方案中寻找最优方案。例如，工程设计中怎样选择设计参数，使设计方案既满足设计要求又能降低成本；资源分配中，怎样分配有限资源，使分配方案既能满足各方面的基本要求，又能获得好的经济效益。在人类活动的各个领域中，诸如此类，不胜枚举。优化这一技术，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性很强的科学。近十余年来，粒子群优化算法作为群体智能算法的一个重要分支得到了广泛深入的研究，在路径规划等许多领域都有应用。本文主要结合现阶段的研究概况对粒子群优化算法进行初步介绍。1.粒子群优化算法的基本原理1.1 粒子群优化算法的起源粒子群优化（PSO）算法是由Kennedy和Eberhart于1995年用计算机模拟鸟群觅食这一简单的社会行为时，受到启发，简化之后而提出的12。设想这样一个场景：一群鸟随机的分布在一个区域中，在这个区域里只有一块食物。所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的方法就是追寻自己视野中目前离食物最近的鸟。如果把食物当作最优点，而把鸟离食物的距离当作函数的适应度，那么鸟寻觅食物的过程就可以当作一个函数寻优的过程。鱼群和鸟群的社会行为一直引起科学家的兴趣。他们以特殊的方式移动、同步，不会相互碰撞，整体行为看上去非常优美。生物学家CargiReynolds提出了一个非常有影响的鸟群聚集模型。在他的模拟模型boids中，每一个个体遵循：避免与邻域个体相冲撞、匹配邻域个体的速度、试图飞向感知到的鸟群中心这三条规则形成简单的非集中控制算法驱动鸟群的聚集，在一系列模拟实验中突现出了非常接近现实鸟群聚集行为的现象。该结果显示了在空中回旋的鸟组成轮廓清晰的群体，以及遇到障碍物时鸟群的分裂和再度汇合过程。由此受到启发，经过简化提出了粒子群优化算法。1.2粒子群优化算法的原理在粒子群优化算法中，每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值，每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。优化开始时先初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个极值就是整个种群目前找到的最优解。这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。第二个极值是粒子本身所找到的最优解，称为个体极值。这是因为粒子仅仅通过跟踪全局极值或者局部极值来更新位置，不可能总是获得较好的解。这样在优化过程中，粒子在追随全局极值或局部极值的同时追随个体极值则圆满的解决了这个问题。这就是粒子群优化算法的原理。在算法开始时，随机初始化粒子的位置和速度构成初始种群，初始种群在解空间中为均匀分布。其中第i个粒子在n维解空间的位置和速度可分别表示为Xi=（xi1,xi2,xid）和Vi=（vi1,vi2,vid），然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己的速度和位置。一个极值是粒子本身到目前为止所找到的最优解，这个极值称为个体极值Pbi=（Pbi1,Pbi2,Pbid）。另一个极值是该粒子的邻域到目前为止找到的最优解，这个极值称为整个邻域的最优粒子Nbesti=(Nbesti1,Nbesti2,Nbestid)。粒子根据如下的式(2-1)和式(2-2)来更新自己的速度和位置：Vi=Vi+c1rand()(Pbesti-Xi)+c2rand()(Nbesti-Xi) (2-1)Xi= Xi+ Vi (2-2)式中c1和c2是加速常量，分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长，若太小，则粒子可能远离目标区域,若太大则会导致突然向目标区域飞去，或飞过目标区域。合适的c1，c2可以加快收敛且不易陷入局部最优。rand()是0到1之间的随机数。粒子在每一维飞行的速度不能超过算法设定的最大速度Vmax。设置较大的Vmax可以保证粒子种群的全局搜索能力，Vmax较小则粒子种群优化算法的局部搜索能力加强。粒子群优化算法是在模拟鸟群觅食时受到启发提出的。提出之后却发现用动物或人的认知来解释算法的原理更加完美。在速度更新公式(2-1)中由3个部分构成。第1个部分是Vi，表示粒子在解空间有按照原有方向和速度进行搜索的趋势，这可以用人在认知事物时总是用固有的习惯来解释。第2个部分是c1rand()(Pbesti-Xi)，表示粒子在解空间有朝着过去曾碰到的最优解进行搜索的趋势，这可以用人在认知事物时总是用过去的经验来解释。第3部分是c2rand()(Nbesti-Xi)，表示粒子在解空间有朝着整个邻域过去曾碰到的最优解进行搜索的趋势，这可以用人在认知事物时总可以通过学习其他人的知识，也就是分享别人的经验来解释。因此，粒子群优化算法实际上是借用了人或动物认知事物时的习惯，经验，及学习过程来进行寻优的。粒子在优化过程中的运动轨迹见图1。图1 粒子群算法优化搜索示意图1.3粒子群优化算法的优点粒子群优化算法具有以下主要优点：(1)易于描述；(2)便于实现；(3)要调整的参数很少；(4)使用规模相对较少的群体；(5)收敛需要评估函数的次数少；(6)收敛速度快粒子群优化算法很容易实现，计算代价低，由于其内存和CPU速度要求都很低。而且，它不需要目标函数的梯度信息，只依靠函数值。粒子群优化算法已被证明是解决许多全局优化问题的有效方法。2.粒子群优化算法的实现粒子群优化算法具有编程简单，易实现的特点，粒子群优化算法的流程如图2所示。下面给出其实现的具体步骤：步骤1：初始化。初始搜索点的位置X0i及其速度V0i通常是在允许的范围内随机产生的，每个粒子的Pbest坐标设置为其当前位置，且计算出其相应的个体极值（即个体极值点的适应度值），而整个邻域的最优粒子就是该粒子邻域中个体极值中最好的，记录该最好值的粒子序号，并将Nbesti设置为该最好粒子的当前位置。步骤2：评价每一个粒子。计算粒子的适应度值,如果好于该粒子当前的个体极值，则将Pbest设置为该粒子的位置，且更新个体极值。如果在该粒子的邻域内所有粒子的个体极值中最好的好于当前的Nbesti，则将Nbesti设置为该粒子的位置，记录该粒子的序号，且更新Nbesti的函数值。步骤3：粒子的更新。用式(2-1)和式(2-2)对每一个粒子的速度和位置进行更新。步骤4：检验是否符合结束条件。如果当前的迭代次数达到了预先设定的最大次数（或达到最小错误要求)，则停止迭代，输出最优解，否则转到步骤2。图2 粒子群算法优化算法流程图3粒子群优化算法的两种模式Kennedy等人在观察鸟群觅食的过程中注意到，通常飞鸟并不一定看到鸟群中其他所有飞鸟的位置和动向，往往只是看到相邻的飞鸟的位置和动向。因此他在研究粒子群算法时，同时开发了两种模式：全局最优(Gbest)和局部最优(Lbest)。基本粒子群优化算法就是全局最优的具体实现。在全局最优中每个个体被吸引到由种群任何个体发现的最优解。该结构相当于一个完全连接的社会网络；每一个个体能够跟种群中所有其他个体进行比较性能，模仿真正最好的个体。每个粒子的轨迹受粒子群中所有粒子的所有的经验和意识的影响。全局模式有较快的收敛速度，但容易陷入局部极值。而在局部模式中，粒子总根据它自己的信息和邻域内的最优值信息来调整它的运动轨迹，而不是群体粒子的最优值信息，粒子的轨迹只受自身的认知和邻近的粒子状态的影响，而不是被所有粒子的状态影响。这样，粒子就不是向全局最优值移动，而是向邻域内的最优值移动。而最终的全局最优值从邻域最优值内选出，即邻域最优之中适应值最高的值。在算法中，相邻两邻域内部分粒子重叠，这样两相邻邻域内公共粒子可在两个邻域间交换信息，从而有助于粒子跳出局部最优，达到全局最优。局部模式本身存在着两种不同的方式。一种方式是由两个粒子空间位置决定“邻居”，它们的远近用粒子间距离来度量；局部最优的另一种方式是编号方法，粒子群中的粒子在搜索之前就被编以不同的号码，形成环状拓扑社会结构。对于第一种方式，在每次迭代之后都需要计算每个粒子与其他粒子间的距离来确定邻居中包括哪些粒子，这导致算法的复杂度增强，算法运行效率降低；而第二种方式由于事先对粒子进行了编号，因而在迭代中粒子的邻域不会改变，这导致在搜索过程中，当前粒子与指定的“邻居”粒子迅速聚集，而整个粒子群就被分成几个小块，表面上看似乎是增大了搜索的范围，实际上则大大降低了收敛速度。局部最优模式收敛速度较慢，但却具有较强的全局搜索能力。例如在环形拓扑中1号与最后一个粒子和2号相邻，2号粒子则与1号、3号相邻，这种定义方式被称为拓扑意义下的邻居。根据社会学家的研究，这两种邻居的概念都是有社会背景的。全局模式的拓扑结构如图3中的(a)所示，环形局部模式的拓扑结构如图3中的(b)所示。图3 粒子群算法的两种模型：(a)全局模型；(b)环形局部模型Suganthan提出带有邻域操作的PSO模型，用每个粒子所定义的当前邻域极值代替粒子群的当前全局极值。在优化的初始阶段，将邻域定义为每个粒子自身，随着迭代次数的增加，将邻域范围逐步扩展到包含所有粒子，则此时的邻域极值即为全局极值。这种模型在一定程度上克服了PSO模型在优化搜索后期，随迭代次数增加搜索结果无明显该进的缺点。4.粒子群算法的应用PSO算法的优势在于算法的简洁性，易于实现，没有很多参数需要调整，需要梯度信息。PSO算法是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具。1函数优化第三章粒子群算法原理与收敛性分析大量的问题最终可归结为函数的优化问题，通常这些函数是非常复杂的，主要表现为规模大、维数高、非线性、非凸和不可微等特性，而且有的函数存在大量局部极小。许多传统确定性优化算法收敛速度较快，计算精度高，但对初值敏感，易陷入局部最小。而一些具有全局性的优化算法，如遗传算法、模拟退火算法、进化规划等，受限于各自的机理和单一结构，对于高维复杂函数难以实现高效优化。PSO算法通过改进或结合其它算法，对高维复杂函数可以实现高效优化。2神经网络的训练PSO算法用于神经网络的训练中，主要包含3个方面:连接权重、网络拓扑结构及传递函数、学习算法。每个粒子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的。与BP算法相比，使用PSO算法训练神经网络的优点在于不使用梯度信息，可使用一些不可微的传递函数。多数情况下其训练结果优于BP算法，而且训练速度非常快。3.参数优化PSO算法己广泛应用于各类连续问题和离散问题的参数优化。例如，在模糊控制器的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果。4、组合优化许多组合优化问题中存在序结构如何表达以及约束条件如何处理等问题，离散二进制版PSO算法不能完全适用。研究者们根据问题的不同，提出了相应问题的粒子表达方式，或通过重新定义算子来解决不同问题。目前，已提出了多种解决TSP、VRP以及车间调度等问题的方案。其他应用:除了以上领域外，PSO算法的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例有:模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等。4.粒子群优化算法的发展方向目前，粒子群算法的发展趋势主要有：(1)粒子群优化算法的改进。粒子群优化算法在解决空间函数的优化问题和单目标优化问题上应用得比较多，如何应用于离散空间优化问题和多目标优化问题将是粒子群优化算法的主要研究方向。如何充分结合其他进化类算法，发挥优势，改进粒子群优化算法的不足也是值得研究的。(2)粒子群优化算法的理论分析。粒子群优化算法提出的时间不长，数学分析很不成熟和系统，存在许多不完善和未涉及的问题，对算法运行行为、收敛性、计算复杂性的分析比较少。如何知道参数的选择和设计，如何设计适应值函数，如何提高算法在解空间搜索的效率算法收敛以及对算法模型本身的研究都需要在理论上进行更深入的研究。这些都是粒子群优化算法的研究方向之一。(3)粒子群算法的生物学基础。如何根据群体进行行为完善算法，将群体智能引入算法中，借鉴生物群体进化规则和进化的智能性也是学者关注的问题。(4)粒子群优化算法与其他进化类算法的比较研究。与其他进化算法的融合，如何让将其他进化算法的优点和粒子群优化算法相结合，构造出有特色有实用价值的混合算法是当前算法改进的一个重要方向。(5)粒子群优化算法的应用。算法的有效性必须在应用中才能体现，广泛的开拓粒子群优化算法的应用领域，也对深入研究粒子群优化算法非常的有意义。参考文献1Kennedy J,Eberhart R.Particle Swarm optimizationC.In:IEEE Int 1 Conf on Neural Networks.Perth,Austraial,1995:1942-1948.2Eberhart R,Kennedy J.A New Optimizer Using Particle Swarm TheoryC.In:Proc of the Sixth I