基于Sobol序列和纵横交叉策略的麻雀搜索算法

段玉先，刘昌云

（1.空军工程大学防空反导学院，西安 710038；2.空军工程大学研究生院，西安 710038）

0 引言

最优化问题是机器学习中的重要问题。在工程应用中，很多复杂问题都可以转化为优化问题来求解。优化的目的是在一定限制条件下，通过计算使效率、绩效、生产率等指标最大化［1］。在现实世界中，从给定的备选方案中找寻选择解决方案对于解决最优化问题至关重要。传统的优化算法（如牛顿法、共轭梯度法等）虽然简单易行，但是仅适用于处理简单的目标函数和单峰函数［2］。因此，如何解决高度复杂的非线性问题成为学界关注的焦点。

术语“元启发式”描述了一种为解决广泛的优化问题而提出的更高层次的启发式算法。Kirkpatrick 等［3］在1983 年正式开启了对于元启发式算法的研究，为解决最优化问题提供了新的思路。它们采用随机化的搜索框架，通过局部和全局两种搜索策略进行寻优。相比穷尽法，元启发式算法能够以可接受的时间成本提供对于复杂问题较好的解决方案［4］。随着研究的不断深入，国内外学者提出了许多新型元启发式算法，例如粒子群算法［5］、蚁群算法［6］、遗传算法［7］、蜻蜓优化算法［8］等。

虽然各种元启发式算法层出不穷，但最主要的优化过程分为两个阶段：探索和开发。在探索阶段，算法以高度的随机性在广泛的邻域中进行全局搜索，以获得最优解所在的区域。在这一阶段，算法多样性较高，收敛速度较快。在开发阶段，算法将专注于在已探索的区域进行局部搜索。随着迭代过程不断逼近最优解，多样性逐渐降低，算法逐渐收敛。如果设定的探索过程比重较大而开发过程比重过小，将减慢搜索过程。反之，则将导致过早收敛。因此，保持探索和开发之间的平衡是所有元启发式算法的共同点和基本特征［9］。传统方法中，粒子群算法局部搜索能力不强，因此容易在复杂的多峰问题中过早收敛。蚁群算法控制参数较多并且具有关联性，性能的提升需要依赖于不断的试错和调整。遗传算法编解码过程较为复杂。

麻雀搜索算法（Sparrow Search Algorithm，SSA）是2020年提出的一种新兴的元启发式算法［10］，它与粒子群算法、蜻蜓优化算法等同属于基于群体的社会化特征优化的群智能算法。该算法通过不断更新个体位置，模拟麻雀觅食和反捕食行为。相比传统算法，麻雀搜索算法的结构简单、易于实现，且控制参数较少，局部搜索能力较强。该算法在单峰、多峰等基准函数上的表现优于粒子群算法、蚁群算法等传统算法。但算法在处理全局最优解不在原点附近的函数时，容易陷入局部最优，并且存在收敛精度较低等缺陷。针对这些问题，本文提出了基于Sobol 序列和纵横交叉策略的麻雀搜索算法（Sparrow Search Algorithm based on Sobol sequence and Crisscross strategy，SSASC）。在初始化阶段引入Sobol 序列，使初始麻雀的位置分布更加均匀，提升种群多样性。其次，引入非线性惯性权重，优化发现者位置更新方式，提高全局搜索能力和收敛效率。最后，引入纵横交叉策略，取得算法在局部搜索能力和全局开发能力上的平衡，防止算法陷入局部最优。为验证算法性能，对13 个基准函数进行仿真实验，同时结合Wilcoxon 秩和检验和Friedman 检验评价SSASC 算法相较其他算法的改进和优势。

1 麻雀搜索算法

在麻雀搜索算法中，将个体区分为发现者、跟随者和警戒者，每个个体位置对应一个解。根据算法设定，警戒者所占种群比例是10%～20%，而发现者和跟随者是动态变化的，即一只个体成为发现者必然意味着另一只个体将成为跟随者。按照分工划分，发现者主要为整个种群提供觅食方向和区域，跟随者则是跟随发现者进行觅食，警戒者负责对觅食区域的监视。在觅食过程中，通过不断更新三者位置，完成资源的获取。

设种群中有n只麻雀，则由所有个体组成的种群可表示为X=[x1，x2，…，xn]T，个体各自对应的适应度函数为F=[f(x1)，f(x2)，…，f(xn)]T。其中，发现者的位置更新方式如下：

