改进的PSO与ACO混合搜索GNSS整周模糊度算法

尚俊娜，王民顿，刘新华，王奕腾

（1. 杭州电子科技大学 通信工程学院，杭州 310018； 2. 通信信息控制和安全技术重点实验室，嘉兴 314033； 3. 中国电子科技集团公司第三十六研究所，嘉兴 314033）

在全球卫星导航系统（Global Navigation Satellite Systems, GNSS）的高精度测姿过程中，确定整周模糊度至关重要。因为如果整周模糊度被准确锚定下来，就可以实现米级定位结果的改善，更有甚者能达到厘米级、毫米级。不能直接求解整周模糊度，因为它涵盖从实数域到整数域的非线性映射，而是选择浮点解的相应整数解集作为样本，最后通过搜索算法寻求真解。

因此整周模糊度的搜索往往取决于算法的质量。文献[1]中应用蚁群算法在整周模糊度空间内寻优，结果表明在样本数较少的情况下获得了很好的搜索结果，并较其他遗传算法更为可靠。文献[2]中利用改进粒子群算法搜索固定解，和经典搜索算法LAMBDA的1000 个历元实验对比，证明了搜索效率要明显优于LAMBDA 算法。

本文在单算法的基础上提出改进粒子群与蚁群混合算法，首先对传统粒子群和蚁群算法进行了适用于GNSS 整周模糊度搜索的改进，再凭借改进粒子群算法高效率的优势快速得到次优解，最后利用改进蚁群算法高可靠性的优势得到最优解。混合算法不仅可以兼具两种算法的优势，而且可以弥补它们的劣势。

1 传统粒子群与蚁群算法

1.1 粒子群算法

粒子群算法（ Particle Swarm Optimization Algorithm, PSO）是一例基于群智能方法的演化计算算法，它是由Eberhart 和Kennedy 受鸟、鱼类群体行为方式启发而提出的。算法的目的是指导下一步迭代位置，其原理是对粒子的当前位置、个体极值（pbest）和全局极值（gbest）的联合计算。该算法适用于解决一些连续函数的优化问题[3,4]。

粒子群常规算法中，粒子的速率和位置变化方程为：

式中： i= 1,2… n ，d= 1,2… D ，w 是惯性权值，c1和 c2是自我认知因子和社会认知因子， r1和 r2是[0,1]区间上的随机数。

1.2 蚁群算法

蚁群算法（Ant Colony Optimization Algorithm, ACO）是以确定最优路径为目的的一种机率型算法，它是由Marco Dorigo 受蚂蚁觅食过程中路径确定的行为方式启发而提出的。算法的本质是利用蚁群在其历史路径上余留的信息素去指导其他蚂蚁寻找食物。该算法适用于解决离散优化问题[5,6]。

在传统算法中，时间t 任意给定，蚂蚁k 从现处位置i 到下一个位置点j 的状态转移概率定义为：

式中：α 、β 分别用来调节信息素及启发式信息所起作用的相对程度，allowedk为蚂蚁k 下一步可以选择的路径的数组， τij( t )为节点i 和j 之间的信息素浓度， nij（ t ）为蚂蚁k 从节点i 到节点j 的启发信息。

在初期搜索时，每条路径上具备相同起始条件的信息素，蚁群进行盲目搜索。每次蚂蚁集体寻找食物完毕，都将更新所有路径下的信息素状况

式中：ρ 为信息素挥发因子，且0＜ ρ＜ 1，m 为蚂蚁数量，为蚂蚁k 在路径(i,j)的信息素，可表示为：

式中：Q 为常数， Lk为蚂蚁k 在这次循环中经过的总路径长度，在整周模糊度搜索中将替换成目标函数 J （ N ）：

2 改进的粒子群与蚁群混合算法

2.1 搜索空间的确定

GNSS 搜寻整周模糊度过程中首先要确定的就是搜索空间。在GNSS 短基线解算过程中，在已知基线尺寸的前提下基于GPS 干涉仪测姿原理确定搜索空间。基线设定长度为L 米，双差整周模糊度的初始取值范围为：

式中：λ 表示卫星载波波长，[ ]为取整。

2.2 粒子群算法权重的改进

