融合正余弦和柯西变异的麻雀搜索算法

李爱莲，全凌翔，崔桂梅，解韶峰

1.内蒙古科技大学 信息工程学院，内蒙古 包头 014010

2.内蒙古科技大学 基建处，内蒙古 包头 014010

麻雀搜索算法（sparrow search algorithm，SSA）是薛建凯等[1]在2020年提出的一种新型优化算法，主要通过模拟麻雀捕食和反捕食的行为特征进行数学建模。麻雀搜索算法具备结构简单、控制参数少、求解精度高等优点。尽管出现时间较短，但在实际工程应用也逐步增加，Liu等[2]针对现有的脑瘤诊断算法存在成功率不足，以及在治疗过程中不能及时跟踪进程，引进了SSA进行优化，增强了检测能力。Zhu等[3]使用SSA对聚合物电解质燃料电池（PEMFC）堆的辨识参数进行优化，成功地降低了电池中电压误差，提高了电能转换效率。吕鑫等[4]在多阈值图像分割中引入一种改进型SSA，利用该算法在整体和局部的探索开发能力，提升了分割速度和精度。

与大多数智能优化算法相比，SSA在对问题优化方面有一定优势，但依然存在收敛精度低，难以跳脱局部极值的问题。Liu等[5]利用自适应权重因子平衡麻雀算法搜索与开发能力，借助柯西-高斯机制提高SSA摆脱停滞能力，应用于无人机航路规划，验证了改进策略的优越性。Yuan等[6]引入重心逆向学习机制对种群初始化，加入权重系数对麻雀算法中的跟随者位置进行更新，增强SSA的全局探索能力，最后在跟随者的位置中引进变异策略，改善算法在挣脱局部极值的能力。毛清华等[7]提出了一种融合柯西变异和反向学习的机制，用于对最优解进行突变，使算法具备跃出局部极值的能力。吕鑫等[8]通过Tent混沌序列对当前出现局部解位置进行扰动操作，增加麻雀算法全局可搜索性。

上述改进策略虽然较基本麻雀算法的全局寻优性能有一定提升，但依然存在SSA在寻优后段出现搜索能力不足和坠入极值空间的概率提高等问题。针对此问题，本文提出了一种融合正余弦和柯西变异的麻雀搜索算法（sine-cosine and Cauchy mutation sparrow search algorithm，SCSSA）。改进算法主要根据以下策略进行：首先，引进一种折射反向学习策略对麻雀种群初始化，进而增强物种多样性，降低SSA在搜索后期出现早熟收敛概率；其次，在麻雀搜索算法的发现者位置更新中引进正余弦策略，并通过非线性递减搜索因子和权重因子对正余弦算法进行改进，进而达到平衡局部开发和全局探索的目的；最后，采用柯西变异机制对跟随者位置更新中的最优解产生扰动，扩大搜索范围，提高算法跳出局部极值的几率。通过10个测试函数下的多种性能测试指标与一些基本智能算法以及其他SSA改进型算法进行比较，并利用工程优化设计问题进行验证，显现了SCSSA的有效性和优越性。

1 麻雀搜索算法

麻雀捕食过程通常由发现者和跟随者两种类型麻雀组成，但受到天敌的威胁，常需设置侦查预警机制。

在麻雀种群中，适合度值高的发现者优先获得食物，主要因为发现者兼具寻找食物并指导整个种群的流动的任务，因而与其他麻雀相比，它们能更快地获取食物，发现者的位置更新公式如下：

除所有的发现者，其余皆为跟随者，位置更新如下：

式中，Xworst为目前整体最差位置；n为麻雀总数，i＞n/2表示此时第i只麻雀处于十分饥饿的状态（因为其能量极低，即适应度值很差），需要到其他地方觅食；X p为发现者占据的最优位置；A为单行d维且元素随机为1或-1的矩阵，

考虑到自身安全以及能够成功获取食物，麻雀将从种群中挑选10%~20%个体进行侦察警戒，位置更新如下：