其中：t表示当前迭代次数，表示在第t代中第i只麻雀在第j维的位置，α∈(0，1]，itermax代表最大迭代次数，R2 表示报警值，ST表示安全阈值，Q是服从正态分布的随机数，L是1×dim的矩阵，dim表示维度。发现者位置更新方式可总结如下：当R2 ＜ST时，觅食区域周围没有捕食者，发现者可以广泛搜索食物；当R2 ≥ST时，捕食者出现，所有发现者都需要飞往安全区域。

跟随者的位置更新方式如下：

警戒者位置更新方式如下：

2 改进的麻雀搜索算法

2.1 基于Sobol序列初始化种群位置

在元启发式算法中，初始化种群的分布很大程度上影响算法的收敛速度和准确性［11］。在处理分布未知的问题时，种群的初始值应当尽可能地在搜索空间中均匀分布，以保证较高的遍历性和多样性，提升搜索效率［12］。在麻雀搜索算法中，在搜索空间采用随机数的方式产生初始化种群。这种方法遍历性较低，并且个体分布不均匀，具有不可预测性，在一定程度上影响了算法的性能。

为提升全局搜索能力，有学者利用混沌搜索优化初始化序列。例如，Tian［13］利用Tent 混沌方式初始化种群、Arora等［14］采用Circle 混沌方法初始化种群、Zhang 等［15］引入Cubic映射算法初始化种群。这些混沌算法虽然具有一定跳出局部最优的能力，但存在两点不足：一是随机性强，算法运行时会面临很大的不确定性；二是相邻点紧密相关，若迭代至不稳定点则无法继续运行，如Tent 映射小周期点（0.2，0.4，0.6，0.8）和不稳定点（0，0.25，0.5，0.75）［16］。

与伪随机数不同，低差异序列采用确定性的低差异序列代替伪随机序列，又称拟蒙特卡洛（Quasi-Monte Carlo，QMC）方法。QMC 通过选择合理的采样方向，将尽可能均匀的点填充至多维超立方体单元，因此在处理概率问题时，具有更高的效率和均匀性。其中，Sobol 序列计算周期更短、采样速度更快，并且在处理高维度序列上有更高的效率［17］。因此，本文采用Sobol 序列［18］对初始化种群进行映射。

设最优解的取值范围为[xmin，xmax]，Sobol 序列产生的随机数Kn∈[0，1]，则种群初始位置可定义为：

假设种群上下界分别为0 和1，通过每种方法运行100 次产生的初始化种群分布如图1 所示。其中，横轴代表取值大小，纵轴表示个体落入一定范围的次数。可以看出，相较于伪随机数序列，通过Sobol序列产生的初始化种群落入每个范围内的个体数量大致相同，分布更加均匀，遍历性更广。

图1 不同方法产生的初始化序列分布Fig.1 Distribution of initialized sequences generated by different methods

2.2 非线性惯性权重

探索和开发之间的平衡是影响元启发式算法的关键因素。在麻雀搜索算法中，原算法中缺乏对于步长的有效控制，在发现最优解后，其他个体迅速向最优解靠拢，使得算法难以有效控制全局探索和局部开发进程，从而陷入局部最优。为此，引入非线性惯性权重ω控制搜索范围和收敛速度。惯性权重ω计算方式如下所示：

当迭代运行500 次，惯性权重ω的变化曲线如图2 所示。从图2 中观察到，迭代初期全局搜索时，惯性权重ω较大，非线性变化速率快，能够使得种群不断探索未知区域，保持较高的全局搜索能力，防止算法过早收敛。在迭代后期ω较小，非线性变化速率慢，将有助于算法专注于在已探索的区域寻找更好的解决方案，保持较高的局部开发能力，提高收敛速度。

图2 非线性惯性权重的变化曲线Fig.2 Change curve of nonlinear inertia weight

在迭代过程中，随着惯性权重ω的不断自适应变化，将利于改善算法在探索和开发之间的平衡。通过改进后，发现者的位置更新方式如下：

2.3 纵横交叉策略

