粒子群优化算法概述[1].doc

word计算机辅助工艺课程作业学生：赵华琳学号:s308070072时间：09年6月粒子群优化算法概述0.前言优化是科学研究、工程技术和经济管理等领域的重要研究工具它所研究的问题是讨论在众多的方案中寻找最优方案例如，工程设计中怎样选择设计参数，使设计方案既满足设计要求又能降低本钱；资源分配中，怎样分配有限资源，使分配方案既能满足各方面的根本要求，又能获得好的经济效益在人类活动的各个领域中，诸如此类，不胜枚举优化这一技术，正是为这些问题的解决，提供理论根底和求解方法，它是一门应用广泛、实用性很强的科学近十余年来，粒子群优化算法作为群体智能算法的一个重要分支得到了广泛深入的研究，在路径规划等许多领域都有应用本文主要结合现阶段的研究概况对粒子群优化算法进展初步介绍1.粒子群优化算法的根本原理1.1 粒子群优化算法的起源粒子群优化〔PSO〕算法是由Kennedy和Eberhart于1995年用计算机模拟鸟群觅食这一简单的社会行为时，受到启发，简化之后而提出的[1][2]设想这样一个场景：一群鸟随机的分布在一个区域中，在这个区域里只有一块食物所有的鸟都不知道食物在哪里但是他们知道当前的位置离食物还有多远。

