一种带有二维扰动和自适应学习因子的粒子群算法

王 磊，王行甫，苗付友，

(中国科学技术大学 计算机科学与技术学院， 合肥 230027)

1 引 言

粒子群算法(Particle Swarm Optimization，PSO)是1995年由Kennedy等人[1]提出的一种模拟鸟类觅食行为过程的随机智能优化算法，该算法结构简单，运行速度快且所调整的参数少，被广泛地应用于函数优化和工程实践等诸多领域，已经成为一种重要的优化工具.但由于基本PSO算法在优化复杂的多峰问题时存在收敛速度慢、容易陷入局部最优等问题，使得基本PSO算法在实际应用中受到限制.在近几年的研究中，许多关于PSO算法的改进和应用逐步涌现.文献[2]提出了一种惯性权重线性递减的PSO算法.文献[3]引入模糊方法非线性的调整惯性权重.文献[4]根据适应度值距离比优化了PSO算法，改善了算法容易陷入早熟的问题.文献[5]使用其他粒子的最优历史信息更新粒子的速度，在避免陷入早熟上具有很好的效果.文献[6]在更新惯性权重时引入了贝叶斯定理论.文献[7]提出了一种基于三角函数的动态参数选择的PSO算法，提高了算法的收敛速度和鲁棒性.文献[8]引入具有周期振荡性的正弦函数因子，使得每个粒子位置获得周期性振荡，扩大了搜索空间，避免了算法陷入早熟.这些算法对于PSO算法性能的提高有比较好的改善，但大部分算法在后期存在收敛速度慢、容易陷入局部最优以及精度不足的问题，特别是在复杂的高峰多维函数问题上尤其明显.

为了解决这些问题，本文提出了一种带有二维扰动和自适应学习因子的粒子群算法(Particle Swarm Optimization algorithm with Two Dimensional Disturbance and Adaptive Learning Factor，TDDALFPSO).

2 PSO算法

PSO算法是从鸟类觅食过程得到启发而提出的一种优化方法，在算法中每个优化问题的解对应搜索空间的一个粒子，每个粒子具有一定的速度来决定其运动的距离和方向.每个粒子通过被优化的函数计算其适应度值.整个问题优化过程就是通过粒子寻找在搜索空间中满足问题需求并具有最优适应度值对应的空间位置.

在D维空间中，初始时PSO有一群大小为N的随机粒子，其中第i个粒子的位置为xi=(xi1,xi2,…,xiD)，速度为vi=(vi1,vi2,…,viD)，然后每个粒子通过两个最优位置来更新自己的速度和位置，一个是自己的历史最优位置pbesti=(pbesti1,pbesti2,…,pbestiD)，另一个是所有粒子的历史最优位置gbestd=(gbestd1,gbestd2,…,gbestdD)，具体公式如下：

vi(t+1)=wvi(t)+c1r1(pbcsti-xi(t))+
c2r2(gbestd-xi(t))

(1)

xi(t+1)=vi(t+1)+xi(t)

(2)

公式中t为当前迭代次数；w为惯性权重；c1和c2分别为认知系数和社会系数(学习因子)，其作用是使粒子具有自我总结和向群体中优秀粒子学习的能力，向两个历史最优位置学习；r1和r2为0～1间的随机数；为了防止粒子冲出搜索空间并获得较好的效果，粒子位置限制在[xmin,xmax]范围内，速度限制在[vmin,vmax]范围内.

3 TDDALFPSO算法

PSO算法之所以会有收敛速度慢、容易陷入局部最优等问题主要原因有两个：

1)算法无法很好地平衡全局搜索能力和局部搜索能力；

2)搜索过程中粒子需要通过自身历史最优位置和全局历史最优位置来调整自己，随着搜索的深入，粒子群的多样性会减少，另外如果全局历史最优位置离真正的最优位置很远的话，算法很容易陷入局部最优；

针对这些问题本文提出了TDDALFPSO，并从三个方面进行改进：

1)为了平衡好全局搜索能力和局部搜索能力，提高算法的效果，本文提出了一种自适应调节惯性权重和学习因子的算法来调节式(1)中的惯性权重w和学习因子c1、c2；

