多星座组合导航系统使得接收机可见卫星数增加，将获得比单一星座更优的卫星几何结构和更多的导航冗余信号^[1]，然而也增大了接收机的处理负担。为此，选星算法成为接收机面向多星座组合导航的一项重要研究内容。现有的选星算法能够应用于选星多于4颗的情况^[2-3]，根据卫星高度角和方位角选取可见卫星子集^[4]，以及通过简化几何精度因子(Geometric Dilution of Precision, GDOP)的计算过程和采用优化算法减少GDOP的计算次数^[5-6]。然而，上述算法仍存在计算复杂以及忽略选星颗数对导航性能的影响等问题。为充分利用多星座卫星导航系统带来的优势，同时，降低因可见卫星增加给接收机运算带来的负担，需要研究多星座快速选星算法。
粒子群优化(Particle Swarm Optimization, PSO)算法常用于处理非线性复杂系统的优化问题，已经在很多领域(如卫星导航、系统控制、图像处理等)中得到应用^[7-8]，将该算法应用到多星座选星过程中，能够减少GDOP的计算次数，从而达到快速选星的目的。PSO选星算法能够减少一半以上的选星时间，但是相对于遍历法选星，该算法的选星结果仍存在不稳定性，GDOP的计算误差在0~0.7范围内^[9]。
本文分析了PSO选星算法参数的变化对选星结果以及选星时间的影响，并提出用自适应惯性权重和模拟退火算法改进PSO选星过程，通过仿真实验验证改进后的算法性能。
1 PSO选星算法参数的影响 PSO选星算法主要包括提取可见卫星、编码、建立初始种群、选取适应度函数、粒子位置/速度更新，以及搜索空间几何结构较好的可见星子集等6个部分。
假设当前时刻接收机接收n颗可见星的导航信号，从中选出m颗卫星。将所有可见卫星按照每m颗为一组进行组合，每种组合方式被视为一个粒子。令种群规模为M，从C_n^m种可见星组合中选取M个组合，形成初始种群G₀={x_i}(i=1, 2, …, M)；种群中第i个粒子表示为x_i=[x_{i, 1}, x_{i, 2}, …, x_{i, m}]，x为卫星编号，m为选星数目；速度v_i=[v_{i, 1}, v_{i, 2}, …, v_{i, m}]，粒子按照式(1)和式(2)进行迭代搜索：

(1)

(2)

式中：ω为惯性权重；c₁和c₂为加速系数；r₁和r₂为[0, 1]之间的随机数。
粒子下一时刻的速度取决于当前时刻速度v_i(t)、个体最佳位置pbest以及全局最佳位置gbest。pbest定义为粒子在迭代过程中，最小适应度函数值所对应的位置；gbest定义为当前种群中最小适应度函数值所对应的粒子位置。经过有限次的迭代，种群中的粒子将以大概率收敛到某个值，最终搜索到GDOP最小的卫星子集。
在PSO算法中，参数的选取对结果起到关键作用，PSO选星算法中的参数包括：种群规模M，惯性权重ω，加速系数c₁和c₂，随机数r₁和r₂。对于PSO算法的“早熟”问题，研究者进行了不同程度的改进^[10]，但改进算法的最优参数还需要从具体应用出发，根据经验值选取。
1.1 惯性权重对算法性能的影响 Shi和Eberhart^[11-12]通过实验验证，当ω＜0.8时，PSO选星算法具有很强的局部搜索能力，能够以很快的速度收敛到全局最优解；当ω>1.2时，算法具有很强的全局搜索能力，但收敛速度较慢；当0.8≤ω≤1.2时，算法收敛到全局最优解的可能性相对上述2种情况大，而且收敛速度适中。为此，研究自适应改变惯性权重，提高算法性能。
算法的终止迭代次数设置为50代，加速系数c₁=c₂=2，种群规模M=100，惯性权重ω分别取值为0.4，0.6，0.8，0.9，1.0，1.1，1.2，1.3，1.4，1.6，每种惯性权重取值进行10次仿真实验，其平均GDOP值及选星耗时结果如表 1所示。
表 1 惯性权重对PSO选星算法性能的影响 Table 1 Effect of inertia weight on PSO satellite selection algorithm performance

