基于邻域速度模仿策略的粒子群算法

邓 浩，李均利，胡 凯

(四川师范大学 计算机科学学院，四川 成都 610101)

0 引 言

粒子群算法(PSO)是Kennedy和Eberhart提出的一种进化计算方法，是通过模仿鸟群在觅食过程中的迁徙和聚集提出的一种基于群体智能的全局随机搜索算法。算法简单、易于实现，没有过多参数的调节，在科学研究和工程实践中受到了广泛关注以及成功应用。但和许多其它群智能优化算法类似，传统的PSO算法存在易陷入局部最优、收敛速度慢等问题。

进化算法中的进化直接表现为个体位置的变化，而在PSO算法中粒子位置的更新依赖于粒子速度。因此，很多研究者对PSO算法中的粒子速度更新方式进行了深入的研究，大体可以分为3类：第一类是调整PSO的参数，如Tanweer等提出一种自调节PSO算法，利用对个体适应值优劣的感知来调整惯性权重w[1]。Liang等提出一种非线性动态改变惯性权重的策略[2],通过平均粒子间距更新惯性权重；第二类是改变粒子邻域拓扑结构，如李文斌等提出邻域结构为复杂网络的粒子群算法[3]，在粒子与网络节点间建立映射关系,并根据节点的邻居集合获得粒子的动态飞行邻居；薛文等提出分群策略的混沌粒子群优化算法[4],将种群分为迭代分群和混沌机制迭代分群，依据早熟判定策略，对种群实行两阶段寻优；第三类是引入其它策略，如Ouyang等引入和声搜索提出了具有全局选择策略的和声搜索粒子群算法[5],Cheng和Jin引入社会学习机制提出了一种社会学习粒子群算法[6]。

本文提出了一种基于邻域速度模仿策略的粒子群算法(imitate neighborhood velocity PSO，INVPSO)，在标准PSO算法的基础上，让粒子以一定的概率直接模仿邻域内最优粒子的速度，自适应地调整粒子收敛情况；然后，对排名靠后的粒子以一定的概率进行质心变异以增强算法跳出局部极值的能力。

1 PSO

1.1 基本PSO算法

1995年Kennedy和Eberhart提出了基本PSO算法。N个粒子组成的种群在大小为D维的空间中以速度V飞行，一个粒子位置代表一个潜在解。每个粒子在每次迭代过程中，通过速度来更新位置X，每个位置代表的坐标值输入到目标函数中会得到一个函数值，由这个函数值可以得到粒子位置的适应值。在飞行的过程中，粒子利用个体经历过的最优适应值pb和群体经历过的最优适应值gb来调整自己的飞行速度，经过若干次迭代得到最终解。

基本PSO算法的速度和位置更新公式如下

Vi,d=Vi,d+c1rand1(pbi,d-Xi,d)+c2rand2(gbi,d-Xi,d)

(1)

Xi,d=Xi,d+Vi,d

(2)

其中,Vi,d表示第i个粒子的第d维，c1、c2为学习因子，分别调节对个体经验和群体经验的学习率，rand1、rand2为(0,1)之间的随机变量。pbi,d、gbi,d、Xi,d分别表示第i个粒子历史最优值第d维、全局历史最优值第d维、第i个粒子位置第d维。

1.2 PSO算法

1998年Shi和Eberhart将惯性权重概念引入基本PSO算法，将粒子速度更新式(1)修正为

Vi,d=wVi,d+c1rand1(pbi,d-Xi,d)+c2rand2(gbi,d-Xi,d)

(3)

其中，w称为惯性权重，用于调节粒子当前速度对新速度的影响，合适的w能够使粒子在保持运动惯性的同时进一步扩展搜索空间。

随着迭代次数线性减小，其更新公式如下

(4)

其中，wmax表示w的最大值，wmin表示w的最小值，t表示当前迭代的次数，tmax表示最大迭代次数。通常设置wmax=0.9，wmin=0.4。

2 INVPSO