在粒子群算法内，文献[7]指出惯性权重w 是能代表粒子的搜索能力，权重越大时下一步探索能力越强，适用于全局搜索，反之则适合局部搜索。因此可以通过对w 值的调整实现对全局搜索和局部搜索能力的权衡。在混合算法中，粒子群算法主要起到快速寻找次优解的作用，因此可在迭代初期适当加大w 值，从而达到加快向全局最优解聚集的效果。采用一种惯性权重递减策略，它是基于sin 函数并已在室内定位中起到很好效果[8]。

式中：k 是指算法当前的迭代次数， kmax是算法最大迭代次数， wmax是最大的惯性权重， wmin是最小的惯性权重。

2.3 蚁群算法选择概率的改进

传统蚁群算法在整周模糊度解算过程中，不可避免地存在着易陷入局部最优、收敛速率慢的问题，因此对选择概率进行改进，加入自反馈因子f ，通过仿真发现，其可以加快收敛速度和解决陷入局部极小时解无法继续进行的问题，选择概率改进为：

式中：传统蚁群系统中的ηij( t )改为适用于混合算 法的，m 为搜索空间的半径，f 为自反馈因子， 其表达式不固定，但必须满足条件：一是在最小目标函数值不断降低的情况下，不干预选择概率；二是在一定循环次数后最小目标函数值发生停滞时，逐渐降低信息素的作用，从而提高启发式信息作用；三是保存信息素的作用，不能使其降至0；四是若在自反馈因子作用一段时间后，最小目标函数值仍未降低，就将信息素作用程度立刻降至最低。本文选取的表达式为f =e(-g/4)，每次循环结束，根据目标函数值是否降低对g 做出相应调整：

2.4 混合算法的描述

改进的粒子群与蚁群混合算法(IPSOACO)首先根据GPS 干涉仪测姿原理建立搜索空间，然后使用改进PSO 快速找到一组次优解，根据式(5)(6)转化为改进ACO 初始信息增量，并根据式(11)得到改进ACO 的初始信息素分布，最后采用改进ACO 搜寻整周模糊度，以此得到最优解：

式中：τp为改进PSO 找到的次优解转化为的信息素增量，τa为混合前信息素初始分布，τi为改进ACO搜索前的信息素初始分布。

图1 IPSOACO 算法整体流程图Fig.1 Overall flow chart of IPSOACO algorithm

算法的具体实现步骤如下：

1)根据基线长度通过式(7)建立搜索空间；

2)初始化改进蚁群算法和改进粒子群算法；

3)运用改进粒子群算法，按照式(6)计算个体最优和全局最优目标函数；

4)达到迭代次数，生成次优解，并按式(5)(6)转化为信息素增量。否则转3)；

5)根据信息素增量按照式(11)生成改进蚁群算法的信息素初始分布；

6)根据式(9)计算蚂蚁的选择概率，根据概率移动蚂蚁达到搜索目的；

7)更新最小目标函数及其相应的整周模糊度；

8)达到迭代次数，输出最优解。否则转6)。

3 实验及分析

3.1 仿真分析

为了验证改进的粒子群与蚁群混合算法在整周模糊度搜索上的性能，与单算法进行对比仿真分析，主要参考的指标有2 个：搜索有效性和搜索可靠性。搜索有效性是指目标函数值能否在一定迭代次数内快速收敛于最优解；100 次重复实验中获取最优解的次数代表着搜索可靠性。借用文献[9]中的经典算例，降相关处理后的整周模糊度浮点解和协方差矩阵为：

粒子群和蚁群的种群数量均设置为10，其他主要参数设置如表1，由于协方差矩阵接近对角阵，说明降相关效果较好，最优解就在浮点解周围，为了更直接地看出仿真结果，不采用GPS 干涉仪测姿原理建立搜索空间，而是对浮点解进行取整并外扩4 个整数解作为搜索空间，因此搜索空间的大小为53。

表1 算法主要参数设置Tab.1 Main parameters setting of the algorithm

