改进粒子群优化的卫星导航选星算法

王尔申，孙彩苗，黄煜峰，李轩，别玉霞，曲萍萍

（1.沈阳航空航天大学 电子信息工程学院，沈阳110136；2.沈阳航空航天大学 辽宁省通用航空重点实验室，沈阳110136）

全球导航卫星系统（Global Navigation Satellite Systems，GNSS）不断发展和日益完善［1］，可用于导航的卫星增多，为了获得更优的几何结构和更多的导航信号，多星座组合导航成为导航技术发展趋势［2］。然而，如果利用全部可见卫星进行定位，不仅增加接收机信号处理负担，更为重要的是，当可见卫星达到一定数量时，几何精度因子（Geometric Dilution of Precision，GDOP）将不会有明显的改善。因此，研究选星算法，在保证定位精度的前提下，从全部可见卫星中选取较优的一组用于定位是必要的。

大部分的选星算法主要是基于衡量定位精度的GDOP，GDOP与用户的几何结构有关，GDOP越小，定位精度越高。基于GDOP的选星算法主要有Bo和Shao［3］研究的加权几何精度（WGDOP）法、Phatak［4］研究的矩阵求逆引理法；也有学者研究了基于遗传算法通过模拟生物进化的方式实现选星［5］。这些算法都在不同程度上减少了选星的计算量。有学者提出一种顾及观测质量的三维凸包选星思路［6］；Liu等［7］提出了一种基于模糊度精度因子（Ambiguity Dilution of Precision，ADOP）的快速卫星选择策略，在一定程度上减轻了接收机的计算负担；也有学者提出一种基于3星子集的GPS快速选星算法，可以有效降低星座突变时由星座选择带来的时间消耗［8］。类似遗传算法，粒子群优化（Particle Swarm Optimization，PSO）算法是一种智能寻优算法［9］，但是该算法在寻优过程中容易陷入局部最优导致寻优结果不准确［10］，为克服这一问题，利用人工鱼群算法（Artificial Fish Swarm Algorithm，AFSA）的全局收敛特性，与PSO算法结合，提高PSO算法的全局收敛能力［11］。

本文基于人工鱼群算法的粒子群优化（Artificial Fish Swarm Algorithm-Particle Swarm Optimization，AFSA-PSO）算法引入到选星过程中，并将得到的结果与标准的PSO选星算法结果对比，验证了AFSA-PSO选星算法的性能。

1 AFSA-PSO算法

AFSA-PSO算法包含标准的PSO算法和AFSA算法的聚群和追尾行为。标准的PSO算法是模仿鸟类觅食行为的一种智能寻优算法［12］，该算法将每个个体看作是空间中一个没有质量和体积的粒子，每个粒子在搜索空间以一定的移动速度改变自身位置，根据自身和集体的寻优经验动态调节自身的移动速度。

每个粒子为d-维空间中的一个点，第k个粒子的位置可以表示为xk=［xk1，xk2，…，xkd］，xk1，xk2，…，xkd分别表示第k个粒子在d-维空间中的位置分量；第k个粒子位置的变化速度可以表示为vk=［vk1，vk2，…，vkd］，vk1，vk2，…，vkd分别表示第k个粒子在d-维空间中的速度分量。每个粒子在运动过程中，都会根据自身经验判断出个体最优位置pbestk，并且在种群中产生全局最优位置gbest。每个粒子通过比较“两个最优”，不断改善自身位置以趋近全局最优。粒子的速度和位置更新如下：

式中：t为当前的迭代次数；ω为惯性权因子；c1和c2为正的加速常数；r1和r2为0～1之间均匀分布的随机数；M为种群规模。

AFSA算法是一种模拟鱼群觅食行为的全局寻优智能算法［13］，相对于PSO算法，AFSA算法全局收敛速度较慢，且寻优过程较为复杂。在AFSA-PSO算法中，粒子经过PSO算法更新后，在AFSA的聚群和追尾行为之间做出判断，基于选择的行为更新自身位置。以求最小值为例，若中心位置的适应度值小于视野范围内最小适应度值，则粒子执行聚群行为，反之，执行追尾行为。

1.1 AFSA聚群行为

