多样性反馈与控制的粒子群优化算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇多样性反馈与控制的粒子群优化算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：

针对粒子群优化（PSO）算法的早熟收敛问题，提出了一种多样性反馈与控制的粒子群优化 （DFCPSO）算法。该算法在搜索过程中根据多样性反馈信息，动态调整算法参数，改善了搜索次数在多样性曲线上的分布情况。当多样性或群体适应度方差下降到给定的阈值时，通过基于最优点排斥的初始化操作，高效率发散，使粒子飞离聚集区域，重新开始搜索，从而使种群多样性保持在合理范围内，避免了早熟收敛现象。对多个标准测试函数的实验结果表明，与当前多样性控制的粒子群优化（DCPSO）算法相比，DFCPSO算法在复杂优化问题和多模态优化问题中具有更强的全局搜索能力。

关键词：粒子群优化；早熟收敛；多样性； 全局最优

中图分类号： TP301.6

文献标志码：A

Diversity feedback and control particle swarm optimization algorithm

Abstract：

Concerning the premature convergence problem in Particle Swarm Optimization （PSO） algorithm， a Diversity Feedback and Control PSO （DFCPSO） algorithm was proposed. In the process of search， the algorithm dynamically adjusted the algorithm parameters according to the feedback information of diversity； as a result， the distribution of iterations in the diversity curve was improved. When the population diversity or the variance of the populations fitness dropped to the given thresholds， the proposed algorithm would let the particle swarm initialize based on the repulsion of the global best position and fly away from the gathering area efficiently to search again， hence the diversity was controlled in a reasonable range， which avoided premature convergence. The experimental results on several well-known benchmark functions show that DFCPSO has stronger global optimization ability in the complicated problems and multi-modal optimization when being compared with the existing Diversity-Controlled PSO （DCPSO）.

Key words：

Particle Swarm Optimization （PSO）；premature convergence；diversity；global convergence

0 引 言

粒子群优化（Particle Swarm Optimization， PSO）算法是由Eberhart和Kennedy于1995年提出的一种基于群体智能的优化方法，其模拟鸟群觅食过程中的迁徙和聚集行为，通过各个粒子间的交流协作，搜索问题的最优解[1]。PSO算法具有运算简便、易于实现、控制参数少等特点，已成功应用于神经网络、路径规划、工业优化等科学和工程领域[2-6]。

PSO算法存在的一个主要问题是在解决多峰优化问题时易出现早熟收敛现象。针对该问题，Riget等[7]提出了吸引—排斥粒子群优化（Attractive and Repulsive Particle Swarm Optimization， ARPSO）算法，当种群多样性下降到给定阈值dlow时，该算法将标准PSO中的学习因子改为负数，使粒子由原来的吸引运动改为排斥运动，增强种群多样性；当种群多样性上升到给定阈值dhig时，再将学习因子改成标准PSO算法中的正数，恢复吸引运动，这样粒子根据多样性信息相对最优粒子作排斥、吸引的交替运动，有效地控制了种群的多样性，避免了早熟收敛现象[7]。方伟等在文献[7]的基础上分析了粒子的收敛和发散行为与算法参数的关系，通过两组不同的算法参数分别控制粒子的吸引、排斥运动，得到了多样性控制的粒子群优化（Diversity-Controlled Particle Swarm Optimization， DCPSO）算法[8]。

以上算法在吸引阶段均采用固定的算法参数，且将多样性下限dlow作为算法进入排斥阶段的唯一信号。然而，在吸引阶段，不同的多样性条件下采用同样的算法参数不利于提高搜索效率[9-10]。另外，在多模态优化问题中，有时粒子陷入多个局部最优点而多样性仍然大于dlow，从而导致算法搜索停滞。因此，以多样性下限dlow作为算法进入排斥阶段的唯一信号并不可靠。

本文提出一种多样性反馈与控制的粒子群优化（Diversity Feedback and Control Particle Swarm Optimization， DFCPSO）算法。在吸引阶段，借鉴文献[9]中多样性反馈的思想并对多样性反馈公式进行了改进，根据多样性信息动态调整算法参数，使迭代次数在多样性曲线上的分布更加合理。同时，将群体适应度方差下限σ2d[11]也作为算法进入发散阶段的信号。粒子群在多样性和群体适应度方差的指导下做收缩—发散的交替运动，既控制了种群多样性，又防止了因粒子陷入多个局部最优点造成的算法停滞现象。另外，在排斥方式上，本文提出新的基于最优点排斥的初始化操作方法，高效率发散，一次性提高种群多样性，跳出粒子聚集或停滞区域，继续搜索，从而避免了早熟收敛现象。对多个标准测试函数的实验表明了该算法的有效性。