式中，Xbest为目前整体最优位置；β为步长修正系数，服从标准正态分布；f i为此时麻雀的适应度，f w和f g各表示此时整体最差适应度、最优适应度；当f i＞f g时，说明麻雀位于种群的边缘周围，容易成为猎物；当f i=f g时，说明位于群体间的麻雀察觉到天敌的威胁，应立刻朝其他麻雀接近，摆脱危险。k∈(0,1)为随机数；ε为极小常数，本文取ε=10E-50。

2 融合正余弦和柯西变异麻雀搜索算法

2.1 折射反向学习策略

针对SSA算法在寻优后期出现群体多样性损失，造成落入局部极值的几率升高，引发收敛精度不足问题，本文采用一种折射反向学习机制对麻雀种群初始化。反向学习是Tizhoosh提出的一种优化策略[9]，基本思想是通过计算当前解的反向解来扩大搜索范围，借此找出给定问题更好的备选解。文献[10-11]将智能算法与反向学习结合，均能有效提高算法求解精度。同时反向学习仍存在一定的不足，在寻优早期引进反向学习能够加强算法的收敛性能，但在后期易使算法陷入早熟收敛。因此在反向学习策略中引进一种折射原理[12]以降低算法在搜索后期陷入早熟收敛的几率。折射反向学习原理如图1所示。

图1 融合折射原理的反向学习Fig.1 Reverse learning with fused refraction principle

其中，x轴上面解的寻优范围为[l,u]，y轴为法线，α、β分别表示入射角、折射角，h和h*分别为入射、折射光线所对应的长度，O为寻优范围[l,u]的中点。根据数学中线几何关系，得到如下：

根据折射率定义n=sinα/sinβ，得到折射率n公式为：

令缩放因子k=h/h*，代入式（5）得到变形公式为：

当n=1且k=1时，式（6）可转为反向学习公式[11]：

式（6）推广到麻雀算法高维空间时，令n=1可得到如下：

式中，x i,j为种群中第i只麻雀在j维位置(i=1,2,…,D;j=1,2,…,N)，D为种群数，N为维度；x*i,j为x i,j的折射反向位置；l j、u j分别为搜索空间第j维的最小值和最大值。

算法1初始化种群算法

（1）在寻优范围中随机初始化N个麻雀位置xi,j作为初始种群位置。

（2）根据式（8）生成折射反向种群x*i,j。

（3）合并初始种群和折射反向种群，根据适应度值的升降进行排序，选取适应度值前N个麻雀个体作为初始种群。

2.2 正余弦策略

在麻雀捕食过程中，食物源位置非常重要作用，影响整个麻雀种群前进方向。但考虑到食物来源可能不同，位置也不尽相同，当发现者搜寻的食物位于局部最优时，大量的跟随者会涌入到该位置，此时发现者与整个群体停滞不前，造成种群位置多样性出现损失，进而增加陷入局部极值的可能性。针对该现象，本文在麻雀搜索算法发现者的位置更新中引进正余弦算法（sinecosine algorithm，SCA）[13]，通过利用正余弦模型震荡变化特性对发现者位置进行作用，维持发现者个体多样性，进而提高SSA的全局搜索能力。SCA的中心思想是根据正余弦模型的振荡变化对整体和局部寻优，获取整体最优值。

针对基本的正余弦算法的步长搜索因子r1=aat/Itermax（a为常数，t为迭代次数，本文设置a=1）呈线性递减趋势，不利于进一步平衡SSA的全局搜索和局部开发能力，受文献[14]启发，对步长搜索因子进行改进，变换曲线如图2所示，新的非线性递减搜索因子如式（9），在前期权重较大，递减速度慢，利于提高全局寻优能力，在权重因子较小时，增强算法在局部开发的优势，加快获取最优解的速度。

图2 r1、r1′、ω变化曲线Fig.2 Change curve of r1，r1′，ω

式中，η为调节系数，η≥1；a=1。

