融合鲸鱼泡泡网机制的SSA算法

冉 琳，潘大志，冯世强

（西华师范大学 数学与信息学院，四川 南充 637009）

0 引 言

受大自然的启发，群智能优化算法（Intelligence Optimization Algorithm，IOA）一般是通过对自然界中各种生物的进化过程与物理现象进行研究而形成的一种迭代寻优搜索算法。近年来，涌现了一些新的群智能优化算法，比如：蛾群算法（moth swarm algorithm，MSA）、哈里斯鹰优化算法（harris hawks optimization，HHO）、布 谷 鸟 搜 索 算 法（cukoo search algorithm，CSA）、萤 火 虫 算 法（firefly algorithm，FA）、蝙蝠算法（bat algorithm，BA）等。麻雀搜索算法是受自然界中麻雀搜索食物与反捕食行为的启发，于2019年由薛建凯提出。为使麻雀搜索算法寻优效果更好，学者们主要通过2个方面对其进行改进。一方面，根据麻雀搜索算法本身的特性进行改进；另一方面，通过将2种或多种智能算法与麻雀搜索算法进行融合，从而达到改进SSA算法的目的。目前，已有许多学者对麻雀搜索算法展开了进一步的研究：王海瑞等人将Levy飞行策略和柯西高斯变异引入麻雀搜索算法，增加算法搜索方向的多样性，同时也加强了局部搜索能力；吕鑫等人将高斯变异方法引入SSA算法，提高了搜索精度以及加强了算法跳出局部的能力；柳长安等人利用萤火虫机制，对最优解进行扰动变异，从而增加种群多样性；汤安迪等人通过引入正余弦算法和线性递减策略，协调局部和全局搜索能力；李敦桥将模拟退火算法的Metropolis准则融入SSA算法中，使算法跳出局部最优。针对麻雀搜索算法迭代过程中，种群多样性减少，以及容易陷入局部最优解等缺点，本文根据Tent混沌映射初始化麻雀种群，增加种群多样性，融合鲸鱼优化算法中的鲸鱼泡泡网捕食数学模型，在搜索过程中，更新麻雀种群中发现者的位置，最后按自适应分布变异方式，加强了算法跳出局部的能力。

1 麻雀搜索算法

在麻雀种群中，麻雀分为发现者、加入者和警戒者三种类型。其中，发现者引导种群觅食，加入者通过发现者得到食物，发现者和加入者都有可能是警戒者。

在麻雀搜索算法（SSA）算法中，麻雀个体的适应度值决定能源高低，发现者具有较多能源，引领加入者搜寻食物。发现者有如下位置更新：

发现者与加入者的身份可以根据拥有能源的多少而改变，但每种类型麻雀的占比不变。加入者的位置更新公式为：

警戒者由整个种群随机产生10%到20%，位置更新的数学表达式：

2 改进麻雀算法

2.1 Tent混沌映射

基本SSA算法利用随机初始化种群，这种方法会导致迭代过程中种群多样性减少。由于混沌映射具有全局遍历性、容易实现和随机性等特点，故本文采用基于Tent混沌映射初始化种群，以提高种群多样性和麻雀搜索的遍历性。Tent映射数学公式如下：

2.2 基于鲸鱼泡泡网捕食机制更新麻雀发现者位置

鲸鱼优化算法（Whale Optimization Algorithm，WOA）是近几年来群智能优化算法中出现的一种新算法，本文结合WOA算法中泡泡网捕食中的收缩包围机制和螺旋式位置更新机制，用以更新麻雀发现者的位置，以提高SSA算法的全局搜索能力。

融合后的麻雀发现者的更新位置公式为：

2.3 自适应t分布变异

分布的曲线形态与自由度参数的大小有关。当1时，分布是标准的柯西分布；当→∞时，分布是标准的高斯分布。分布的概率密度函数为：

在算法的初始阶段，分布近似于柯西分布变异，此时分布的全局搜索能力较强；在算法运行中期，分布变异逐渐由柯西分布变异向高斯分布变异过渡，提高了算法平衡全局搜索与局部开发的能力；在算法运行的后期阶段，由于→∞，分布近似于高斯分布，此时分布的局部开发能力较强。

其中，X 表示分布变异后的麻雀个体位置，（）表示基于迭代次数为参数的分布。

2.4 改进麻雀算法

针对麻雀优化算法的不足，首先利用Tent混沌映射初始化种群，提高初始解的质量；在改进麻雀算法（WSSA）中，为提高寻优效果，利用鲸鱼泡泡网机制扰动发现者位置更新，使得改进后算法更有利于平衡局部开发和全局搜索；最后，利用自适应分布变异更新位置，提高算法跳出局部最优的能力。具体实现步骤如下：

设置参数，预警值、发现者比例、意识到危险麻雀的比重。

基于Tent混沌映射初始化种群。

计算麻雀个体适应度值并排序。

利用式（5）更新麻雀发现者位置。

利用式（2）对加入者位置进行更新。

利用式（3）对警戒者位置进行更新。

对种群中的越界个体做越界处理。若新适应度值优于旧值，则更新位置和适应度值，反之保留。

