融合吸引排斥和双向学习的改进粒子群算法

汪雅文，钱 谦，冯 勇，伏云发

昆明理工大学 信息工程与自动化学院，云南省计算机技术应用重点实验室，昆明 650500

粒子群算法（particle swarm optimization，PSO）是一种群智能优化算法，由Eberhart和Kennedy[1]在1995年首次提出。该算法由于操作简单，不依赖于目标问题的梯度信息等优点，一经提出便在众多领域得到了成功应用，例如神经网络分类[2]、图像分割[3]、机械的位置控制[4]、雷达站布局优化[5]、路径规划[6]等。虽然PSO算法有较好的优化性能，但在对一些复杂问题进行优化时仍存在“早熟”、种群多样性缺失和收敛速度慢等现象，引起这些现象主要是因为PSO算法在进化过程中难以有效地平衡局部搜索能力与全局搜索能力[7]。许多学者针对PSO算法的不足提出了很多的改进方法，文献[8]提出了一种将粒子的惯性权重w与粒子的位置信息相关联的改进方法，可以更精确地调节算法中的w，使粒子的搜索行为得到了更好的平衡，改善了算法易“早熟”收敛的缺陷；文献[9]提出了一种异步变化策略来更新算法中的学习因子，通过该算法的学习能力使得算法陷入局部极值的几率大大减小；文献[10]提出了一种能够将种群动态地分层的自主学习策略，通过利用不同阶层粒子的特性采取不同的学习模式，增加了粒子的多样性，使该算法的收敛速度和精度得到了提高；文献[11]定义了一种高斯变异策略，使种群多样性得到了保持，降低早熟收敛的概率；文献[12]将遗传算法与PSO算法相融合，丰富了算法在进化过程中的群体多样性，提升了算法的收敛速度。

虽然上述改进使算法的性能获得了一定程度上的提升，但PSO算法仍有很大的改进空间，为了使算法同时拥有较好的收敛性能和收敛精度，进一步加强PSO算法的性能，在已有研究的基础上，本文提出了一种新的改进的PSO算法。首先，将借鉴文献[13]中天牛须搜索思想提出的一种双向学习策略和一种改进的吸引-排斥策略融入PSO算法的全局寻优过程中，双向学习策略能够允许粒子在寻优过程中进行双向学习，丰富种群的多样性；吸引-排斥策略使粒子能够在全局最优粒子的吸引力和全局最差粒子排斥力的合力方向上随机地移动寻找最优解，以增强算法的局部寻优能力和收敛能力；然后提出了双重自适应策略，使双向学习策略速度更新公式中的惯性权重w和学习因子c根据算法的进化现状动态地调整，这种双重自适应的方式能够有效地控制算法全局搜索行为与局部搜索行为之间的平衡；形成融合吸引排斥和双向学习的改进粒子群算法（integrating attraction-repulsion and bidirectional learning IPSO，ARLIPSO），通过对本文所提出的改进算法进行仿真测试，结果表明本文算法可以更好地在寻优过程中跳出局部极值，减小出现“早熟”收敛的可能，使算法的性能得到提升。

1 基本PSO算法

PSO算法是基于鸟群或鱼群寻找食物的社会行为方式而产生的一种算法[14]。群体中的每个个体都在自己已有的搜索方向和历史上寻找更好的解，即向个体的历史经历中最好的解学习；此外，每个个体都从其他成员那里学习，通常是向群体当中表现最好的个体学习。粒子群优化算法可概括为，初始化种群个体的位置和速度、速度更新、位置更新。如果种群大小为N，则在D维搜索空间中PSO算法的更新公式如下：

其中，第i个粒子的速度、位置分别为vi、xi,i=1,2,…,N,t为当前代数，w为惯性权重，c1、c2为学习因子；r1、r2为均匀随机数，范围在0和1之间，gbesti(t)为全局最优个体对应的位置，pbesti(t)为个体历史最优对应的位置。

2 融合吸引排斥和双向学习的改进粒子群算法（ARLIPSO）

