Convergence Analysis and Application of a Hybrid Sparrow Search Algorithm Incorporating with GWO Framework

SSA是一种基于群体智能的优化算法，其灵感来自麻雀在自然界中的觅食习惯和逃避天敌的行为。在这个算法框架下，部分麻雀扮演“发现者”的角色，专注于寻找资源，而其余麻雀则作为“跟随者”进行行动。此外，群体中还专门有一部分麻雀担任“警戒者”，它们负责监测潜在威胁并及时发出警报，确保群体在追求食物的同时能够保持警惕，避免陷入危险。

在D维解空间中，麻雀个体的位置表示为X=(x₁，x₂···x_D)，适应度值f_i=f(x₁，x₂···x_D)。麻雀种群的数量为N，每一代都会从种群中挑选出位置最优的P只麻雀作为发现者，其余的M只麻雀则成为跟随者，同时它们中的部分会作为警戒者。三者位置更新公式如下：

式中：X_i，d^t+1表示第t代中第i个个体的位置；ζ为(0，1]上均匀分布的随机数；Q是服从标准正态分布的一个随机数；R₂为[0, 1]中的均匀分布的随机数；W表示安全阈值，取值范围是[0.5，1.0]；T_max是最大迭代次数；L是一个一行多维的全1矩阵。

式中：X_p代表麻雀的最优位置；X_worst代表麻雀的最差位置；A⁺是一个由1或-1组成的一行多维矩阵。

式中：ρ₁为服从均值为0，方差为1的正态分布随机数；ρ₂为[-1, 1]上的随机数；ε为一个较小的数防止分母为零；f_i是当前麻雀的适应度值；f_g和f_w是当前最佳适应度值和最差适应度值。

群体算法的初始化会影响其搜索性能。由于没有先验信息，SSA中的麻雀通常是由随机初始化产生的。但是，有时候麻雀在搜索域中的分布并不均匀，这会使麻雀远离全局最优解，导致收敛速度较低。本文采用佳点集策略对麻雀种群进行初始化，确保初始种群在目标函数定义域内均匀分布，从而有效提升了算法的精确度、收敛速率以及全局寻优能力^[10]。佳点集理论源自我国著名数学家华罗庚，假设H_m是m维欧氏空间的单位立方体，其中存在点集$ G_n(k)=\left\{\left(\left\{r_1^n \cdot k\right\}, \left\{r_2^n \cdot k\right\}, \cdots, \left\{r_m^n \cdot k\right\}\right), 1 \leqslant k \leqslant n\right\}$，它的偏差满足$ \varphi(n)=C(r, \vartheta) n^{-1+\vartheta}$，其中$ C(r, \vartheta)$是常数，只与$ r \vartheta(\vartheta>0)$有关。那么G_n(k)称为佳点集，r称为佳点，n为点数。佳点集$ C(r, \vartheta)$的值为：$ r_i=2 \cos \left(\frac{2 \mathsf{π} i}{g}\right)$，1≤i≤m，其中，g是满足$ \frac{(g-3)}{2} \geqslant m$ 的最小素数。

为了验证佳点集初始化的有效性，设置初始种群数量为100，在二维空间中初始化麻雀种群，与Logistic混沌映射和Tent映射进行对比，对比结果见图 1。从图 1中可以直观看出，佳点集策略初始化的麻雀种群分布更为均匀，能进一步优化算法收敛速度，避免陷入局部最优。

在SSA中，发现者和跟随者的数量保持不变。这样的设置在算法初期可能导致发现者数量不足，不足以进行充分的全局搜索。而在算法后期，当发现者数量较多时，全局搜索的需求减少，反而需要增加跟随者的比例以进行更精确的局部搜索^[11]。为优化这一过程，本文提出了发现者-跟随者自适应调整机制。在算法早期，发现者比例较高以加强全局搜索，随后随着迭代进行，发现者数量逐渐减少，而跟随者数量相应增加，使得搜索过程逐渐由全局转向局部，从而提升算法的整体收敛精度^[12]。发现者和跟随者数目调整公式为：