经过PSO算法更新后，第k个粒子的位置和适应度值为xk（t+1）和yk（t+1），每个粒子搜索当前视野范围内的粒子数目Nf及粒子中心位置xc，若满足式（3），则表示中心位置粒子的适应度值更优且粒子不太拥挤，则粒子向中心位置移动［14］。粒子中心位置及向中心位置移动的计算如下：式中：yc为中心位置粒子的适应度值；xi为视野范围内各粒子的位置；δ为拥挤度因子；s为粒子位置的移动步长；r为0～1之间的随机数。

1.2 AFSA追尾行为

经过PSO算法更新后，粒子的位置和适应度值为xk（t+1）和yk（t+1），粒子搜索当前视野范围内粒子的数目Nf及视野内粒子适应度值yb最优的粒子的位置xb，若满足式（6），则表明xi所处的位置并不拥挤且适应度值最优，那么粒子则按照式（7）向xi位置移动。

2 基于AFSA-PSO的选星算法

设某历元时刻可见卫星数为n，选择m颗卫星，使构成的卫星组合的GDOP值最小。在AFSA-PSO选星算法中，每组卫星组合代表一个粒子，GDOP为适应度函数。具体的选星步骤如下：

步骤1获取可见卫星。根据导航电文，获取当前时刻仰角大于遮蔽角的卫星（本文中选取5°），得到可见卫星。

步骤2编码。将步骤1获取的可见卫星随机排列，对其从1，2，…，n依次编码，编码与卫星号一一对应。

步骤3生成初始种群。从n颗可见星中选取m颗，共有种卫星组合，每种组合代表一个粒子。设在AFSA-PSO选星算法中，种群大小为M，从所有可见星组合中随机搜索M 个组合，得到初始种群，初始种群中粒子k的位置表示为：xk=［x01，x02，…，x0m］，m为选择的卫星数。初始化粒子的速度为vk=［v01，v02，…，v0m］，下标“0”为粒子k的初始迭代次数。

步骤4适应度值计算。将初始种群中的每个粒子代入到适应度函数中，计算每个粒子的适应度值，将适应度值最小的粒子位置设为初始全局最优位置gbest，每个粒子本身的位置设置为初始个体最优位置pbestk。

步骤5更新。通过判断每个粒子的个体最优值，确定每次迭代过程中每个粒子经过的个体最优位置pbestk和群体中的全局最优位置gbest。基于式（1）～式（7）更新粒子的位置和速度，计算粒子的适应度值，直到满足条件，得到最佳卫星组合和适应度值。

3 AFSA-PSO选星算法性能分析

参数的选取影响算法的性能，本文中基于Shi和Eberhart的经验进行多次仿真实验［15］，选取标准PSO算法的参数值为：种群规模M=100，最大迭代次数Mt=50，加速常数c1=c2=1.4962，粒子最大移动速度vmax=2，最小移动速度vmin=-2，惯性权因子引入自适应值，其表示为

式中：ωmax=0.9和ωmin=0.4分别为最大和最小惯性权因子；Mt为最大迭代次数。

AFSA-PSO选星算法主要包括以下参数：人工鱼视野V、移动步长s、拥挤度因子δ。本文中将遍历法［16］选星得到的GDOP值作为参考，计算同一时刻、同一参数取不同值时的GDOP误差。

3.1 视野对算法性能影响

在AFSA-PSO选星算法中，通过多次仿真选取合适的视野值，终止迭代次数设为50，移动步长设为10，拥挤度因子设为0.4，得到的GDOP误差及选星耗时如表1所示。

表1结果表明，视野值越大，平均选星的耗时越长，GDOP误差值越小，但是算法整体的GDOP平均误差在0～0.07之间，表明视野对AFSA-PSO选星算法的精度影响不大。

表1 视野对算法性能的影响Table 1 Effect of visual field on algorithm perform ance

3.2 移动步长对算法性能影响

在AFSA-PSO选星算法中，设置终止迭代次数为50，视野值为10，拥挤度因子为0.4，其GDOP误差及选星耗时如表2所示。

表2 移动步长对算法性能的影响Table 2 Effect of step length on algorithm perform ance

