基于分层学习的改进PSO算法求解复杂优化问题

白晓慧，何小娟，孙超利，张国晨

(太原科技大学 应用科学学院，太原 030024)

粒子群算法(PSO)[1]作为最重要的进化算法之一，目前已被应用于各种优化问题的求解中，取得了较好的效果[2]，但是在求解大规模优化问题中，PSO存在过早收敛、易陷于局部最优及种群多样性丢失等问题。为了提高PSO求解大规模优化问题的效率，学者们在PSO中引入协同进化策略(CC)、局部搜索策略以及多种群策略等方法。

协同进化策略是由Potter在1997年提出的方法[3],该策略通过分而治之的方法解决大规模优化问题。Li 等人在2009年提出了一种基于协同进化的粒子群优化算法(CCPSO)[4]，该算法将决策变量随机分组协同进化，但是随机分组不能精确地将相关变量分到同一组导致算法的优化性能较差。李晓东等人提出一种自动分组的法(DG)[5]，该方法根据决策变量的相关性将决策变量分组，但是在求解决策变量的相关性时会花费大量的评价次数。文献[6]将邻域策略引入PSO中，使得每个粒子都向邻域最优值学习而不是向全局最优值学习。文献[7-8]将多种群策略引入PSO中，该算法把种群分为多个子种群分别进行优化，有效提高了PSO的搜索能力。2015年，程然和金耀初将社会学习机制引入PSO中，提出了社会学习粒子群算法(SLPSO)[9].虽然SLPSO提高了PSO的优化性能，但在解决大规模优化问题时仍然存在多样性缺失、收敛速度慢等缺点。针对该不足，本文引入分层学习策略与贡献值策略对SLPSO进行改进，进一步提高PSO求解大规模优化问题的性能。

1 大规模优化问题

一般来说，大规模优化问题可以用式(1)表述：

min/maxF(x)=f(x1,x2,…,xn)

(1)

其中x⊆Rn表示可行解集；n表示搜索空间的维数(即决策变量的个数)；xi表示决策变量；f表示目标函数。在大规模优化问题中，决策变量的个数n一般大于100，通常达到1 000维以上。

2 社会学习粒子群算法

程然和金耀初在2015年提出了SLPSO算法。该算法首先根据粒子的适应度值对种群中的粒子进行排序，其次除最优粒子外，每个粒子在每一维上随机选取比它适应度值好的粒子以及种群的平均位置进行学习。粒子的位置与速度更新公式如(2)所示：

Vi,j=

Xi,j=Xi,j+Vi,j

(2)

3 基于分层学习的改进社会学习粒子群算法

针对SLPSO存在的问题，本文提出了一种基于分层学习的改进社会学习粒子群算法(HSLPSO).一方面引入分层学习策略，差别对待不同状态的粒子，充分发挥不同状态的粒子在探索和开发搜索空间中的不同潜能。另一方面引入贡献值策略，减少计算资源的浪费。

3.1 分层学习策略

在进化期间，粒子在开发和探索搜索空间表现出了不同的潜能。适应度值好的粒子在开发搜索空间中表现出了较优的潜能，它可以引导种群向全局最优区域移动，从而实现快速收敛，而适应度值差的粒子在探索搜索空间中表现出了较优的潜能，它可以帮助种群跳出局部最优。因此不同状态的粒子应该被差别对待。

为了区别对待不同状态的粒子，引入分层学习策略。首先根据粒子的适应度值把粒子分为三层，适应度好的粒子放入第一层，适应度值较好的粒子放入第二层，适应度值较差的粒子放入第三层。因为适应度值较差的粒子在探索搜索空间表现出了较优的潜能，能帮助种群跳出局部最优。因此，为了增加种群的多样性，在第三层放入的粒子数量最多的，第一层放入的粒子最少。分层学习策略的框架如图1所示。

图1 分层学习策略框架Fig.1 Hierarchical learning strategy framework

图1中，种群中的粒子根据粒子的适应度值按照升序排序，并且把粒子分为三层，每一层用Hi(1≤i≤3)表示。H1是第一层，H2是第二层，H3是第三层。第三层的粒子向当前层以及第二层的粒子学习，第二层的粒子向当前层以及第一层的粒子学习，第一层的粒子仅仅向当前层的粒子学习。从图1(c)中可以看到，第三层和第二层的粒子从当前层以及它的前一层随机选取示范粒子对应的维进行学习，第一层的粒子从当前层随机选取示范粒子对应的维进行学习，种群中的最优粒子不进行学习。第二层与第三层粒子的更新公式如(3)所示，第一层粒子的更新公式如(4)所示：

(3)

(4)

3.2 贡献值策略