式中：P为发现者数目；M为跟随者数目；b为比例系数，本文取0.15，用于控制发现者和加入者之间的数目(在算法执行方面，前期需要更多的发现者进行全局搜索，经过反复实验取0.15，同时0.1对发现者比例起到下限支撑作用，确保算法在后期仍有一定全局搜索能力，避免过早收敛)；k为扰动偏离因子，对非线性递减值φ进行扰动。

SSA中，发现者在迭代时采取的跳跃式移动可加速收敛，但易导致种群快速集中，减少搜索多样性，并可能因忽视搜索盲区或范围限制而陷入局部最优。此外，发现者在位置更新时对当前位置的利用程度不变。借鉴PSO算法，本文通过引入惯性权重扰动策略来优化SSA中发现者的位置更新，以增强其全局搜索能力^[13]。其中，三角函数具有周期性和波动性，在迭代过程中，这种波动使得惯性权重不会单调增加或减少，而是呈现出一定的波动变化。该方法使得种群中适应度较高的个体在其原始位置附近进行扰动，从而促进了麻雀种群内的信息交互。改进的发现者位置更新公式如下：

式中：X_i，d^t+1表示基于Levy飞行的跟随者改进策略t代中第i个个体的位置；Q为一个标准正态分布随机数；R₂为[0, 1]上均匀分布的随机数；W为安全阈值，取值范围为[0.5，1.0]；τ是一个控制指数衰减速度的参数，用于调整衰减速度，取0.1。

当跟随者了解到发现者寻找到更好食源时会大量聚集，这会使发现者密度过大，从而导致陷入局部最优。在Levy飞行^[14]策略中，步长是根据Levy分布生成的。Levy飞行策略通过引入Levy分布，使得步长可以具有更大的幅度变化，从而更好地模拟真实世界中的飞行情况。本文通过Levy飞行策略优化跟随者位置，扩大其搜索空间，改善易陷入局部最优的问题。改进的跟随者位置更新公式为：

式中：$ S=\frac{\theta}{|h|^{\frac{1}{\lambda}}} ; \theta \sim N\left(0, \sigma_\mu^2\right) ; h \sim N\left(0, \sigma_\nu^2\right) \sigma_\nu=1 ; \sigma_\mu=\left\{\frac{\varGamma(1+\lambda) \sin \left(\frac{\mathsf{π} \lambda}{2}\right)}{\varGamma^{\frac{(\lambda \div 1)}{2}} \lambda 2^{\frac{(\lambda-1)}{2}}}\right\}^{\frac{1}{\lambda}}$，通常λ取1.5；X_worst为全局最差位置；X_p为发现者最优位置。

在种群遇到危险时，麻雀个体逃生方式单一，并在更新位置时只考虑当前状态的最优解，没有考虑到剩余次优解，这会导致全部个体收敛于当前最优个体，如果当前最优个体非全局极值点，那么结果容易陷入局部解，所以引入GWO中的等级制度策略，选取前3个历史最优位置{X_α，X_β，X_δ}以得到潜在的最优解^[15]。改进后的警戒者位置更新公式为：

式中：γ是标准正态分布的随机数。

各头狼对应权重Z_i计算公式为：

采用灰狼等级体系后，SSA算法的搜索范围得到了扩展。然而，在个体向最佳解移动的过程中，其位置的更新依赖于当前最优解、次优解和第三优解的加权平均，这导致了更新结果的不确定性。为了确保算法能够有效收敛至最优解，借鉴了差分进化算法中的“贪婪”选择原则，仅使用当前具有最低代价的解来更新个体位置^[16]。当得到的更新位置X_new^t+1的适应度优于当前的位置，即f_new≤f_current时，新个体位置才被接受，否则个体的位置保持当前最优而不进行更新。位置更新函数为：

引入灰狼等级制度后，警戒者凭借类似α狼的主导地位，可利用其对全局最优解的较强感知能力，快速引导搜索向更有希望的区域靠近。β警戒者和δ警戒者依据与高等级警戒者的相对关系更新位置，能逐步细化搜索范围，避免盲目随机搜索。

以经典函数优化问题为例，如Rosenbrock函数、Rastrigin函数等，在相同初始条件下，引入灰狼等级制度的SSA更有可能在更少的迭代次数内接近全局最优值。