考虑SSA算法在整个搜索过程中，种群个体位置更新常受到当前位置影响。因此引入式（10）非线性权重因子ω用于调整种群个体位置更新对此时个体信息的依赖度。在寻优前期，较小的ω降低了寻优个体位置更新对当前解位置影响，提升了算法全局寻优能力。在后期较大的ω利用当前位置信息与个体位置更新的高度依赖性，加快了算法的收敛速度，变化曲线如图2所示。则得到新的发现者位置更新公式如式（11）：

式中，r2∈[0,2π]的随机数，决定麻雀的移动距离；r3∈[0,2π]的随机数，控制最优个体对麻雀后一位置的影响。

2.3 柯西变异策略

在觅食过程中，跟随者经常围绕最好的发现者周围进行觅食，其间也有可能发生食物的争夺，使其自己变成发现者，为避免算法陷入局部最优，在跟随者更新公式中引入柯西变异策略，提升全局寻优能力。新的跟随者位置更新如下：

式中，cauchy(0,1)为标准柯西分布函数；⊕表示相乘含义。

以原点为中心的一维柯西变异函数如下：

柯西分布与标准的正态分布相似，为连续的概率分布，在原点处值较小，两端较为扁长，逼近零速率较慢，因而相比于正态分布能产生更大的扰动。因此，利用柯西变异对麻雀位置更新中的个体进行扰动，从而扩大麻雀算法的搜索规模，进而提升算法跳出局部最优能力。

2.4 SCSSA算法流程

步骤1设置种群大小N，最大迭代次数Itermax，发现者比例PD，侦察者比例SD，警戒阈值R2，安全阈值ST等。

步骤2执行算法1对麻雀种群初始化。

步骤3计算每只麻雀的适应度值并排序，确定当前最优、最差适应度个体。

步骤4根据式（11）对发现者位置更新。

步骤5根据式（12）对跟随者位置更新。

步骤6根据式（3）对警戒者位置更新。

步骤7判断当前迭代次数是否达到结束条件，若满足，则进行下一步，否则跳转步骤3。

步骤8程序结束，输出最优适应度值和最佳位置。

2.5 SCSSA复杂度分析

在标准麻雀算法SSA中，假设种群规模为N，求解空间维数为D，则标准SSA进行参数初始化的复杂度为O(1)，个体适应度为O(N)，种群复杂度为O(N×D)，所以麻雀算法SSA的整体复杂度为O(SSA)=O(1)+O(N)+O(N×D)=O(N×D)。

SCSSA算法在初始化引进折射反向学习策略替换随机初始化需O(N×D)，个体适应度与SSA一样，引进正余弦阶段需要O(N×D)，柯西变异阶段复杂度为O(N×D)。因此SCSSA总的复杂度为O(SCSSA)=O(N×D)+O(N)+O(N×D)+O(N×D)=O(N×D)。

通过对比发现，SSA与SCSSA的时间复杂度一样，说明在基本SSA算法中引进多种策略并没有影响时间复杂度，运行效率并未下降。

3 性能测试

为验证SCSSA算法的性能，选取了飞蛾扑火算法（MFO）[15]、正余弦算法（SCA）[13]、旗鱼算法（SFO）[16]、多元宇宙算法（MVO）[17]、基本麻雀算法（SSA）[1]，以及融合2.2节正余弦的麻雀算法（记为SSSA）、融合2.3节柯西变异的麻雀算法（记为CSSA）共7种算法，在表1的10个经典测试函数下进行综合性比较。其中f1~f4为单峰函数，f5~f10为多峰函数。表2为8种算法的主要参数设置。采用的实验环境为Windows10，64位操作系统，处理器为Intel®Core™i7-10870H CPU，主频率为2.20 GHz。算法基于MATLAB2016b，使用M语言编写。

表1 测试函数Table 1 Test function

表2 主要参数设置Table 2 Main parameter settings

3.1 收敛曲线分析