1 标准粒子群优化算法

在标准PSO算法中，每个粒子被视为设计空间的一个可行解，粒子的优劣由一个事先设定的适应度函数来度量。每个粒子在可行解空间中参照自身经验和整个种群的经验随机运动，粒子在若干次运动后找到整个优化问题的最优解[12]。

在D维搜索空间中，粒子的位置和速度分别表示为

式中：w为惯性权重，在迭代过程中从0.9线性递减到0.4；r1、r2为均匀分布在[0，1]内的随机数；cp、cs为学习因子，通常取为2；vid（t）和xid（t）分别为第i个粒子在第t次迭代中第d维的速度和位置；pid（t）是第i个粒子第t次以内迭代中找到的个体极值的第d维分量；gd（t）为整个种群在第t次以内迭代中找到的最优位置的第d维分量。

2 两种典型的多样性控制PSO

2.1 吸引—排斥粒子群优化算法

Riget等在文献[7]中定义了粒子的两种运动状态，即收缩状态（对应吸引运动）和发散状态（对应排斥运动），设定了多样性上限dhig和下限dlow。算法开始时按标准PSO的参数设置进行迭代（收缩状态）；当种群多样性下降到多样性下限dlow时，通过将粒子原来的吸引运动改为排斥运动（发散状态），以增加种群多样性；当多样性增加到多样性上限dhig时，粒子恢复标准PSO算法中的吸引运动，多样性下降。这样粒子根据多样性做吸引—排斥的交替运动，从而将种群多样性控制在一个合理的范围。具体方法是将标准PSO中的速度更新公式中改为[7]：

式中：dir的取值根据运动阶段确定，当需要吸引运动时，dir=1；当需要排斥运动时，dir=-1。

2.2 多样性控制粒子群优化算法

方伟等[8]认为ARPSO算法对于多样性的控制比较简单，没有充分发挥多样性控制方法的潜力，并且ARPSO算法对其他参数如粒子群规模、迭代次数等的灵敏度太高，不易调节。因此在分析了PSO算法的收敛与发散行为与算法参数的关系后，通过两组不同的算法参数控制粒子的吸引和排斥运动，控制种群多样性，提出了DCPSO[8]。

3 多样性反馈与控制粒子群优化算法

本文提出的DFCPSO算法也定义了粒子的两种运动状态，即收缩状态和发散状态，还定义了多样性的下限dlow和群体适应度方差下限σ2d[11]。

当种群多样性diversity大于dlow 且群体适应度方差大于σ2d时，粒子向最优位置作收缩运动；当粒子群的多样性diversity小于dlow或群体适应度方差小于σ2d时，进入发散状态，粒子以最优点为中心作排斥运动。粒子群在多样性和群体适应度方差的指导下做收缩—发散的交替运动，直到满足收敛条件或最大迭代次数。另外，新算法在对算法参数的选择上进行了改进，并提出了新的粒子发散方法。

1）对收缩阶段算法参数的设置采用基于多样性反馈的动态调节方法。在文献[9]的基础上，将惯性权重的计算公式设置为：

w=（e-div+δ）（1-y/a）（3）

且当由上式计算出w小于0.5时，取w=0.5。式中， δ是一个较小的负数，控制惯性权值的取值范围；a为一个较大的常数，控制多样性从从初值下降到下限时对应的搜索次数；y为一个变量，它的初始值为0，每迭代一次，它的值增加1，而一旦种群多样性下降到多样性下限dlow时，y的值清零，之后又随着迭代次数增加，如此反复；div为种群多样性度量，其公式[7]为：

式中：m表示种群粒子数；|L|表示搜索空间的最大对角距离；pid表示第i个粒子位置的第d维分量；D 表示问题的维数；〖AKp-〗d表示所有粒子位置第d维分量的平均值。

2）在发散方式上，本文提出基于最优点排斥的初始化方法。当种群多样性下降到给定的临界值dlow或群体适应度方差下降到临界值σ2d时，对所有粒子进行基于最优点排斥的随机初始化，一次操作完成发散阶段。具体做法为：

式中：disi为第i个粒子与最优点的距离；dismax是一个常数，为最大排斥量，可选为设计变量上下限绝对值中较大者的10%左右。

算法流程为：

步骤1 随机初始化粒子的位置与速度。

