一种混合麻雀搜索算法

李敦桥

摘要：元启发式算法由于可产生多样的解决方案在科学及工业领域受到了广泛的应用，麻雀搜索算法（SSA）是一种相对新颖的基于群体的元启发式算法，已被证明具有较好的寻优求解性能。由于在某些情况下麻雀种群多样性不足，导致算法寻优精度低，易陷入局部最优，因此提出了一种混合麻雀搜索算法（HSSA），首先利用反向对立学习策略提高初始种群质量，其次混合了模拟退火算法的Metropolis准则，避免算法陷入局部最优。为了验证算法的性能，利用HSSA对多个单峰和多峰测试函数进行求解，实验结果表明，与WOA、SSA和IPSO相比，HSSA具有更快的收敛速度和更高的求解精度。

关键词：麻雀搜索算法;反向对立学习;Metropolis准则;混合算法;函数优化

Abstract： Meta-heuristic algorithm has been widely used in science and industry because it can produce a variety of solutions. The sparrow search algorithm （SSA） is a relatively new population-based meta-heuristic algorithm， which has been proved to have good performance in optimization. Due to the insufficient diversity of sparrow population in some cases， the optimization precision of the algorithm is low and it is easy to fall into the local optima. Therefore， the hybrid sparrow search algorithm （HSSA） is proposed， which firstly improves the initial population quality by using the Opposition-based learning strategy， and secondly the algorithm mixes the Metropolis criterion of simulated annealing algorithm to avoid the algorithm falling into local optimal. In order to verify the performance of the algorithm， HSSA was used to solve some unimodal and multimodal test functions. The experimental results show that compared with WOA， SSA and IPSO， the proposed HSSA has faster convergence rate and higher solution accuracy.

Key words： sparrow search algorithm; opposition-based learning; metropolis criterion; hybrid algorithm; function optimization

群智能优化算法已被广泛应用于现实生活中各种优化问题求解，通过模仿飞蛾、蜜蜂、狼和鸟类等自然界各种物理或生物行为构造出数学模型，利用多次迭代获取最佳解决方案[1-3]。麻雀搜索算法（Sparrow Search Algorithm， SSA）[4]是由沈波等在2020年提出的一種新型群智能优化算法，该算法通过模拟麻雀群体智慧、觅食和抗捕食行为来获取最优解，经实验证明，SSA在精度、收敛速度、稳定性和鲁棒性都具有较强的性能。但由于种群多样性不足，SSA算法在迭代过程中极易跳过最优解而陷入局部最优，导致全局搜索能力较差，No Free Lunch（NFL）定理[5]表明，没有任何一种算法可以在每个优化问题上都表现出色，因此，研究群智能优化算法的改进依旧具有很强的实际意义。

针对上述问题，本文提出了一种混合麻雀搜索算法（Hybrid Sparrow Search Algorithm， SSA），利用反向对立学习优化麻雀初始种群，优化种群的质量可以极大程度的提高收敛速度和收敛精度，其次，混合了模拟退火优化算法[6]中的Metropolis准则，利用一定的概率接受麻雀寻优过程中的恶化解，使得算法能够跳出局部最优而避免过早收敛。通过多个测试函数验证了HSSA具有更高的精度，证明了本文提出改进方法的有效性。

1 SSA

麻雀是杂食性群居鸟类，与其他鸟类相比，麻雀相对聪颖，具有较好的记忆力。在日常生活中，麻雀被分为生产者和乞讨者两类，生产者积极寻找食物，而乞讨者从生产者那里获取食物。通过这种生产者与乞讨者的策略，麻雀得以获得食物从而生存，这种策略的数学模型描述如下：

在迭代寻优过程中，麻雀种群中的生产者负责寻找食物和指导整个种群的移动，如果发现危险，会发出警报并引导乞讨者至安全区域，在每次迭代中，生产者的位置更新如下：

式中，[Xtbest ]表示第[t]代种群中的最优位置，[β]是符合正态分布的步长控制参数，均值为0，方差为1，[K]是[-1，1]的随机数，[fi]表示麻雀当前位置的适应度，[fg]与[fw]分别为全局最优和最差适应度，[ε]为不为零的极小值。

2 HSSA

2.1 基于反向对立学习的种群初始化

由于SSA的初始种群都是随机产生的，很容易聚集于某一区域或过于分散，对后续的迭代寻优有很大的影响，极易陷入局部最优，因此，本文引入反向对立学习[7]提高初始种群质量，该策略通过计算当前位置在搜索空间内的对立点来改善初始种群，在[d]维空间内，若麻雀的初始位置为[X=x1，x2，...，xd]，其对立点[X]位置计算方法如下：

