一种多策略驱动的改进樽海鞘群算法

黄小根，钟尚勤，2

(1.中共广东省佛山市委党校，广东 佛山，528300；2.北京邮电大学，北京 100876)

1 引言

全局优化问题普遍存在于各个学科之中，例如特征选择、参数识别、资源分配等。传统优化算法并不能很好的解决这些复杂的优化问题，因此，受自然界中生物或物理现象启发而设计的智能优化算法应运而生。群体智能算法在没有先验知识的情况下随机搜索解空间以寻找最优解。较为经典的智能优化算法有受鸟类群体行为启发而提出的粒子群优化算法(Particle swarm optimization，PSO)[1]，受蚂蚁协作觅食行为启发而提出的蚁群优化算法(Ant colony optimization)[2]。

澳大利亚学者Mirjalili等人在2017年通过观察海洋生物樽海鞘的群体觅食行为而受到启发，提出一种新型群体智能优化算法——樽海鞘群算法(Salp Swarm Algorithm，SSA)[3]。SSA主要通过模拟樽海鞘链群在海洋中的导航和觅食行为来实现对复杂全局优化问题的求解。SSA凭借其设置参数少、寻优机制简单、优化效率高等优点已成功应用于目标分类[4]、参数识别[5]、特征选择[6]等多个领域。

SSA算法在优点众多的同时，也和其它元启发式算法一样，存在寻优精度不足、收敛速度慢等缺点。为解决这些问题，许多学者对基本SSA算法进行了改进。Sayed等人[7]采用混沌序列对SSA算法的控制参数进行调整，从而提高算法跳出局部最优的能力。Ren等人[8]在基本SSA算法中引入随机游走策略和自适应权值，帮助平衡算法的全局开发和局部勘探能力。Bairathi等人[9]采用反向学习策略生成初始种群，提高了初始种群的多样性，从而提高算法的收敛速度。Ibrahim等人[10]将SSA算法与PSO算法合并，提出一种新的SSAPSO算法，有效提高了算法在勘探阶段的灵活性。

上述不同改进版本的SSA均在一定程度上提高了原SSA算法的寻优性能，但仍有提升的空间。本文提出一种多策略集成的改进SSA算法，首先设计一种指数衰减因子，很好的解决了算法收敛速度慢的问题；其次提出一种新型的惯性权重算子，有效地改善了算法平衡全局勘探和局部开发的能力；此外提出潜在食物源概念，引导樽海鞘链群向最优解空间运动，从而避免算法出现早熟收敛现象。最后通过7个基准测试函数对所提MSSSA算法的性能进行测试，实验结果表明了MSSSA算法的有效性和优越性。

2 基本樽海鞘群算法

SSA算法是模仿樽海鞘独特的群体行为的群体智能优化算法，樽海鞘个体在觅食过程中会形成链群形态，并不断逼近食物源，从而完成寻优过程。SSA中，位于樽海鞘链首个的个体是领导者，其余个体为跟随者。

在SSA的寻优过程中，领导者在当前食物源的引导下进行随机搜索，其数学模型可表示为

(1)

(2)

跟随者位置更新的数学模型为：

(3)

SSA在每轮迭代中比较当前最优个体的适应值与当前食物源的适应值，并选择较优个体作为新的食物源。

3 多策略驱动的改进樽海鞘群算法

基本SSA算法中，在领导者位置更新阶段，个体搜索时的动态性过大，影响算法的收敛速度和收敛精度；其次，跟随者的位置更新方式较为单一，导致算法的全局勘探和局部开采能力不平衡；此外，食物源对SSA的寻优过程有重要的引导作用，如果食物源陷入局部最优，将会导致算法早熟收敛。综合上述分析，本文对原SSA算法做出三个方面的调整：针对领导者位置更新阶段动态性较大的问题，添加指数衰减因子，提高寻优精度；针对跟随者位置更新方式较为单一的问题，添加惯性权重算子，平衡算法的勘探和开采能力；针对缺乏先验知识判断食物源是否处于全局最优的问题，提出虚拟食物源概念，帮助引导群体向全局最优区域运动。

3.1 指数衰减因子

在基本SSA中，领导者在食物源附近不断扰动，搜索范围不受限制[11]，使得算法在迭代前期收敛速度慢且迭代后期收敛精度低。为解决这一问题，在领导者位置更新公式中引入指数衰减因子，通过限制领导者的搜索范围，提高算法的收敛速度和搜索精度。引入指数衰减因子的领导者位置更新模型如下

(4)

其中，H(t)是用于控制搜索范围的指数衰减因子，定义为

H(t)=H0e-st

(5)

其中，H0是取值固定的参数；s∈[0，1]是衰减系数，取值大小决定衰减速度；t为当前迭代次数。

根据式(5)可知，迭代早期衰减因子的值会很大，随迭代次数增加呈指数下降。在收敛前期较大的衰减因子使得搜索步长较大，全局开发能力较强，帮助算法充分搜索解空间；在收敛后期较小的衰减因子使得搜索步长较小，约束了领导者的搜索范围，将其限制在某个限定区域内进行精确搜索，以此提高寻优精度。因此，在领导者位置更新公式中引入衰减因子有助于在解的步长上建立适当的平衡[12]，以此平衡算法的种群多样性和收敛性。

3.2 随机惯性权重

由式(3)可知，在基本SSA中，樽海鞘跟随者i在保留自身特征的情况下学习跟随者i-1，完成位置移动，且其自身特征和跟随者i-1的位置在其位置更新时的影响力相同。若樽海鞘i-1处于局部最优，则盲目学习会导致樽海鞘i也陷入局部最优。针对此问题，本文在跟随者位置更新公式中引入随机惯性权重，动态调整跟随者吸收先前个体位置信息的能力。引入惯性权重因子的追随者位置更新模型如下

