基于旋转状态转移的麻雀搜索算法

刘西全， 周新志

（四川大学 电子信息学院， 成都 610065）

0 引言

近年来，群体智能优化算法在智能机器学习上被广泛应用，群体智能优化算法主要是模仿昆虫、动物、鱼类、鸟类的群体行为、根据其觅食行为启发而提出的算法［1］。 如粒子群优化算法［2］（PSO）、蚁群优化算法［3］（ACO）、灰狼优化算法［4］（GWO）、天鹰优化器［5］（AO）和麻雀搜索算法［6］（SSA）等。 其中，麻雀搜索算法是在2020年由薛建凯提出的一种新型智能优化算法，是通过模拟麻雀在自然界的捕食行为来进行研究与开发的。 与其他智能优化算法相比，SSA 具有调节参数少、搜索精度高、收敛速度快、稳定性强等优势。 然而，在SSA 收敛过程中，却存在容易陷入局部最优、收敛停滞等问题，直接影响算法的优化效果。

为了提高麻雀优化算法（SSA）的性能，国内外学者提出了许多改进方法。 研究发现初始种群对寻优结果有至关重要的作用。 为了优化初始种群，吕鑫等学者［7］、Liu 等学者［8］分别提出tent 混沌映射和改进Circle 混沌映射对初始种群进行优化。 钱敏等学者［9］在麻雀初始化种群个体位置时引入反向学习策略，以提高寻优前期麻雀种群整体质量，加快全局搜索速度。 Ouyang 等学者［10］提出一种自适应搜索策略以提高局部搜索能力，避免种群陷入局部最优。 Ma 等学者［11］在文章中引用三角相似理论设计了相似扰动函数，提高算法的搜索能力。 Liang 等学者［12］对算法的边界约束进行改进以提高算法的收敛精度。 毛清华等学者［13］通过引入柯西变异算子，来增强算法越出局部最优空间的能力。

1 麻雀搜索算法

在SSA 中，麻雀种群可分为3 类，分别为：发现者、加入者、警戒者。 其中，发现者为整个种群提供丰富食物的方向与位置；跟随者是根据发现者提供的食物方向与位置进行食物的搜索；警戒者是为整个种群提供警戒侦察，一旦发现捕食者，群体边缘麻雀则向安全区域移动获取食物。

（1）发现者。 在SSA 中，发现者往往根据其自身的更高适应度发挥领导作用，其位置更新策略如下：

（2）加入者。 加入者跟随发现者，一旦其发现其寻到更好的食物，则会离开现在位置去争夺食物，其更新策略如下：

（3）警戒者。 警戒者为麻雀种群提供危险预知，其更新策略如下：

2 改进的麻雀搜索算法

2.1 精英旋转搜索策略

状态转移算法［14］（State Transition Algorithm，STA）是由周晓君等学者于2012年提出的一种全局优化算法，包括旋转、平移、伸缩、坐标四种状态转移的变换，旋转状态转移变换的数学模型如下：

其中，n表示计算维度；α为旋转因子，表示在半径为α的半径范围内寻找下一组最优解；Rr是［－1，1］的随机数；表示向量的二范数。

由于麻雀发现者在新一代的探索中是随机状态，脱离上一代的最优种群，容易陷入局部最优。 因此，本文对精英麻雀发现者进行旋转状态转移变换，增加麻雀的种群多样性，经状态转移后的新种群为：

2.2 融合莱维飞行的搜索策略

莱维飞行是服从莱维分布的一种随机搜索方法，是一种短距离的搜索与偶尔较长距离的行走相间的行走方式，从而促使莱维飞行具有良好的全局搜索能力，莱维飞行的位置更新公式为：

其中，δ表示步长大小，δ ＞0，通常设置为δ ＝1；“⊕” 表示点对点乘法；Levy（β） 表示服从莱维分布的路径，并且满足：

使用Mantegna 方法来生成莱维飞行的随机步长s为：

在这里，β设置为1.95。

本文采用莱维飞行搜索策略进行全局探测，使得全部麻雀个体广泛分布在整个搜索空间中，提高全体麻雀的全局搜索能力。 经过对麻雀加入者位置适应度值较优的个体进行莱维扰动后，得到的新种群为：

2.3 贪婪算法寻优

虽然旋转状态转移和莱维飞行可以实现位置的更新，但是其无法保证得到的新解较原解更优，因此对新解和原解的适应度值进行比较，通过贪婪算法机制来保留最优的适应度值和解。 具体公式如下：

2.4 RLSSA 算法流程

RLSSA 算法引入旋转状态转移和莱维分布，增加了种群的多样性，提高算法搜索精度、收敛速度，算法实现流程见如下：

（1）初始化种群。 参数主要包括： 麻雀的种群规模N，迭代次数M，发现者和警戒者的比例，目标函数fit，麻雀算法的搜索边界范围Lb和Ub。