由于不同等级警戒者位置更新公式中的随机系数会导致种群聚集，所以引入动态随机因素避免算法过早收敛。当算法陷入局部最优“陷阱”时，这种随机变化促使警戒者打破现有束缚，探索新区域。

1) 设优化问题为求函数f_x的最小值，其中$ x \in \Omega \subseteq \mathbb{R}^d$，Ω为d维搜索空间，函数f_x存在全局最优解x^*。用$ X_n=\left\{x_n^1, x_n^2, \cdots, x_n^N\right\}$表示算法在第n次迭代时的种群状态，其中N为种群规模，x_nⁱ∈Ω为第n次迭代时第i个个体的位置。定义改进的麻雀算法中，受灰狼结构影响的警戒者引导下的个体位置更新公式为：

式中：o_n是与迭代次数相关的步长因子，由警戒者根据当前搜索情况调整，用于控制个体移动步长；Δx_nⁱ(ξ_n)是基于警戒者收集的环境信息ξ_n所确定的个体位置调整量，它反映了警戒者引导个体移动的方向和幅度，且ξ_n包含如当前搜索区域的适应度均值、方差，以及与历史最优区域的对比信息等，用于判断是否接近局部最优或全局最优趋势。

2) Lyapunov函数的选取

设计Lyapunov函数V_Xn为：

式中：$ \left\|x_n^i-x^*\right\|^2=\sum\limits_{i=1}^N \sum\limits_{j=1}^d\left(x_{n, j}^i-x_j^*\right)^2$表示第n次迭代时第i个个体与全局最优解的距离平方。显然，V_Xn≥0并且当且仅当所有个体位置都与全局最优解重合，即x_nⁱ=x^*对所有i=1，2，···，N成立时，V_Xn=0。

3) 计算V_Xn+1-V_Xn

首先将V_Xn+1展开：

利用模的平方展开公式$ \|a+b\|^2=\|a\|^2+2 a^T b+\|b\|^2$ (这里$ a=x_n^i-x^*, b=o_n \cdot \varDelta x_n^i\left(\xi_n\right)$)，将上式进一步化简：

4) 基于警戒者行为的不等式推导

由于警戒者在算法中的作用是引导种群向全局最优解靠近并避免陷入局部最优，当警戒者正常发挥作用时：对于任意个体i，存在一个与警戒者决策相关的常数c₁≥0使得：

又因为警戒者引导个体趋向全局最优解，所以存在常数c₂≥0使得：

结合上述两个不等式对V_Xn+1-V_Xn进行缩放：

令C=N(2c₂·c₁+c₁²)，则有：

随着迭代次数的增加，通过调整警戒者的相关参数，使得常数C逐渐减小趋近于零，那么根据Lyapunov稳定性理论，就有当$ n \rightarrow \infty$时，V_Xn→0，即种群中的个体越来越接近全局最优解，从而证明算法收敛。

为了验证混合灰狼结构的麻雀搜索算法(GWO Hang and SSA，GWHASSA)的收敛精度，本文将对改进麻雀搜索算法(Improved Sparrow Search Algorithm，ISSA)^[17]、GWO^[18]、鲸鱼算法(Whale Optimization Algorithm，WOA)^[19]、PSO^[20]和鹦鹉优化算法(Parrot Optimization，PO)^[21]进行基准函数的测试，各个测试函数的维度如表 1所示。

将这6种群优化算法进行极值寻优测试。为了保证实验的客观性，设置所有算法种群个数均为30，迭代次数为1 000次，试验在同一环境下独立运行30次。得到的均值、标准差和最优值如表 2所示。

在表 1的11组测试函数中，F₁-F₇是单峰测试函数，可以用来测试算法的全局搜索能力。对于F₆的求解，虽然GWHASSA在求解最优值时不能稳定收敛，但收敛效果和收敛精度都优于其他对比算法。其中F₅函数的全局最优解较难求解，大部分优化算法很难找到全局最优解，而GWHASSA在求解时明显优于其他算法。相较于ISSA，GWHASSA在寻优效果和全局寻优能力方面均有所提高。