步骤2 检查是否达到最大迭代次数，若达到，则停止程序；否则继续。

步骤3 计算当前种群多样性和群体适应度方差。

步骤4 比较当前种群多样性与下限dlow的大小，以及当前群体适应度方差与下限σ2d的大小。若当前多样性小于dlow或当前群体适应度方差小于σ2d，则根据式（5）、（6）、（7）对种群进行基于最优点排斥的初始化操作；否则继续。

步骤5 根据式（3）基于多样性反馈计算惯性权值，若计算的惯性权值大于或等于0.5，则惯性权值取为计算值；若小于0.5，则取为0.5。

步骤6 根据式（1）更新粒子速度并进行速度限制，根据式（2）更新粒子位置。

步骤7 跳到步骤2。

4 实验分析

4.1 实验设置

为了测试算法的有效性，选用4个标准测试函数对本文提出的DFCPSO算法和文献[8]中的DCPSO算法进行对比实验，各个标准函数的表达式及取值范围如下所示：

Rosenbrock函数是一个单峰函数，但靠近最优点的区域为香蕉状，变量之间具有很强的相关性，且梯度信息经常误导算法的搜索方向，优化困难。Rastrigin函数是Sphere类函数的多峰版本，该函数具有大量按正弦拐点排列的、很深的局部最优点，优化算法很容易在通往全局最优点的路径上陷入一个局部最优点。Ackley函数是一个具有许多局部最小点的多峰函数。Griewank函数是一个复杂的多峰函数，存在大量的局部最小点和高大障碍物，由于各变量之间的显著相关，优化算法很容易陷入局部最优 [12]。

对每个函数进行3组对比实验。每组实验的粒子数均为20，问题维数分别为20、50和100，最大迭代次数为问题维数的2000倍，每组实验都独立运行50次。其中DCPSO算法的参数设置与文献[8]中所述相同，即：dhig=0.25，dlow=5×10-6。收缩阶段时w=0.65，cp=cs=1.5；发散阶段时w=3，cp=cs=10。DFCPSO算法的参数设置为： dlow=5×10-6，cp=cs=1.5，δ=-0.15，dismax取为搜索区间上下限绝对值的最大值的0.1倍，a和σ2d因函数和维数而异，如表1所示。

4.2 实验结果与讨论

4个标准测试函数的理论最优解均为0，表2列出了分别用DCPSO和DFCPSO对4.1节所述4个标准测试函数进行50次优化的平均最优解，图1～4分别为两种算法优化不同测试函数（50维）时的进化曲线。

从表3、图1～4可以看出，在对4个测试函数20、50和100维的优化中，DFCPSO算法的优化结果均比DCPSO算法好，尤其是对Rasgiu和Ackey函数的优化上，DFCPSO的结果要比DCPSO好多个数量级。

DFCPSO算法之所以在复杂优化问题和多维优化问题上比DCPSO具有更强的搜索能力，是由于DFCPSO在发散效率和搜索效率上的提高。

在发散效率上，DFCPSO算法采用基于最优点排斥的初始化方法，一次操作便完成发散阶段。与ARPSO和DCPSO相比，发散阶段在整个迭代过程中所占比例达到最小。文献[7]和文献[8]的研究均表明：在ARPSO算法和DCPSO算法中，粒子最优位置的更新基本都发生在收缩阶段，在发散阶段更新的很少或者几乎没有。DFCPSO算法发散效率高，发散阶段所占比例的减少提高了算法的搜索能力。

在搜索效率上，DCPSO采用恒定的惯性权值，而DFCPSO通过多样性反馈动态调整惯性权值，从本文提出的惯性权值计算公式可以看出，在多样性从初始值逐渐下降到下限dlow的过程中，DFCPSO的惯性权重先增加后减少，且最大值小于0.85，最小值大于等于0.5。从文献[13]的分析可知，当cp=cs=1.5，而w∈[0.5，0.85]时，DFCPSO的收敛速度随w的增大而减小。因而在开始阶段具有较高的收敛速度，能够快速找到最优解所在的大致区域；在中间阶段，收敛速度较慢，能够在最优解区域充分搜索；而多样性接近dlow的阶段，较快地收敛。表4列出了DCPSO和DFCPSO两种算法在多样性大于0.03范围内进行搜索的次数占总搜索次数的百分比。从表4可以看出，DFCPSO在多样性大于0.03范围内的搜索次数比DCPSO小得多。在初始化时，种群的多样性在0.28左右，多样性大于0.03，说明粒子在较大空间内搜索。在该范围内搜索对于寻找全局最优解是必要的，但对于收敛、发散阶段交替反复搜索的粒子群优化算法，如果在该范围内搜索次数过多，只会重复前期的搜索过程，浪费了一些搜索次数，降低搜索效率，而DFCPSO正是在这一点上得到了改善，因而优化效果更好。