2)为了避免离种群最优位置较远的全局历史最优位置对搜索的影响，本文提出了一种基于位置、速度二维扰动的算法来更新粒子的位置；

3)为了增加粒子群的多样性，在每次迭代过程中变异一些适应度值比较差的粒子，让它们来搜索空间的其他领域.

3.1 自适应惯性权重和学习因子调节算法

为了获得更好的效果，PSO算法需要平衡好全局搜索能力和局部搜索能力.在迭代初期，惯性权重w应该具有更快的下降速度，增加粒子更新的步长，使得群体能够较快的搜索到可行解区域；在迭代后期，惯性权重w应该具有较慢的下降速度，减小粒子更新速度的步长，使得粒子群在可行解区域里微调搜索到全局最优解；并且在迭代的初期，群体应该具有比较强的自我学习能力，随着迭代的继续，自我的学习能力应该减弱，社会学习能力不断的增加.

基于上述思想本文提出了一种自适应惯性权重和学习因子调节算法：

(3)

(4)

(5)

w(t)=wmin+α(wmax-wmin)

(6)

c1(t)=c1max-α(c1max-c1min)

(7)

c2(t)=c2min+α(c2max-c2min)

(8)

式(3)中x表示算法进度，被映射到0～1，0表示算法开始，大于等于1表示算法结束，β是控制参数，用来控制收敛速度β>1.因为TDDALFPSO算法的运行分为能够确定的最大适应度评估次数和没法确定两种情况，所以进度x的计算需要分开讨论，公式(4)用来计算能够确定最大适应度评估次数时算法的进度，其中t是当前迭代次数，T是全部的评估次数.公式(5)用来计算无法确定最大适应度评估次数时算法的进度，其中δ表示算法要达到的精度，fitnessi和fitnessi+1分别代表第i、i+1次迭代中获得的全局历史最优值.式(6)中wmax和wmax分别为惯性权重的上下界，根据文献[2]分别为1.2和0.9.式(7)中,c1max和c1min是认知系数的上下界，根据文献[9]分别设置为2.5和0.1.式(8)中c2max和c2min是社会系数的上下界，根据文献[9]分别设置为3.2和0.8.式(6)和式(8)是一个变化速率先快后慢的单调递减函数，式(7)是一个变化速率先快后慢的单调递增函数.要想证明式(6)、式(8)是一个单调递减函数，式(7)是一个单调递增函数，并且速率是越来越慢，只需要证明式(3)是一个单调递减函数，并且速率越来越慢就可以了，下面给出证明：

(9)

(10)

对式(3)求导获得式(9)，因为β>1，所以α′<0，所以公式(3)是一个单调递减函数.再对式(9)求导获得式(10)，因为α″>0，所以式(9)单调递增，导致|α′|单调递减，证明式(3)变化速率越来越慢，得证.

通过图1可以发现β对式(3)的变化曲线有着重要的影响，β越大式(3)前期的下降速度越快，后期下降速度越慢.因为式(3)的变化速度影响着c1和c2的变化，所以β对于PSO自我学习能力和社会学习能力有着重要的作用.在PSO学习的过程中我们希望算法在前期能够具有较好的自我学习能力，后期能够具有较好社会学习能力，通过图1可以发现β为10能够比较好的满足这个需求，当β小于10的时候前期的变化速度比较慢，当β大于10的时候，前期的变化速度又太快，所以在下面的实验中将β设置为10.

图1 不同β值下公式(3)的变化曲线

3.2 基于位置、速度的二维扰动更新位置

因为PSO算法寻求最优值的时候，所有的粒子都会向全局历史最优值学习，在每次迭代过程中通过简单的对上一次迭代时的位置和当前迭代的速度进行求和来更新每个粒子的位置，如果全局历史最优值离种群最优值所在区域比较远的话，那么所有粒子就会向错误的方向学习，从而导致算法容易陷入局部最优.文献[8]引入具有周期振荡性的正弦函数因子，使得在每次迭代中每个粒子位置获得周期性振荡，扩大搜索空间，避免算法陷入局部最优，更新速度函数如下：

