粒子群算法研究进展_邢晓溪.doc

2015.3 数据通信 技术交流 Technology Discussion  粒子群算法研究进展 邢晓溪( 国网北京市电力公司物资分公司北京 100054） 摘 要：粒子群算法（PSO）是一种仿鸟群 食行为的智能 化算法，是目前解决组合 化 的重要工 具之一。为了扩展粒子群算法在工程实际中的应用范围，有助于针对工程应用 行算法选择，本文讨论了粒子群算法理论基础， 述了该算法的实现步骤与特点，并分析讨论了几种典型粒子群算法的 算方法与特 点，即 交粒子群算法（HPSO）、离散二 制粒子群算法（BPSO与DPSO）、 同粒子群算法（CPSO）及免疫粒子群算法（IM-PSO）。最后，根据粒子群算法的研究现状，展望了该算法所面 的挑 与 一步研究方向。 关键词：粒子群算法； 交粒子群算法； 同粒子群算法；免疫粒子群算法 中图分类号：TP18 文献标志码：A  1 引言 粒子群算法（PSO）由美国心理学家Kennedy与电气工程师Eberhart[1]首次提出，该算法源于针对鸟群捕食行为的研究，通过模拟鸟群捕食过程中相互协作从而找到最优路径的行为以获取最优解。目前，该算法已被广泛应用于各个工业领域。其中，最具备实际应用价值的领域主要包含物资运输的路径选择、多目标问题的优化求解、模式识别、决策与模拟等。 虽然已经有大量文献针对粒子群算法进行了一定的研究，但是，在理论与实践中该算法均尚未成熟，需要进行改进。PSO算法[2][3]主要解决自身与种群位置最佳的求解问题，具备收敛速度好的优点，但是，容易出现局部收敛的情况从而影响最终求解。杂 交PSO算法（HPSO）[4]结合了进化计算，提高了PSO算法的收敛速度并在一定程度上保证了全局最优的获得。离散PSO算法（BPSO与DPSO）[5][6][7]有效解决了针对二进制问题优化求解的困难。协同 PSO 算法（CPSO）[8]将有哪些信誉好的足球投注网站空间进行分割，以达到使每个粒子群具备独立进行粒子更新的能力，降低了对其他粒子群的依赖性。为了提高粒子群的记忆，避免重复工  作，提出了免疫记忆粒子群优化算法[9]（IM-PSO），该算法具备较高的收敛速度与精度。 本文首先介绍了PSO算法的基本原理，然后基于粒子群算法的改进过程，给出了各种改进粒子群算法的理论分析，阐述其算法特点，最后，讨论了粒子群算法的实际工程价值与发展前景。 2 粒子群算法的理论基础 1995年，美国心理学家Kennedy与电气工程师Eberhart首次提出用于解决最优化问题的粒子群算法，该算法基于鸟类捕食的模型，模仿鸟群获取最佳捕食路径的方法以在实际工程中计算最优值。 2.1 基本原理 基于对鸟类捕食行为的模拟，PSO算法可以计算出多个粒子共存及合作最优的路径最优解。粒子本身在飞行过程中所获取的最好位置被记作个体最优解（pBest），整个粒子群所获得的最优位置可以记作全局最优解（gBest），用D维速度Vi=(vi1,vi2,…,viD)与位置Pi=(pi1,pi2,…,piD)进行粒子状态的表示，通过针对自身速度与位置进行状态更新，可以产生新一代群体。  19 技术交流 Technology Discussion  数据通信 2015.3  k+1 k k kk k kk vid =ωvid+c1r1d×(pBestid－pid)+c2r2d(gBestd－pid)% %（1） k k k pid=pid+vid%%%%%%%%%%% （2） 其中，ω表示惯性权值，c1 、c2 为表示学习因子的常数，r1d、r2d为［0,1］中的随机数，k表示迭代次数。 根 据文献［10］，当w=0.729,c1 =c2 =1.494时，算法收敛性 较好。 算法流程 步骤1：对粒子群进行初始化，同时随机初始化各粒子； 步骤2：基于适应度函数，进行各粒子适应度值计算； 步骤3：针对粒子进行当前适应度值与历史最优适应度值比较，同时进行历史最优值替代； 步骤4：针对粒子进行当前适应度与种群历史最优位置适应度值比较，并进行历史最优值替换； 步骤5：使用方程（1）与（2）进行计算；步骤6：如果获得最优值，则结束，否则跳转步骤 2。 算法特点 粒子群算法具备以下优点：（1）设置参数较少；（2）易于理解与描述；（3）收敛速度较好；（4）实现较易。 该算法同时具有如下缺点：（1）容易陷入局部最优；（2）收敛精度不高；（3）后期收敛速度较慢。 3 粒子群算法模型 经典粒子群算法虽然具备一定的优点，适用于一定的工程实践领域，但是，该算法同时具备一些改进空间。 杂交PSO算法 结合PSO算法与进化计算，Angeline[11]提出了杂 交PSO算法。该算法中，每个粒子的适应度值与其他 粒子的适应度值进行比较，同时记录最差的一个，将