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選星算法的搜索結果不穩定問題。