(6)

ω(t)=ωs(ωs-ωe)rand()/2

(7)

其中，ωs和ωe分别是初始惯性权重和终止惯性权重；rand()是[0，1]服从均匀分布的随机数。通过大量实验，惯性权重ωs=0.9，ωe=0.4时算法性能最优。通过在跟随者位置更新公式中引入随机惯性权重因子，能够避免跟随者的盲目跟随，从而增强算法在迭代前期的勘探能力和迭代后期的开发能力。

3.3 潜在食物源

基本SSA中，食物源位置对樽海鞘群体的寻优过程有重要作用，在搜索过程中，适应度值最优个体的位置定义为当前食物源的位置，樽海鞘链群在领导者的带领下以食物源位置为目标进行移动，一旦食物源位置陷入局部最优，则容易导致樽海鞘链群集体陷入局部最优区域，出现搜索停止现象。针对这一问题，本文受GWO算法[13]的启发提出一种基于加权方式的潜在食物源生成方法，通过对每轮迭代更新中最优的三个樽海鞘个体进行加权发现一个新的潜在食物源，公式如下

(8)

(9)

其中，fitnessα、fitnessβ、fitnessδ分别表示α、β、δ个体的适应度值。根据适应度值动态调整α、β、δ个体的权重系数，能够使潜在食物源尽可能地汲取当代最优三个个体的优秀信息，帮助自身上升为最优解。

每轮迭代最后，通过加权方式发现潜在食物源位置，计算潜在食物源和当前食物源的适应度值后根据贪婪准则决定是否替换原有食物源。

3.4 MSSSA实现的流程

所提MSSSA算法的实现流程如下所示

Step1：参数设置：种群规模N，最大迭代次数Max iteration，搜索空间上下界；

Step2：初始化种群，计算个体适应值，并将最优个体确定为当前食物源；

Step3：根据式(5)计算当前轮次的衰减因子，并根据式(4)更新领导者的位置；

Step4：根据式(7)计算惯性权重，并根据式(6)更新跟随者的位置；

Step5：计算当前种群的适应值，并比较最优个体和当前食物源的适应值，取较优者作为当前食物源；

Step6：根据式(8)生成潜在食物源，并计算适应值，若优于当前食物源，则将潜在食物源更新为当前食物源；

Step7：判断是否达到最大迭代次数，若已达到，输出食物源位置，否则返回Step3继续迭代。

4 测试实验分析

4.1 算法参数设置

算法实验平台为：Windows 10操作系统，8G内存，算法基于Matlab 2014b用M语言编写。算法参数设置为：种群规模为30，最大迭代次数为500，所有算法对每个测试函数独立运行30次。

为保证比较的公平性，所有对比算法的参数与原文献保持一致，以保证算法具备最优的性能。所提MSSSA算法的其它参数如下：衰减因子H0=8，衰减系数s=0.9。

4.2 测试函数

为验证所提MSSSAS算法的可行性，实验选取7个国际上常用的基准测试函数进行仿真实验，如表1所示。其中f1(x)～f4(x)为高维单峰函数，用来验证算法的局部开采能力。f5(x)～f7(x)为高维多峰函数，用来验证算法平衡局部开采和全局开发的能力。所有基准函数的维度设置为30，理论最优值均为0。

表1 标准测试函数

4.3 MSSSA算法与SSA算法和改进SSA算法的比较

利用MSSSA算法求解表1中的7个基准测试函数，并与基本SSA算法、生命周期启发的SSA算法(LSSA)[14]、自适应SSA算法(ASSA)[15]相比较。记录30次仿真得到的平均值和标准差，并采用Fridman’s排名检验对算法进行排名，如表2所示。

由表2可知，MSSSA算法在除f2、f4、f6之外的四个测试函数上均达到了理论最优值。对于测试函数f2、f4、f6，MSSSA算法取得的结果仍然令人满意。此外，相比于基本SSA算法、LSSA算法和ASSA算法，所提MSSSA算法在所有测试函数上均取得了较好的结果。

表2 MSSSA算法与其它3种算法对7个30维测试函数的结果比较

根据表2中Friedman排名检验结果，所提MSSSA算法排名第一，依次为ASSA、LSSA、SSA。这说明不同改进算法均在一定程度上提升了原SSA算法的性能，且本文算法提升程度最大，在四种算法中表现最优。

4.4 收敛性比较

为进一步验证所提MSSSA算法的收敛性能，本节给出基本SSA算法和MSSSA算法在7个基准测试函数上的收敛曲线，如图1至图7所示。

图1 函数f1收敛曲线 图2 函数f2收敛曲线

图3 函数f3收敛曲线 图4 函数f4收敛曲线

图5 函数f5收敛曲线 图6 函数f6收敛曲线

图7 函数f7收敛曲线

从图1至图7可以看出，所提MSSSA算法在所有测试函数上的收敛速度明显优于基本SSA算法。综上，所提MSSSA算法在保持高收敛精度的同时，具备同样优越的收敛速度。证明所提算法有效提高了原SSA算法的性能。

5 结论

为了提高基本SSA算法的收敛速度和收敛精度，本文提出一种多策略协同作用的改进樽海鞘群算法。首先在领导者位置更新公式中引入指数衰减因子，提高了算法在迭代前期的收敛速度；其次提出一种随机惯性权重，并引入跟随者位置更新公式中，提高算法平衡全局勘探和局部开采的能力；此外，提出加权食物源概念，改善算法在迭代后期的收敛精度。仿真结果表明，所提MSSSA算法能够有效改善基本SSA算法收敛精度不足和收敛速度慢的问题。