粒子群算法中一个重要的问题是如何指导粒子向更优点运动，式(3)使用历史速度、个体历史最优点和全局历史最优点信息来更新粒子速度。有研究指出，在进化算法中，差分方法提供了类似梯度的信息，在粒子间距较大时，更新前后适应度的变化并不能很好描述梯度信息来指导算法的搜索，但是在粒子距离较近时，这类信息就能给出很好的指导[7]。和差分方法类似，邻域最优粒子的速度也提供类似于梯度的信息，在粒子间距较大时，因为粒子距离较远，邻域最优粒子的速度并不能很好描述梯度信息来指导算法的搜索，但是在粒子距离较近时，这类信息就能给出很好的指导。同时，相比于差分中粒子位置提供梯度信息，速度项本身还包含了更新速度时涉及到的个体历史信息和全局最优的信息。

2.1 邻域速度模仿策略

对邻域内的邻居粒子，比较位置更新前后的适应值，选择向着更优方向前进最多的粒子按一定概率在各个维度模仿其速度。

最优邻域粒子速度的选择

(5)

这里可以模仿的速度可以是式(3)更新前的旧速度或者更新后的新速度，而因为新速度在更新的过程中，因为受到本轮迭代历史速度、个体历史最优、全局历史最优的影响，所以包含更多的信息。

速度模仿

(6)

其中，Vi,d表示第i个粒子第d维速度，rand表示(0,1)之间的随机数，Vbi,d表示第i个粒子邻域最优粒子速度的第d维。

当模仿对象速度指向当前粒子适应值减方向，则模仿行为会加速粒子向当前局部极值运动。当模仿对象速度指向当前粒子适应值增方向，则模仿行为会使粒子远离当前局部极值。为了说明邻域速度模仿策略思想，以下针对求最小值问题进行分析，因为最大值问题取负即可变为最小值问题，所以以下分析对最大值问题同样成立。

情况1：当前粒子如果和模仿目标在同一个单调区间，并且目标速度指向谷底(即当前局部极值)，则模仿行为会加速粒子向当前局部极值运动；如果目标速度指向谷底反方向，则模仿行为会使粒子远离当前局部极值或者减弱趋向极值的速度。前一种情况更容易出现在求解后期，后一种情况更容易出现在求解前期。

情况2：当前粒子如果和模仿目标在不同单调区间，则不管在前期、后期，目标速度提供的梯度信息和当前粒子无关，模仿其行为相当于随机变异。而在前期，粒子和目标在不同单调区间的概率大于后期粒子和目标在不同单调区间的概率。

粒子位置更新前后的适应值变化提供了一定的梯度信息，而与位置更新有关的速度项则提供了梯度方向信息。因为在前期，粒子均匀分布在搜索空间中，互相之间距离较大，在后期，粒子收敛到一些局部地区，互相之间距离较小，所以模仿速度这一策略，利用速度提供的梯度信息，在前期更容易出现情况1，粒子邻域的速度提供了较大范围内适应值的变化信息，模仿其速度使粒子在向全局最优方向前进的同时也保持种群的多样性；在后期更容易出现情况2，粒子邻域的速度提供了较小范围内适应值的变化信息，模仿其速度使粒子向极值方向加速收敛，并且保持一定的种群多样性。

综上所述，邻域速度模仿策略能根据邻域粒子的情况自适应地调整粒子收敛情况。在前期粒子间距较大时更可能给粒子随机的扰动，增强跳出局部极值的能力；在后期粒子间距较小时能加速粒子向最优点收敛。

2.2 邻域策略

本文使用动态邻居拓扑结构，在每次迭代中根据各个粒子的位置，选择离目标粒子最近的K个粒子作为其邻居。

粒子xi和粒子xj的距离di,j采用欧氏距离

(7)

2.3 变异策略

在质心法[8]的基础上，采用质心变异策略，对当前粒子，另外随机选取两个粒子，将当前粒子迁移到3个粒子的质心周围。

在具体计算时，针对目标粒子目标维度，与其它随机两粒子对应维度求和取平均，然后再乘以一个(0,1)之间的随机数

(8)

其中，xr2，xr3表示另外随机选取的两个粒子。

2.4 模仿和变异发生条件

随着算法的迭代，粒子向最优点收敛， 在前期，要让粒子扩展搜索范围以跳出局部极值点，在后期，要让粒子加速收敛以提高收敛速度和精度。所以模仿和变异发生的概率要随着迭代次数的增加而减小。本文以式(4)定义的线性惯性权重为参考，设计了随着迭代次数增加而减小的模仿和变异发生概率条件

rand

(9)

