一种用于DGPS 整周模糊度解算的混合策略麻雀搜索算法∗

霍 刚，尚俊娜

(杭州电子科技大学通信工程学院，浙江 杭州 310018)

差分全球定位系统(Differential Global Position System，DGPS)是利用已知精确三维坐标的差分GPS 基准站，求得伪距修正量或位置修正量，将此修正量发送给监测站，监测站使用接收的基准站修正量进行误差修正，从而提高GPS 定位精度。差分GPS 根据差分GPS 基准站发送的差分校正目标参量分为位置差分、伪距差分和载波相位差分。在采用载波相位差分测量时，整周模糊度的确定是核心问题。整周模糊度是指在测量中，基准站与监测站的载波相位观测值作差，其差值是载波波长中的小数部分长度，但是其载波波长的整数部分是个未知数，此未知数即为整周模糊度。通常整周模糊度求解步骤如下:首先利用最小二乘法得到模糊度的浮点解和协方差矩阵；其次对模糊度浮点解和协方差阵进行去相关处理降低模糊度间的相关性，然后构建模糊度搜索空间；最后通过LAMBDA 算法、麻雀搜索算法、混合策略麻雀搜索算法等方法搜索整周模糊度固定解[1－3]。本文引入混合策略麻雀搜索算法求解整周模糊度。

麻雀搜索算法(Sparrow Search Algorithm，SSA)是近年来提出的一种新型群体智能优化算法，被成功应用于各个行业当中[4－5]。该算法主要受麻雀日常的觅食行为启发，在实际应用中具有局部搜索能力强、所需调节参数少等特点。然而在搜索过程中，种群多样性减少，易陷入局部最优，全局搜索能力弱。为提升麻雀搜索算法的寻优性能，国内外学者对其算法的改进进行了研究。张晓萌等[6]在前人研究的基础上，对麻雀搜索算法进行了优化和完善，借助于正弦搜索方法来提升算法的局部检索能力，甚至还融入了生物种群聚集的相关概念和规律，促使算法的检索功能更为强大。此外，段玉先等[7]则将Sobel 理念与麻雀搜索算法相结合，并通过纵横交叉策略来改善算法的全局检索能力，扩大了算法的适用范围。

SSA 具有较快的收敛速度与求解精度，在面对解空间较大的高维问题时也有良好表现，但其全局搜索能力不足、易于陷入局部最优，因此本文提出一种混合策略麻雀搜索算法(Hybrid Strategy Sparrow Search Algorithm，HSSSA)。改进算法引入Circle 混沌映射进行种群初始化，提高初始种群的多样性，改善全局搜索能力[8]。引入粒子群算法(PSO)中粒子移动时的速度策略，加强麻雀种群每一代之间的联系，加强个体间的信息交流，增强算法的寻优能力。引入高斯变异策略对最优麻雀个体进行扰动，改善算法易陷入局部最优的问题，有效增强了算法的适用性[9]。选取9 个基准函数对HSSSA 算法的性能与SSA 算法、PSO 算法、GWO 算法和其他文献改进麻雀搜索算法的性能进行对比，进而验证HSSSA 算法的优越性。通过应用HSSSA 算法于DGPS 整周模糊度的解算当中，进一步验证了HSSSA 算法的有效性和可行性。

1 麻雀搜索算法基本原理

麻雀搜索算法(SSA)是在麻雀觅食的行为规律基础上经过创新而得到的一种检索算法。在数据检索中，该算法就像麻雀觅食一样来探寻有效数据样本，同时还具备一定的预警功能。SSA 将麻雀种群分为发现者和跟随者，同时加入警戒者机制，随机选取一定数量的警戒者。

1.1 更新发现者位置

种群中的发现者作为整个种群中的觅食引导者，引导跟随者向食物的方向靠近。一旦发现有捕猎者靠近，即预警值大于安全值，将会带领种群朝安全地区前进。其位置更新公式如下:

式中:t代表当前迭代次数，j是每个个体的维度，j＝1，2，3，…，N。MaxIter 是一个常数，是全局检索过程中最大的迭代次数。Xi，j表示第i个发现者在第j维中的位置信息，Q是服从标准正态分布的随机数，L是一个1×N的全1 矩阵。α∈(0，1]是一个随机数。R2(R2∈[0，1])和ST(ST∈[0.5，1])分别表示预警值和安全值。在本文中，R2是一个随机值，ST 是一个固定值。

1.2 更新跟随者位置

跟随者根据发现者提供的信息时刻进行觅食来获取更高的适应度。此外，在算法工作的过程中，两者是可以相互转换的，但种群的规模是维持不变的。跟随者位置更新公式如下:

