基于改进蝴蝶搜索算法的DGPS 整周模糊度快速解算

尚俊娜，罗照旺

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

在差分全球定位系统（Differential Global Positioning System,DGPS）定位方式中，载波相位观测值[1]是否能够达到厘米级甚至毫米级的定位结果，关键在于能否正确快速地解算出整周模糊度。通常解算整周模糊度的关键步骤为：首先通过最小二乘估计得到模糊度的浮点解[2]和协方差矩阵；其次，利用去相关操作处理协方差矩阵，从而降低模糊度间的相关性；最后通过搜索算法得到模糊度固定解[3-5]。

近年来，大量学者在模糊度解算方法上不断探索，在提高搜索效率和降低模糊度之间的相关性方面进行了研究，尤其在搜索算法方面采用了现代启发式算法。刘新华等[6]提出了一种改进蚁群算法（Improved Ant Colony Optimization,IACO），在传统蚁群算法的基础上引入自反馈因子，改善了传统蚁群的寻优性能，将整周模糊度解算成功率提升了3%。然而，蚁群算法容易缺乏初始信息素，从而导致模糊度解算时间较长。欧阳利等[7]提出了一种基于短基线整周模糊度求解的改进鸡群优化算法（Improved Chicken Swarm Optimization,ICSO），对模糊度解算过程进行优化，提高了搜索速度和求解成功率，但是在基线不固定时或者在长基线环境下存在搜索空间变大、搜索效率下降和模糊度搜索速度变慢的问题。针对模糊度解算时间长、效率低的问题，张波等[8]提出了改进粒子群（Improved Particle Swarm Optimization,IPSO）的模糊度解算优化算法，通过引入sin 函数对惯性权重进行改进，缩短了模糊度解算时间。上述算法在模糊度解算问题上虽然取得了一定的性能提升，但现代启发式算法自身所固有的寻优精度不高、收敛速度慢、易于早熟收敛等问题还有待进一步解决，这使得在提高模糊度搜索效率和模糊度解算成功率等问题上仍然有进一步的优化空间。

为了提高模糊度固定解的搜索成功率，本文提出了一种改进的蝴蝶搜索算法（Improved Butterfly Optimization Algorithm,IBOA）来求解整周模糊度。首先，引入动态切换概率来权衡蝴蝶搜索算法（Butterfly Optimization Algorithm,BOA）中全局搜索和局部搜索的比例，从而提高全局搜索能力；其次，在BOA 算法的香味系数中加入一个自适应权重，在全局搜索和局部搜索阶段引入新的位置更新策略，不仅提升了全局寻优精度，还改善了跳出局部最优的能力；最后，通过实验对比IBOA 算法与LAMBDA 算法解算的整周模糊度。

1 载波相位模型分析

载波相位观测量是通过接收机捕获到的相位与自身生成的相位之差得到的，载波相位观测量的观测精度比伪距观测量更高，但其中包含着未知的整周模糊度，如何快速准确地求解这个未知数是实现高精度载波相位相对定位的关键所在。

1.1 模糊度最小二乘估计模型

在实现高精度载波相位相对定位时，通常对站星间载波相位双差观测方程进行处理[9]。假设接收机q和r同步观测卫星s和k，那么在接收机q和r之间求得单差观测值后，再在卫星s和k之间作差求得双差观测值，其方程为：

将式(1)进行载波相位双差模型线性化，其数学模型为：

其中，y为载波相位观测值；N为整周模糊度向量；b为两接收机之间的基线向量；A、B均为设计矩阵；ε为观测噪声；D(y)和Qy分别为观测量y的方差阵和协方差阵，是其单位先验方差。

在GPS 领域，一般采用最小二乘方法或Kalman滤波方法[10]求解式(2)。由于式(2)中不仅包含未知的实数参数，还包含未知的整数信息，因此，式(2)被称为混合整数模型[11]。通过最小二乘估计准则求解式(2)，有：

如果先不考虑整周模糊度N的整数特性，利用标准最小二乘方法来解算，可以得到整周模糊度N和基线向量b各自的浮点解及其协方差矩阵和：

在解算出N和b的浮点解后，再考虑整周模糊度的整数特性，式(3)可以进一步展开：