对所有的粒子都按式(9)设定模仿行为发生的概率。对于适应值排名靠后粒子按式(9)设定变异发生的概率，适应值排名靠后以各粒子均值为参照，对适应值大于0.8倍均值的粒子施加变异。

2.5 边界策略

当位置超过边界时，采用随机回退策略，让粒子退回到超出的边界附近1/4取值范围内

(10)

其中，xi,d表示第i个粒子的第d维坐标，ld表示第d维的取值下限，ud表示第d维的取值上限。

当速度超过限制时，则速度保持在边界

(11)

其中，Vi,d表示第i个粒子的第d维速度，Vmin表示速度的取值下限，取Vmin=-0.01(ud-ld)，Vmax表示速度的取值上限,取Vmax=0.01(ud-ld)。

2.6 位置更新策略

比较位置更新前后的适应度变化，若更新后适应值没有优于原位置，则返回原位置

(12)

其中，f(xi)表示第i个粒子的位置的适应值，f(xi+vi)表示第i个粒子的位置加上其速度vi之后位置的适应值。

2.7 算法步骤

输入：种群规模N，学习率c1、c2,惯性权重最大值最小值wmax、wmin,最大迭代次数M，维度D,搜索空间(l,u)，邻域大小k。

输出：最优解

步骤1 随机初始化粒子群和速度，评估个体适应值，迭代器item=0；