惯性权重 ω	平均 GDOP	最大 GDOP	最小 GDOP	平均选星耗时/s
0.4	2.320 4	2.364 5	2.251 0	1.517
0.6	2.314 5	2.419 6	2.251 0	1.566
0.8	2.318 5	2.358 5	2.251 0	1.546
0.9	2.288 0	2.419 6	2.251 0	1.548
1.0	2.345 7	2.370 7	2.251 0	1.527
1.1	2.299 8	2.481 1	2.251 0	1.626
1.2	2.327 3	2.540 2	2.251 0	1.538
1.3	2.343 4	2.370 7	2.251 0	1.561
1.4	2.352 9	2.460 5	2.251 0	1.544
1.6	2.342 5	2.426 9	2.251 0	1.539

表选项






将算法的适应度函数定义为计算卫星的GDOP值，算法通过多次迭代搜索最小GDOP值与其对应的卫星组合。从表 1中的结果可知，惯性权重在0.8≤ω≤1.2范围内得出的平均适应度函数解最优，ω＜0.8或ω>1.2时平均适应度函数解较差，尤其在ω较大时粒子的全局搜索能力变差。在10次仿真实验中，最小GDOP值都是相同的，这表明该算法能够搜索到全局最优解，但是同一历元循环10次寻找最小值，对应的选星耗时也变大。此外，PSO算法的平均选星耗时在1.5~1.7 s，惯性权重对选星耗时影响不大。
1.2 加速系数对算法性能的影响 加速系数c₁和c₂分别用于调节粒子在个体最优和种群最优方向上的移动步长，从式(1)可以得出，当c₁>c₂时，粒子更新速度取决于自身位置与所经过最优位置的比较；当c₁＜c₂时，粒子更新速度倾向于自身位置与种群最优位置的比较；当c₁=c₂时，pbest与gbest二者共同作用。同样，PSO选星算法的终止迭代次数设置为50代，惯性权重ω=0.9、种群规模M=100，加速系数c₁/c₂分别取值为0.25，0.5，1，2，3，4，每种加速系数取值分别进行10次仿真实验，其平均GDOP值及选星耗时结果如表 2所示。
表 2 加速系数对算法性能的影响 Table 2 Effect of acceleration factor on algorithm performance

加速系数	c1/c2	平均 GDOP	最大 GDOP	最小 GDOP	平均选星耗时/s
c1=1，c2=4	0.25	2.339 4	2.380 1	2.251 0	1.559
c1=1，c2=2	0.5	2.348 3	2.540 2	2.251 0	1.573
c1=1，c2=1	1	2.355 1	2.419 6	2.251 0	1.616
c1=1.5，c2=1.5	1	2.381 9	2.540 2	2.251 0	1.566
c1=2，c2=2	1	2.295 1	2.347 4	2.251 0	1.569
c1=0.5，c2=0.5	1	2.403 5	2.540 2	2.251 0	1.557
c1=0.25，c2=0.25	1	2.357 7	2.509 9	2.251 0	1.578
c1=4，c2=2	2	2.298 5	2.370 7	2.251 0	1.573
c1=2，c2=1	2	2.308 3	2.419 6	2.251 0	1.638
c1=1，c2=0.5	2	2.366 2	2.419 6	2.251 0	1.565
c1=3，c2=1	3	2.329 4	2.460 5	2.251 0	1.579
c1=4，c2=1	4	2.317 9	2.370 7	2.251 0	1.581

表选项






从表 2可以看出，c₁和c₂的较优组合为(2, 2)、(4, 2)、(2, 1)，算法的优化效果较好。在算法的更新迭代过程中，需要权衡考虑算法收敛速度和全局最优解。
1.3 种群规模对算法性能的影响 基本PSO算法需要调节的参数较少，其中一个参数就是种群的大小，也可称为种群规模。种群规模通常根据待解决问题的难易程度凭经验值选取，一般取值20~50较为常见。本文种群规模M选取10个值进行实验验证，种群规模M取值如表 3所示，设定算法的终止迭代次数设置为50代，惯性权重ω=0.9，加速系数c₁=c₂=2。对M的每种取值分别进行10次仿真实验，其平均GDOP值及选星耗时结果如表 3所示。
表 3 种群规模对算法性能的影响 Table 3 Effect of population sizes on algorithm performance