表2结果表明，当移动步长为6～10时，随着移动步长的增加，AFSA-PSO平均选星耗时减少，GDOP平均误差也随之减小；当移动步长超过10时，随着移动步长的增加，AFSA-PSO平均选星耗时增加，GDOP误差也逐渐增大。

3.3 拥挤度因子对算法性能影响

在AFSA-PSO选星算法中，设置终止迭代次数为50，视野值为10，移动步长为8，其GDOP误差值及选星耗时如表3所示。

表3结果表明，当δ=0.2和δ=1时，AFSAPSO算法平均耗时增加；因此，为实现快速选星，拥挤度因子可在0.4～0.8之间取值。

表3 拥挤度因子对算法性能的影响Tab le 3 E ffect of crow ding factor on algorithm perform ance

4 仿真验证与结果分析

为了验证本文算法的性能，实验计算机采用CPU处理器（i5-4570，3.20GHz）、RAM 4GB，通过实际的导航数据进行仿真实验，导航电文和观测文件来自于IGS（International GNSS Service，IGS）网站，北斗/GPS接收机坐标为［-2 279 827.315 6，5004704.3094，3219776.2093］m，选星颗数为6。卫星位置由导航星历计算，卫星的截止高度角设为5°，仿真时长为3 h，仿真步长为1min。图1给出了3 h内北斗/GPS双星座下可见卫星数及最小GDOP值。

图1表明，3 h内北斗/GPS双星座下可见卫星数目约为18颗，设需从全部可见卫星中选取6颗，按照遍历法选星，需要进行C=18 564次GDOP值的计算，选星耗时约为4.5 s，最小GDOP值为2.251 028。

本文根据AFSA-PSO选星算法步骤进行单次选星，选取参数拥挤度因子δ=0.4，视野值V=10，移动步长s=10。图2给出了相同时刻PSO算法和AFSA-PSO算法GDOP误差的变化曲线。结果表明，标准PSO算法的收敛速度很快，但在迭代次数为11时，GDOP误差就稳定在0.1758，然而，标准PSO算法容易陷入局部最优；而AFSA-PSO算法在迭代次数为21时，GDOP误差就趋于0。因此，AFSA-PSO算法克服了标准PSO算法“早熟”的问题。

选星颗数为6和8时，3 h内标准PSO算法和AFSA-PSO算法的GDOP误差结果如图3所示。

根据图3，在3 h内对比不同选星颗数下2种选星算法的GDOP误差，选星颗数为8时的GDOP误差小于选星颗数为6时的误差，表明随着选星颗数的增加，2种选星算法的精度都有所提高。

在3 h内对比相同选星颗数下的2种选星算法，图3（a）、（b）表明，当选星颗数为6时，AFSA-PSO算法有67%的GDOP误差趋近于0；对比PSO算法，AFSA-PSO算法的GDOP误差更小更稳定；对比图3（c）、（d），当选星颗数为8时，AFSA-PSO算法有92%的GDOP误差趋近于0，PSO算法GDOP误差分布在0.1～0.4之间，因此。AFSA-PSO 选星算法在精度上优于 PSO算法。

图1 可见卫星数及对应的最小GDOP值Fig.1 Visible number of satellites and corresponding min-GDOP

图2 单次选星GDOP误差变化Fig.2 GDOP error change of single satellite selection

图3 AFSA-PSO算法与PSO算法的GDOP误差Fig.3 GDOP error in AFSA-PSO and PSO algorithms

表4对比了不同选星算法单次选星耗时，给出了选星颗数为6时的耗时结果。从中可知，AFSA-PSO选星算法单次选星耗时优于遍历算法。

表4 不同选星算法单次选星耗时Tab le 4 Single satellite selection tim e of different satellie selection algorithm s

5 结 论

本文研究了一种改进粒子群优化卫星导航选星算法，将AFSA-PSO算法引入到选星过程中，减少GDOP的计算次数，通过对算法进行仿真验证和分析，得到以下结果：

1）AFSA引入到PSO算法中，克服了PSO算法陷入局部最优的不足。

2）在组合导航下，选星颗数相同时，AFSAPSO选星结果的准确性优于PSO选星算法。

3）随着选星颗数的增加，AFSA-PSO选星算法的GDOP误差减小。

4）与遍历法相比，当选星颗数为6时，AFSAPSO选星效率得到改善。