基于种群分区的多策略综合粒子群优化算法

李冰晓，万睿之，朱永杰，赵新超

(北京邮电大学 理学院，北京 100876)

粒子群优化算法[1]是由KENNEDY和EBERHART于1995年提出的一种全局优化算法.它源于对鸟群觅食行为的模拟.自提出以来，粒子群优化算法以其参数少、概念简单、易于实现等优点引起众多研究者关注，并在数据聚类[2]、图像处理[3]、特征选择[4]、电力系统[5]、人工神经网络[6]等实际问题中得到了广泛应用.

然而，粒子群算法容易早熟收敛，算法后期多样性不足等问题限制了它的性能.为改善上述问题，众多学者做了大量的研究工作，主要分为四个方面：参数调整[7]、拓扑结构改善[8]、改进学习策略[9]和与其他算法相结合.文献[10]提出了CLPSO，算法中的粒子以一定概率向其他粒子的历史最佳经验学习，极大地增加了种群多样性；文献[11]提出了一种简化而高效的粒子群优化算法,算法中对粒子的学习样本以一定概率施加均匀扰动，能够有效改善算法陷入局部极值，增大找到最优解的概率；文献[12]提出了一种基于扰动全局最优概念的新粒子更新策略的扰动粒子群优化算法(pPSA)，以解决粒子群中的早熟收敛和多样性保持问题；文献[13]提出了一种新的多阶段扰动差分进化算法(MPDE)，采用方向性差异信息策略和多参数自适应实现了一种新的变异策略“多阶段扰动”；文献[14]提出一种基于分段优势学习的SLPSO算法，算法中的整个种群被分为精英子群与普通子群，普通子群中粒子分段向精英种群中的粒子进行学习，使得算法能够充分利用精英粒子的信息，避免了早熟收敛；文献[15]将差分变异操作与SLPSO算法相结合提出了差分变异与新型社会学习粒子群优化算法(DSPSO)；文献[16]在SLPSO算法的启发下提出了带有混合变异策略的多种群协作粒子群优化算法(MPCPSO); 文献[17-21]都采用了多种群的策略对各个子群进行不同的进化策略，研究结果表明多种群的多策略进化是改善粒子群算法性能的一个有效研究方向.

目前对粒子群算法的研究使得算法性能得到了不同程度的提高，多种群操作以及不同扰动策略的引进有效改善了粒子群算法收敛精度不高的问题.然而，在很多问题上粒子群陷入局部最优以及早熟收敛的问题还没有得到很好的解决. 针对此现状，本文提出一种基于种群分区的多策略综合学习粒子群优化算法(MSPSO).在每次迭代中，利用一种新的竞争机制将种群分为两个子群：潜力子群与普通子群，对这两个子群采取不同的学习策略.在潜力子群中，粒子的进化除惯性部分外，还向该子群中随机选取的某粒子的历史最佳经验学习，这种学习策略能够在充分利用优秀粒子精英信息的同时保持种群多样性.在普通子群中，设置了两种学习策略.算法前期，粒子向潜力子群中随机选取的某粒子的历史最佳经验学习；算法后期，则以一定概率直接向全局最优经验学习.这种进化方式既保持了两个子群的协同进化和种群多样性，又加快了收敛速度.实验结果表明，所提算法具有较快的收敛速度，并且能够有效防止陷入局部极值，获得极有竞争力的解.

1 相关工作

1.1 标准PSO算法

PSO算法首先随机初始化一群粒子，然后通过飞行速度和位置的逐步更新迭代找到最优解.在每一次迭代中，粒子通过跟踪个体发现的最好极值和群体发现的全局极值更新自己的飞行速度和位置.假设在D维搜索空间中，有N个粒子组成一个群体，t时刻粒子i由位置向量(xi1,xi2,…,xiD)和速度向量(vi1,vi2,…,viD)表示.在优化过程中，下一代种群中个体的速度和位置向量由如下公式更新，

Vij(t+1)=ωVij(t)+c1r1(Pij(t)-Xij(t))+c2r2(Pgj(t)-Xij(t)),

Xij(t+1)=Xij(t)+Vij(t+1).

(1)

