一种改进的粒子群优化算法

《一种改进的粒子群优化算法》由会员分享，可在线阅读，更多相关《一种改进的粒子群优化算法（7页珍藏版）》请在装配图网上搜索。

1、一种改进的粒子群优化算法安 进（宁夏回族自治区宁东供电局，银川市 751408）摘要：基本PSO算法及其各种改进算法都是着眼于如何更有效地用一个粒子群在解空间中搜索最优解。但是粒子们在搜索时，总是追逐当前全局最优点和自己迄今搜索到的历史最优点，因此粒子们的速度很快降到接近于0,导致粒子们陷入局部极小而无法摆脱，而出现粒子的趋同或早熟。本文的改进PSO从BP神经网络中得到启示，改进如同使用低通滤波器来平滑权重。通过使用经典测试函数，结果表明改进PSO在收敛精度和计算速度方面都有一定程度的提高。关键词：粒子群算法；平滑权重；改进粒子群；优化算法1 引言20世纪90年代以来，通过模拟生物群体的行为来

2、解决计算问题已经成为新的研究热点，形成了以群体智能(swarm intelligence)为核心的理论体系，并已在一些实际应用领域取得突破性进展。作为群体智能的典型实现模式，模拟蚂蚁群落食物采集过程的蚁群优化算法1(ant colony optimization)和模拟鸟群运动模式的粒子群优化算法2(particle swarm optimization)受到学术界的广泛关注。粒子群优化算法(Particle Swarm Optimization, PSO)是在1995年由美国社会心理学家James Kennedy和电气工程师Russell Eberhart共同提出的，其基本思想是受他们早期对

3、鸟类群体行为研究结果的启发，利用了生物学家Frank Heppner的生物群体模型。PSO同遗传算法类似，粒子群优化算法也是基于个体的协作与竞争来完成复杂搜索空间中最优解的搜索，是一种基于群体智能方法的进化计算技术。但PSO并没有遗传算法用的交叉(crossover)、变异(mutation)等操作，而是粒子在解空间追随最优的粒子进行搜索，因此具有简单容易实现并且没有过多参数需要调整的优点。2 基本粒子群算法2.1基本粒子群算法数学模型PSO的基本概念源于对人工生命(artificial life)和鸟群捕食行为的研究。设想这样一个场景：一群鸟在随机搜寻食物，在这个区域里只有一块食物，所有的鸟

4、都知道食物在哪里，但是它们不知道当前的位置离食物还有多远。那么找到食物的最优策略中最简单有效的就是搜寻目前离食物最近的鸟的周围区域。PSO算法就从这种生物种群行为特性中得到启发，用于求解优化问题。在PSO中，每个优化问题的潜在解都可以想象成维搜索空间上的一个点，我们称之为“粒子”(particle)，所有的粒子都有一个被目标函数决定的适应值(fitness value)。每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。在一个维的目标搜索空间中，由个粒子组成一个群落，其中第个粒子表示为一个维的向量， i=1,2, m，即第个粒子在维空间的位置。将带入一

5、个目标函数就可以计算出其适应值，根据适应值的大小衡量的优劣。第个粒子的飞翔速度也是一个维的向量，记为，其算法图如图1所示。通过以下公式对粒子进行操作：(1) (2)图1 PSO算法示意图2.2基本粒子群算法参数(1) 粒子种群大小：:粒子种群大小的选择视具体问题而定，但是一般设置粒子数为20-50。其实对于大部分的问题10个粒子已经足够可以取得很好的结果，不过对于比较难的问题或者特定类型的问题，粒子数也可以取到100或200。(2) 粒子的长度：即是问题解空间的维数。(3) 粒子的最大速度：粒子的速度在空间中的每一维上都有一个最大速度限制值，用来对粒子的速度进行钳制使速度控制在范围内，决定问题

6、空间搜索的粒度。(4) 加速常数c1、c2 ：调节pbest和gbest方向飞行的最大步长，决定粒子个体经验和群体经验对粒子运行轨迹的影响，反映粒子群之间的信息交流。如果,则粒子只有群体经验，它的收敛速度较快，但容易陷入局部最优；如果，则粒子没有群体共享信息，一个规模为M的群体等价于运行了个单粒子，很难得到最优解，因此一般设置。改变这些常数会改变系统的“张力”，较低的c1、c2值使得粒子徘徊在远离目标的区域，较高的c1、c2值产生陡峭的运动或越过目标区域。Shi和Eberhart建议，为了平衡随机因素的作用，一般情况下设置，大部分算法都采用这个建议。(5) rand()：是介于0,1之间的随机