由于b为实数向量，所以当，且取最小值时取得最小值。因此，式(3)的最小问题就转化为：

1.2 模糊度降相关

由式(4)得到的N和b的浮点解存在非常强的相关性，若不采用降相关方法处理就直接进行整周模糊度的搜索，会造成模糊度搜索时间过长。为了获得更好的搜索效率，在搜索前需要先进行模糊度降相关操作。本文采用Z 变化[12]的降相关处理方法：

其中，z和Q分别为N和经整数变化后的向量，为经整数变化后的浮点解。注意的是，为保证N和z之间的变化是整数变换，z∊ Zn×1,Z∊Zn×n，Z和Z-1中的元素均为整数。

式(6)转换成一个新的整数最小二乘问题：

通过Z 变化降低协方差矩阵之间的相关性，这样能够减少一些搜索时间，由于Z 变化自身的运算量增加了模糊度解算的整体计算时间，因此，想进一步提升搜索效率，需要使用一个高效的搜索算法。

2 IBOA 算法求解整周模糊度

模糊度搜索的本质是在搜索空间中找到J(z)的最小值。为了进一步提升模糊度的搜索效率，本文提出了一种IBOA 算法进行模糊度搜索。BOA 算法是一种模拟觅食行为的新型优化技术[13-15]，蝶群中的每个蝴蝶通过感知其他蝴蝶散发出的香味进行位置更新，并且每个蝴蝶的位置是解空间中的一个解。

2.1 BOA 算法的基本原理

2.1.1 初始化种群位置

假设在一个D维搜索空间中，存在n只蝴蝶，第i只蝴蝶在D维空间中的位置为：

其中，1≤i≤n，1≤d≤D，xi,d是第i只蝴蝶在d维空间的位置。

为了更好地解算整周模糊度，搜索空间的边界条件可以设置为：

其中，Xmin和Xmax分别表示搜索空间的下限和上限。

蝴蝶Xi的第j维参数的初始化公式为：

其中，R是[0,1]之间的随机数。

蝴蝶在进行位置更新时，需要保证位置更新后的向量元素处于预先设定的搜索空间之内。若超出范围，则需要进行修正。修正方法为：

2.1.2 更新蝴蝶位置

蝴蝶位置更新分为两个阶段：在全局搜索阶段，蝴蝶个体会朝着产生香味最浓的蝴蝶进行位置更新；在局部搜索阶段，当蝴蝶个体感知不到其它蝴蝶的香味时，就会随机移动。在迭代阶段，为了控制全局搜索和局部搜索的占有比例，传统的BOA 算法采用一个切换概率p=0.8的固定值与每次迭代产生的一个随机数rand进行判断。如果rand＜p，则进行全局搜索；反之则进行局部搜索。蝴蝶的位置更新为：

其中，c表示感觉模态；α表示功率指数，反映蝴蝶香味吸收程度的变化。α和c的取值范围都在[0,1]之间。I表示刺激强度，在整周模糊度搜索[14,15]中将I替换成目标函数J(z)，其中z用蝴蝶位置Xi表示：

2.1.3 搜索空间的构建

BOA 算法寻优本质是在备选空间中搜索能够使目标函数J(Xi)取得最小值的一组解向量，所以搜索空间中必须包含正确的模糊度整数解。因此，在DGPS基线定位中可以利用基线长度构造搜索空间[16,17]。搜索空间为：

基线长度可以约束搜索空间，通过多次测量取平均值来减小基线长度的测量误差。例如1.0 m 长的基线，L1 载波波长为19.03 cm，则。其中，l为基线长度，[l/λ]表示向上取整。因此，边界条件确定为xmax,j=[zj]+6，xmin,j=[zj] -6。通过基线长度来约束搜索空间，一般基线长度测量误差比较小，如果出现基线长度测量误差大的情况，会造成搜索空间变大和候选值冗余的问题。因此，下文提出的IBOA算法搜索速度较快，即使搜索空间变大了，对解算效率影响很小。

2.2 IBOA 算法