1.3 更新警戒者位置

警戒者会随时侦查环境，警戒周围环境所发生的变化。如果发现捕食者的踪迹，会第一时间发出警示，位于边缘的个体会朝着安全区移动，而原本就位于安全位置的个体则会在个体附近移动。警戒者的数量一般占据整个种群的10%～20%。警戒者位置更新公式如下:

式中:Xbest是当前的全局最优觅食位置；fi是当前麻雀个体的适应度值，fg和fw分别是当前全局最佳和最差的适应度值；β和K均为步长控制参数，β服从标准正态分布，K∈[－1，1]的一个随机数；ε是最小的常数。

1.4 SSA 搜索流程

SSA 搜索流程如算法1 所示。

算法1 SSA

2 混合策略麻雀搜索算法

针对SSA 在求解过程中出现的种群多样性减少、全局搜索能力弱以及易陷入局部最优等问题，提出了一种混合策略麻雀搜索算法(HSSSA)。首先，引入Circle 混沌映射策略进行种群初始化，增强初始种群的多样性；其次，引入粒子群算法(PSO)中粒子速度策略对发现者位置更新公式进行改进，增强算法的寻优能力；最后，引入高斯变异策略对最优个体进行变异以生成新个体，增强跳出局部最优的能力。

2.1 HSSSA 算法

HSSSA 搜索流程如算法2 所示。

算法2 HSSSA

2.2 基于Circle 混沌映射策略的种群初始化

麻雀搜索算法采用随机生成的方式对种群初始化，所以导致初始种群容易出现聚集现象，且初始种群在空间内覆盖不均匀，个体之间差异性较大，给之后的迭代寻优带来极大的负面影响。由于混沌映射具有随机性、遍历性和规律性等优点，因此通过引入混沌映射完成种群初始化，其主要思想是利用混沌的特性，将变量映射到混沌变量空间的取值区间内，最后将解线性地转化到优化变量空间。考虑到各项映射方法的特点，本文采用Circle 混沌映射对麻雀种群进行初始化，其表达式如下:

式中:a＝0.5，b＝0.2，k表示维度。

将随机生成和Circle 混沌映射的初始化粒子做归一化处理，在[0，1]区间内生成粒子分布如图1所示。

图1 初始化粒子分布图

从图1(a)和图1(b)对比分析可知，利用Circle映射的粒子分布比随机生成的粒子分布在空间中更加均匀，扩大了麻雀种群在空间中的搜索范围，增强种群的多样性，进而增强算法的寻优能力，且能避免在最优解附近麻雀种群较少的情况[10]。

2.3 基于粒子速度策略的发现者位置更新

在SSA 算法中，当R2

粒子群算法(Particle Swarm Optimization，PSO)是根据鸟群捕食的行为研究提出的一种群智能算法。在PSO 算法中，各个粒子拥有两类属性，其一是粒子的坐标，其二则是粒子运动的速度。前者表示粒子在运动过程中的相对位置，而后者则表示运动的快慢。PSO 算法在工作过程中可以分为以下步骤:首先，每个粒子在搜索空间内进行局部检索，其次找到每个粒子的个体极值与当前全局最优粒子的个体极值，其中每个粒子的速度由当前粒子的个体极值与最优粒子的个体极值确定。

根据粒子群算法中的粒子速度策略，在混合策略麻雀搜索算法中，各个麻雀的位置即是粒子群算法中的粒子，每只麻雀移动的速度大小是根据自己的当前位置和当前全局最优麻雀位置进行调整计算，速度更新公式如下:

式中:w为惯性因子，在HSSSA 算法中，w是一个具有随机的周期性下降的常数，c1和c2为加速常数，一般取c1＝c2∈[0，4]，random(0，1)表示区间[0，1]上的随机数。Pi，j表示第i个变量的个体极值的第j维，Pg，j表示全局最优解的第j维，Vti，j表示第i个变量第j维的速度值。

经过完善之后的发现者位置更新公式如下:

经过优化完善之后，每一只麻雀的行动会先跟最优麻雀位置参照对比，在最优解的基础上来明确行进的方向，这样就能够解决各次迭代缺少信息交流的问题，提高数据迭代的精准性。并且由于惯性因子w的存在，麻雀个体的移动在一定程度上受到上一代种群个体的影响，加强了每一代种群之间的联系。另一方面，PSO 速度策略的引用，在一定程度上扩大了搜索空间，在式(6)中，速度对发现者的影响随着迭代次数的增加不断减小，以保证在迭代中搜索空间不会一直增大。