种群规模M	平均 GDOP	最大 GDOP	最小 GDOP	平均选星耗时/s
30	2.405 439 541	2.509 928 411	2.251 0	0.546 194 8
50	2.332 476 761	2.419 611 127	2.2510	0.828 243 7
70	2.289 530 344	2.364 511 595	2.251 0	1.127 988 2
90	2.308 514 516	2.358 491 188	2.251 0	1.441 279 7
100	2.292 758 802	2.419 611 127	2.251 0	1.586 975 4
110	2.317 243 548	2.419 611 127	2.251 0	1.793 920 8
120	2.326 449 813	2.540 188 469	2.251 0	1.924 731 8
150	2.312 394 223	2.370 668 208	2.251 0	2.491 832 2
180	2.283 993 701	2.334 593 796	2.251 0	2.775 929 5
200	2.306 857 579	2.370 668 208	2.251 0	3.123 896 5

表选项






随着种群规模的增大，算法的平均选星时间也随之增加。在种群规模M=30时，算法选星耗时为0.54 s，且在10次实验中能够找到目标函数值。算法性能并没有随着种群规模的增大呈现递增趋势。同时考虑GDOP和选星耗时参数，在粒子群算法用于选星问题中，种群规模M在70~100之间算法的综合性能较好。
2 自适应模拟退火PSO选星算法 对于PSO算法在选星问题中的应用，通过仿真实验调节算法各参数，从上述的实验结果可以看出：算法参数的选取直接影响算法性能以及选星耗时。因此，若是固定算法参数，只能采取折中方式，平衡算法性能和选星耗时之间的关系。然而折中选取参数的优化效果往往并不理想，这就要求算法的参数能够随着迭代次数自适应调整。算法在刚进入迭代时，种群中粒子差异大，全局搜索能力强，而经过多次迭代搜索后，种群中粒子逐渐趋近全局最优值，此时的搜索调整比较慢，而且不能保证搜索到全局最优，从而出现算法“早熟”问题。本文采用自适应模拟退火粒子群优化(Adaptive Simulated Annealing Particle Swarm Optimization, ASAPSO)算法优化选星过程，以提高算法搜索结果的准确性。
2.1 自适应惯性权重 从式(1)可以看出，当ω≥c₁且ω≥c₂时，粒子将不受个体最优pbest和全局最优gbest的影响，按照原有的速度运动，种群中粒子很难收敛；而当ω→0时，粒子下一时刻速度与当前速度无关，种群中粒子快速收敛，此时得到的搜索结果是当前种群最优值，而非问题解空间的最优值，这就是算法的“早熟”问题，因而，惯性权重ω的大小直接影响着算法的搜索结果。本文采用随粒子目标值大小的不同而改变的自适应惯性权重，其更新公式为

(3)

式中：ω_max和ω_min分别为惯性权重ω的最大值和最小值；f_i为粒子的适应值；f_avg和f_min分别为种群中粒子的平均适应值和最小适应值^[13]。
2.2 结合模拟退火的PSO算法 模拟退火(Simulated Annealing, SA)是一种根据金属的冷却和退火方式而产生的用于解决组合优化问题的算法^[14-16]。引入模拟退火算法是给性能较差的粒子赋予一定的选中概率，提高粒子的多样性，从而增强算法的全局搜索能力^[17]。
算法首先通过给定初始温度T₀，随着温度的降低，能够以一定概率接受较差的解，温度与接受较差解概率的关系为

(4)