为了提高算法的全局搜索和局部搜索能力提出了融合吸引排斥和双向学习的方法，通过双向学习方法来增加种群多样性，提高算法的全局寻优性能；通过吸引-排斥方法来增加算法的局部搜索和收敛能力。此外，为了克服单一性的学习因子和惯性权重在优化复杂函数时无法很好地调节寻优进程的问题，提出了双重自适应策略，使双向学习策略速度更新公式中的惯性权重w和学习因子c根据算法的进化现状动态地调整。

2.1 双重自适应优化策略

在标准PSO算法中，粒子更新的影响因素主要包括全局最优位置、个体历史最优位置和粒子原有的速度。其中，惯性权重w的大小决定了粒子当前速度对下一代速度更新的影响程度，学习因子c1、c2分别决定了个体历史最优位置和全局历史最优位置对速度更新影响的程度。由此可以看出惯性权重w和学习因子c是影响算法性能的主要参数。文献[15]提出了一种使惯性权重w在线性和非线性之间进行动态调整的方法。文献[16]采用了余弦函数使学习因子c随着不同的搜索阶段非线性地变换的方法。上述文献所提出的方法均在不同程度上加强了算法的搜索能力，减少了算法的“早熟”收敛情况。在前人研究的基础上，本文提出了一种双重自适应优化策略，使算法在寻优过程中能够自适应地同时调节惯性权重w和学习因子c，使算法前期的全局搜索能力和后期的局部搜索能力得到提升。

2.1.1 改进的惯性权重

惯性权重w对PSO算法的全局搜索和局部搜索能力有着很大程度的影响[17]，对w加以适当的调整，能够使算法的寻优能力以及收敛速度同时得到提升。若使算法的全局搜索能力较强，则需要较大数值的惯性权重w；若使算法的局部搜索能力较好，则需要较小数值的惯性权重w，若采用固定数值的w，算法无法根据进化的情况来调整搜索能力，会增加陷入“早熟”收敛的可能性。文献[8]指出PSO算法的寻优过程是复杂的，单一变化w的方法很大程度上限制了算法在复杂寻优进程中的调节能力，容易出现“早熟”收敛，所以本文提出了一种新的改进惯性权重的方法，使惯性权重非线性取值，根据粒子的迭代次数进行适当的调整，能够使惯性权重在复杂系统中呈现出动态变化关系，进而使算法在全局搜索和局部搜索之间达到一定的平衡。ARLIPSO算法的惯性权重w的更新方式如下：

其中，wmin为惯性权重最小值，取值为0.1；wmax为惯性权重最大值，取值为0.8；A是控制曲线曲率的参数，经过测试A取值为6；t为当前迭代次数；T为最大迭代次数。

惯性权重w的非线性变化曲线如图1所示。在算法初期，w能够维持比较平稳的状态，使粒子在此期间保持比较大的更新速度，确保算法具有较好的全局搜索能力，在算法的早期阶段提高了种群多样性，避免出现“早熟”的情况；而在算法后期阶段，为了提高算法的收敛能力，使算法的惯性权重w值快速降低，使粒子能够以较小的步长更新，实现更加精细的搜索。

图1 惯性权重w自适应曲线Fig.1 Adaptive curve of inertia weight w

2.1.2 改进的学习因子

文献[18]证明了单粒方法在探索方面较优且降低了计算复杂度，因此本文同样采用了单粒更新方式。即从较优的粒子中随机选取一个粒子xk作为学习对象，并在此基础上提出了更进一步的自适应单粒学习因子。学习因子c更新公式如下：

其中，cmin为学习因子最小值，取值为0.5；cmax为学习因子最大值，取值为2；fit为当前粒子个体的适应度值，fmax为当代粒子中最大的适应度值。

学习因子c数值的变化趋势如图2所示，本策略中，学习因子的大小决定了粒子向xk学习的程度。在算法初期，学习因子较小，且呈缓慢上升的趋势，使粒子较少的向xk学习，提升算法的全局寻优能力；在算法的后期，学习因子以较大幅度上升，使粒子更多地向xk学习，起到提高算法局部搜索能力的作用。

图2 学习因子c自适应曲线Fig.2 Adaptive curve of learning factor c

2.2 双向学习策略