xi(t+1)=x1(t)(1-sin(h))+vi(t+1)sin(h)

(11)

但是这个方法有两个缺点：第一，如果全局历史最优解已经在最优解附近的话，扰动反而会导致搜索偏离最优解；第二，式(11)第一项xi(t)(1-sin(h))的范围在0和2xi(t)，振荡后的位置可能和原来位置较远.对于第一个问题，可以通过限定粒子振荡的条件来解决，只有被判定陷入早熟的粒子才进行振荡.为了判断粒子是否陷入早熟，引入一个精度ε，如果连续多次迭代中，邻近两次粒子历史最优值的差都小于ε，则判断该粒子陷入早熟，然后对粒子进行振荡.对于次数的选择，需要根据具体的问题来决定，在后面的实验中，通过将次数分别设置10、20、30、40和50进行对比，发现将其设定为20效果最好.对于第二个问题，可以通过限制粒子的振动幅度来解决.另外虽然粒子已经陷入了早熟，但是一般陷入早熟的粒子的位置在一些维度上是靠近全局最优解的，为了利用这些维度的优势，本文对粒子位置的每个维度进行一定幅度的振荡，同时为了避免粒子在振荡幅度过大，导致大幅度偏离原来的位置，将振荡的幅度限制在20%内.通过上面的想法对公式(2)进行改造：

xij(t+1)=r1vij(t+1)+(1-0.2r2)xij(t)

(12)

式(12)中xij(t)和xij(t+1)分别表示第t次、t+1次迭代过程中第i个粒子位置的第j维，vij(t+1)表示第t+1次迭代过程中第i个粒子速度的第j维，r1和r2都是在-1～1范围内的随机值.

3.3 随机变异增加粒子群的多样性

由于在PSO算法中，所有的粒子都要向全局历史最优值学习，从而导致算法在迭代的过程中粒子群的多样性会越来越低.为了优化这个问题，在每次迭代中选取一定数量适应度值最差的粒子进行随机变异，这样一方面可以增加粒子群的多样性，另一个方面可以让粒子群搜索更多的区域.对于选取多少粒子进行变异，需要针对不同的问题进行设置，如果选取的太多将会影响算法的性能，如果选取的太少无法很好的增加粒子的多样性，根据2/8原则，在后面的实验中我们将这个值设置为粒子群数量的20%.

3.4 DDALFPSO算法流程

基于上面的理论和改进方法，本文提出的TDDALFPSO算法的基本流程如下:

1)设置PSO算法中的各个参数，初始化粒子的位置和速度，并求出每个粒子的历史最优值pbesti和全局历史最优值gbestd；

2)首先通过式(1)、(3)～(8)更新粒子速度，然后判断当前粒子是否陷入早熟，如果陷入早熟用式(12)更新位置，否者通过式(2)更新位置.最后计算每个粒子当前的适应度值；

3)更新每个粒子历史最优位置和群体历史最优位置；

4)选取一些适应度值最差的粒子进行随机的变异；

5)如果评估次数达到最大评估次数或者精度达到目标要求则输出最优适应度值和对应的位置；否则，转向第3步，进入下一次寻优.

4 试验与结果分析

为了验证TDDALFPSO算法的性能，本文设计了TDDALFPSO算法和其他6个PSO算法的性能对比实验，其中包括1个基本PSO算法和5个已经优化了的PSO算法.

4.1 5个优化的PSO算法

5个优化的PSO算法分别为：文献[2]提出的一种线性的惯性权重线性递减的PSO算法(PSO-W)，文献[4]提出一种基于适应值距离比例的PSO算法(FDR-PSO)，文献[5]提出的一种基于综合学习PSO算法(CLPSO)，文献[7]提出的基于三角函数的动态参数选择的PSO算法(TPSO)，文献[8]提出的一种带正弦函数因子的粒子群优化算法(TFPSO).

4.2 测试函数