7、数。(6) 迭代终止条件：一般设为最大迭代次数、计算精度。2.3基本粒子群算法步骤(1)初始化粒子群:给定群体规模：解空间维数，随机产生每个粒子的位置、速度。(2)用基准测试函数各计算每个粒子的当前适应值。(3)更新个体极值：对每个粒子的适应值进行评价，即将第i个粒子的当前适应值与该粒子的个体极值的适应值进行比较，若前者优，则更新，否则保持不变。(4)更新全局极值：从所有中选出最好的，作为全局极值。(5)更新速度和位置：通过公式(1) 和公式（2)来更新每个粒子的速度和位置。(6)检查是否满足中止条件，若满足则退出，否则，转至步骤(2)。3 基本PSO算法存在的问题 粒子趋同性限制了粒子的搜索

8、范围。要想扩大搜索范围，就要增加粒子群的粒子数，或者减弱粒子对整个粒子群当前搜索到的全局最优点的追逐。增加粒子数将导致算法计算复杂度增高，而减弱粒子对全局最优点的追逐又存在算法小、易收敛的缺点。由于基本PSO算法依靠的是群体之间的合作与竞争，粒子本身没有变异机制，因而单个粒子一旦受某个局部极值约束后本身很难跳出局部极值的约束，此时需要借助其它粒子的成功发现。事实上，PSO算法的寻优能力主要来自于粒子之间的相互作用和相互影响。如果从算法中除去粒子之间的相互作用和相互影响，则PSO算法的寻优能力就变得非常有限。试验指出在算法的运行的初始阶段，收敛速度比较快，运动轨迹呈正弦波摆动，但运行一段时间后，

9、速度开始减慢甚至停滞 34。当所有粒子的速度几乎为0，此时粒子群丧失了进一步进化的能力，可以认为算法执行已经收敛。而在许多情况下(如复杂的多峰函数寻优)，算法并没有收敛到全局极值，甚至连局部极值也未必达到。这种现象被称为早熟收敛或停滞(Stagnation)。发生该现象时粒子群高度聚集，严重缺乏多样性，粒子群会长时间或永远跳不出聚集点。因此大量对粒子群优化算法的改进集中在提高粒子群的多样性上，使得粒子群在整个迭代过程中能保持进一步优化的能力。4 改进粒子群算法4.1改进粒子群算法数学模型改进粒子群算法从BP神经网络中得到启示。BP算法是目前处理多层次神经网络问题常用的方法。它使用梯度下降法来减

10、少实际输出结果和预测输出结果之间的误差。但是它存在着在局部最优值附近的停滞和振荡，从而陷入局部最优，不容易得到全局最优解。对这个问题通过以下的方法改进。这种改进如同使用低通滤波器来平滑权重5。其数学表达式为： (3)其中，为需要被平滑的信号序列，为时间时信号的值，为滤波器在时间时的输出。取的值愈大，平滑性能越好。因此，通过对PSO的速度更新方程引入新的参数如下： (4) (5)与原始PSO方程相比，改进的PSO算法增加了这项，其中为引入项的系数。这种改进同已经存在的对速度更新方程改进方法相比，很不相同。这是因为，原有的对粒子速度更新方程为一阶差分方程，而本文的改进型PSO的粒子更新速度方程为二

11、阶差分方程。这种改进的PSO的主要优点有：1.简单易操作。本文所采用的改进型PSO无论是在数学表达式还是在程序的执行方面都具有很强的操作性，由于没有引入复杂的操作和数据结构，因此操作比较容易。2.平滑粒子的运动轨迹，消除了在迭代后期的振荡不收敛而陷入了局部最优的停滞。3.本文的改进PSO几乎可以应用在已经存在的所有具有明确粒子速度更新方程的改进型PSO算法中，例如惯性权重改变型PSO6，收缩因子改变型PSO7，混合型PSO8等。4.2改进型PSO流程图改进型PSO流程图如图2所示：图2 改进型PSO流程图5 实验与结果分析5.1测试函数为了验证改进型PSO算法的性能，目前该领域的研究人员一般采

12、用下列测试函数，图3是这些函数的图像。图3 测试函数9 10（从左上到右下依次为 Sphere函数、Rosenbrock函数、Rastrigrin函数、Schaffer函数） (1)Sphere函数：全局极小点在，全局最小值。 (2)Rosenbrock函数：Rosenbrock函数是一个单峰函数，各变量之间有很强的耦合性。它的全局最小点在，全局最小值。 (3)Rastrigrin函数： Rastrigin函数是一个多峰函数，有很多正弦突起的局部极小点，各变量相互独立，它的全局极小点在，全局最小值。 (4)Schaffer函数：Schaffer函数是二维函数，全局极小点在，全局最小值 。5.2