因为HSLPSO算法中粒子的更新是采用基于维的社会学习方式，因此在进化后期，大量相似粒子的出现会影响HSLPSO算法的性能，并且会造成计算资源的浪费。为了解决这一问题，设定贡献值策略，度量全局最优值在一个迭代周期的改进性能。贡献值较大时表示全局最优值在这一个迭代周期内的改进性能较大，否则认为全局最优值的改进性能较小。贡献值较小时，说明种群中出现了大量相似粒子，通过减少种群数量，删除种群中大部分的相似粒子，有助于缓解由于大量相似粒子的出现对算法性能的影响，并且在每次迭代中减少了评价次数，从而减少了计算资源的浪费。初始化阶段，贡献值r0为1，然后每隔一个迭代周期计算贡献值。贡献值的计算公式如(5)所示：

(5)

其中ri表示第i个迭代周期的贡献值，bestyi表示第i个迭代周期中最优个体的适应度值。

在种群进化期间，当两个相邻的贡献值ri-1与ri同时小于阈值ε，并且种群数量为N时，把第三层的粒子放入到第二层，并随机删除第二层一半的粒子。

伪代码1 HSLPSO

1:初始化种群与参数

2：while不满足终止条件 do

3:计算粒子的适应度值,并且把粒子分为3层

4:每隔一个周期通过公式(5)计算ri

5:ifri<ε&&ri-1<ε&&N=350

6:把第三层的粒子合并入第二层，并在第二层中随机删除一半粒子

7:c1=1/2*c1

8:end if

9:ifri<ε&&ri-1<ε

10: if FEs>=0.3*MaxFEs

11:根据公式(3)与(4)对粒子进行更新

12: else

13:根据公式(3)对粒子进行更新

14: end if

15:else

16:根据公式(3)对粒子进行更新

17:end if

18:end while

19:输出最优值

3.3 算法流程

HSLPSO的伪代码见伪代码1，首先初始化种群，其次根据分层学习策略对种群进行分层并更新粒子，在种群进化期间计算贡献值，当贡献值满足一定条件时，减少种群数量。最后，当评价次数达到最大评价次数时，输出最优值。

4 仿真实验及结果分析

为了验证本文所提算法的有效性，在CEC2010测试函数集上进行仿真实验[10]。并与5种典型算法(DLLSO[11]、SLPSO 、CSO[12]、DECC-DG以及DECC-G[13])的测试结果进行对比。在实验中，HSLPSO的参数设定如表1.每个算法分别独立运行20次，最大评价次数设置为3 000*n，其中n是大规模优化问题的维数。

表1 HSLPSO的参数设置

在初始化阶段种群的数量被设置为350.第一层的粒子数量M为50，当种群被分为三层时，第二层和第三层的粒子数量分别为2M与4M.当种群被分为两层时，第二层的粒子数量为3M.

表2给出了6种算法的测试结果。均值和方差取20次运行结果的平均值。当HSLPSO与CSO、SLPSO、 DECC-DG对比时，使用威尔克逊秩和检验来进行显著性检验(α=0.05).P-value上角标的“+”“-”与“=”分别表示HSLPSO算法的性能比其他算法的性能“显著好”“显著差”“几乎等同”。

从测试结果看出HSLPSO在解决大规模优化问题时的有效性，其中HSLPSO在13个函数的测试结果明显好于其他5种算法。对于测试函数F20，HSLPSO的测试结果与SLPSO、CSO的测试结果相同，并且好于其余3种算法的测试结果。本文在CECC2010测试函数集中选择了4个典型的函数(F1：完全可分的单模态函数，F3：完全可分的多模态函数，F7：部分可分的单模态函数以及F8：部分可分的多模态函数)对HSLPSO、SLPSO与CSO进行收敛性对比，对比结果如图2-图5所示。对于完全可分函数，从图2与图3中可以看出HSLPSO的收敛速度明显比其他两种算法的收敛速度快；对于部分可分函数，从图4中可以看出在进化前期HSLPSO的收敛速度比SLPSO的收敛速度快，和CSO的收敛速度一样，但在进化后期HSLPSO的收敛速度明显比其他两种算法的收敛速度快，从图5中看出，HSLPSO在进化前期的收敛速度和其他两种算法的收敛速度一样，但在进化后期HSLPSO收敛速度比其他两种算法的收敛速度快。

表2 6种算法测试结果

图2 测试函数F1的收敛图Fig.2 Convergence graph of test function F1

图3 测试函数F3的收敛图Fig.3 Convergence graph of test function F3

图4 测试函数F7的收敛图Fig.4 Convergence graph of test function F7

图5 测试函数F8的收敛图Fig.5 Convergence graph of test function F8

5 结束语

为了解决大规模优化问题，提出一种改进的SLPSO算法——HSLPSO.针对SLPSO存在的收敛速度慢以及进化后期多样性缺失等问题。本文引入分层学习策略以及贡献值策略，改善了SLPSO在进化后期多样性缺失的问题，提高了SLPSO的收敛速度。通过仿真实验，测试结果表明在解决大规模优化问题时HSLPSO的有效性。