在产生初始种群后，选择适应度较高的[n2]个麻雀个体并通过反向对立学习获取其对立位置，产生新的初始种群[Xnew=Xn2?Xn2]。

2.2 Metropolis准则

Metropolis准则[8]由模拟退火算法产生，受启发于退火原理，利用该准则对当前解与新解进行比较替换，避免寻优迭代过程产生停滞和陷入局部最优，本文将Metropolis准则与SSA混合，避免麻雀种群在寻优过程中早熟，提高其全局搜索能力，Metropolis准则的描述如下：

2.3 HSSA算法描述

综上所述，HSSA算法的流程如图1所示。具体步骤为：

①初始化HSSA算法的[R2]，[n]，[T]，[Te]等参数;

②生成初始种群并获取适应度较高的前[n2]只麻雀[Xn2];

③利用反向对立学习计算麻雀对立点[Xn2];

④产生新初始种群[Xnew=Xn2?Xn2];

⑤获取当前最好与最差的麻雀;

⑥利用公式（2）-（5）更新麻雀位置并计算适应度;

⑦根据适应度值判断是否更新全局最优位置;

⑧利用公式（7）Metropolis准则判定是否接收新解;

⑨判定是否达到最大迭代次数，若满足，输出最优麻雀位置，若不满足，跳转至步骤⑤。

3 仿真实验

3.1测试函数

为了评估提出HSSA算法的性能，本文选用了6种不同的单峰和多峰函数进行测试，测试函数如表1所示，设置种群数量[n]为100，最大迭代次数[T]为1000，在相同实验条件下，将HSSA与WOA[9]、SSA和IPSO[10]进行30次对比实验，证明提出改进的有效性。

3.2实验结果与分析

为了验证提出HSSA的优越性，比较4种算法30次运行结果的平均值（Mean）和标准差（Std），表2中的结果表明，HSSA在求解6个单峰和多峰函数时都表现出了优秀的性能，均优于其他对比算法。此外，F1-F6测试函数的收敛曲线如图2所示，由图可知，与其他算法相比，提出的HSSA在6种情况下具有明显优势，证明本文提出的改进能改善算法的全局搜索能力，避免过早收敛，防止麻雀种群在迭代过程中陷入局部最优。

4 结论

本文提出了一种混合麻雀优化算法，通过反向对立学习策略改善了随机初始种群的质量，利用Metropolis准则提高了麻雀种群的全局搜索能力，提高了收敛精度，加快了搜索速度，避免迭代过程中陷入局部最优。利用6种不同的函数验证了HSSA的性能，与WOA，IPSO和SSA相比，本文提出的HSSA具有更快的收敛速度和更高的精度，证明了提出改进策略的有效性。

参考文献：

[1] 陈堂功，刘超，王梦莹，等.基于动态参数的人工搜索群算法[J].控制与决策，2019，34（9）：1923-1928.

[2] 黄海松，范青松，魏建安，等.基于CEEMDAN-IGWO-SVM的轴承故障诊断研究[J].组合机床与自动化加工技术，2020（3）：22-25，31.

[3] 王林，吕盛祥，曾宇容.果蝇优化算法研究综述[J].控制与决策，2017，32（7）：1153-1162.

[4] Xue J， Shen B. A novel swarm intelligence optimization approach： sparrow search algorithm[J]. Systems Science & Control Engineering. 2020， 8（1）： 22-34.

[5] Wolpert D H， Macready W G. No free lunch theorems for optimization[J]. IEEE Transactions on Evolutionary Computation. 1997， 1（1）： 67-82.

[6] 杨飞. 模拟退火算法在物流线路选择方面的研究[J].电脑知识与技术，2019， 15（4）： 270-271.

[7] Liang Z， Zhang J， Feng L， et al. A hybrid of genetic transform and hyper-rectangle search strategies for evolutionary multi-tasking[J]. Expert Systems with Applications. 2019， 138： 112798.

[8] 邹宾森，张则强，蔡宁，等. 工具约束下多目标拆卸线平衡问题的猫群模拟退火算法[J]. 计算机集成制造系统. 2018， 24（9）： 2210-2222.

[9] Mirjalili S， Lewis A. The Whale Optimization Algorithm[J]. Advances in Engineering Software. 2016， 95.

[10] 劉秀梅. 动态系统中粒子群优化算法综述[J]. 软件导刊. 2016， 15（10）： 43-46.

【通联编辑：唐一东】