为了测试算法的寻优性，本文选取了5个经典的函数进行测试.每一个函数都有自己的特征，如无峰性，单峰性、多维性和凹凸性等，根据这些特征本文将5个测试函数分为两类：第一类，单峰函数(F1、F2)；第二类，多峰函数(F3、F4和F5).5个函数都是寻求极小化问题，每个函数的形式、维数、搜索空间、理论极值和函数峰值特征如表1所示.

4.3 参数设置

基本PSO算法的参数设置和文献[1]一致；其他5个PSO算法的参数和对应论文中的设置一致；通过文中的讨论对TDDALFSO算法中的参数速度上限vmax设为空间上限的10%，速度下限vmin设置为空间的10%，式(3)中β的设为10，每次迭代过程中粒子变异数目设置为种群规模的20%，根据文献[2]将惯性权重上限wmax设为1.2、下限wmin设为0.9，根据文献[9]认知系数上c1max限设为2.5、下限c1min设为0.1，社会系数上限c2max设为3.2、下限c2min设为0.8、早熟判定精度ε为1E-3、早熟判定次数l为20.所有算法种群规模N设置为50，维度为30，最大适应度评估次数为5000，运行次数为30，精度阈值δ为1E-8.

表1 5个经典的测试函数

4.4 试验结果分析和比较

为了尽量避免因随机操作而造成比较结果的不公平性，对表1中的5个测试函数进行30次独立实验，每次实验最大适应度评估次数为5000，然后求取平均值、方差和最优值作为测试结果，具体测试结果详细见表2(其中黑色加粗并加下划线的表示对应项的最好结果)和图2.从表2中可以看出TDDALFPSO在所有函数测试中的性能表现都要优于基本PSO，其中对于函数F1、F4函数的均值达到了全局最优值0，对于函数F2、F3和F5的均值相对于基本PSO分别降低了5、30和2个数量级，且对于所有的函数的标准差都要比基本PSO要小，说明TDDALFPSO能够显著的提高寻优效果和稳定性.和其他5个优化了的PSO相比，对于函数F3和F4，TDDALFPSO的平均值、方差和最优值显著小于其他5个PSO算法.对于函数F1，虽然TDDALFPSO和TFPSO的均值、方差都达到了全局最优值0，但是仍显著的优于其他3个PSO算法.对于函数F2、F5，TDDALFPSO的均值、方差和最优值都要优于其他PSO算法，特别是对于函数F5，TDDALFPSO的最优值和其他PSO算法相比要低7个数量级，说明对于F5，TDDALFPSO在避免陷入早熟的问题上具有更大的优势.由此可见TDDALFPSO和基本PSO以及其他5个优化了的PSO算法相比它的寻优效果和稳定性具有极大的优势.

表2 不同PSO改进算法性能比较

图2是7个PSO算法对5个测试函数寻优过程的曲线图，由图可以清楚的看出，TDDALPSO算法在5个测试函数上的收敛速度要好于其他PSO算法，特别是在函数F1(Sphere)、F4(Griewanks)和F5(Schwefel)上，TDDALPSO的最优收敛曲线直线下降，说明和基本PSO算法以及其他5个优化PSO相比TDDALPSO更容易跳出局部最优值.

综上所述，无论是在处理单峰函数还是处理多峰函数的问题上，和其他六个PSO算法相比，TDDALFPSO算法在精度、收敛速度和稳定性上都有巨大的优势.

5 结 论

本文针对基本PSO算法在寻优过程中容易陷入局部最优值、后期收敛速度慢和收敛精度低等问题，提出了一种带有二维扰动和自适应学习因子的粒子群算法(TDDALFPSO)，从三个方面对基本PSO算法进行改进.通过与基本PSO算法其他5个已经优化了的PSO算法在5个经典测试函数上进行实验对比，可以看出本文提出的算法在收敛速度、精度和稳定性方面和基本PSO算法相比有了显著的提高，并且和其他5个PSO算法相比也有很大的优势，其中部分函数成功摆脱了局部最优值的干扰，找到了全局最优值.但是本文提出的算法仍没有完全解决陷入早熟的问题，对于如何更加有效地跳出局部最优仍有待近一步的解决.

图2 函数寻优曲线