本文借鉴了天牛须搜索算法的主要思想，提出了一种双向学习策略，其中适应度评估、行为学习和种群排序是本策略的重要组成部分。不同于标准PSO算法的是，本策略的搜索过程是基于社会学习原理，粒子随机选择一个较优者学习，提高了全局搜索能力。但由于种群整体往较优者逼近，导致多样性不足，因此通过双向学习的方法，丰富种群多样性，提高算法全局搜索能力。即粒子在解空间搜索时，每一次进化都会进行正反方向的学习行为。在每一次迭代时，先将个体按照适应度值由优到差进行排序，再从中随机选择一个比xi好的个体作为学习对象即xk(1≤k≤i)，排序如图3所示。然后对正向学习(xk-xi)和反向学习(xi-xk)对应的适应度值进行评估，并从两种学习方式中选择适应度值更优的一种作为更新方式，改进后的粒子速度与位置更新公式为：

图3 粒子适应度排序Fig.3 Fitness ordering of particles

其中，第i个粒子的速度、位置分别为vi、xi,i=1,2,…,N,t为当前代数，r1为均匀随机数，w为惯性权重，按照公式（3）更新；c为学习因子，按照公式（4）更新。粒子每次更新时会根据公式（5）同时进行正向学习和反向学习两种行为，粒子通过学习获得了新的适应度，并向产生适应度值较优的方向移动。这种双向学习的粒子更新方式不但扩大了算法的搜索范围，使算法的全局寻优能力得到了提高，一定程度上也减小了算法陷入局部最优的可能性。

2.2.1 双向学习策略的伪代码

双向学习策略的伪代码如下：

2.2.2 双向学习策略的测试

本文使用函数F1和F2来测试双向学习策略的性能。其中，F1为单峰函数，定义域为-10＜xi＜10,F1全局最小值为0；F2为多峰函数，定义域为-100＜xi＜100；F2全局最小值为0，函数F1、F2表达式如下所示：

本次测试维度D设置为20，种群大小设置为100，进化代数为400，c1=c2=1.5、w=0.9，将PSO算法与本文方法各独立进行20次仿真实验；种群进化过程中，每次迭代时粒子选择正向学习和与之相反方向的反向学习次数的曲线图如图4所示，优化结果对比如表1所示。

图4 正反向学习次数Fig.4 Number of forward and reverse learning

表1 函数F1、F2的优化结果对比Table 1 Comparison of optimization results of functions F1 and F2

图4结果表明，在测试函数F1中种群接近一半的个体采用了反向学习的方法，丰富了种群的多样性，从而提高了算法的全局搜索能力；在函数F2中每次进化时个体采用正向学习次数的曲线呈波峰形状，函数F2有很多的局部极小值点，当种群集中在局部极值附近时，反向学习的方法扩大了种群搜索范围，有助于算法跳出局部最优。通过对比表1的优化结果证明了本学习方式在单峰测试函数和多峰测试函数中均优于传统PSO算法的单向学习，说明了本策略的有效性。

2.3 吸引-排斥策略

拟态物理学方法提出具有速度和位置的个体，通过个体之间虚拟力（引力和斥力）的作用产生速度，进而改变个体位置[19]。通过PSO算法速度更新公式可知，粒子在更新过程中受到了个体最优粒子和全局最优粒子引力的影响，这种作用力规则在一定程度上具有局限性，对此文献[20]通过算法的不同搜索阶段，分别构造了引斥力规则和双引力规则，提高了种群的多样性，使算法在很大程度上减小了陷入局部极值的可能性。

在前人研究的启发下，本文从拟态物理学角度构造出一种新的粒子间作用方式，通过对比粒子适应度值的大小提出了一种新的吸引-排斥策略。该策略将标准PSO算法中粒子的更新受全局最优个体以及自身历史最优个体的双引力作用，扩展为粒子在受全局最优粒子gbesti吸引的同时还受全局最差粒子gworsti的排斥，使得粒子在引力和斥力所产生的合力作用下朝着更优的方向进化。其中，(gbesti-xi)为全局最优粒子对xi的吸引，-(gworsti-xi)为全局最差粒子对xi的排斥，本策略中粒子的更新公式为：

其中，r1为[0，1]范围内的均匀随机数，r2=1/2(1-r1)，第i个粒子的位置为xi,i=1,2,…,N,t为当前代数，公式（9）中引力、斥力占比相同，引斥力使粒子向适应度值较好的个体聚拢，同时也远离适应度值较差的个体，使得粒子更快逼近最优值，提高了算法的局部寻优能力。

