粒子群优化算法大作业

1、粒子群优化算法综述尹兆杰（内蒙古民族大学数学学院 内蒙古 通辽028000）摘要粒子群优化（PSO）算法是一种基于群智能方法的演化计算技术，通过粒子间的相互作用发现复杂搜索空间中的最优区域，优势在于简单容易实现而且功能强大。由于它简单易操本文从粒子群优PSO算法及其应用。算法改进应用作的特点，PSO 提出，立刻引起演化计算等领域学者们的广泛关注，并在函数优化、神 经网络训练、工业系统优化和模糊系统控。制等领域得到了广泛的应用。 化算法的理论分析切入，阐述了 PSO算法的基本原理、若干类改进的 关键词粒子群算法1. 引言Kennedy和 Eberhart1、2于 1995 年提出粒子群优化算法

2、（Particle Swarm Optimization , PSO），它是一种基于种群智能方法的演化计算技术。因受鸟类捕食行为的启发，设想有一 群鸟在随机搜寻一块食物，则找到食物的最简单有效的方法就是搜寻距离食物最近的鸟的周 围区域。PSO从这种模型中得到启示并用于优化问题。PSO 提出，其简单易操作的特点立刻引起演化计算等领域学者们的广泛关注。PSO在解决许多GO问题上被证明是一种有效的方法；在函数优化、神经网络训练、工业系统优化和模糊系统控制等领域得到了广泛的 应用。2. 算法原理在粒子群优化算法中，每个个体称为一个 粒子”其实每个粒子代表着一个潜在的解。例如 ，在 一个D维的目标搜索空

3、间中，每个粒子看成是空间里的一个点。设群体由 m个粒子构成。M 也被称为群体规模，过大的m会影响算法的运算速度和收敛性。设X =（Xii,Xi2,，Xd,，XiD）为第i个粒子（i=1,2,，m ）的D维位置矢量，根据事先设定 的适应值函数（与要解决的问题有关）计算Xi当前的适应值，即可衡量粒子位置的优劣Vi= （Vii，V2,Vid，,ViD）为粒子i的飞行速度，即粒子移动的距离；=（Pi1, P2,，Pid ,，PiD ）为粒子位置迄今为止搜索到的最优位置;= （Pg1，Pg2,，Pgd，Pg。）为整个粒子群迄今为止搜索到的最优位置。在每次迭代中粒子根据以下式子更新速度和位置(2-1)(2

4、 2)ViF =Vid +Ciri( Pid -Xd )+32( Pgd -Xid )k4lk . k4tXid= Xid + Vid其中i =1,2,m,d =1,2,D,k是迭代次数，r,和为b,l之间的随机数,这两个参数是用来保持群体的多样性。C1和C2为学习因子，也称为加速因子，使粒子具有自我总结和向群体中优秀个体学习的能力，从而向自己的历史最优点以及群体历史最优点靠近。这两个参数对粒子群算法的收敛起的作用不是很大，但如果适当调整这两个参数，可以减少局部最小值的困扰,当然也会使收敛速度变快。由于粒子群算法中没有实际的机制来控制粒子速度，所以有必要对速度的最大值进行限制，但速度超过这个阈