式中：p为接受较差解的概率；f_g为种群中粒子最优适应度值；T为温度，温度越高，接受较差解的概率就会较大。为此，算法在应用过程中通常设置较高的初始温度，提高粒子的全局搜索能力，而经过一定比率降温后，逐渐减小搜索空间，直到收敛到全局最优解。
2.3 ASAPSO选星算法流程 假设当前时刻接收机接收到可见卫星数为n颗，从中选取m颗空间几何结构较好的卫星，基于ASAPSO选星算法的步骤如下：
步骤1??提取可见卫星、编码、形成初始种群。
步骤2??初始化。
1) 初始化种群中粒子的位置。
2) 设初始温度T₀=-f_g/ln 0.2。
3) 计算各粒子的适应值f_i，平均适应值f_avg。
4) 令种群中GDOP最小的粒子为初始最佳群体位置gbest，各粒子自身位置为最佳位置pbest。
步骤3??进入迭代。
1) 根据式(3)更新权重ω。
2) 根据式(1)和式(2)更新粒子位置和速度。
3) 如果新粒子的适应值优于pbest的适应值，pbest设为当前个体极值；如果当次迭代种群中最佳适应值优于pbest的适应值，pbest设为当前全局极值。
4) 根据式(4)计算接受较差解概率。
5) 生成随机数r，r∈(0, 1)，如果r＜min [1, p]，粒子进入新位置，返回步骤3)。
6) 冷却：T_k+1=λT_k，其中，k为迭代次数，λ为降温速率。
步骤4??判断是否达到最大迭代次数，如果满足，输出pbest及适应值，否则，返回步骤3。
改进后的算法在迭代过程中，当粒子的新位置比当前位置适应值小时，粒子移动到新位置；当新位置的适应值大于当前位置适应值时，粒子不一定舍弃新位置，而是通过接受差值概率决定粒子是否移动到新位置。
3 实验验证与结果分析 为了验证ASAPSO选星算法的性能，实验所用的计算机CPU处理器(i5-4570，3.20 GHz)、RAM 4 GB，通过实际的导航数据进行仿真实验，导航电文和观测文件来自于IGS(International GNSS Service)网站，北斗/GPS接收机坐标为[-2 279 827.315 6，5 004 704.309 4，3219776.2093] m，选星颗数为6。卫星位置由导航星历计算，卫星的截止高度角设为5°，仿真开始时刻为2016-07-31 00:00:00，仿真时长为3 h，仿真步长为1 min。
图 1为相同时刻情况下ASAPSO和PSO选星算法在迭代搜索过程中的GDOP变化。在ASAPSO选星算法中，粒子经过50次迭代搜索到全局最小值，选星时间为2.736 459 s，ASAPSO算法能够实现快速选星。从图中曲线可以看出，ASAPSO具有从局部极值“跳出”的能力，在迭代次数为15~25时，算法搜索的结果在2.45附近，而在第26次迭代中，算法“跳出”局部极值，搜索到全局最优解，说明ASAPSO算法能够提高选星结果的准确性。

图 1 PSO和ASAPSO选星算法GDOP变化 Fig. 1 GDOP changes in PSO and ASAPSO satellite selection algorithm

图选项

仿真时长为3 h的PSO、自适应PSO和ASAPSO选星算法GDOP计算误差结果如图 2所示，其误差定义为SAPSO选星算法所得到的GDOP值与遍历法选星所得到GDOP值的差值，从图 2(a)~图 2(c)可知，通过自适应调整惯性权重改进的PSO选星算法GDOP误差趋于零的时间点多于PSO选星算法，而ASAPSO选星算法得出的GDOP误差图中，有64.7%的点的GDOP误差为0，该算法很大程度地改善了搜索结果的准确性，且计算误差在0~0.45范围内。

图 2 PSO、改进PSO及ASAPSO选星算法的GDOP计算误差 Fig. 2 GDOP calculation error of PSO, improved PSO and ASAPSO satellite selection algorithm

图选项

4 结论 本文研究了PSO选星算法中的各项参数对选星结果和耗时的影响，给出了参数的选取范围，并提出自适应惯性权重和模拟退火算法改进PSO选星过程，通过仿真实验，得出以下结论：
1) 惯性权重0.8≤ω≤1.2，加速系数c₁和c₂的较优组合(2, 2)、(4, 2)、(2, 1)，种群规模70≤M≤100，选星算法在该参数下搜索结果更为准确。
2) ASAPSO选星算法的单次选星耗时为2.736 459 s，选星结果误差在0~0.45。该算法能够实现快速选星，且提高了PSO选星算法的搜索准确性。
3) ASAPSO选星算法能够解决PSO选星算法的搜索结果不稳定问题。

参考文献