（2）初始化适应度值，并排序，得出最优适应度值fg和最差适应度值fw及其各自的种群位置

（3）根据式（1）更新发现者的位置，根据式（5）得到经旋转策略变换的位置。

（4）根据式（2）更新加入者位置，根据式（11）得到莱维飞行扰动的位置。

（5）根据式（3）更新警戒者位置。

（6）一次迭代结束，计算适应度值，并根据式（12）选择新一代的适应度值和麻雀位置。

（7）根据当前麻雀种群状态，计算最优适应度值fg和最差适应度值fw及其各自的种群位置。

（8）判断算法是否满足最大迭代次数，满足则退出，输出结果，否则重复执行步骤3～7。

3 实验结果及分析

3.1 实验设计

为了验证RLSSA 的有效性和优越性，采用基准测试函数进行仿真实验，见表1。

表1 基准测试函数Tab. 1 Benchmark functions

表1 中，F1～F4为单峰测试函数，用来测试函数的收敛速度和精度；F5～F8为多峰测试函数，主要用来测试算法跳出局部最优的能力；F9～F12为固定维多峰测试函数，这类函数主要表现为工程优化问题。 为了验证算法的有效性和优越性，将本文改进后的旋转麻雀算法（RLSSA）与GWO、WOA、PSO、SSA 及一种基于相似变换改进的麻雀搜索算法EMSSA 进行对比求解实验。

图1 为部分函数的三维图，依次分别为F1、F2、F5、F8、F9、F12。

图1 函数三维图Fig. 1 Three－dimensional diagram of functions

3.2 仿真实验结果及分析

本实验是在Windows10 系统，Intel（R） Core（TM） i5－62－－U CPU＠ 2.30 GHz，内存8.00 GB，Matlab R2016a 的环境下进行的，实验种群规模N ＝30，最大迭代次数M ＝500，发现者和警戒者的比例分别为20%和10%，每个目标函数的维度d和边界Lb和Ub由表1 中给出。 考虑到每次算法寻优都具有偶然性，所以对每个基准函数都运行30 次寻优运算，由此计算出的平均值和标准差作为最终的评价指标。 表2 和表3 分别给出了12 个基准测试函数在GWO、WOA、PSO、SSA、EMSSA、RLSSA 优化算法后的均值和方差。

表2 基准测试函数优化结果均值比较Tab. 2 Comparison of the mean of the optimization results of the benchmark functions

表3 基准测试函数优化结果方差比较Tab. 3 Comparison of variance of the optimization results of the benchmark functions

由表2 和表3 可知，对于高维单峰函数F1～F4，RLSSA 较其他5 种算法有较小的适应度值和较小的标准差，说明RLSSA 有较高的寻优精度和寻优稳定性。 在多峰测试函数F5～F8上，F5函数在EMSSA 上有最好的精度，RLSSA 对比其他4 种算法有较优的精准度。 而在F6～F8上，RLSSA 能跳出局部最优，稳定找到全局最优解。 对固定维多峰测试函数F9～F12，RLSSA 较其他5 种算法的均值和标准差提升并不高，但是在寻优精度和稳定性上都要优于其他5 种算法。

3.3 收敛曲线分析

为了反映出RLSSA 的收敛速度，在500 次迭代中画出各个算法的收敛特性曲线，如图2 所示。 在高维单峰函数F1～F4的曲线中可以看出，RLSSA的收敛速度均优于其他算法，同时还看出，RLSSA能快速跳出算法的局部最优解。 在高维多峰函数F5的曲线中看出RLSSA 的精度不如EMSSA 和WOA 算法，比其他3 种算法更优，这是因为莱维飞行策略是一种较短步长多，较长步长少的策略，算法不能通过合适的步长实现全局寻优。在F6～F8中，RLSSA 收敛速度快、精度高；在固定多峰函数F9～F12的曲线中，算法结果都趋于稳定，并且结果相近，但可以看出RLSSA 的收敛速度或者精度优于其他算法。

图2 基准测试函数的收敛曲线Fig. 2 Convergence curve of the benchmark functions

4 结束语

针对传统麻雀搜索算法（SSA）容易陷入局部最优、收敛停滞等问题，提出了一种融合旋转状态转移的麻雀搜索算法（RLSSA），改进的算法具有收敛速度快、精度高、稳定性强等优势。 首先，对于麻雀发现者，引入一种旋转状态转移策略的搜索方法以提高算法跳出局部最优的能力；其次，引入莱维飞行策略对麻雀加入者加以改进，此方法可以提高麻雀算法的全局搜索能力；最后，通过贪婪算法的准则，对原算法和改进的算法进行择优。通过12个基准测试函数并与其他5 个算法进行仿真测试验证，实验结果表明RLSSA 具有良好的收敛速度、收敛精度及鲁棒性。