2.4 自适应抉择因子F

采用自适应的抉择因子F，使双向学习和吸引排斥两种方法在不同进化时期有所侧重，有利于保持种群多样性和收敛能力之间的平衡。R是0到1之间的随机数，其中，R＜F时，采用双向学习策略；R≥F时，采用吸引排斥策略。由图5F变化曲线可知，F在进化初期以大于0.5的数值缓慢下降，使得算法更加侧重于双向学习策略；进化后期F以小于0.5的数值快速减小，使得算法更侧重于吸引-排斥策略，在整个寻优过程中两种方法处于一个动态平衡的状态。在提高种群的丰富度的同时加快了算法的收敛速度。自适应抉择因子F的更新公式如下：

图5 自适应抉择因子曲线Fig.5 Curve of adaptive decision factor

其中，d2=0.6,d1=0.4,a=10,t为当前迭代次数，T为最大迭代次数。融合双向学习与吸引-排斥的策略不仅考虑了种群的多样性，而且也提高了算法的收敛速度，有效地平衡了算法的全局和局部搜索的能力。

3 算法步骤

ARLIPSO算法的流程如下：

输入：算法迭代次数T、种群规模N。输出：最优位置x。

步骤1初始化粒子群个体，包括位置x、速度v，粒子数量N和算法参数。

步骤2计算群体中各个粒子适应度函数值fit。

步骤3将fit由优到差排序，每个个体从群体中随机选取一个较优个体作为学习对象xk，更新全局最优个体gbesti和全局最差个体gworsti。

步骤4根据公式（3）、（4）、（10）自适应地更新w、c和抉择因子F。

步骤5若R＜F采用双向学习策略，即公式（5）、（6）更新粒子的x、v；反之采用吸引-排斥策略，即公式（9）更新粒子。

步骤6更新所有粒子适应度函数值fit。

步骤7t=t+1,若t＜T转步骤3，否则执行步骤8。

步骤8输出x，结束。

4 仿真实验及结果分析

4.1 测试函数及对比算法

为了验证本文提出的ARLIPSO算法的性能，对表2给出的9个测试函数进行了仿真测试，其中，f1～f5为单峰值测试函数，f6～f9为多峰值测试函数。此外，将本文提出的ARLIPSO算法的测试结果与近年来新提出的自适应惯性权重混沌PSO算法（CPSO-NAIW）[8]和基于学习与竞争的改进PSO算法（LC-PSO）[21]进行比较，这些对比算法的优化性能在相应的文献中已经得到证明，它们在各方面都比标准PSO算法优秀。

表2 测试函数Table 2 Test functions

4.2 测试方案与实验分析

在对比实验分析中，具体实验参数设置为：算法的种群数量N设置为100，最大进化代数为400代。ABLPSO算法中，wmin=0.1、wmax=0.8,cmin=1.494 45、cmax=2,CPSO-NAIW算法与LC-PSO算法的其他参数设置与原文献保持一致。为了避免算法的随机性保证实验的公平性，针对每种算法，在上述9种函数的测试中，3种算法分别独立进行30次仿真实验，本文采用3个参量作为评估算法性能的指标：（1）最优值，反应算法求解质量好坏的标准。（2）均值（Mean），表示算法最优解的平均值，均值越小说明算法的搜索性能越好。（3）标准差（STD），用来反映算法稳定性的指标，STD越小表明算法稳定性越强。

4.2.1 单峰值函数优化下的性能分析

表3给出了3种算法在5个单峰测试函数上不同维度的优化结果。对比表中数据可以得出，ARLIPSO算法的最优值、Mean和STD多数都为最优，说明该算法的收敛能力和寻优能力相比于另外两种算法更为突出。通过对比3种算法的Mean可知，ARLIPSO算法虽然没有达到理想最优值，但优化能力仍要优于另外两种算法，此外相对于CPSO-NAIW而言，LC-PSO算法较好。从实验结果上看，虽然函数从10维到60维，随着维度的提高寻优的复杂度也增加了，但ARLIPSO算法的优化能力并没有降低。对比表中的STD可知，算法ARLIPSO的标准差在5个测试函数中均为最小，说明该算法每次的优化结果波动较小，稳定性较另外两种算法更为出色；而算法CPSO-NAIW的STD值多部分在3种算法中最大，特别是在函数f2中虽最优值取到了理想值0，但其Mean值在3种算法中最小，表明该算法稳定性最差，适用性最差。