[1]	DEANE B, LEO E, DEBORAH L.GNSS evolutionary architecture study Phase Ⅱ Report[R]. Washington, D.C.: FAA, 2010.
[2]	ZHENG Z Y, HUANG C, FENG C G, et al. Selection of GPS satellites for the optimum geometry[J]. Chinese Astronomy and Astrophysics, 2004, 28: 80-87. DOI:10.1016/S0275-1062(04)90009-4
[3]	DONG S H. A closed-form formula for GPS GDOP computation[J]. GPS Solutions, 2009, 13(3): 183-190. DOI:10.1007/s10291-008-0111-2
[4]	霍航宇, 张晓林. 组合卫星导航系统的快速选星方法[J]. 北京航空航天大学学报, 2015, 41(2): 273-282. HUO H Y, ZHANG X L. Fast satellite selection method for integrated navigation systems[J]. Journal of Beijing University of Aeronautics and Astronautics, 2015, 41(2): 273-282. (in Chinese)
[5]	BLANCO-DELGADO N, NUNES F D. Satellite selection method for multi-constellation GNSS using convex geometry[J]. IEEE Transactions on Vehicular Technology, 2010, 59(9): 4289-4297. DOI:10.1109/TVT.2010.2072939
[6]	宋丹, 许承东, 胡春生, 等. 基于遗传算法的多星座选星方法[J]. 宇航学报, 2015, 36(3): 300-308. SONG D, XU C D, HU C S, et al. Satellite selection with genetic algorithm under multi-constellation[J]. Journal of Astronautics, 2015, 36(3): 300-308. DOI:10.3873/j.issn.1000-1328.2015.03.008 (in Chinese)
[7]	WANG E S, JIA C Y, TONG G, et al. Fault detection and isolation in GPS receiver autonomous integrity monitoring based on chaos particle swarm optimization-particle filter algorithm[J]. Advances in Space Research, 2018, 61(9): 1260-1272.
[8]	冯智博, 黄宏光, 李奕. 基于改进粒子群算法的WSN覆盖优化策略[J]. 计算机应用研究, 2011, 28(4): 1272-1275. FENG Z B, HUANG H G, LI Y. Strategy of wireless sensor networks coverage optimization by improved particle swarm algorithm[J]. Application Research of Computers, 2011, 28(4): 1272-1275. DOI:10.3969/j.issn.1001-3695.2011.04.020 (in Chinese)
[9]	王尔申, 贾超颖, 曲萍萍, 等. 基于混沌粒子群优化的北斗/GPS组合导航选星算法[J]. 北京航空航天大学学报, 2019, 45(2): 259-265. WANG E S, JIA C Y, QU P P, et al. Research on BDS/GPS integrated navigation fast selection algorithm[J]. Journal of Beijing University of Aeronautics and Astronautics, 2019, 45(2): 259-265. (in Chinese)
[10]	胥小波, 郑康锋, 李丹, 等. 新的混沌粒子群优化算法[J]. 通信学报, 2012, 33(1): 24-30. XU X B, ZHENG K F, LI D, et al. New chaos-particle swarm optimization algorithm[J]. Journal on Communications, 2012, 33(1): 24-30. DOI:10.3969/j.issn.1000-436X.2012.01.004 (in Chinese)
[11]	SHI Y H, EBERHART R C.A modified particle swarm optimizer[C]//IEEE International Conference on Evolutionary Computation.Piscataway, NJ: IEEE Press, 1998: 69-73. http://www.researchgate.net/publication/3755900_Modified_particle_swarm_optimizer
[12]	EBERHART R C, SHI Y H.Particle swarm optimization: developments, applications and resources[C]//Proceedings of the 2001 Congress on Evolutionary Computation.Piscataway, NJ: IEEE Press, 2002: 81-86. http://www.researchgate.net/publication/247116719_particle_swarm_optimization_developments
[13]	KURU L, OZTURK A, KURU E, et al. Determination of voltage stability boundary values in electrical power systems by using the chaotic particle swarm optimization algorithm[J]. International Journal of Electrical Power & Energy Systems, 2015, 64(15): 873-879.
[14]	WU G, WANG H, PEDRYCZ W, et al. Satellite observation scheduling with a novel adaptive simulated annealing algorithm and a dynamic task clustering strategy[J]. Computers & Industrial Engineering, 2017, 113: 576-588.
[15]	ASSAD A, DEEP K. A hybrid harmony search and simulated annealing algorithm for continuous optimization[J]. Information Sciences, 2018, 450: 246-266. DOI:10.1016/j.ins.2018.03.042
[16]	TAVARES R S, MARTINS T C, TSUZUKI M S G. Simulated annealing with adaptive neighborhood:A case study in off-line robot path planning[J]. Expert Systems with Applications, 2011, 38(4): 2951-2965. DOI:10.1016/j.eswa.2010.08.084
[17]	薛永生, 吴立尧. 基于模拟退火的改进粒子群算法研究及应用[J]. 海军航空工程学院学报, 2018, 33(2): 248-252. XUE Y S, WU L Y. Research and application of improved PSO algorithm based on simulated annealing[J]. Journal of Naval Aeronautical and Astronautical University, 2018, 33(2): 248-252. (in Chinese)