那么找到食物的最优策略是什么呢最简单有效的方法就是追寻自己视野中目前离食物最近的鸟如果把食物当作最优点，而把鸟离食物的距离当作函数的适应度，那么鸟寻觅食物的过程就可以当作一个函数寻优的过程鱼群和鸟群的社会行为一直引起科学家的兴趣他们以特殊的方式移动、同步，不会相互碰撞，整体行为看上去非常优美生物学家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+c1·rand()·(Pbesti-Xi)+c2·rand()·(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个局部是c1·rand()·(Pbesti-Xi)，表示粒子在解空间有朝着过去曾碰到的最优解进展搜索的趋势，这可以用人在认知事物时总是用过去的经验来解释第3局部是c2·rand()·(Nbesti-Xi)，表示粒子在解空间有朝着整个邻域过去曾碰到的最优解进展搜索的趋势，这可以用人在认知事物时总可以通过学习其他人的知识，也就是分享别人的经验来解释因此，粒子群优化算法实际上是借用了人或动物认知事物时的习惯，经验，与学习过程来进展寻优的粒子在优化过程中的运动轨迹见图1图1 粒子群算法优化搜索示意图粒子群优化算法具有以下主要优点：(1)易于描述；(2)便于实现；(3)要调整的参数很少；(4)使用规模相对较少的群体；(5)收敛需要评估函数的次数少；(6)收敛速度快粒子群优化算法很容易实现，计算代价低，由于其内存和CPU速度要求都很低。

而且，它不需要目标函数的梯度信息，只依靠函数值粒子群优化算法已被证明是解决许多全局优化问题的有效方法2.粒子群优化算法的实现粒子群优化算法具有编程简单，易实现的特点，粒子群优化算法的流程如图2所示下面给出其实现的具体步骤：步骤1：初始化初始搜索点的位置X0i与其速度V0i通常是在允许的X围内随机产生的，每个粒子的Pbest坐标设置为其当前位置，且计算出其相应的个体极值〔即个体极值点的适应度值〕，而整个邻域的最优粒子就是该粒子邻域中个体极值中最好的，记录该最好值的粒子序号，并将Nbesti设置为该最好粒子的当前位置步骤2：评价每一个粒子计算粒子的适应度值,如果好于该粒子当前的个体极值，如此将Pbest设置为该粒子的位置，且更新个体极值如果在该粒子的邻域内所有粒子的个体极值中最好的好于当前的Nbesti，如此将Nbesti设置为该粒子的位置，记录该粒子的序号，且更新Nbesti的函数值步骤3：粒子的更新用式(2-1)和式(2-2)对每一个粒子的速度和位置进展更新步骤4：检验是否符合完毕条件如果当前的迭代次数达到了预先设定的最大次数，如此停止迭代，输出最优解，否如此转到步骤2图2粒子群算法优化算法流程图3．粒子群优化算法的两种模式Kennedy等人在观察鸟群觅食的过程中注意到，通常飞鸟并不一定看到鸟群中其他所有飞鸟的位置和动向，往往只是看到相邻的飞鸟的位置和动向。

因此他在研究粒子群算法时，同时开发了两种模式：全局最优(Gbest)和局部最优(Lbest)根本粒子群优化算法就是全局最优的具体实现在全局最优中每个个体被吸引到由种群任何个体发现的最优解该结构相当于一个完全连接的社会网络；每一个个体能够跟种群中所有其他个体进展比拟性能，模仿真正最好的个体每个粒子的轨迹受粒子群中所有粒子的所有的经验和意识的影响全局模式有较快的收敛速度，但容易陷入局部极值而在局部模式中，粒子总根据它自己的信息和邻域内的最优值信息来调整它的运动轨迹，而不是群体粒子的最优值信息，粒子的轨迹只受自身的认知和邻近的粒子状态的影响，而不是被所有粒子的状态影响这样，粒子就不是向全局最优值移动，而是向邻域内的最优值移动而最终的全局最优值从邻域最优值内选出，即邻域最优之中适应值最高的值在算法中，相邻两邻域内局部粒子重叠，这样两相邻邻域内公共粒子可在两个邻域间交换信息，从而有助于粒子跳出局部最优，达到全局最优局部模式本身存在着两种不同的方式一种方式是由两个粒子空间位置决定“邻居〞，它们的远近用粒子间距离来度量；局部最优的另一种方式是编号方法，粒子群中的粒子在搜索之前就被编以不同的，形成环状拓扑社会结构。

对于第一种方式，在每次迭代之后都需要计算每个粒子与其他粒子间的距离来确定邻居中包括哪些粒子，这导致算法的复杂度增强，算法运行效率降低；而第二种方式由于事先对粒子进展了编号，因而在迭代中粒子的邻域不会改变，这导致在搜索过程中，当前粒子与指定的“邻居〞粒子迅速聚集，而整个粒子群就被分成几个小块，外表上看似乎是增大了搜索的X围，实际上如此大大降低了收敛速度局部最优模式收敛速度较慢，但却具有较强的全局搜索能力例如在环形拓扑中1号与最后一个粒子和2号相邻，2号粒子如此与1号、3号相邻，这种定义方式被称为拓扑意义下的邻居根据社会学家的研究，这两种邻居的概念都是有社会背景的全局模式的拓扑结构如图3中的(a)所示，环形局部模式的拓扑结构如图3中的(b)所示图3粒子群算法的两种模型：(a)全局模型；(b)环形局部模型Suganthan提出带有邻域操作的PSO模型，用每个粒子所定义的当前邻域极值代替粒子群的当前全局极值在优化的初始阶段，将邻域定义为每个粒子自身，随着迭代次数的增加，将邻域X围逐步扩展到包含所有粒子，如此此时的邻域极值即为全局极值这种模型在一定程度上克制了PSO模型在优化搜索后期，随迭代次数增加搜索结果无明显该进的缺点。

4.粒子群算法的应用PSO算法的优势在于算法的简洁性，易于实现，没有很多参数需要调整，需要梯度信息PSO算法是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具1．函数优化第三章粒子群算法原理与收敛性分析大量的问题最终可归结为函数的优化问题，通常这些函数是非常复杂的，主要表现为规模大、维数高、非线性、非凸和不可微等特性，而且有的函数存在大量局部极小许多传统确定性优化算法收敛速度较快，计算精度高，但对初值敏感，易陷入局部最小而一些具有全局性的优化算法，如遗传算法、模拟退火算法、进化规划等，受限于各自的机理和单一结构，对于高维复杂函数难以实现高效优化PSO算法通过改良或结合其它算法，对高维复杂函数可以实现高效优化2．神经网络的训练PSO算法用于神经网络的训练中，主要包含3个方面:连接权重、网络拓扑结构与传递函数、学习算法每个粒子包含神经网络的所有参数，通过迭代来优化这些参数，从而达到训练的目的与BP算法相比，使用PSO算法训练神经网络的优点在于不使用梯度信息，可使用一些不可微的传递函数多数情况下其训练结果优于BP算法，而且训练速度非常快PSO算法己广泛应用于各类连续问题和离散问题的参数优化。

例如，在模糊控制器的设计、机器人路径规划、信号处理和模式识别等问题上均取得了不错的效果4、组合优化许多组合优化问题中存在序结构如何表达以与约束条件如何处理等问题，离散二进制版PSO算法不能完全适用研究者们根据问题的不同，提出了相应问题的粒子表达方式，或通过重新定义算子来解决不同问题目前，已提出了多种解决TSP、VRP以与车间调度等问题的方案其他应用:除了以上领域外，PSO算法的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等其中具体应用实例有:模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等4.粒子群优化算法的开展方向目前，粒子群算法的开展趋势主要有：(1)粒子群优化算法的改良粒子群优化算法在解决空间函数的优化问题和单目标优化问题上。