为了对各种算法的收敛性进行详细描述，将用收敛曲线图来实现。保证对比的公平性，设置8种算法的种群数为30，维度dim=30，最大迭代数目500，得到了独立运行100次的收敛曲线，图3给出了函数f1~f2、f5~f10下的8个收敛曲线。如图3所示，纵坐标取10为底的对数，其中当曲线随着迭代次数的增加不再显示，即表示该算法已得到理论最优解0。

图3 8个测试函数下的收敛曲线Fig.3 Convergence curves under eight test functions

由图3（a）、（b）单峰收敛曲线可知，SSA的收敛性能略优于MFO、SCA、MVO、SFO，但收敛曲线同样呈现平缓趋势，出现停滞状态，寻优精度低，陷入局部最优。CSSA和SSSA这两种改进算法较SSA在收敛速度和精度都有明显的提高，也验证了正余弦策略和柯西变异具有跳出局部最优和快速搜索能力，在CSSA与SSSA的整体比较，两者在收敛速度上相当，而CSSA最终表现出更高的收敛精度，主要因为借助柯西变异寻最优时表现的突变性。而SCSSA在收敛速度和精度相比于CSSA、SSSA得到进一步提升，且均获取了理论最优解。由图3（c）~（h）多峰收敛曲线可知，与MFO、SCA、MVO、SFO相比，SSA在（c）~（e）、（g）、（h）收敛速度与精度表现显著性优势，曲线一开始就迅速下降，同时在收敛精度上，SSA与CSSA、SSSA、SCSSA在（c）和（e）皆取得理论最优解0。CSSA和SSSA在多峰寻优时较SSA有明显提升，CSSA相比于SSSA在（h）表现更优，SSSA则在（c）~（g）表现出更强寻优精度和速度，验证了正余弦策略和两种非线性因子的引进有助于全局寻优能力的提升，而SCSSA较两种改进策略性能更为突出。通过收敛曲线，验证了SCSSA在求解单峰和多峰函数时均有优异的表现，主要因为折射反向学习策略的引进，丰富了群体多样性，降低SSA在寻优后期落入早熟收敛的可能性；融合正余弦策略，并利用非线性递减搜索因子和权重因子对其改进，提高SSA在全局搜索和局部开发的平衡作用以及快速性；借助柯西变异对当前陷入局部极值位置产生扰动，扩大搜索范围，提升跃出局部最优解的几率。

3.2 收敛精度分析

为了测试SCSSA的寻优精度，将上述8种算法在10个测试函数（空间维数dim=30/50/100）情况下进行寻优，其中每种算法在函数下独立运行100次，采用均值Mean、均方差S.D.以及运行时间t这3个性能指标进行结果评价，得到如表3所示的实验对比结果。

由表3可知，本文提出的SCSSA算法仅在函数f6、f9下未取得理论最优值，在其余8个测试函数不同维度皆取得理论最优值0，表现了很强的寻优能力。而对f1~f10的10个测试函数，SCSSA仅在f9的鲁棒性处于劣势，在其余9种测试函数的各种维度下寻优结果的标准差都为0，显现了SCSSA极强的稳定性。从维度方面分析，随着测试函数维度的增加，MFO、SCA、MVO、SFO寻优能力和鲁棒性整体呈现下降趋势。SSA、CSSA、SSSA在求解单峰函数f1~f4、多峰函数f8~f10时，随着维度的升高，SSA鲁棒性和寻优精度在f1、f3、f8~f10呈下降趋势，在f2、f4上呈现波动；SSSA在f1时精度存在波动，但保持很强的鲁棒性，在f2和f8时随着维度增加表现更好的精度与稳定性，在f3、f4、f9、f10随之变差；CSSA稳定性和收敛精度主要为波动变化，但在f1、f3、f10具有极好的稳定性。而SSA、CSSA、SSSA在f5~f7中皆能保持良好的稳定性和全局探索能力。就标准差而言，CSSA与SSSA的值整体小于SSA，从侧面也说明正余弦策略与柯西变异的引进提高了SSA的鲁棒性。