在整周模糊度解算问题上传统的BOA 算法还存在很多问题，比如收敛速度慢和容易陷入局部最优值等。为了解决这些问题，本文从搜索策略上对传统BOA 算法进行改进，提出一种IBOA 算法。该算法引入非线性递减函数P改进切换概率，有效地平衡了全局搜索和局部搜索的比例，提升了算法的收敛性；引入自适应权重S对香味公式进行改进，增强算法的寻优能力。

2.2.1 动态切换概率策略

在BOA 算法中，采用了一个固定值切换概率p与每次迭代产生的一个随机数进行比较，从而实现全局搜索和局部搜索之间的切换比例。如果p的取值越大，进行全局搜索的概率就越大；反之，局部搜索的概率就越大。为了更有效地平衡全局搜索和局部搜索的比例，本文基于cos 函数的权重递减方法[18]对BOA算法的开关概率进行改进，改进后的开关概率P是一个递减函数，前期函数下降速度慢，后期函数下降速度快，保证了前期全局搜索可以充分进行，后期局部搜索也可以更好地二次精细寻优。

其中，t和Tmax分别为当前迭代次数和最大迭代次数。

2.2.2 自适应权重和新的位置更新策略

为了减小BOA 中香味系数fi,d的随机性和盲目性[19]，在香味系数fi,d中加入自适应权重S，使香味分布范围越来越小，算法能够越来越仔细地搜索。当搜索过程开始时，初始香味分布范围很大。随着迭代过程的进行，香味分布范围逐渐减小，保证了收敛速度和跳出局部极值点的能力。

新的香味系数fnew：

理想的寻优过程包括前期的高搜索能力和后期的高精度能力。对于全局搜索阶段，IBOA 算法通过调整全局最优位置g*与当前迭代的每个蝴蝶位置之间的差异来进行位置更新。因此，IBOA 算法使每个个体围绕当前迭代的最优位置有一个更加仔细和彻底的搜索机制。全局搜索阶段新的位置更新公式为：

对于局部搜索阶段，IBOA 算法使用每次迭代中最优位置g*和最差位置w*的平均值来更新每只蝴蝶的下一个位置，减少随机选择两只蝴蝶的盲目性。新的局部搜索阶段的位置更新公式为：

由于整周模糊度具有整数特性，IBOA 算法的位置更新公式需要进行四舍五入：

其中，round(∙)是四舍五入函数。

2.2.3 IBOA 算法的流程图

IBOA 算法的流程如图1 所示，输入值为经过Z变化后的浮点解和协方差矩阵Q，通过IBOA 算法搜索后输出整周模糊度固定解。

图1 IBOA 算法搜索流程图Fig.1 Flow chart of the search of the IBOA algorithm

3 实验与结果分析

3.1 仿真实验

为了验证IBOA 算法解算整周模糊度的性能，利用最小二乘估计得到模糊度浮点解和协方差矩阵，如式(25)所示，再根据经典算例[20]进行仿真处理。

为了有更好的搜索效率，在搜索前先进行降相关处理和矩阵变化，即对进行 Z 变化（z=ZTN），运算步骤及结果为和经过处理后的浮点解和协方差为：

为了验证IBOA 算法的有效性，与IACO 算法、ICSO 算法、IPSO 算法和传统BOA 算法进行对比。将降相关处理后的数据进行整周模糊度解算，五种算法的种群数量都为80，最大迭代次数Tmax=30。表1 为五种算法的参数设置，图2 是以J(Xi)为目标函数的五种算法解算整周模糊度的收敛过程，表2 是五种算法的最优解演变过程。

表1 五种算法参数设置Tab.1 Parameter setting of five algorithms

表2 最优解的演变Tab.2 Evolution of the optimal solution

图2 五种算法的收敛曲线Fig.2 Convergence curves of five algorithms

