PSO选星算法参数分析与改进

王尔申， 杨迪， 王传云， 曲萍萍， 庞涛， 蓝晓宇

(1. 沈阳航空航天大学电子信息工程学院， 沈阳 110136； 2. 北京航空航天大学 电子信息工程学院， 北京 100083;3. 沈阳航空航天大学计算机学院， 沈阳 110136)

多星座组合导航系统使得接收机可见卫星数增加，将获得比单一星座更优的卫星几何结构和更多的导航冗余信号[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个部分。

vi(t+1)=ωvi(t)+c1r1[pbest-xi(t)]+

c2r2[gbest-xi(t)]i=1,2,…,N

(1)

xi(t+1)=xi(t)+vi(t+1)i=1,2,…,N

(2)

式中：ω为惯性权重；c1和c2为加速系数；r1和r2为[0,1]之间的随机数。

粒子下一时刻的速度取决于当前时刻速度vi(t)、个体最佳位置pbest以及全局最佳位置gbest。pbest定义为粒子在迭代过程中，最小适应度函数值所对应的位置；gbest定义为当前种群中最小适应度函数值所对应的粒子位置。经过有限次的迭代，种群中的粒子将以大概率收敛到某个值，最终搜索到GDOP最小的卫星子集。

在PSO算法中，参数的选取对结果起到关键作用，PSO选星算法中的参数包括：种群规模M，惯性权重ω，加速系数c1和c2，随机数r1和r2。对于PSO算法的“早熟”问题，研究者进行了不同程度的改进[10]，但改进算法的最优参数还需要从具体应用出发，根据经验值选取。

1.1 惯性权重对算法性能的影响

Shi和Eberhart[11-12]通过实验验证，当ω<0.8时，PSO选星算法具有很强的局部搜索能力，能够以很快的速度收敛到全局最优解；当ω>1.2时，算法具有很强的全局搜索能力，但收敛速度较慢；当0.8≤ω≤1.2时，算法收敛到全局最优解的可能性相对上述2种情况大，而且收敛速度适中。为此，研究自适应改变惯性权重，提高算法性能。

算法的终止迭代次数设置为50代，加速系数c1=c2=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值与其对应的卫星组合。从表1中的结果可知，惯性权重在0.8≤ω≤1.2范围内得出的平均适应度函数解最优，ω<0.8或ω>1.2时平均适应度函数解较差，尤其在ω较大时粒子的全局搜索能力变差。在10次仿真实验中，最小GDOP值都是相同的，这表明该算法能够搜索到全局最优解，但是同一历元循环10次寻找最小值，对应的选星耗时也变大。此外，PSO算法的平均选星耗时在1.5～1.7 s，惯性权重对选星耗时影响不大。

1.2 加速系数对算法性能的影响

加速系数c1和c2分别用于调节粒子在个体最优和种群最优方向上的移动步长，从式(1)可以得出，当c1>c2时，粒子更新速度取决于自身位置与所经过最优位置的比较；当c1

从表2可以看出，c1和c2的较优组合为(2,2)、(4,2)、(2,1)，算法的优化效果较好。在算法的更新迭代过程中，需要权衡考虑算法收敛速度和全局最优解。

1.3 种群规模对算法性能的影响

基本PSO算法需要调节的参数较少，其中一个参数就是种群的大小，也可称为种群规模。种群规模通常根据待解决问题的难易程度凭经验值选取，一般取值20～50较为常见。本文种群规模M选取10个值进行实验验证，种群规模M取值如表3所示，设定算法的终止迭代次数设置为50代，惯性权重ω=0.9，加速系数c1=c2=2。对M的每种取值分别进行10次仿真实验，其平均GDOP值及选星耗时结果如表3所示。

随着种群规模的增大，算法的平均选星时间也随之增加。在种群规模M=30时，算法选星耗时为0.54 s，且在10次实验中能够找到目标函数值。算法性能并没有随着种群规模的增大呈现递增趋势。同时考虑GDOP和选星耗时参数，在粒子群算法用于选星问题中，种群规模M在70～100之间算法的综合性能较好。

表2 加速系数对算法性能的影响Table 2 Effect of acceleration factor on algorithm performance

表3 种群规模对算法性能的影响Table 3 Effect of population sizes on algorithm performance

2 自适应模拟退火PSO选星算法

对于PSO算法在选星问题中的应用，通过仿真实验调节算法各参数，从上述的实验结果可以看出：算法参数的选取直接影响算法性能以及选星耗时。因此，若是固定算法参数，只能采取折中方式，平衡算法性能和选星耗时之间的关系。然而折中选取参数的优化效果往往并不理想，这就要求算法的参数能够随着迭代次数自适应调整。算法在刚进入迭代时，种群中粒子差异大，全局搜索能力强，而经过多次迭代搜索后，种群中粒子逐渐趋近全局最优值，此时的搜索调整比较慢，而且不能保证搜索到全局最优，从而出现算法“早熟”问题。本文采用自适应模拟退火粒子群优化(Adaptive Simulated Annealing Particle Swarm Optimization,ASAPSO)算法优化选星过程，以提高算法搜索结果的准确性。

2.1 自适应惯性权重

从式(1)可以看出，当ω≥c1且ω≥c2时，粒子将不受个体最优pbest和全局最优gbest的影响，按照原有的速度运动，种群中粒子很难收敛；而当ω→0时，粒子下一时刻速度与当前速度无关，种群中粒子快速收敛，此时得到的搜索结果是当前种群最优值，而非问题解空间的最优值，这就是算法的“早熟”问题，因而，惯性权重ω的大小直接影响着算法的搜索结果。本文采用随粒子目标值大小的不同而改变的自适应惯性权重，其更新公式为

(3)

式中：ωmax和ωmin分别为惯性权重ω的最大值和最小值；fi为粒子的适应值；favg和fmin分别为种群中粒子的平均适应值和最小适应值[13]。

2.2 结合模拟退火的PSO算法

模拟退火(Simulated Annealing,SA)是一种根据金属的冷却和退火方式而产生的用于解决组合优化问题的算法[14-16]。引入模拟退火算法是给性能较差的粒子赋予一定的选中概率，提高粒子的多样性，从而增强算法的全局搜索能力[17]。

算法首先通过给定初始温度T0，随着温度的降低，能够以一定概率接受较差的解，温度与接受较差解概率的关系为

(4)

式中：p为接受较差解的概率；fg为种群中粒子最优适应度值；T为温度，温度越高，接受较差解的概率就会较大。为此，算法在应用过程中通常设置较高的初始温度，提高粒子的全局搜索能力，而经过一定比率降温后，逐渐减小搜索空间，直到收敛到全局最优解。

2.3 ASAPSO选星算法流程

假设当前时刻接收机接收到可见卫星数为n颗，从中选取m颗空间几何结构较好的卫星，基于ASAPSO选星算法的步骤如下：

步骤1提取可见卫星、编码、形成初始种群。

步骤2初始化。

1) 初始化种群中粒子的位置。

2) 设初始温度T0=-fg/ln 0.2。

3) 计算各粒子的适应值fi，平均适应值favg。

4) 令种群中GDOP最小的粒子为初始最佳群体位置gbest，各粒子自身位置为最佳位置pbest。

步骤3进入迭代。

1) 根据式(3)更新权重ω。

2) 根据式(1)和式(2)更新粒子位置和速度。

3) 如果新粒子的适应值优于pbest的适应值，pbest设为当前个体极值；如果当次迭代种群中最佳适应值优于pbest的适应值，pbest设为当前全局极值。

4) 根据式(4)计算接受较差解概率。

5) 生成随机数r，r∈(0,1)，如果r

6) 冷却：Tk+1=λTk，其中，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算法能够提高选星结果的准确性。

仿真时长为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范围内。

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

图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，加速系数c1和c2的较优组合(2,2)、(4,2)、(2,1)，种群规模70≤M≤100，选星算法在该参数下搜索结果更为准确。

2) ASAPSO选星算法的单次选星耗时为2.736 459 s，选星结果误差在0～0.45。该算法能够实现快速选星，且提高了PSO选星算法的搜索准确性。

3) ASAPSO选星算法能够解决PSO选星算法的搜索结果不稳定问题。