图6给出了本次实验中3种对比算法在9种测试函数中测试时随机选取的寻优收敛曲线。由图6中（a）～（e）可以看出，与CPSO-NAIW算法和LC-PSO算法相比，ARLIPSO算法在单峰值函数优化的收敛速度和收敛精度方面具有明显的优势，其中，CPSO-NAIW算法整体上的寻优能力表现最差。证明了ARLIPSO算法拥有较好的局部寻优能力。

4.2.2 多峰值函数优化下的性能分析

表4给出了3种算法在4个多峰测试函数上不同维度的优化结果。其中f6～f9可以作为测试算法能否有效跳出局部最优值的评价函数，通过对比分析可知，算法ARLIPSO在优化多峰函数时，无论低维还是高维，均值Mean和标准差STD两个性能指标都大幅度优于其他两种算法，说明其全局寻优能力较好。实验结果显示，ARLIPSO算法在函数f8、f9上均值都达到了理想最优值0，CPSO-NAIW算法寻优效果整体最差，归因于该算法在搜索后期跳出局部极值的能力有所缺陷，总之，相比于LC-PSO和CPSO-NAIW两种算法，ARLIPSO算法优化能力更强，收敛速度更快。

表4 3种算法在函数f6～f9中的优化结果对比Table 4 Comparison of optimization results of three algorithms in function f6～f9

从图6中（f）～（i）可以看出，ARLIPSO算法的寻优能力在优化多峰函数时也表现出众，由图6（f）的优化曲线可知，CPSO-NAIW算法相比其他两种算法其收敛速度非常快，即在迭代初期曲线就呈水平状态，但由于局部最优值的存在，导致收敛精度极低，反之ARLIPSO算法虽然收敛速度慢，但收敛精度最高，表明ARLIPSO算法能够在双向学习策略的作用下保持种群的多样性，即使是复杂的多峰值函数也能取得良好的优化结果。

4.3 算法计算复杂度分析

数学模型的参数拟合决定了算法的时间复杂度[22]。设种群最大迭代数目为Tmax，种群大小为N，其中，Tmax、N的数值越大，其计算的时间复杂度O(TmaxN)也就越大。ARLIPSO和对比算法（CPSO-NAIW、LC-PSO）采用了相同的种群规模，ARLIPSO采用了两种不同的进化策略，即双向学习策略和吸引-排斥策略，通过自适应抉择因子F调整种群的进化策略，实现不同的进化功能。因为这两种策略是作为算法寻优附加模块参与计算，所以该操作没有使算法本身进行更深层次的循环，使得ARLIPSO基本运算的频度与标准PSO相同，时间复杂度仍为O(TmaxN)，没有多余地增加算法的时间复杂度。而本文选取的另外两种对比算法（CPSONAIW、LC-PSO）分别采用了混沌优化摆脱局部极值法和社会学习法。CPSO-NAIW使用的摆脱极值法，使算法在原有的基础上额外地增加摆脱极值的循环操作，增加了算法的时间复杂度。LC-PSO基本运算的频度与标准PSO相同，没有多余地增加算法的时间复杂度。与对比算法相比，ARLIPSO在没有增加时间复杂度的情况下，寻优精度更高，所以此算法更优。

5 结束语

为了解决PSO算法存在收敛速度较慢且难以跳出局部最优值的问题，本文提出了ARLIPSO算法，该算法提出一种双向学习的策略与吸引-排斥策略相结合的方法，在提高了全局寻优能力的同时提高了局部搜索能力。此外还采用了双重自适应优化策略，对双向学习策略中的惯性权重和学习因子进行自适应调整，使算法的全局寻优能力和局部寻优能力达到更好的平衡。最后，通过对9个测试函数进行仿真实验，表明本文提出的ARLIPSO算法在单峰值和多峰值函数寻优中都具有较好的收敛速度和寻优精度。