在寻优精度方面，SSA算法在各测试函数不同维度下的寻优精度皆优于MFO、SCA、MVO、SFO，且求解f5、f7时，SSA算法取得了理论最优值0，在求解f6时，SSA取得了极值8.88E-16，虽未寻得最优解，但对比于MFO、SCA、MVO、SFO的寻优能力仍有明显提高。而对SSA的两种改进策略CSSA和SSSA算法在求解不同维度单峰函数f1~f4、多峰函数f8、f10时，仅SSSA在求解dim=100时的f10未显现出优势，其余CSSA、SSSA均值的数量级相较于SSA至少提升了16个，最多时达到250个数量级；CSSA、SSSA求解f5~f7时，与SSA皆取得相同解；在求解f9，两者寻优精度略高于SSA。在整个测试函数中，CSSA、SSSA整体收敛精度得到明显的提高，同时也说明了正余弦策略和柯西变异策略对于SSA算法在全局寻优能力具有积极作用，降低SSA陷入局部最优的几率。

通常一个算法的时间复杂度能够根据其运行消耗的时间进行衡量，而时间复杂度能反映算法的优劣性，当算法的复杂度变高，表示该算法的运行效率降低。在10个测试函数下，随着维度增加，求解问题复杂度升高，全体算法耗时变长。算法比较方面，SCA整体耗时最短，SSA相比于改进的SSSA、CSSA、SCSSA耗时更长，说明改进策略的引进没有提升SSA的复杂度，降低执行效率。由于SSSA兼具全局搜索和局部开发，SSSA相比CSSA耗时更长。但针对部分函数不同维度出现CSSA耗时与SCSSA相当的现象，主要由于几种改进策略的引进，扩大了SSA算法的寻优范围，进而需要更多时间，导致耗时也变得较长。综上，由图3和表3结论分析验证本文提出的改进策略的有效性。

表3 不同维度下的实验结果对比Table 3 Comparison of experimental results in different dimensions

3.3 MAE测试

统计学中的平均绝对误差（mean absolute error，MAE）常用于评估真实值与预估值之间的差异。文献[18]借助MAE对几种算法进行比较和性能排序，验证了该指标的可行性。当MAE值越小时，表示算法的寻优性能更优，其公式如下：

式中，N为测试函数数目；y i为算法得到最优解的平均值，k i为理论最优解。

表4分别给出了几种算法基于单峰函数、多峰函数、整体函数在维度dim=30的MAE值以及排序。由表4可知，SCSSA在单峰、多峰、全体函数下MAE的值皆最小，且排序均第一，从整体表明了SCSSA的优越性。而CSSA、SSSA两种改进策略在单峰和多峰各略显优势，但较SSA的MAE值都小，说明CSSA、SSSA较SSA的寻优性能更佳。而SSA较MFO、SCA、MVO、SFO的MAE值更小，表明SSA相比其他智能算法具有更好的收敛性能。

表4 单峰、多峰、全体函数下MAE结果及排序Table 4 MAE results and ranking under unimodal，multimodal and whole function

3.4 Wilcoxon秩和检验

为验证SCSSA与另外7种算法在全局寻优上是否存在显著性区别，利用Wilcoxon秩和检验[19]能够对两两算法之间进行性能测试比较的特点，选取原假设H0：两种算法在性能上相当，备选假设H1：两种算法性能有着明显差异。利用检验结果p-value来比较两种算法之间的差异性，当p-value<0.05时，拒绝H0，说明两种算法在性能上存在明显区别；当p-value>0.05，接受H0，即两种算法在全局寻优上性能相当。