由于麻雀个体在迭代过程中不断向最优个体周围靠拢，随着算法的进行，很可能造成种群将聚集于局部最优解周围，从而使得算法开发全局最优解的能力下降。为使算法在局部搜索能力和全局开发能力之间取得平衡，避免算法陷入局部最优，防止过早收敛的状况发生，本文将纵横交叉策略［19］引入麻雀搜索算法，改进警戒者的搜索方式，在不影响算法收敛速度的前提下提高求解精度。通过横向交叉将多维问题的求解空间拆分为半群超立方体，对空间进行边缘搜索，在减少盲点的同时提升算法全局寻优能力；通过纵向交叉在种群中不同维度进行交叉运算，在不影响其他维的前提下，促进陷入停滞的维度跳出局部最优。通过二者的竞争比较，完成算法的求解。

2.3.1 横向交叉操作

横向交叉操作类似于遗传算法中的交叉操作，是在不同种群的相同维度中进行交叉运算。针对麻雀搜索算法全局搜索能力不强的问题，本文应用横向交叉策略对警戒者的位置进行更新。首先将父代个体随机配对，在第d维进行交叉操作，如下所示：

经过横向交叉操作后，警戒者能够以较大概率在各自的超立方体空间及外边缘产生子代个体，以便扩充算法的搜索空间，提高全局搜索能力。横向交叉产生的解需要与其父代进行比较，选择适应度较高的个体进行保留。这就意味着，在外边缘空间产生子代的数量会随与父代个体的距离增加而逐渐线性递减。在此影响下，算法能够不断向最优解收敛，可以在不影响寻优精度的同时保证收敛效率。通过横向交叉操作，算法平衡探索和开发之间的能力得到了加强。

2.3.2 纵向交叉操作

麻雀搜索算法在后期容易陷入局部最优，在很大程度上是由于种群中某些个体在某一维度上陷入局部最优，从而使整体过早收敛。经过分析发现，在麻雀搜索算法中缺乏一定的变异机制，无法对已经陷入局部最优个体进行控制，从而阻断了搜索进程和找到全局最优解的可能性。因此，在执行横向交叉操作之后，需要对新生个体进行纵向交叉操作，提高算法规避局部最优的能力。不同于横向交叉操作，纵向交叉操作是在新生个体的所有维度进行的交叉运算，发生的概率小于横向交叉操作，类似于遗传算法中的变异操作。

在迭代过程中，如果某一个体的某一维度通过纵向交叉操作跳出局部最优，会迅速通过横向交叉操作散布至整个种群，而更新后的维也会使陷入局部最优的其他维有更多跳出局部最优的机会。通过横向交叉操作和纵向交叉操作的有机融合，可以有效地提高所提算法的收敛效率和求解精度。

2.4 算法流程

通过分析可以发现，麻雀搜索算法虽然具有一定的局部搜索能力，但仍有几点不足：第一，算法的初始化方式是不确定的，伪随机数产生的序列难以保证多样性和遍历性；第二，原算法缺乏个体之间的信息交流，新个体仅仅在同当前最优个体进行比较后，就向某一区域靠拢，从而失去了向其他个体周围区域探索的机会，也致使种群的多样性和遍历性有一定程度的降低。针对这些问题，本文作出三点改进：第一，采用Sobol 序列生成更加均匀分布的种群；第二，采用非线性惯性权重，对算法步长进行有效控制，提升收敛速度；第三，变更警戒者的位置更新策略，通过引入纵横交叉策略，在每一次迭代后利用横向交叉操作增强算法的全局寻优能力，在所有个体位置更新完毕一遍后，再利用纵向交叉操作使部分个体某一维度发生突变，通过更新适应度值，使算法跳出局部最优。具体改进流程如下。

步骤1 参数初始化。设定最大迭代次数itermax，种群规模N，发现者数量PD、警戒者数量SD，报警阈值ST，初始值上、下界xmax、xmin，最大寻优次数Cmax。

步骤2 种群初始化。根据式（4），生成遍历性强的Sobol 序列用以种群初始化。

步骤3 计算每只麻雀个体的适应度f(x)，记录最佳适应度和最差适应度对应的个体位置。

步骤4 选取适应度高的前PD只个体作为发现者，根据式（6）更新位置。

步骤5 余下的个体作为跟随者，根据式（2）更新位置。

步骤6 从种群中随机选取SD只个体作为警戒者，进行横向交叉操作，根据式（7）、（8）更新位置。

步骤7 根据式（9）进行纵向交叉操作，比较适应度大小，择优保留。

步骤8 本次迭代完成后，计算个体适应度f(x)，记录全局最优解Pg以及当前最优解Px。