其中i=1,2,…,N,j=1,2,…,D,N为群体规模，w为惯性权重，r1,r2为(0,1)区间均匀分布的随机数，c1,c2为加速系数.Pij(t)为粒子i的历史最佳位置的第j维分量，Pgj(t)为整个种群的历史最佳位置的第j维分量，t为当前迭代次数.

1.2 CLPSO算法

与标准PSO算法不同的是，CLPSO算法中的粒子以概率(1-pc)向个人历史最佳经验学习，以概率pc向由竞争机制选择出的其他粒子的历史最佳经验学习.粒子更新过程由如下公式产生：Vij(t+1)=ωVij(t)+cr(Pfi(j)(t)-Xij(t)),其中w为惯性权重,r为(0,1)区间内的随机数,c为加速系数，fi(j)为由CLS构建的学习样本的索引.下面是CLPSO构建学习样本的过程.

对于粒子i的每一维度j：[1]产生随机数p,p∈(0,1);[2]若p≤pc，粒子向由竞争机制选择出的其他粒子的历史最佳经验学习；[3]若p>pc，粒子向其个体历史最佳经验学习.

与标准PSO算法相比，粒子可以向不同的粒子历史最佳个体学习，有效保证了种群多样性，提供了大范围而有潜力的搜索区域.

1.3 Nmp3PSO算法

文献[22]提出一种基于非均匀变异和多阶段扰动的粒子群优化算法(Nmp3PSO).该算法在执行的不同阶段利用对当前最优解施加大小不同的邻域扰动操作，并且引入非均匀变异运算适应性调整解向量的搜索步长，具体操作如下.

1.3.1非均匀变异算子

假设对粒子xi={xi1,xi2,…,xin}T的第d个分量执行变异运算，而xid的下界和上界分别记为LB和UB，则变异后的分量：

1.3.2最优粒子扰动策略及粒子更新

对全局最优粒子gbest依据方差可调的正态随机分布进行扰动得到新的最优粒子pgbest，然后选定的待更新粒子向pgbest学习，速度更新公式为：

其中σ1>σ2>σ3表示正态扰动幅度的半径参数；α1,α2是半径变化的控制参数，且α1<α2；t是当前函数值计算次数，T是最大函数值计算次数.

算法性能分析表明，Nmp3PSO能够较好兼顾群体优化算法的多样性和精英学习强度之间的平衡问题.

1.4 其他群体智能算法

文献[23]提出了一种自适应差分进化算法(SaDE)，算法中的试验向量生成策略及其相关的控制参数通过学习它们以前生成的潜力解的经验而逐渐实现自适应，从而自适应地确定更合适的进化策略及参数设置来匹配搜索过程的不同阶段.实验结果与传统DE[24]以及几个先进的参数自适应DE变体相比,SaDE能够获得更高质量的解、更小的标准差以及更高的成功率.

文献[25]提出了一种遗传算法的变体(GL25)，算法在交叉操作之前执行了3个过程.首先是雌性和雄性的分化过程，它决定了种群中可能成为雌性或雄性父母的个体；然后采用两种不同的选择机制从每个群体中选择雌雄亲本；最后讨论了最适合的进化模型的选择以及从这些亲本选择机制中获益.实验表明这3个过程可以增强以父代为中心的交叉算子的操作性能.

2 多策略综合学习粒子群优化算法(MSPSO)

2.1 研究动机

对粒子群体中不同适应值的粒子信息如何个性化的进行开发和利用是本文最初的出发点，逐步具体化为如何设置一种新的竞争规则将整个种群划分成不同的子群，对携带精英信息较多的子群如何在加强精英搜索的基础上引进较多的群体多样性，对携带差异化信息较多的群体如何在扩大全局搜索的基础上适当加速算法的收敛，同时保证整个种群及多个子群能够保持协同进化来平衡算法的全局搜索能力和局部开发能力.

2.2 MSPSO算法

首先设计合理的竞争机制将整个种群分为两个子群，对这两个子群进行不同偏向的进化操作.

为了利用群体进化过程中多种关键信息，本文考虑划分不同子群的两个指标：一是每个粒子相邻两次迭代适应值的改变量，二是当前迭代适应值的大小.粒子前后两次迭代适应值的改变量越大，说明该方向潜力越大；粒子当前适应值越大，也说明该方向潜力越大.竞争机制构建的两个指标α和β分别设置如下,