5 结语

本文针对粒子群优化算法的早熟收敛问题，提出了一种多样性反馈与控制的粒子群优化（DFCPSO）算法。与DCPSO相比，DFCPSO将群体适应度方差作为判定算法进入发散阶段的判据之一，避免了粒子陷入多个局部最优点引起的算法停滞问题；在算法的吸引阶段，根据多样性信息动态调节，使搜索次数在多样性曲线上的分布更加合理；当粒子需要进入排斥运动时，本文提出的发散方法具有更高的效率。实验表明，本文提出的DFCPSO算法在复杂优化问题和多模态优化问题上取得了更好的效果，具有更强的全局寻优能力。

参考文献：

[1] KENNEDY J， EBERHART R C. Particle swarm optimization[C]// Proceedings of 1995 IEEE International Conference on Neural Networks. Piscataway： IEEE， 1995：1942-1948.

[2] NABAVI-KERIZI S H， ABADI M， KABIR E. A PSO-based weighting method for linear combination of neural networks[J]. Computers & Electrical Engineering， 2010， 36（5）： 886-894.

[3] AMEUR T， ASSAS M. Modified PSO algorithm for multi-objective optimization of the cutting parameters[J]. Production Engineering， 2012， 6（6）： 569-576.

[4] CORMIER N， CORMIER G， POITRAS G， et al. Automated critical point identification for PIV data using multimodal particle swarm optimization[J]. International Journal for Numerical Methods in Fluids， 2012， 70（7）： 923-938.

[5] MAO Y， PANG Y. Application of improved particle swarm optimization in path planning of underwater vehicles[J]. Journal of Computer Applications， 2010， 30（3）：789-792.（毛宇峰，庞永杰.改进粒子群在水下机器人路径规划中的应用[J].计算机应用，2010，30（3）：789-792.）

[6] ZHANG C， ZHAO Y， MA X. Optimal design of dry-type air-core reactor using diversity-guided particle swarm optimization algorithm[J]. Journal of Xian Jiaotong University， 2012， 46（4）：64-69.（张成芬，赵彦珍，马西奎. 采用多样性引导粒子群算法的干式空心电抗器优化设计[J].西安交通大学学报，2012，46（4）：64-69）

[7] RIGET J， VESTERSTROM J S. A diversity-guided particle swarm optimizer-the ARPSO[R]. Aarhus， Denmark： University of Aarhus Department of Computer Science， 2002.

[8] FANG W， SUN J， XU W. Diversity-controlled particle swarm optimization algorithm[J]. Control and Decision， 2008， 23（8）：863-868.（方伟，孙俊，须文波.一种多样性控制的粒子群优化算法[J].控制与决策，2008，23（8）：863-868.）

[9] JIAO W， LIU G. Particle swarm optimization algorithm based on diversity feedback[J]. Computer Engineering， 2009， 35（22）：863-868.（焦巍，刘光斌.基于多样性反馈的粒子群优化算法[J].计算机工程，2009，35（22）：202-204.）

[10] JIANG C， ZHAO S， SHEN S， et al. Particle swarm optimization algorithm with sinusoidal changing inertia weigh[J]. Computer Engineering and Applications， 2012， 48（8）： 40-42.（姜长元， 赵曙光， 沈士根，等.惯性权重正弦调整的粒子群算法[J].计算机工程与应用，2012，48（8）：40-42.）

[11] LYU Z， HOU Z. Particle swarm optimization with adaptive mutation[J]. Acta Electronica Sinica， 2004， 32（3）： 416-420.（吕振肃，侯志荣.自适应变异的粒子群优化算法[J].电子学报，2004，32（3）：416-420.）

[12] LI L， NIU B. Particle swarm optimization [M]. Beijing： Metallurgical Industry Press， 2009.（李丽，牛奔.粒子群优化算法[M].北京：冶金工业出版社，2009.）

[13] REN Z， WANG J. Accelerate convergence particle swarm optimization algorithm[J]. Control and Decision， 2011， 26（2）： 201-206.（任子晖，王坚.加速收敛的粒子群优化算法[J].控制与决策，2011，26（2）：201-206.）