步骤9 判断算法是否达到最大迭代次数itermax：若没有则返回步骤步骤3，同时当前迭代次数t=t+1；否则算法结束，输出结果。

3 仿真实验与结果分析

3.1 实验设置

在这一节将验证所提出的SSASC 算法的有效性，并与正弦余弦算法（Sine Cosine Algorithm，SCA）［20］、灰狼优化（Grey Wolf Optimizer，GWO）算法［21］、鲸鱼优化算法（Whale Optimization Algorithm，WOA）［2］、SSA［10］、混沌麻雀搜索优化算法（Chaotic Sparrow Search optimization Algorithm，CSSA）［22］五种算法进行比较。选取了具有代表性的13 个基准函数进行测试，这些函数均来自文献［2］，其中：f1(x)到f4(x)是单峰函数，在定义上下限范围内只有一个全局最优解，通常用于检测算法的收敛速度和寻优能力；f5(x)到f10(x)是多峰函数，在函数的定义域内存有多个局部极值，通常用于检测算法全局搜索和避免过早收敛的能力；f11(x)到f13(x)是固定维复合函数，通常用于检测算法平衡探索和开发之间的能力。

仿真实验环境为Intel Core i5-9300H CPU @ 2.40 GHz，16 GB 内存，Windows 10 操作系统MATLAB R2019b 仿真实验平台。为保证实验的公平性和客观性，将所有算法的种群规模N设置为30，最大迭代次数itermax设置为500，各算法分别独立运行30次，统计30次实验的平均值和标准差。由于维度也是影响寻优精度的一个重要因素，因此将f1(x)到f10(x)从10 维扩展到100 维，验证算法在不同维度下的求解能力。在实验完成后，需要对各算法结果进行评价。本文通过比较平均值（avg）、标准差（std），分析各算法效率性能。其中，平均值可以反映算法的求解精度和质量，标准差反映算法的稳定性。

3.2 算法参数设置

为使实验更加公平，对选取的算法内参数进行了设置，如表1 所示。除表内参数外，其他参数设置保持一致。

3.3 实验过程与结果分析

从表2 中可以看出，当维度dim=10 时，相比其他算法，SSASC 取得了除f11(x)外其他优化函数平均值和标准差的最佳值，并在其中8 个函数上取得了全局最优解。此外，CSSA在f11(x)上取得最佳平均值和标准差值。SSA 则找到了f6(x)、f8(x)最佳值。总体来看，SSASC 表现最佳，而SCA 表现较为不佳。

表2 不同算法比较结果（dim=10）Tab.2 Comparison results of different algorithms（dim=10）

对实验结果进行分析，与其他启发式算法相比，SSASC更加具有竞争优势。在单峰问题f1(x)～f4(x)上，SSASC 的表现均优于其他算法；并且，SSASC 多次运行表现稳定，说明算法具有较好的鲁棒性。在多峰问题f5(x)～f10(x)上，SSASC也取得了很大的进步，结果表明算法具有良好的跳出局部最优和全局搜索的能力。在复合问题f11(x)～f13(x)上，SSASC也取得了逼近最优解的结果，说明在嵌入非线性惯性权重和纵横交叉策略后，算法平衡全局探索和局部开发的能力得到了加强。

表3 显示了当dim=30 时，在前10 个基准函数得到的平均值与标准差结果比较。可以看出，SSASC 均取得了平均值和标准差的最好结果。同时，SSA 也可以找到了2 个函数的全局最优解。CSSA 在求解f4(x)问题上排名第二，在f5(x)上取得的平均值仅次于SSASC。WOA 在f1(x)求解能力较好，并且运行结果较为稳定。通过结果分析，当dim=30 时，SSASC 算法性能最优。

表3 不同算法比较结果（dim=30）Tab.3 Comparison results of different algorithms（dim=30）

表4 显示了当dim=100 时，在前10 个基准函数得到的平均值与标准差结果比较。可以看出，SSASC 的性能依旧保持稳定。在f1(x)～f2(x)、f6(x)、f8(x)上取得了理论最优值，并且表现稳定。说明SSASC 具有解决高维问题的能力，并且具备出色的稳定性和鲁棒性。此外，随着维度的增加，SCA、GWO 的求解精度明显下降。而WOA、SSA、CSSA 则具备一定的鲁棒性。WOA 和SSA 在f6(x)、f8(x)上取得了理论最佳值。总体来说，SSASC 运行取得的结果更具有优势。