同时，在SSA 算法的警戒者更新公式中，若该麻雀个体不是处于当前最优觅食位置时，它会跳跃至当前的最优麻雀位置附近，由于该操作会导致SSA 算法易于陷入局部最优，因此对警戒者更新公式做如下修改:

式中:β为标准正态分布随机数；Xbest和Xworst分别是当前的全局最优觅食位置和全局最差觅食位置。

2.4 基于高斯变异策略的最优个体位置更新

最初的SSA 算法中，最优个体的位置更新依赖于种群的更新，即每次迭代完成后，由当前种群内适应度最好的个体作为新的最优个体，算法没有主动对最优个体进行扰动。如果最优个体陷入局部极值空间，会导致算法陷入局部最优的泥淖中。因此，为了增强算法跳出局部最优能力，本文使用高斯变异策略，对当前适应度最好的个体进行变异，与变异前的位置进行比较，选择较优的位置进入下一代，具体公式为:

2.5 HSSSA 的时间复杂度分析

时间复杂度能够直观地反应一个算法的性能，假设麻雀算法的种群规模参数和解空间维度参数分别为N和D，目标函数求解所需要的执行时间为f(D)，根据文献[11]知基本麻雀算法的时间复杂度为:

在HSSSA 算法中，参数初始化执行时间为t0，按照式(6)生成初始种群所需时间为t1，则算法在初始化麻雀种群阶段的时间复杂度为:

麻雀算法的发现者与警戒者比例分别是SD 与PD，则麻雀种群中，发现者数量为SD×N，警戒者数量为PD×N，跟随者数量为(1－SD)×N。

在更新发现者阶段，速度更新所需时间为t2，则该阶段的时间复杂度为:

在更新跟随者位置阶段和更新警戒者阶段，HSSSA 算法与麻雀算法的时间复杂度相同，均为O(D)，其时间复杂度为:

在高斯变异扰动阶段，生成高斯变异随机变量所需要的时间为t3，按照式(10)更新高斯变异所需时间为t4，则此阶段时间复杂度为:

综上所述，HSSSA 在最大迭代次数为MaxIter的情况下，其时间复杂度为:

由此可见，HSSSA 算法与SSA 算法的时间复杂度相同。

3 混合策略麻雀搜索算法求解整周模糊度

在DGPS 的载波相位差分定位中，原始伪距、载波相位值经过单差、双差处理后，使用最小二乘法可以得到整周模糊度浮点解，即整周模糊度中未固定的解。但整周模糊度的不固定会对测量结果造成分米级甚至米级的误差，例如GPS 卫星中的L1 载波，其频率为1 575.42 MHz，波长为0.190 3 m，这代表1 个整周波长对测量结果的影响是0.190 3 m。因此采用混合策略麻雀搜索算法来求解整周模糊度固定解。

表1 基准测试函数

利用HSSSA 找出样本数据中的最优解，首先要明确搜索的最佳检索范围，这个范围并不是随意确定的，不仅需要缩小检索的范围，提高检索效率，同时还必须含有系统的最优解。对此，检索空间表示如下:

式中:[Ni]为浮点解N在第i维的整数取值，m为搜索空间的大小，计算公式为m＝｜1/λ｜，例如，L1 载波，波长为19.03 cm，则m＝｜1/λ｜＝6。因此，HSSSA 算法的上下界可由式(15)确定为lb＝[Ni]－6，ub＝[Ni]＋6。

搜索空间确定后，HSSSA 算法还需确定每只麻雀的适应度值，在搜索整周模糊度固定解问题中，其适应度函数的表达式为:

式中:Ni表示为浮点解矩阵，QN表示为协方差矩阵，N为麻雀每次搜索得到的一组整数。

至此，混合策略麻雀搜索算法确定整周模糊度工作步骤具体可以参见图2。首先，算法的输入值是经过一系列预处理之后的浮点解，接着将这部分数值进行HSSSA 搜索，最终可以得到整周模糊度固定解[12－13]。

图2 混合策略麻雀搜索算法搜索整周模糊度流程

4 仿真实验结果与验证

4.1 仿真实验与结果分析

4.1.1 基准测试函数说明和算法参数设置

本次实验选取9 个基准测试函数对HSSSA 算法的性能进行对比测试检验，基准测试函数的具体信息如表1 所示。