表5为10个测试函数在维度dim=30下独立运行100次的SCSSA与MFO、SCA、MVO、SFO、SSA、SSSA、CSSA比较的秩和检验结果，其中“S”表示差异性判别，“+/=/-”分别表示SCSSA在性能上“优于/相当/逊于”其他算法，N/A表示两算法性能相当，且为最优。由表5可知，SCSSA的p-value绝大部分小于0.05且为“+”，说明SCSSA相比与其他7种算法性能更优，至于在f5~f7函数下，SCSSA与SSA、SSSA、CSSA在全局寻优上性能相当，且皆能取得最优值。总体而言，SASSA相比于另外7种算法具有显著性优势。

表5 Wilcoxon秩和检验结果Table 5 Wilcoxon rank sum test results

3.5 与最新的改进型麻雀算法作比较

为进一步验证SCSSA算法的优越性，与最新提出的几种麻雀改进型算法进行比较，分为别ISSA[7]、CSSA[8]、ISSA[20]，为保证对比的公正性，设置4种算法种群数30，最大迭代数100，维度dim=30，分别计算在7种测试函数f1~f7下独立运行30次的Mean和S.D.，其中未给出的数据用“—”表示，实验结果如表6所示。

表6 与三种改进策略性能比较Table 6 Comparison of performance with three improvement strategies

由表6所示，在单峰函数f1~f3中，SCSSA在全局寻优中皆未能得到理论最优解，但相比于CSSA[8]在Mean上至少提升了50个数量级，多则102个，提升效果明显；对于ISSA[7]，SCSSA则至少有28个数量级优势；而对于ISSA[20]，SCSSA在f1、f2的全局搜索能力和稳定性略显优势，但在f3中，在求解精度方面提高了11个数量级，且标准差皆为零，表示SCSSA鲁棒性比ISSA[20]更强。在多峰函数f4中，ISSA[7]、ISSA[20]未给出相关数据，SCSSA较于CSSA[8]在全局寻优有45个左右数量级优势。在多峰函数f5~f7中，SCSSA与另外三种改进型SSA在求解精度和稳定性方面相当，且在f5和f6均能寻得最优解0。综上所述，表明了SCSSA在单峰和多峰函数下皆取得较优解且表现较强的鲁棒性，验证SCSSA相比于其余三种算法具有一定的竞争力。

3.6 工程优化问题应用

为验证SCSSA在实际工程中的优越性，选取了压力容器设计优化问题，并通过与表2中的其他7种算法进行验证比较。压力容器设计问题是一个经典的工程优化设计问题[17]，目的是通过减少压力容器的耗材来降低制造成本。压力容器的两端由盖子封顶，头部一端由半球状盖子组成。该设计问题主要包括4个变量：即非头部的圆柱体部分的截面长度(L)、内壁直径(R)、壁厚(T s)及头部的壁厚(T h)。数学模型表示如下：

其中，0≤x1,x2≤99，10≤x3,x4≤200。

由表7可知，对于压力容器设计问题SCSSA相比较其他7种算法具有较好的优化结果。进一步表明SCSSA在实际工程应用的有效性和优越性。

表7 几种算法的压力容器设计比较Table 7 Comparison of pressure vessel design results for several algorithms

4 结束语

本文提出了一种融合正余弦算法和柯西变异的麻雀搜索算法，在种群初始化中引入一种折射反向学习机制，用于解决种群多样性不足而造成麻雀在搜索后期出现停滞问题；在麻雀发现者位置中加入正余弦机制以及非线性递减搜索因子和权重因子用于更好解决SSA在兼顾全局和局部寻优时表现的不足；在麻雀跟随者中利用柯西变异能对当前最优个体产生突变，从而扩大麻雀捕食范围，进而提高SSA的全局寻优精度和速度。通过10个经典测试函数进行检验，将SCSSA与其他算法在收敛速度、精度、MAE测试以及Wilcoxon秩和检验下进行比较，并与最新麻雀算法改进策略进行对比，最后通过压力容器优化设计问题进一步验证。结果表明，融合正余弦与柯西变异的麻雀搜索算法在全局寻优以及局部开发具有更优表现，因此也证明了改进策略的有效性和可靠性。后续工作考虑将SCSSA深入应用到炼钢工艺中用于解决实际问题。