表4 不同算法比较结果（dim=100）Tab.4 Comparison results of different algorithms（dim=100）

García 等［23］提出，在评估元启发式算法的性能时，仅基于均值和标准差值进行比较是不够的。因此，为了证明所提出算法取得的结果与其他算法是否在统计上具有显著不同，需要进行统计测试［24］。调用Wilcoxon秩和检验［25］和Friedman 检验［26］来比较算法之间的性能。在Wilcoxon 秩和检验中，将p设置为0.05，提出两个假设，即null 和alternative。如果统计值大于p，则接受null；如果统计值小于p，则接受alternative。将SSASC 与SCA、GWO、WOA、SSA、CSSA 算法依次进行比较，分别记为p1、p2、p3、p4、p5。由于无法将在某个基准函数上的最佳算法与自身比较，因此将每个基准函数上的最佳算法标记为N/A，表示为“不适用”。从f1(x)到f10(x)之间的维度为10，种群规模N设置为30，最大迭代次数itermax设置为500，各算法分别独立运行30 次，得到结果如表5 所示。

由表5可知，仅对于SSASC 与CSSA 的f5(x)、f11(x)、f13(x)，SSASC 与SSA 的f7(x)、f11(x)外，SSASC 得到的p值均小于0.05，可以判定该算法的优越性具有统计学意义。因此，进而可以判定SSASC 具有更高的收敛精度。维度为10，种群规模N设置为30，最大迭代次数itermax设置为500。图3（a）～（d）为单峰函数的收敛曲线，图3（e）～（h）为多峰函数的收敛曲线。根据结果分析，SSASC 在解决单峰问题和多峰问题上表现突出。由于改进了初始化种群生成策略，种群多样性和遍历性得到了提高，使生成的初值更加接近全局最优。同时，由于引入了非线性惯性权重，使得算法在收敛速度上有了明显改进。此外，通过横向交叉和纵向交叉操作，算法可以跳出局部最优解，寻优精度也得到了提升。

表5 十三个基准函数上的Wilcoxon秩和测试的p值Tab.5 p values of Wilcoxon rank sum test on 13 benchmark functions

此外，为使实验结果更具有说明力，对6种算法在f1(x)到f10(x)上取得的平均值进行Friedman 检验，实验结果如表6 所示。同样，将p设置为0.05。当p值小于0.05 时，可以认为算法之间存在显著性差异。根据平均排名可以看出，当前10 个基准函数的维度设置为10时，6个算法的平均排名为SSASC＞SSA＞CSSA＞GWO＞WOA＞SCA。同时，p=2.856× 10-7＜0.05，表明算法之间存在明显差异。当前10 个基准函数的维度设置为30 时，6 个算法的平均排名为SSASC＞SSA＞CSSA＞WOA＞GWO＞SCA。此时，实验所得到的p=2.349 7× 10-7＜0.05，说明算法之间也存在明显差异。当前10 个基准函数的维度设置为100 时，SSASC＞SSA＞CSSA＞WOA＞GWO＞SCA。此时，根据实验结果，计算所得到的p=3.175 9× 10-7＜0.05，说明算法之间依旧存在明显差异。

表6 十个基准函数上的Friedman检验结果Tab.6 Friedman test results on 10 benchmark functions

为了比较算法的收敛速度和寻优精度，选取了8 个函数进行收敛测试，收敛图像如图3所示。从f1(x)到f10(x)之间的

图3 8个不同函数的收敛曲线Fig.3 Convergence curves of 8 different functions

4 结语

本文提出了一种基于Sobol 序列和纵横交叉的麻雀搜索算法。在保留原算法优点的基础上，利用Sobol低差异序列改进麻雀个体初始化策略，提高种群遍历性和多样性。在算法运行过程中，设置了一个非线性的惯性权重，改进了发现者的位置更新方式，提升了算法的收敛效率。同时，引入了纵横交叉策略，平衡算法在迭代时的探索与开发能力。进行了13 个基准函数的仿真实验，表明SSASC 的寻优结果均优于其他5种元启发式算法，且在部分函数上能够取得全局最优解。收敛曲线反映出SSASC的收敛速度相较于其他算法得到了明显提升。通过Wilcoxon 秩和检验、Friedman 检验，证明了实验结果具有统计学意义。在未来研究中，计划扩展改进算法的应用范围，用于解决更加复杂的实际问题。