利用式（7）对麻雀个体的位置进行分布变异，对越界个体做越界处理，并更新麻雀个体位置、适应度值以及对适应度值排序。

判断当前迭代次数是否达到，若已达到，则循环结束并输出结果，反之返回Step 3。

3 实验与仿真

3.1 标准测试函数

表1分别给出了标准测试函数的公式、维数以及搜索区间。这些标准测试函数被用于测试算法的可行性、稳定性。

表1 标准测试函数Tab.1 Standard test functions

3.2 参数设置

在本文中，将各个算法的最大迭代次数设置为1 000，种群规模设定为100，即100。在灰狼优化算法（Grey Wolf Optimizer，GWO）中，是从2线性递减至0，∈［0，1］，∈［0，1］；将引力搜索算法（Gravitation Search Algorithm，GSA）的参数设置为100，20；将麻雀搜索算法（Sparrow Search Algorithm，SSA）以及本文的改进麻雀算法（WSSA）的参数设置为：发现者占麻雀种群的0.2，警戒者占0.1，安全阈值0.8。避免程序运行一次出现误差，本文在实验仿真阶段运行30次来获得标准测试函数的最优值、均值以及标准差，以反映算法的收敛性、精确度和稳定性。

实验环境：Windows 10，CPU为Intel（R）Core（TM）i5-10210U CPU＠1.60 GHz 2.11 GHz，内存16 G，Matlab 2018a。

3.3 与其他算法对比

因为单峰测试函数有且仅有一个全局最优解，并没有局部最优解，故用单峰测试函数检验算法的局部开发能力。与单峰测试函数不同的是，多峰测试函数具有多个局部极值点，搜索全局最优值的难度较大，但是能够测试出算法的搜索能力。表2给出了引力搜索算法（GSA）、灰狼优化算法（GWO）、哈里斯鹰算法（HHO）、麻雀搜索算法（SSA）以及本文的改进麻雀搜索算法（WSSA），在独立运行了30次后的实验结果。图1～图8则分别给出了在测试函数上5种算法的收敛曲线。

图8 函数f8的对比曲线Fig.8 Comparison curve of function f8

表2 测试函数优化结果Tab.2 Test function optimization results

图1 函数f1的对比曲线Fig.1 Comparison curve of function f1

图2 函数f2的对比曲线Fig.2 Comparison curve of function f2

图3 函数f3的对比曲线Fig.3 Comparison curve of function f3

图4 函数f4的对比曲线Fig.4 Comparison curve of function f4

图5 函数f5的对比曲线Fig.5 Comparison curve of function f5

图6 函数f6的对比曲线Fig.6 Comparison curve of function f6

图7 函数f7的对比曲线Fig.7 Comparison curve of function f7

3.4 结果分析

表2中给出了灰狼优化算法（GWO）、引力搜索算法（GSA）、麻雀搜索算法（SSA）、哈里斯鹰算法（HHO）以及本文的改进麻雀搜索算法（WSSA），对于8个标准测试函数在独立运行了30次后的优化结果，、、分别表示运行30次后所得到的最优解、均值以及标准差，最优解在表2中已加粗。

从表2可以得出，引力搜索算法（GSA）的解的质量较差，灰狼优化算法（GWO）对于函数、可获得最优解，就收敛速度而言，GWO算法对于函数、、，优于HHO算法和GSA算法，次于SSA算法和WSSA算法。哈里斯鹰算法（HHO）相较于GSA算法、GWO算法的寻优结果更好，对于函数，HHO算法寻优结果比SSA算法的好，说明此时HHO算法的局部开发能力更优，且对于函数，虽然HHO算法的收敛速度次于SSA算法和WSSA算法，但也能搜索到最优解。SSA算法相比于GSA算法、GWO算法和HHO算法，总体来说，收敛速度更快、寻优结果更好，这说明SSA算法在跳出局部极值点和全局搜索能力方面都要强于GWO算法、GSA算法和HHO算法。WSSA算法对于函数，成功地找到了全局最优解，且最优解、最优解均值、标准差都比GSA算法、GWO算法、HHO算法以及SSA算法好，表现出了很好的平衡局部与全局、跳出局部极值的能力。

为说明算法的收敛性，图1～图8中给出了5种算法对于标准测试函数在独立运行30次后所得最优结果的收敛性能对比图。在基本麻雀搜索的基础上，因为改变了麻雀发现者的位置更新和加入了自适应分布变异，改进后的算法不仅能够平衡局部和全局搜索，在收敛速度方面也优于其他4种算法。综上所述，WSSA算法具有稳定性较强、收敛速度较快等特点。

4 结束语

本文针对基本SSA算法易陷入局部极值、后期种群多样性减少等缺陷，提出了一种融合鲸鱼优化算法和自适应分布变异的麻雀搜索算法（WSSA）。在SSA算法中，基于Tent混沌映射初始化种群，对发现者的位置融入鲸鱼优化算法的泡泡网捕食机制进行更新，以平衡局部开发与全局搜索能力；加入自适应分布变异，增强算法跳出停滞的能力。但对于发现者、加入者、意识到危险麻雀的位置更新公式可做进一步改进。还可以将算法运用到实际问题中，如背包问题等，这也是接下来要解决的问题。