(2)

(3)

R=λ1α+λ2β.

(4)

综合竞争指标R既考虑解的改变量，又考虑解的优异程度，因此从算法搜索状态和搜索性能两方面构建了启发式信息.对R进行降序排列，前1/2作为潜力子群，后1/2作为普通子群.其中F,FN分别是粒子前后两次迭代的适应值,λ1,λ2为参数，本文初步设置为1和3;α初始化为0.

针对潜力子群，粒子i的飞行速度和位置向量在第j维上的更新公式如下:

Vij(t+1)=ωVij(t)+r3(randn*Pkj(t)-Xij(t)),

(5)

Xij(t+1)=Xij(t)+Vij(t+1),

(6)

其中w为惯性权重，更新公式为0.5×(1-FES/maxFES)+0.15.FES为当前函数评价次数，maxFES为最大评价次数.Pk为该子群中随机选择的粒子的历史最佳经验.r3为随机性参数，为保证(5)式中学习部分的有效性，此参数不宜过小，故设置为0.45+r，其中r为(0,1)区间内均匀分布的随机数,randn为满足标准高斯分布的随机数.对学习样本施加高斯扰动,目的是增加种群多样性，加大粒子的学习范围，研究动机是在精英综合学习的基础上增加一定的群体多样性，即选择多样化的精英搜索路径.

针对普通子群，粒子i的飞行速度和位置向量在第j维上的更新公式如下,

(7)

Xij(t+1)=Xij(t)+Vij(t+1),

(8)

其中w,r1的设置如(1)式；Pl为潜力子群中随机选择的粒子l的历史最佳经验;Pg为全局历史最佳经验;μ为参数，设置为1/(1+(FES/N)(1/2)×exp(i/N)).随着算法的进行，粒子飞向全局历史最佳经验的概率逐渐增加，能够加速算法收敛；对普通子群粒子更新公式的研究动机是在保持种群多样性的基础上加速算法的收敛，并且排名越靠后的粒子飞向全局历史最佳经验的概率越大，有助于加速粒子的收敛速度，从而提高整个种群解的质量.

2.3 算法步骤

步骤1 初始化粒子种群规模N、粒子搜索空间D、函数最大评价次数maxFES等算法参数，随机初始化粒子的飞行速度和位置；

步骤2 初次按照适应值升序排序分为两个子群，分别执行不同搜索偏向的速度和位置更新操作，转到步骤4；

步骤3 按照竞争机制将整个种群分为两个子群，对不同子群中的粒子分别执行对应进化操作；

步骤4 对溢出边界粒子进行修正操作；

步骤5 执行位置更新公式；

步骤6 保留粒子历史最佳经验，全局最佳经验；

步骤7 若函数最大评价次数达到设置值，输出结果；否则回到步骤3.

3 对比仿真实验与结果分析

3.1 测试函数与参数设置

为了验证所提出的MSPSO算法的性能，将MSPSO与标准PSO，CLPSO，Nmp3PSO，标准差分算法DE，SaDE，以及GL25这6种算法在CEC2005的11个经典基准测试函数上进行对比分析,为方便起见将CEC中的测试函数重新编号为F1～F11，如表1所示.

表1 基准测试函数

表2 7种算法数值实验结果

表2包含各算法运行最终所达到的最优值Min、均值Mean和标准差STD，另外小计部分显示在11个测试函数上各算法的最优值Min及均值Mean能达到相对最优结果的个数，总计部分显示各算法综合考虑最优值Min以及均值Mean能达到相对最优结果的个数.各算法的收敛曲线如图1所示.

3.2 算法仿真结果与分析

由表2可以看出，1)PSO，CLPSO，Nmp3PSO，MSPSO，DE，SaDE和GL25在11个测试函数最终结果的最优值上分别取得0个、1个、2个、8个、4个、4个和2个最优结果；2)PSO,CLPSO,Nmp3PSO,MSPSO,DE,SaDE和GL25在11个测试函数最终结果的平均值上分别取得0个、2个、0个、10个、1个、1个和0个最优结果；3)结合最优值与平均值来看PSO,CLPSO,Nmp3PSO,MSPSO,DE,SaDE和GL25分别取得0个、3个、2个、18个、5个、3个和2个最优结果.综合表2和相应分析可以看出，在这11个基准测试函数上，MSPSO算法相对优于其他对比算法.

