大部分的选星算法主要是基于衡量定位精度的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。每个粒子通过比较“两个最优”，不断改善自身位置以趋近全局最优。粒子的速度和位置更新如下：
 | (1) |
 | (2) |
式中：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]。粒子中心位置及向中心位置移动的计算如下：
 | (3) |
 | (4) |
 | (5) |
式中：yc为中心位置粒子的适应度值；xi为视野范围内各粒子的位置；δ为拥挤度因子；s为粒子位置的移动步长；r为0~1之间的随机数。
1.2 AFSA追尾行为 经过PSO算法更新后，粒子的位置和适应度值为xk(t+1)和yk(t+1)，粒子搜索当前视野范围内粒子的数目Nf及视野内粒子适应度值yb最优的粒子的位置xb，若满足式(6)，则表明xi所处的位置并不拥挤且适应度值最优，那么粒子则按照式(7)向xi位置移动。
 | (6) |
 | (7) |
2 基于AFSA-PSO的选星算法 设某历元时刻可见卫星数为n，选择m颗卫星，使构成的卫星组合的GDOP值最小。在AFSA-PSO选星算法中，每组卫星组合代表一个粒子，GDOP为适应度函数。具体的选星步骤如下：
步骤1??获取可见卫星。根据导航电文，获取当前时刻仰角大于遮蔽角的卫星(本文中选取5°)，得到可见卫星。
步骤2??编码。将步骤1获取的可见卫星随机排列，对其从1, 2, …，n依次编码，编码与卫星号一一对应。
步骤3??生成初始种群。从n颗可见星中选取m颗，共有Cnm种卫星组合，每种组合代表一个粒子。设在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.496 2，粒子最大移动速度vmax=2，最小移动速度vmin=-2，惯性权因子引入自适应值，其表示为
 | (8) |
式中：ω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 视野对算法性能的影响 Table 1 Effect of visual field on algorithm performance
| 视野 | 最大GDOP误差 | 平均GDOP误差 | 选星耗时/s |
| 2 | 0.112 5 | 0.065 21 | 2.451 830 |
| 4 | 0.137 5 | 0.057 34 | 2.691 055 |
| 6 | 0.100 5 | 0.051 91 | 2.869 438 |
| 8 | 0.107 5 | 0.030 03 | 2.938 141 |
| 10 | 0.096 4 | 0.027 48 | 2.969 203 |
表选项
表 1结果表明，视野值越大，平均选星的耗时越长，GDOP误差值越小，但是算法整体的GDOP平均误差在0~0.07之间，表明视野对AFSA-PSO选星算法的精度影响不大。
3.2 移动步长对算法性能影响 在AFSA-PSO选星算法中，设置终止迭代次数为50，视野值为10，拥挤度因子为0.4，其GDOP误差及选星耗时如表 2所示。
表 2 移动步长对算法性能的影响 Table 2 Effect of step length on algorithm performance
| 移动步长 | 最大GDOP误差 | 平均GDOP误差 | 选星耗时/s |
| 6 | 0.289 2 | 0.093 55 | 3.291 174 |
| 8 | 0.168 6 | 0.055 69 | 3.018 298 |
| 10 | 0.107 5 | 0.047 54 | 2.855 520 |
| 12 | 0.113 5 | 0.087 41 | 2.866 246 |
| 14 | 0.119 6 | 0.094 40 | 2.965 653 |
表选项
表 2结果表明，当移动步长为6~10时，随着移动步长的增加，AFSA-PSO平均选星耗时减少，GDOP平均误差也随之减小；当移动步长超过10时，随着移动步长的增加，AFSA-PSO平均选星耗时增加，GDOP误差也逐渐增大。
3.3 拥挤度因子对算法性能影响 在AFSA-PSO选星算法中，设置终止迭代次数为50，视野值为10，移动步长为8，其GDOP误差值及选星耗时如表 3所示。
表 3 拥挤度因子对算法性能的影响 Table 3 Effect of crowding factor on algorithm performance
| 拥挤度因子 | 最大GDOP误差 | 平均GDOP误差 | 选星耗时/s |
| 0.2 | 0.214 9 | 0.123 94 | 3.153 434 |
| 0.4 | 0.107 5 | 0.067 93 | 2.240 370 |
| 0.6 | 0.129 0 | 0.095 77 | 2.083 249 |
| 0.8 | 0.119 6 | 0.080 65 | 2.022 105 |
| 1 | 0.113 5 | 0.097 68 | 3.082 750 |
表选项
表 3结果表明，当δ=0.2和δ=1时，AFSA-PSO算法平均耗时增加；因此，为实现快速选星，拥挤度因子可在0.4~0.8之间取值。
4 仿真验证与结果分析 为了验证本文算法的性能，实验计算机采用CPU处理器(i5-4570，3.20 GHz)、RAM 4 GB，通过实际的导航数据进行仿真实验，导航电文和观测文件来自于IGS(International GNSS Service, IGS)网站，北斗/GPS接收机坐标为[-2 279 827.315 6，5 004 704.309 4，3 219 776.209 3]m，选星颗数为6。卫星位置由导航星历计算，卫星的截止高度角设为5°，仿真时长为3 h，仿真步长为1 min。图 1给出了3 h内北斗/GPS双星座下可见卫星数及最小GDOP值。
 |