13、改进PSO算法的评价指标为了表征改进PSO算法的性能，需要引入评价指标。本文引入以下四个评价指标，它们分别是：收敛精度误差、算法成功比率、收敛速度和迭代收敛曲线。其中收敛精度误差表征的是目标函数理论最优值和实际结果之间的偏差，的值越小说明计算的精度越高。PSO算法成功比率，成功运行时间是指算法从收敛至给定基准的全局最优点到满足算法精度结束时间。收敛速度表征了算法收敛到全局最优值所花费的时间。迭代收敛曲线表征了随着迭代次数的变化，目标函数的值的变化轨迹。通过迭代收敛曲线对比，可以得到直观清晰的结论。5.3计算结果计算结果分别如图4、图5、图6和图7所示：图4 0.4时，Sphere函数计算结果图

14、5 0.3时Rosenbrock函数计算结果图6 0.2时Rastrigrin函数计算结果图7 0.1时Schaffer函数计算结果6 结论本文所采用的改进型PSO减轻了PSO算法在迭代过程中，由于陷入局部最优解而陷入局部迭代振荡的程度，通过计算结果的对比，改进PSO算法加快了算法的收敛速度，提高了计算的速度。由于采用的对粒子速度方程的更新，使得速度方程变为二阶差分方程，提高了粒子在空间运动的可控性，极大的消除了在迭代后期的振荡。同时，通过实验发现当从0.2变化到0.4时，改进PSO算法以较少的迭代次数而收敛到最优。本文的改进PSO当时，就演变为权重的基本型粒子群算法，可见本文的改进PSO具有

15、较好的通用性。由于PSO对于处理大规模优化问题所具有的强大处理能力，因此，对于高维数、非线性的电力系统研究中，PSO算法得到了极其广泛的应用。因此，针对研究电力系统的相关问题1112，应用改进PSO算法，对电力系统的进行优化分析，就成为了一个必要而且可行的手段。参考文献1 A. Colorni, M. Dorigo, V Maniezzo. Distributed Optimization by Ant Colonies. Proceedings of ECAL91-European Conference on Artificial Life. Paris, France, 1991:134-

16、142.2 Kennedy J, Eberhart R. C. Particle swarm optimizationA.Proc.IEEE International Conference on Neural NetworksC. Perth, Australia, 1995,4:pp. 19421948.3 李爱国等.粒子群优化算法J.计算机工程与应用2002. 21: 1-3.4 俞欢军，许宁，张丽平，胡上序.混合粒子群优化算法研究J.信息与控制.2005.8:500-509.5 Xiang Tao, Wang Jun, Liao Xiaofeng. An Improved Partic

17、le Swarm Optimizer with MomentumJ. 2007 IEEE Congress on Evolutionary Computation pp2241-3345.6 Shi Y, Eberhart R. A modified Particle Swarm Optimization .IEEE World Congress on Computational Intelligence.1998:6973.7 Maurice Clerc .The Swarm and the Queen: Towards a Deterministic and Adaptive Partic

18、le Swarm Optimization. IEEE 1999:1951-1957.8 Angeline P, Using selection to improve particle swarm optimizationA.Proceedings of IJCNN 99C.Washington, USA .1999:84-89.9 刘金洋.粒子群优化算法的研究与改进D. 哈尔滨:哈尔滨工业大学,2006.10 张彤.粒子群优化算法的研究和改进D. 南京:南京理工大学,2006.11 刘自发，张建华. 基于改进多组织粒子群体优化算法的配电网络变电站选址定容J. 中国电机工程学报,2007,27

19、(1):105-111.12 张振宇，葛少石，刘自发. 粒子群优化算法及其在机组优化组合中应用J.电力自动化设备.2006,26(5):28-31. 作者简介：安 进（1983-），男，陕西咸阳人，大学本科，助理工程师，研究方向：电力系统运行与保护 （EMAIL：）An Improved Particle Swarm Optimization AlgorithmAN Jin(Ningdong Power Supply Company of Ningxia Hui Autonomous Region, Nidong town, Yinchuan 751408)Abstract：The basic

20、 and improved algorithms of PSO focus on how to effectively search the optimal solution in the solution space using one of the particle swarm. However, the particles are always chasing the global optimal point and such points currently found on their way of search, rapidly leading their speed down t

21、o zero and hence being restrained in the local minimum. Consequently, the convergence or early maturity of particles exists. The improved PSO is based on the enlightenment of BP neural network while the improvement is similar to smooth the weight through low-pass filter. The test of classical functions show that the PSO provides a promotion in the convergence precision and calculation velocity to a certain extent.Key words：PSO; Smooth weight; improved particle swarm; optimization algorithm