F₈-F₁₁为多模态的基准测试函数，多峰测试函数主要用于测试算法的探索能力。从表 2中的测试结果可以分析得出。在求解F₈时，由于该函数是一个多峰、连续、可导(除了零点外)、非线性、无约束的多维函数，求解难度较高，存在许多局部最优解，PO能够在搜索空间中更均匀地分布个体，从而增加了找到全局最优解的可能性。ISSA的位置更新方式相对简单，在局部搜索阶段，算法在局部最优解附近徘徊，难以进一步逼近全局最优解，改进后的GWHASSA算法在很大程度上弥补了该缺陷，在实际应用时影响较小。6种算法对于该测试函数寻优时均未达到理想效果，统计结果表明，GWHASSA整体寻优能力优于WOA、PSO、GWO、ISSA及PO。

为了比较6种算法的收敛效果和稳定性，本文还对6种算法进行了仿真对比，列出了F₁、F₃、F₅、F₈、F₁₀、F₁₁ 6个测试函数的迭代收敛曲线，结果如图 2所示。

图 2为各算法收敛曲线图，GWHASSA的收敛速度和精度整体上优于WOA、PSO、GWO、ISSA及PO 5种算法。相较于之前改进的ISSA算法，本文改进过的GWHASSA算法在寻优能力和全局搜索方面都有所提高。

路径规划问题是机器人领域目前比较受关注的一类研究问题，其目的是找到一条有效又简单的路径。随着近年来越来越多的群智能优化算法的提出和改进，研究者们将群智能优化算法应用到路径规划问题当中，并且取得了一定的效果。为了验证GWHASSA在解决实际工程问题时的能力，本文将GWHASSA、WOA、PSO、GWO、ISSA及PO 6种群智能优化算法应用到机器人路径规划的问题当中。

首先，将机器人的活动范围设置在二维平面空间内，然后使用栅格法来构建地图模型。其中，黑色的栅格表示空间中存在的障碍物，而白色的栅格则表示无障碍物可顺利通过的路径，路径规划问题的目的便是找到一条安全无碰撞并且高效的路径。为了仿真实验的顺利进行，把现实问题中不规则的障碍物全部填充满栅格。图 3便是栅格法生成的二维平面地图，其中包括障碍物较少的简单环境地图和障碍物较多的复杂环境地图。

在本次实验中，算法的种群数量均设置为30，迭代次数为100次，试验在同一环境下独立运行30次。实验统计结果如表 3所示。

如图 4所示，红色路径为GWHASSA生成的路径，可以看出，无论是在简单地图还是复杂地图，本文算法所生成的路径比其他5种算法更短，且路径的拐点相对较少，生成的路径也更加平滑，说明本文算法有效提高了原算法的全局搜索能力，能够在各种环境中寻找到更优的路径。

从表 3的实验数据能够得出GWHASSA在简单地图中与WOA和ISSA算法具有相同的最短路径，且小于GWO、PSO和PO算法的最短路径。但是就平均值而言，在30次实验中GWHASSA的平均路径长度为21.084 2，小于其他算法，在标准差方面也优于其他5种算法。而在复杂地图中GWHASSA生成的最短路径为47.073 2，平均路径长度为49.817 3，相比其他5种算法，GWHASSA都表现出一定的优势，且标准差也明显优于其他算法。实验表明，本文提出的GWHASSA有较好的稳定性和鲁棒性。

GWHASSA良好的性能来自本文所提出的5种改进策略，其中包括佳点集初始化种群、比例自适应变化、通过动态惯性权重改进发现者、通过Levy飞行策略改进跟随者和通过灰狼等级制度改进警戒者。图 4和图 5也验证了改进的有效性和GWHASSA算法的良好性能。总之，相比于其他几种群智能优化算法，GWHASSA在寻优效果上效果显著，且表现出良好的收敛性和稳定性。

针对SSA的缺陷，进行了多重算法的融合，并且分析了算法的收敛性。对改进算法进行了函数测试，收敛曲线和平均值、标准差分析结果均表明GWHASSA在稳定性和精度上有了很大提升。在后续的机器人路径规划问题中GWHASSA的优势得到进一步体现，但目前只在静态环境中进行了测试，还无法适应复杂的动态环境。