图1给出7种算法在11个测试函数上平均适应值的进化性能对比，可以看出， MSPSO比PSO,CLPSO,Nmp3PSO,DE,SaDE以及GL25有着较为明显的进化优势，说明MSPSO算法有着更快的收敛速度和更高的收敛精度.综上所述，本文提出的MSPSO算法相比其他对比算法有着较为优异的性能.

Friedman检验[26]是利用秩实现对多个总体分布是否存在显著差异的非参数检验方法.为讨论7个算法平均结果对比统计的显著性，对算法所得结果的平均值做Friedman统计检验，结果如表3所示.由此可见，MSPSO对比PSO，CLPSO，Nmp3PSO，DE，SaDE以及GL25有显著性差异.

表3 7种算法的Friedman统计检验结果

3.3 高斯扰动效用测试

为验证MSPSO算法对于潜力子群中局部历史最佳经验施加高斯扰动的有效性，本文设置了一组对照试验，其中MSPSO1为不加高斯扰动的对照组，其余设置与MSPSO相同.两种算法的测试函数仍然为表1中的11个经典基准函数，种群规模、粒子最大飞行速度、函数最大评估次数等参数也与上文保持一致.图2为MSPSO与MSPSO1在各测试函数上的收敛曲线对比图.

从图2可以看出MSPSO在收敛速度和收敛精度上都比MSPSO1具有明显的优势.因此MSPSO中对于潜力子群中优秀粒子的局部历史最佳经验施加高斯扰动是非常有效的，提升了算法找到最优解的能力.

3.4 竞争机制排序的参数分析

为检验MSPSO算法中竞争机制所考虑两个指标权重λ1,λ2的参数敏感性，本文设置了几组对比试验，其中MSPSO2,MSPSO3,MSPSO4和MSPSO5分别将(λ1,λ2)设置为(1,2)、(1,1)、(2,1)和(3,1)，其余设置与MSPSO相同.这5种算法的测试函数为由表1中选取的3个单峰函数F1,F2和F5，3个多峰函数F9～F11.

表4为这5种算法在6个测试函数上达到的平均值对比.由表4可看出这5种算法都能获得较高精度的解，说明不同的λ1,λ2设置对算法性能影响不大，但探索其更好的设置值能为算法提供较好的稳定性.本文中MSPSO算法的设置值要略好于其他4种对比算法.

表4 不同设置值算法的平均值对比

3.3节对局部历史最佳经验高斯扰动的有效性进行了分析，表明算法对高斯扰动操作对潜力子群局部历史最佳经验具有较明显的影响提升；3.4节对两个重要指标权重λ1,λ2参数敏感性和鲁棒性进行了分析，结果表明指标权重参数λ1,λ2对算法性能的影响不明显.除此之外，除了30维的测试结果，又补充了问题维数50和100时的结果，见表5，可以看出MSPSO算法的数值结果并未随着测试函数维数上升而有明显下降，说明MSPSO算法较好的稳定性.结合3.2节算法仿真结果分析认为MSPSO算法性能不仅具有更高的收敛精度和更快的收敛速度，还具有较好的鲁棒性.

表5 MSPSO在不同维度测试函数上的数值结果

4 结 论

为改善粒子群算法早熟收敛、收敛速度慢的问题，提出了基于竞争机制和种群分区的多策略综合学习算法(MSPSO).MSPSO算法通过一种有效的竞争机制将整个种群划分为两个子群，对这两个子群采用了不同的学习策略，一个子群在精英学习的基础上引进更多种群多样性，另一子群在保持多样性的基础上加速了算法收敛，并且两个子群体和整个群体保持协同进化，较好地平衡了算法的寻优能力与收敛速度.在11个经典基准函数上对MSPSO,PSO,CLPSO,Nmp3PSO,DE,SaDE,GL25算法的性能进行了比较.结果表明，本文所提出的MSPSO算法性能具有更高的收敛精度和更快的收敛速度，并且具有较好的鲁棒性.