选取麻雀搜索算法(SSA)、粒子群算法(PSO)[14]、灰狼算法(GWO)[15]、融合柯西变异和反向学习的改进麻雀算法(ISSA1)[11]、基于Sobol 序列和纵横交叉策略的麻雀搜索算法(SSASC)、基于萤火虫改进麻雀搜索的算法(ISSA2)及混合策略麻雀搜索算法(HSSSA)进行寻优对比。表2 是每个算法的参数设置。七种算法的种群规模为120，最大迭代次数30，为降低实验结果的统计误差，每种算法独立运行50 次，每种算法达到最大迭代次数后停止迭代，并输出最优解。表3 是50 次独立实验每种算法求解各测试函数的最优解(Best)、最差值(Worst)、平均值(Mean)和标准差(Std)。

表2 算法参数设置

表3 基准测试函数优化对比

4.1.2 仿真结果分析

从表3 分析可知，HSSSA 算法的统计结果在9个基准测试函数的求优实验中明显优于其他六种算法。在单峰函数f1、f2、f3、f4的实验中，HSSSA 能够稳定地找到其理论最优解，寻优效果远超SSA、PSO、GWO、SSASC、ISSA1、ISSA2；在单峰函数f5的实验中，七种算法都不能找到理论最优解，但HSSSA 算法的寻优结果优于其他六种对比算法；在多峰函数f6、f7的实验中，SSA、SSASC、ISSA1、ISSA2以及HSSSA 都能稳定地寻找到其理论最优解，说明了该算法本身的优越性；在多峰函数f8的实验中，七种算法都不能找到其理论最优解，但HSSSA 在最优值、平均值和标准差上相比于其他算法有较大的提升；在低维多峰函数f9的实验中，HSSSA 和ISSA1可以找到最优值，但HSSSA 算法的平均值、标准差优于ISSA1，且寻优效果达到100%。

通过上述分析可知，对于五种单峰函数的测试，HSSSA 算法的寻优效果优于其他六种算法，说明HSSSA 算法收敛效率优于其他六种算法；其次，对于四种多峰函数的测试，HSSSA 算法的寻优效果优于其他六种算法，说明HSSSA 算法具有良好的跳出局部最优的能力。

为了更加直观地说明HSSSA 有着更好的寻优精度以及收敛速度，图3 给出各个算法优化测试函数的收敛曲线对比，图3 中横坐标为迭代次数，纵坐标为适应度值。

图3 9 个基准测试函数的寻优实验收敛曲线

从图3 可以看出，对于9 个基准测试函数在相同的收敛精度下，HSSSA 所需迭代次数最少，其收敛速度优于其他六种对比算法。在相同的寻优次数下，HSSSA 的求解精度高于其他六种对比算法的求解精度。至此，HSSSA 的可行性和有效性得以证明。

4.2 实测结果与分析

本次实验以现场测试来了解改进后算法的性能，具体试验图可以参见图4。在图中，整个测试系统包含两个天线模组，数据的接收模块能够处理多种类型的数据，并输出伪距、载波相位等数据。计算机对接收到的数据进行处理，使用传统LAMBDA 算法、麻雀搜索算法(SSA)、融合柯西变异和反向学习的改进麻雀算法(ISSA1)和混合策略麻雀搜索算法(HSSSA)进行整周模糊度解算。本实验一共观测了7 200 个历元，选取其中3 000 个历元进行解算。表4 所示是每个算法的参数设置，所有算法的种群规模为120，最大迭代次数为30，对四个算法的成功率和解算时间进行了对比，如表5 所示。

表4 算法参数设置

表5 四种算法解算结果对比

图4 现场测试图

从表5 分析可知，本文提出的HSSSA 算法在解算整周模糊度的性能上有一定的提升，在解算时间上，HSSSA 与LAMBDA 算法接近，略慢于SSA，优于ISSA1；其成功率优于其他三种算法，其中，HSSSA的成功率比LAMBDA 算法高3.34%，比SSA 高20.6%，比ISSA1 高1.6%。

5 结论

针对SSA 在求解过程中出现的种群多样性减少、全局搜索能力弱以及易陷入局部最优的问题，本文创新性地提出了一种混合策略麻雀搜索算法。首先，引入Circle 混沌映射提高样本初始种群的分布均匀度，增强种群多样性，提升算法的全局搜索能力；其次，引入粒子群算法中粒子速度策略，增强个体间的信息交流以及每一代种群之间的联系；最后借助于高斯变异策略丰富种群内部多样性，提高算法跳出局部最优的能力，从而提升算法的寻优精度。9 个基准测试函数的实验结果表明，与SSA 相比，HSSSA 具有更好的求解精度、寻优能力和收敛速度，验证了HSSSA 的改进效果。使用HSSSA 对整周模糊度解算中，通过与LAMBDA 算法、SSA 以及ISSA1 的对比，进一步验证了HSSSA 的有效性和应用可行性。