图2 是一次搜索中粒子群算法（PSO）、蚁群算法（ACO）和改进粒子群和蚁群混合算法（IPSOACO）的目标函数值变化图，目标函数值越小说明所搜索到的整数解与最优解越接近，并可根据式(6)计算出最优解对应的最小目标函数值为0.2183，同时给出本次搜索中三种算法最优解的演变过程。结合图2 和表2 可以看出PSO 算法收敛速率快，但陷入局部极小且最终并没有收敛于最优解；因为初始信息素的匮乏，ACO算法收敛较慢，在第19 次迭代后收敛于最优解；IPSOACO 算法相比于单算法而言就可以快速收敛于最优解，说明混合算法相较于单算法而言具有良好的搜索有效性。之后又重复进行了100 次搜索，结果如表3 所示，可以发现IPSOACO 算法搜索可靠性要明显优于单算法。

图2 目标函数值的变化Fig. 2 Change of objective function value

表2 三种算法最优解的演变Tab.2 evolution of optimal solution of three algorithms

表3 100 次搜索结果Tab.3 100 search results

与经典的LAMBDA 搜索算法同时进行1000 个历元的对比仿真实验，搜索结果如表4 所示。可以发现在成功率相差不大的情况下，IPSOACO 算法的搜索时间要明显优于LAMBDA 算法，主要是因为LAMBDA算法通常是从解空间的初始点搜索最优解，由于是从一个初始点开始的，所以容错率会很低，如果这个点选择不合理，就很容易产生搜索结果陷入局部最优解的问题；而IPSOACO 算法具有独特全局搜索特性，从一个包含多初始点的种群开始搜索最优解，所以理论上IPSOACO 算法的容错率比较高，其搜索效率也更高。

表4 两种算法搜索成功率和解算时间对比Tab.4 Comparison of search success rate and calculation time of two algorithms

3.2 实例验证

为了检验该混合算法在实际搜索中的性能，采用一组基线长度约为4 m 的GPS/BDS 实测数据，测试环境如图3 所示，采样频率为1 s，取中间连续100 s的实验数据做分析解算。首先对两个天线做单点定位，经过双差处理，借助加权最小二乘估计得到浮点解及其协方差矩阵，最后采用混合算法搜索双差后的整周模糊度，以固定的整周模糊度修正基线[10]。在搜索整周模糊度的过程中，参考卫星选取高度角最高的5 号卫星，与7 号、11 号、13 号及20 号卫星构成双差模糊度，搜索结果如图4 所示。

图3 测试环境Fig.3 Test environment

图4 双差整周模糊度解算结果Fig.4 Ambiguity resolution results of double difference integer

由于无法直接检验整周模糊度搜索结果，但基线的长度是已知的，因此采用基线解算结果反验搜索结果的方法。已知卫星L1 载波，其波长为0.1903 m，这也代表了模糊度 1 个整周对于基线的影响是0.1903 m，因此如果基线解算结果稳定且精度在其范围内，就可以暂定搜索结果无误。图5 为基线解算结果，可见三个方向的相对坐标解算结果都较为稳定。图6 为基线解算误差，这里的误差是指基线L 的误差， 其中误差的极差范围在0.1903 m 以内，并且通过计算其均方根误差，得到其精度为2.63 mm，由于它的影响远远小于一个整周误差，因此判定整周模糊度搜索无误，说明改进的混合算法可以很好地处理短基线解算中的整周模糊度搜索问题。

图5 基线解算结果Fig.5 Baseline solution results

图6 基线解算误差Fig.6 Baseline solution error

4 结 论

本文提出一种用于搜索GNSS 整周模糊度的新方法。首先在已知基线长情况下，基于GPS 干涉仪测姿原理确定搜索空间，然后使用改进粒子群算法快速搜索次优解，并以此来初始化改进蚁群算法的信息素分布，最后使用改进蚁群算法确定最优解。改进的混合算法理论上可以解决传统粒子群算法局部寻优能力差的问题，并且也可以弥补蚁群算法初始信息素匮乏的缺点。通过对经典算例的仿真，验证了改进的混合算法较单算法可以更快更可靠地收敛于最优解，且搜索效率要明显优于经典的LAMBDA 算法，并经实测数据检验，该算法可以很好地解决短基线解算中的整周模糊度搜索问题。在滑坡和钢架结构沉降监测方面有良好应用场景，降低了危险发生的可能性。但改进的混合算法还有很多地方需要深入探讨，比如在基线较长情况下会因搜索空间较大导致搜索效率低下等，都是本文需要进一步研究的问题。