从图2 可知，在解算整周模糊度的收敛过程中，BOA 算法在第9 次迭代时进入局部最优，在第15 次迭代时才跳出，最后仍然没有达到最优解。IPSO 算法在第18 次迭代时达到最优解，目标函数值J(Xi)达到最小，不再变化；ICSO 算法在第19 次迭代时达到最优解，目标函数值J(Xi)达到最小，不再变化；IACO 在第15 次迭代时达到最优解，目标函数值J(Xi)达到最小，不再变化；IBOA 算法在第5 次迭代时就达到最优解，目标函数值J(Xi)达到最小，且不再发生变化。IPSO、ICSO、IACO 和IBOA 算法都能够寻到最优解，但是IBOA 收敛效果比其他三种算法要好。此外，IBOA 算法具有不错的全局寻优能力，解决了BOA 算法无法跳出局部最优的问题，进一步提升了整周模糊度解算的效率。表2 的最优解演变过程证明了IBOA 算法求解整周模糊度固定解的有效性。

3.2 实验分析

本文实验分为两次测试：第一次测试使用武汉大学IGS（International GPS service for Geodynamics）数据中心下载的观测值文件进行测试，第二次测试是在苏州市科技城中科地理信息产业园进行。由于两次测试的数据量不同，为了方便进行比较，统一从各自数据量中按顺序选取其中1000 个历元进行解算。

武汉大学IGS 数据中心是由国际地球动力学服务机构组织授权建立，可免费下载国际IGS 基准站观测数据、GNSS 卫星精密轨道和精密误差等数据服务。本次测试数据来自香港基站hkws 和hksl，其中hkws基站作为流动站，hksl 基站作为基准站，基线长度为42.7 km。下载两个基站同一天的数据文件，使用RTKLIB（Real-Time Kinematic Library）程序进行数据解析。采用传统LAMBDA、BOA、IPSO、ICSO、IACO和IBOA 算法进行整周模糊度解算，一天的数据总计2347 历元，选取其中1000 个历元进行解算，对六种算法的成功率和解算时间进行对比，如表3 所示。

表3 六种算法解算结果Tab.3 Solution results of six algorithms

第二次测试的实验数据是使用两个GPS/BDS 双模天线进行不同距离的短基线解算，基线长度分别为0.43 m 和3.45 m，可以从接收模块中得到载波相位和伪距等数据，然后利用串口把数据传输给计算机，最后在MATLAB 上运行六种算法程序进行整周模糊度解算。实验总共采集了两次数据，第一次采集的是GPS数据，总共观测了3875 个历元；第二次采集的是BDS数据，总共观测了3627 个历元。两次数据都取前1000个历元进行解算，表4 和表5 是六种算法分别使用GPS 和BDS 数据的解算结果。

表4 六种算法使用GPS数据的解算结果Tab.4 Solution results of six algorithms using GPS data

表5 六种算法使用BDS数据的解算结果Tab.5 Solution results of six algorithms using BDS data

由表3～表5 可知，长基线的解算成功率比短基线的低很多，因为基线长度的增加使得模糊度范围增大，导致解算成功率降低。本文提出的IBOA 算法在解算整周模糊度的性能上依然有一定的提升，解算时间比LAMBDA、IPSO、ICSO 和IACO 四种算法都要快，成功率也优于其他五种算法。其中，IBOA 算法成功率比LAMBDA 算法平均高5.07%，比IPSO 算法平均高5.77%，比ICSO 算法平均高4.90%，比BOA 算法平均高24.13%，比IACO 算法平均高3.37%。虽然BOA算法解算平均时间在六种算法中最少，但其解算成功率在六种算法中最低。IBOA 算法在GPS 和BDS 双模模糊度解算结果上比较接近，因此将IBOA 算法应用于整周模糊度解算，在理论研究和实际应用上都有很大的优势，适用于GPS 差分和BDS 差分。

4 结论

本文主要研究了IBOA 算法在DGPS 整周模糊度求解中的应用。首先，采用动态切换概率平衡全局搜索和局部搜索的比例，改善了传统BOA 算法搜索能力弱的缺点；其次，引入自适应权重使香味分布因子范围越来越小，同时通过调整最优解与每个解之间的差值来更新位置，改善了传统BOA 算法易于陷入局部最优的问题；最后，采用IBOA 算法求解整周模糊度固定解。仿真结果表明，IBOA 算法比BOA、IPSO、ICSO 和IACO 算法的收敛速度更快、效果更好。实验结果表明IBOA 算法的解算成功率更高，也进一步验证了IBOA 算法在GPS 和BDS 双模模糊度固定中的有效性和应用可行性。