步骤2 while(item

步骤3 按式(4)更新权重w，按式(3)更新速度；

步骤4 更新全局最优、个体历史最优、邻居表、各粒子适应值均值fmean；

步骤5 比较每个粒子位置更新前后适应度的变化趋势，按式(5)确定每个粒子在k邻域大小内的最优邻居粒子；

步骤6 对每个粒子的每个维度，如果rand(0,1)

步骤7 对每个粒子,如果f(xi)>0.8fmean，则：

对该粒子的每个维度，如果rand(0,

1)

步骤8 按式(10)和式(11)对位置和速度进行超限处理；

步骤9 按式(12)评估粒子适应度值，更新粒子位置；

步骤10item++；

步骤11 END while；

步骤12 输出最优解。

3 实验结果及分析

3.1 测试函数

实验采用表1所示的函数，其中f1-f5是单峰函数，主要用来测试寻优精度，f6-f13为多峰函数，具有很多局部极值点，可以检验全局搜索性能和跳出局部极值的能力。所有函数的最优值都为0，搜索范围为(-100，100)。

3.2 有邻域速度模仿和无邻域速度模仿的对比

本小节对比了有邻域速度模仿策略和无邻域速度模仿策略(即算法步骤6条件改为ifrand>1)，最大迭代次数M=1000，种群规模N=100，搜索空间维D=30,邻域大小取k=10,重复30次结果见表2，结果“+”表示在该函数上有邻域速度模仿策略优于无邻域速度模仿策略，结果“-”表示有邻域速度模仿策略劣于无邻域速度模仿策略，结果“=”表示有邻域速度模仿策略性能和无邻域速度模仿策略相同。B、W、S分别表示对“+”、“-”、“=”的统计数量，B-W表示“+”个数和“-”个数之差。表中加粗数字表示：从均值上看，在该函数上该算法结果优于其它算法。T值中～表为对比的两项均值和标准差均为0，T值计算出现除以0错误。

表1 13个标准测试函数

从结果可以看出，除了在f1、f10、f11上两方法效果相同外，有邻域速度模仿策略方法在其它测试函数上均显著优于无邻域速度模仿策略，说明邻域速度模仿策略确实提高了算法性能。

3.3 模仿更新后的速度与更新前的速度的对比

粒子模仿的速度可以是式(3)更新前的速度(旧速度)也可以是更新后的速度(新速度)。两种方法重复30次的结果见表3。从结果可以看出，在各个测试函数上模仿新速度的结果全部优于或同于模仿旧速度，特别是在单峰函数上。模仿更新后的速度效果明显优于模仿更新前的速度。这可能是因为更新后的速度包含更多的信息。

表2 有邻域速度模仿与无邻域速度模仿的对比

表3 新旧速度模仿

3.4 邻域大小对INVPSO的影响

邻域速度模仿策略利用邻域速度在不同阶段的变化情况达到了对不同阶段的自适应功能。这种能力和模仿的邻域大小是否有关系？

本节比较了邻域邻居数量在1～30的情况下INVPSO算法的运行结果，具体情况见表4，对其进行Friedman检验分析，结果见表5，其中P值表示在“不同邻域大小情况下算法性能相同”假设下该观察结果或者更极端情况出现的概率。P值越小，算法间差异越显著。当P<0.05时表明各算法存在显著性能差异，当P>0.05时各算法不存在显著差异。

由表5可以看出，邻域大小取1～30时，在整个测试集上P=0.299>0.05,不存在显著差异；在单峰函数上在P=0.081>0.05，不存在显著差异；在多峰函数上P=0.997，不存在显著差异。可以说，INVPSO算法对邻域大小不敏感，具有较强的鲁棒性。

表4 邻域数1～30下独立运行30次的平均结果

表5 邻域数1～30的平均排名与Friedman检验分析

3.5 与其它算法对比

本文选取了4种算法与INVPSO比较，分别是标准PSO算法、混合萤火虫算的粒子群算法HFPSO[9]、适应度依赖优化算法FDO[10]、基于多种群的自适应迁移PSO算法MSMPSO[11]。将这4种法所使用共同参数都设为相同，最大迭代次数M=1000，种群规模N=100，搜索空间维D=30。INVPSO算法邻域大小取k=10，其它参数都与参考文献持一致。

3.5.1 求解精度

从表6可以看出，INVPSO在10个函数上取得了最优的均值结果，特别在f8到f11上达到了最优点，其中f8函数其它算法均不能正确求解。PSO取得了一个最优均值结果，MSMPSO取得了两个最优均值结果。对f6和f12，各个算法均未正确求解。从最优均值结果来看，在单峰函数和多峰函数上，INVPSO均有最优表现，明显优于其它对比算法。

3.5.2 收敛性能分析

对各个算法在以下各个函数上取得最好成绩的一次的收敛过程画出曲线，比较其收敛速度的快慢。因对f12各函数均未正确求解且差距较大，所以给出f1到f11及f13的收敛曲线，如图1所示，各函数收敛图图例同f1函数收敛图图例。可以看出，除了f4、f9和f13,在其它函数上，INVPSO的收敛性能均优于其它对比算法，在f4上，INVPSO和FDO优于HFPSO、MSMPSO和PSO。在f9上，10代以前HFPSO的收敛速度快于INVPSO算法，但是在10代到20代之间，INVPSO和HFPSO相近。在f13上，HFPSO收敛速度优于INVPSO，INVPSO优于MSMPSO和PSO。通过在13个函数上的比较可以看出，INVPSO算法在单峰测试函数和多峰测试函数上均有较优的收敛性能。

3.5.3 显著性检验

T检验：对INVPSO算法和对比算法在13个函数上的结果进行T检验，结果见表3，“+”、“-”、“=”表示INVPSO算法在均值结果上对相应算法的均值结果在T检验下分别处于显著优于、显著劣于、差异不显著3种状态。

从表7可以看出，INVPSO算法其它对比算法的B-W得分均大于0，具有更好的综合性能。在单峰函数f1～f5上，INVPSO和MSMPSO在T检验下性能相同，而在多峰函数f6～f13上，INVPSO算法对MSMPSO算法B-W分数为4分。在单峰函数上，INVPSO和MSMPSO有相同的性能，而在多峰函数上，INVPSO算法优于MSMPSO算法。

4 结束语

本文提出了一种邻域速度模仿策略，并将这一策略引入粒子群优化算法，提出了基于邻域速度模仿的粒子群优化算法(INVPSO)。通过模仿邻域粒子的速度更新后的速度，利用了邻域粒子包含的梯度变化信息，使得前期扩展了粒子的探索范围，后期加速了粒子的收敛，实现了粒子群的自适应调整。同时采用三点质心变异，提高了粒子跳出局部极值的能力。实验结果表明,邻域模仿策略确实有效；模仿新速度效果优于模仿旧速度；邻域速度模仿策略对于邻域大小不敏感，具有较强的鲁棒性；INVPSO具有较好的收敛性能和收敛精度，尤其在多峰函数上具有更好的收敛性能。

表6 5种算法在测试集上的表现

图1 在12个函数上各算法收敛曲线

表7 INVPSO算法对其它算法的T检验结果