5、值时，设其为vmax,这个参数被证明是非常重要的，因为值太大会导致粒子跳过最好解 ，但太小的话容易导致对搜索空间的不充分搜索。此外速度Vi最小取值为vmin ,位置Zi的取值范围为Vmin: Vmax.式(2-1 )的第二项是 认知”部分，代表了粒子对自身的学习。而公式的第三项是社会”部分,代表着粒子间的协作。式(2-1)正是粒子根据它上一次迭代的速度、它当前位置和自身最好经验与群体最好经验之间的距离来更新速度。然后粒子根据式(2-1 )飞向新的位置。从此可得到粒子群优化算法是主要遵循了五个基本原则，定义为:(1 )邻近原则：粒子必须能够执行简单的空间和实践计算;(2品质原则：粒子群必须能够对

6、周围环境的品质因素有所反应;(3多样性反应原则：粒子群不应该在过于狭窄的范围内活动;(4定性原则：粒子群不应该在每次环境改变的时候都改变自身的行为;(5适应性原则：在能够接受的计算量下，粒子群能够在适当的时候改变他们的行为。简单来说，粒子群优化算法的流程可表示为：Step 1,依照初始化过程，对微粒群的随机位置和速度进行初始设定;Step 2,计算每个微粒的适应值；Step 3,对于每个微粒，将其适应值与所经历过的最好位置p的适应值进行比较,若较好,则将其作为当前的最好位置;Step 4,对每个微粒，将其适应值与所经历过的最好位置Pg的适应值进行比较,若较好，则将其作为当前的全局最好位置;St

7、ep 5,根据方程式(2-1卜式(2 -2 )对微粒的速度和位置进行进化;Step 6,如未达到结束条件，同城为足够好的适应值或达到一个预设最大代数(Gmax则返回step 2。由于PSO算法需要用户确定的参数并不多，而且操作简单。但是它的缺点是 易陷入局部极小点，搜索精度不高，因此研究者们对其进行了各种各样的改进。3改进的粒子群优化算法3.1收敛pso文献3通过对算法的研究，证明采用收敛因子能够确保算法的收敛。在收敛因子模型 中速度的更新公式为：vF =xvid+屮1(Pidxdpgdxd)2(4)2半-Jb -4其中，+C2,:4,通常取w=4.1,由此计算得x = 0.729.改进后的公

8、式(4)被称为标准 pso。3.2基于拓扑结构的PSO文献4在研究了领域拓扑结构对粒子群算法性能的影响后，设计了两种动态邻域生成 策略，验证不同的邻域拓扑结构和不同的算法模型能够影响粒子群算法的性能。文献5提出了一种该改进的PSO算法PSO - DSF。引进有向类无标度网作为粒子群寻优的拓扑结 构，提出作为粒子邻域拓扑的有向网络动态变化机制，从而提高算法的多样性，避免过早陷入局部最优的情况。文献6提出基于KRTG的动态拓扑结构的粒子群算法研究。从粒子 间的拓扑结构出发，动态地调整种群的拓扑结构，增加种群的多样性，使算法收敛于全局最 优解。文献7提出了一种动态拓扑结构改进PSO算法。在这种结构中

9、，用了两种方法改1的粒进邻居的拓扑结构：随机边缘移植(Random Edge Migration , REM)、邻居重组 (Neighborhood Restructuring , NR)。随机边缘移植是指随机选取一个邻居数目大于子节点，移去一个邻居节点，并把这个邻居节点和另一个随机选取的未满的粒子节点相连接。 邻居重组保持粒子的邻居结构在一段时间内固定，然后重新构造粒子邻居的结构。通过对六个基准函数的实验表明这种方法是一种好的策略，对每一个函数的测试都取得了令人满意的结果。研究基于拓扑结构的 PSO算法一直在持续，是一个值得研究的方向。3.3混合PSO文献8针对带障碍约束的空间聚类，提出了一

10、种改进的蚁群算法(IACO)和混合粒子群算法(HP SO)。首先，使用蚁群算法获得最短的障碍距离，然后设计了一个带障碍约 束的遗传K中心空间聚类分析算法。文献9中，使用交叉算子和变异算子，并结合混合 粒子群优化算法以及遗传算法解决柔性作业调度问题，并提出混合整数编程模型。3.4 统一 PSOPSO算法的性能依赖于全局搜索和局部搜索之间(Expl oration and Expl oitati on) 的平衡能力，即搜索空间的全局搜索能力和快速收敛于有希望的区域的能力，分别对应全局变量和局部变量。根据这一思想，文献10提出了一种新的PSO结构UPSO( UnifiedParticle Swarm

11、 Optimization)。为达到全局搜索和局部搜索的平衡，UPSO将全局变量和局部变量合在一个公式里，从而更新粒子的位置：uf uGiJ+(1U 屛中n十n 丄I I n +其中，u 应着局部 示在局部Xid =Xid + Uid是统一因子，在0, 1 之间取值，用来平衡全局和局部搜索。U = 0和1分别对PSO和全局PSO。Gn + 1id表示在全局PSO变量中粒子xi的速度更新，Ln + 1id表PSO变量中粒子的速度更新，它们分别用下式计算：Gi= x M 中 1 ( pin Xid 严2 ( pg xn )L=xvin +1(Pid -x： )+2( Pgni - Xi：)部部变量

12、）是Xi的邻居目前找到的粒子最优位置的下标。其中，k是迭代次数，g(全局变量)是整个粒子群目前找到的粒子最优位置的下标,gi(局4 结束语PSO是一种新兴的有潜力的基于群智能的演化计算技术。自从2002年PSO算法被引进PSO 算法缺乏数学理论支持。 4，5对算法的收敛做了一定的分 所以开展一些理论研究， 的应用领域也有深远意义。国内 27，已经有很多学者对 PSO 进行了研究。虽然已经取得了一些研究成果，但是仍 然有许多问题值得关注。 PSO 算法在实际应用中已被证明是一种有效的优化工具，已广泛 的应用于科学研究和工程实践，但是其内部机理仍不明确，不仅可以PSO 的改进算法及其应用也都停留在

13、实验阶段。文献 析，但是对于这样一个年轻有潜力的算法，还远远不够。 加深对 PSO 算法内部机理的认识，而且对于扩展 PSO参考文献1 Kennedy J，Eberhart R. Particle swarm optimization C IEEE Int 1 Conf on Neural Networks ， Perth， Australia ， 1995: 1942-1948 2 Eberhart R ，Kennedy J. A new optimizer using particleswarm theory C Proc of the siXth international sympos

14、iumon Micro Machine and Human Science ，Nagoya， Japan，1995: 39-43 3 Clerc M. The swarm and the Queen: Towards a deterministic and adaptive particle swarm optimization C Proc of the Congress of Evolutionary Computation ， 1999: 1951-1957 :4:韩立娜，熊盛武.基于动态领域的粒子群算法的研究J 计算机工程与应用，2009,45( 6) : 60-65 5 姚灿中，杨建

15、梅 . 一种基于有向动态网络拓扑的粒子群优化算法 J 计算机工程与应用，2009， 45( 27) : 15-17 6 田玉玲，杨朋樽 . 基于 KRTG 的动态拓扑结构的粒子群算法研究 J 计算机与数学工程，2010， 38( 2) : 25-277 Arvind Mohais ， Rui Mendes ， Christopher Ward ， Christian Postoff. Neighborhood Re structuring in Particle Swarm Optimization C Australian Conference on Artificial Intellige

16、nce 2005: 776-785 8 Zhang Xueping， Wang J iayao ， Zhang DeXian， Fang Zhongshan. An IACO and HPSOmethod for spatial clustering with obstacles constraints C The 4th International Conference on Intelligent Computing ， ICIC 2008，2008: 848-856 8 Lingli Zeng ， FengXing Zou， Xiaohong Xu. Mathematical model and hybrid particle swarmoptimization for fleXible job shop scheduling problem C Proceedings of the first ACM/SIGEVO Summit on Gene