| 图 1 可见卫星数及对应的最小GDOP值 Fig. 1 Visible number of satellites and corresponding min-GDOP |
| 图选项 |
图 1表明，3 h内北斗/GPS双星座下可见卫星数目约为18颗，设需从全部可见卫星中选取6颗，按照遍历法选星，需要进行C186=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.175 8，然而，标准PSO算法容易陷入局部最优；而AFSA-PSO算法在迭代次数为21时，GDOP误差就趋于0。因此，AFSA-PSO算法克服了标准PSO算法“早熟”的问题。
 |
| 图 2 单次选星GDOP误差变化 Fig. 2 GDOP error change of single satellite selection |
| 图选项 |
选星颗数为6和8时，3 h内标准PSO算法和AFSA-PSO算法的GDOP误差结果如图 3所示。
 |
| 图 3 AFSA-PSO算法与PSO算法的GDOP误差 Fig. 3 GDOP error in AFSA-PSO and PSO algorithms |
| 图选项 |
根据图 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算法。
表 4对比了不同选星算法单次选星耗时，给出了选星颗数为6时的耗时结果。从中可知，AFSA-PSO选星算法单次选星耗时优于遍历算法。
表 4 不同选星算法单次选星耗时 Table 4 Single satellite selection time of different satellie selection algorithms
| 算法 | 单次选星耗时/s | GDOP值 | 最佳卫星组合 |
| 遍历法 | 4.902 163 | 2.251 028 | 9 21 27 31 38 39 |
| AFSA-PSO | 2.502 947 | 2.251 028 | 9 21 27 31 38 39 |
| PSO | 1.695 711 | 2.358 500 | 9 21 27 39 38 37 |
表选项
5 结论 本文研究了一种改进粒子群优化卫星导航选星算法，将AFSA-PSO算法引入到选星过程中，减少GDOP的计算次数，通过对算法进行仿真验证和分析, 得到以下结果：
1) AFSA引入到PSO算法中，克服了PSO算法陷入局部最优的不足。
2) 在组合导航下，选星颗数相同时，AFSA-PSO选星结果的准确性优于PSO选星算法。
3) 随着选星颗数的增加，AFSA-PSO选星算法的GDOP误差减小。
4) 与遍历法相比，当选星颗数为6时，AFSA-PSO选星效率得到改善。
参考文献
| [1] | 吴丹.GNSS观测数据预处理及质量评估[D].西安: 长安大学, 2015. WU D.GNSS observation data preprocessing and quality assessment[D].Xi'an: Chang'an University, 2015(in Chinese). |
| [2] | WANG E S, YANG D, WANG C Y, et al. Optimized fault detection algorithm aided by BDS baseband signal for train positioning[J]. Chinese Journal of Electronics, 2020, 29(1): 34-40. DOI:10.1049/cje.2019.09.004 |
| [3] | BO X, SHAO B.Satellite selection algorithm for combined GPS-Galileo navigation receiver[C]//International Conference on Autonomous Robots and Agents.Piscataway: IEEE Press, 2009: 149-154. |
| [4] | PHATAK M S. Recursive method for optimum GPS satellite selection[J]. IEEE Transactions on Aerospace and Electronic Systems, 2001, 37(2): 751-754. DOI:10.1109/7.937488 |
| [5] | SONG J C, XUE G X, KANG Y A. A novel method for optimum global positioning system satellite selection based on a modified genetic algorithm[J]. PloS One, 2016, 11(3): e0150005. DOI:10.1371/journal.pone.0150005 |
| [6] | 胡思华, 张显云, 李婷, 等. 顾及观测质量的多系统融合PPP三维凸包选星算法[J]. 大地测量与地球动力学, 2019, 39(3): 269-272. HU S H, ZHANG X Y, LI T, et al. Three-dimensional convex hull satellites selection algorithm:Considering the quality of observation[J]. Journal of Geodesy and Geodynamics, 2019, 39(3): 269-272. (in Chinese) |
| [7] | LIU X, ZHANG S B, ZHANG Q Z, et al. A fast satellite selection algorithm with floating high cut-off elevation angle based on ADOP for instantaneous multi-GNSS single-frequency relative positioning[J]. Advances in Space Research, 2019, 63(3): 1234-1252. DOI:10.1016/j.asr.2018.10.032 |
| [8] | 霍国平, 缪玲娟, 高志峰. 基于3星子集的GPS快速选星算法[J]. 宇航学报, 2014, 35(5): 574-580. HUO G P, MIAO L J, GAO Z F. GPS fast constellation selection based on 3-SAT subset[J]. Journal of Astronautics, 2014, 35(5): 574-580. DOI:10.3873/j.issn.1000-1328.2014.05.011 (in Chinese) |
| [9] | EBERHART R C, KENNEDY J.A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science.Piscataway: IEEE Press, 1995: 39-43. |
| [10] | 王雪莹, 安玮, 李骏. 天基光学短弧观测约束域的粒子群优化定轨方法[J]. 国防科技大学学报, 2014, 36(6): 146-151. WANG X Y, AN W, LI J. An orbit-determination method with particle swarm optimization using space-based optical short-arc observation in admissible region[J]. Journal of National University of Defense Technology, 2014, 36(6): 146-151. (in Chinese) |
| [11] | WEI P, LI Y, ZHANG Z, et al. An optimization method for intrusion detection classification model based on deep belief network[J]. IEEE Access, 2019, 7: 87593-87605. DOI:10.1109/ACCESS.2019.2925828 |
| [12] | 钊守国, 周长林, 梁臻鹤, 等. 一种基于群体行为动力学的粒子群优化算法[J]. 信息工程大学学报, 2017, 18(3): 299-304. ZHAO S G, ZHOU C L, LIANG Z H, et al. Particle swarm optimization algorithm based on collective behavior dynamics[J]. Journal of Information Engineering University, 2017, 18(3): 299-304. DOI:10.3969/j.issn.1671-0673.2017.03.009 (in Chinese) |
| [13] | 席亮, 王勇, 张凤斌. 基于自适应人工鱼群FCM的异常检测算法[J]. 计算机研究与发展, 2019, 56(5): 1048-1059. XI L, WANG Y, ZHANG F B. Anomaly detection algorithm based on FCM with adaptive artificial fish-swarm[J]. Journal of Computer Research and Development, 2019, 56(5): 1048-1059. (in Chinese) |
| [14] | HE J, JIN X, XIE S Y, et al. Multi-body dynamics modeling and TMD optimization based on the improved AFSA for floating wind turbines[J]. Renewable Energy, 2019, 141: 305-321. DOI:10.1016/j.renene.2019.04.005 |
| [15] | EBERHART R C, SHI Y H.Particle swarm optimization: Developments, applications and resources[C]//Proceedings of the 2001 Congress on Evolutionary Computation.Piscataway: IEEE Press, 2002: 81-86. |
| [16] | 王尔申, 贾超颖, 曲萍萍, 等. 基于混沌粒子群优化的北斗/GPS组合导航选星算法[J]. 北京航空航天大学学报, 2019, 45(2): 259-265. WANG E S, JIA C Y, QU P P, et al. BDS/GPS integrated navigation satellite selection algorithm based on chaos particle swarm optimization[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(2): 259-265. (in Chinese) |
