基于哈里斯鷹優化算法的多GNSS快速選星方法

楊 光，屈德新*，張更新

(1.南京郵電大學 通信與信息工程學院，江蘇 南京 210003；2.南京郵電大學 通信與網絡技術國家地方聯合工程研究中心，江蘇 南京 210003)

0 引言

隨著全球導航衛星系統(Global Navigation Sate-llite System,GNSS)的快速發展,越來越多的領域將GNSS運用到工程當中,從而使得更多的人從中受益。然而,在導航系統快速發展的同時,為了提高適用性以及可靠性,對該系統的要求也越來越嚴格,其中就包括更短的定位耗時以及更高的定位精度。由此,全世界各個有能力的國家都將發展自己的導航衛星列為國家的長期發展規劃。截至目前,全球已經建成了4套完善的全球定位系統:中國的BDS、歐盟的Galileo、俄羅斯的GLONASS以及美國的GPS,已有超過120顆全球導航衛星在軌運行,能夠實現在同一地點有多顆衛星為用戶提供服務。然而,隨著可見星數量的快速增加,如果將所有可見星同時應用到定位中去,計算效率將會大幅度降低,其對定位精度的提升效果有限,因此,如何快速地從所有可見星中選出最優構型成為一個熱門問題。

選星是在獲取當前所有可見星位置、鐘差等信息后,確定一定數量的衛星參與定位解算的過程。傳統選星過程以最小幾何精度因子(Geometric Dilution of Precision,GDOP)遍歷法[1]為基礎,此外還有最大四面體體積法[2]、最大行列式法[3]、幾何布局算法[4]、最優GPS遞歸算法[5]、GPS/Galileo組合導航定位系統選星算法[6]等。目前主要還是依據最小GDOP準則進行選星操作,然而如何簡化選取擁有最小GDOP值的衛星組合成為了一個急需解決的問題。Mosavi等[7]提出了基于進化算法(EA)的自適應濾波技術來計算GDOP的方法,但該方法存在一定的誤差。宋丹等[8]提出了一種基于遺傳算法的選星方法,該方法能夠快速準確地實現多個GNSS下選星顆數大于4的選星。徐小鈞等[9]提出了一種將選星數目和GDOP值同時作為目標的基于NSGA-II遺傳算法的多星座選星方法,該算法能夠綜合優化GDOP和選星數目,同時保證較小的計算量和更高的定位精度。張兆龍等[10]提出了一種將BP神經網絡和遺傳算法結合的選星算法,既大大減小了計算量,又增加了選星的準確率。王爾申等[11]提出了一種基于人工魚群算法的粒子群優化選星算法,利用人工魚群算法良好的全局收斂特性,克服粒子群算法易于陷入局部最優的缺點,使其準確率優于標準PSO選星算法。王暉等[12]提出了一種顧及信噪比的蝙蝠選星算法,通過設置信噪比閾值,剔除信號受干擾的衛星,結合選星算法的高效率優點,減少選星耗時。余德熒等[13]提出了一種基于灰狼優化(Grey Wolf Optimizer,GWO)算法的快速選星方法,利用自適應收斂因子和信息反饋機制,避免局部極值,能夠大幅度減小計算量。石濤等[14]提出了一種利用多種群并行遺傳算法(Parallel Genetic Algorithm,PGA)進行快速選擇當前最優可見星組合的方法,該方法可以有效地在典型高軌環境下快速準確地完成選星。邱明等[15]提出了基于帝國競爭優化算法的雙目標選星算法,通過引入可見星仰角和方向角先驗信息,同時約束GDOP以及選星數,提高選星靈活度。

雖然上述算法在不同程度上提高了選星效率,但為了避免局部最優,需要多次實驗尋找最優的參數配置,從而實現尋得全局最優解。哈里斯鷹優化(Harris Hawks Optimization,HHO)算法是Heidari等[16]于2019年提出的一種新型群體智能算法,整個尋優過程包括探索、探索與開發轉換和開發3個階段,具有原理簡單、控制參數少和全局搜索能力出色等特點。HHO算法相較于其他成熟的元啟發式技術而言,提供了非常有前途的結果,有時甚至具有競爭性,同時以靈活的結構、高性能和高質量的結果越來越受到研究人員的關注,在作業車間調度[17]、神經網絡[18]、惡意軟件檢測[19]、定位解算[20]和結構體壽命預測[21]等領域得到廣泛應用。

鑒于目前沒有將HHO算法應用于GNSS系統快速選星的研究,本文將HHO算法引入到多GNSS組合導航選星過程中,建立了基于HHO算法的快速選星模型。通過對多GNSS下不同時間、不同選星顆數、HHO算法種群數以及算法迭代次數進行仿真實驗,以GWO、改進粒子群算法(Improved Particle Swarm Optimization,IPSO)以及遍歷法結果作為對比,驗證了HHO算法的快速選星能力和高準確率。

1 HHO算法

1.1 算法背景

HHO算法靈感來源于哈里斯鷹在自然界中的合作行為和追逐方式,稱為“突襲”,在該策略中,幾只老鷹合作從不同方向撲向獵物,試圖以出乎意料的方式將其捕獲。整個搜索過程可以分為3個階段:① 探索階段;② 探索與開發轉換階段;③ 開發階段。

1.2 數學模型

在每次迭代過程中,為了確定下一次位置更新策略,將擁有最優適應度值的哈里斯鷹作為獵物或者預期的獵物。

1.2.1 探索階段

此階段哈里斯鷹會隨機飛抵某些位置,并根據2種策略探索獵物。如果每種飛行策略機會p相等,隨機生成p的大小,當p≤0.5時,哈里斯鷹根據其他成員和獵物的位置進行棲息;當p>0.5時,則隨機棲息在鷹群活動范圍內的大樹上,具體模型為:

(1)

(2)

式中:X(t+1)為下一次迭代中鷹的坐標向量,Xrabbit(t)為獵物的坐標(即擁有最優適應度的個體坐標),X(t)為當前鷹的位置向量,r1、r2、r3、r4和p為(0,1)的隨機數,UB、LB為位置數據的上下限,Xrand(t)為在所有已知的鷹群中隨機選擇的鷹的坐標,Xm(t)為坐標的平均值,N為鷹群大小,Xi(t)為當前第i只鷹的坐標。

1.2.2 探索到開發的轉換

HHO算法會從探索轉到開發階段,隨后根據獵物的逃逸能量在不同的開發行為之間進行轉換。獵物逃跑會導致能量下降,逃逸能量可表示為:

(3)

式中:E表示獵物逃逸能量,T為最大迭代次數,t為當前迭代次數,E0為能量初始狀態,是(-1,1)的隨機數。當|E|≥1時,哈里斯鷹處于探索階段,反之進入開發階段,進而采取不同的更新策略。

1.2.3 開發階段

當鷹處于開發階段時,會對之前發現的預定獵物進行突襲捕捉,同時,獵物也在嘗試逃脫追捕。因此,在實際情況下會根據獵物狀態采用不同的捕獵風格。HHO依據獵物的逃逸風格和哈里斯鷹的追逐策略,提出了4種策略去模擬攻擊階段。此處定義r用來表示獵物在突襲前是否有機會逃脫,當r<0.5時表示有機會逃脫,反之則沒有機會。

① 軟圍攻

在r≥0.5且|E|>0.5時,獵物有足夠的能量,但沒有逃脫的機會,只能通過隨機跳動來嘗試逃脫,在此過程中哈里斯鷹輕柔地包圍獵物,使其疲憊后再進行突襲。此行為可以建模為:

X(t+1)=ΔX(t)-E|JXrabbit(t)-X(t)|,

(4)

式中:ΔX(t)為最優個體和當前個體的差值,J為獵物逃跑時移動的距離。

ΔX(t)=Xrabbit(t)-X(t),

(5)

J=2(1-r5),

(6)

式中:r5為(0,1)的隨機數。

② 硬圍攻

在r≥0.5且|E|≤0.5時,獵物既沒有逃脫的機會,也沒有足夠的逃脫能量,此時哈里斯鷹采用硬包圍的方式捕獲獵物,該行為可以建模為:

X(t+1)=Xrabbit(t)-E|ΔX(t)|。

(7)

圖1為哈里斯鷹進行硬圍攻時的示例。

圖1 硬圍攻矢量示例Fig.1 Hard siege vector example

③ 漸進式快速俯沖的軟包圍

在r<0.5且|E|>0.5時,獵物有機會逃脫,并且有足夠的能量,因此哈里斯鷹需要在進攻前形成一個更加智能的軟包圍圈,采用2種策略實施,根據情況選擇其中一個策略。

策略1:

Y=Xrabbit(t)-E|JXrabbit(t)-X(t)|。

(8)

策略2:

Z=Y+S×LF(D),

(9)

式中:D為問題維度,S為一個D維的隨機向量,LF為Levy函數。

(10)

式中:

(11)

u和v為(0,1)的D維隨機向量,β=1.5,Γ( )為伽瑪函數。策略選擇標準如式(12)所示:

(12)

式中:F()為適應度函數,即GDOP值。

這一過程的矢量示例如圖2所示。

圖2 漸進式快速俯沖的軟包圍矢量示例Fig.2 Example of soft encirclement vector for progressive rapid subduction

④ 漸進式快速俯沖的硬包圍

在r<0.5且|E|≤0.5時,獵物有機會逃脫,但能量不足,此時哈里斯鷹在突襲前形成一個硬包圍圈,縮小和獵物的平均距離,策略如下:

(13)

Y=Xrabbit(t)-E|JXrabbit(t)-Xm(t)|,

(14)

Z=Y+S×LF(D)。

(15)

2 基于HHO算法的快速選星方法

2.1 哈里斯鷹算法適應度函數

在多GNSS中,用戶從接收機獲取的自身位置精度與接收機中觀測到的參與定位的衛星幾何構型和偽距值有關,其中幾何構型用GDOP表示。其值越小,表示利用該衛星構型進行定位時定位精度越高,因此選用GDOP值作為HHO算法的適應度函數。

(16)

式中:tr(*)表示取矩陣的跡,H為觀測矩陣。在多GNSS中,同時可觀測到BDS、Galileo、GLONASS以及GPS組成的多顆衛星,此時H可表示為:

(17)

式中:下標分別代表對應所屬的衛星系統。假設某一個系統有n顆衛星參與定位,則此時H*為n行3列矩陣,3列分別是各個衛星與觀測站連線在(x,y,z)軸上的方向余弦,1*為n行1列的純1向量,0*為n行1列的純0向量。

2.2 哈里斯鷹選星算法設計

圖3 HHO選星算法流程Fig.3 Flowchart of HHO satellite selection algorithm

具體的選星步驟如下:

步驟①:提取可見星。根據導航電文,獲取當前仰角大于5°的所有可見星。

步驟②:編號。將獲取的所有可見星按PRN由小到大編號為:1,2,3,…,m。

步驟③:初始化種群。設種群數為j,從m顆可見星中隨機抽取n顆進行組合,產生j只不同的鷹構成一個種群。

步驟④:計算適應度值。計算每只鷹對應的GDOP值作為該只鷹的適應度值,將適應度值最小的鷹作為當前目標組合。

步驟⑤:迭代更新。計算當前獵物能量E,隨機生成r,根據值的不同決定采用探索還是不同的開發策略,從而產生新的衛星組合,計算更新后的適應度值,將本次迭代適應度值與原目標組合適應度值比較,將適應度值小的組合作為本次迭代目標組合。不斷重復本步驟,直至達到最大迭代次數,當前目標組合即最優衛星組合。

3 HHO選星算法性能分析

針對智能優化算法在多GNSS選星中的應用,參數選擇是決定算法性能的關鍵。在HHO選星算法中,主要影響選星性能的參數為種群規模(鷹的數量)和迭代次數(搜索次數),規模和次數的差異對選星誤差和耗時有著較大的影響。

群體智能優化算法是將種群逐漸向真值逼近的算法,但因存在隨機性和初始種群選取的差別,每次結果并不一定能夠與真值保持一致。因此,為了具象化算法的選星性能,對算法進行了多次蒙特卡羅實驗,最后統計出GDOP最大、最小和平均值,最大值表示此時衛星構型最差,最小值表示此時構型最優,平均值則反映了算法的平均選星性能。遍歷法的選星結果是最優結果,將遍歷法結果與HHO法選星結果比較可以看出HHO法選星的性能。

3.1 鷹群個體數對HHO選星性能的影響

將迭代次數固定為40,鷹群個體數依次設置為20、40、60、80、100,各進行100次蒙特卡羅實驗求取均值,分析鷹群個體數對選星性能的影響,結果如圖4～圖6和表1所示。

圖4 種群數引起的GDOP值變化Fig.4 Changes in GDOP value caused by population number

圖5 種群數引起的計算耗時變化Fig.5 Changes in calculation time due to population number

圖6 種群數引起的GDOP誤差變化Fig.6 Changes in GDOP error due to population number

表1 鷹群個體數對算法性能影響

分析圖5和表1的數據可知,增加種群規模也會增加選星算法的耗時,由開始的0.057 1 s逐漸增加到0.279 0 s,但仍舊低于遍歷法的耗時?？梢奌HO選星算法能夠實現在保證準確率的前提下快速選出最優構型。

3.2 迭代次數對HHO選星性能的影響

將鷹群個體數固定為40,迭代次數依次設置為20、40、60、80、100,進行同3.1節的實驗,結果如圖7～圖9和表2所示。

圖7 迭代次數引起的GDOP值變化Fig.7 Changes in GDOP values caused by the number of iterations

圖8 迭代次數引起的計算耗時變化Fig.8 Change in computation time due to the number of iterations

由圖7～圖9可以看出,隨著迭代次數的增加,其選星性能變化類似于種群數對HHO選星性能的影響。在迭代次數增加過程中,選星性能逐漸提高,最終GDOP值逼近遍歷法的選星結果,可見,通過增加迭代次數能夠有效改善HHO選星算法性能。

表2 迭代次數對算法性能影響

通過觀察表2的數據可以直觀地發現迭代次數對HHO選星算法性能的影響。

結合3.1和3.2節的仿真分析可知,種群規模和迭代次數對于HHO選星算法的性能起著關鍵作用,需要在誤差和耗時之間做折中。因此要想最大限度地保證HHO選星的性能,正確地選取種群規模和迭代次數至關重要。由表1可以看出,在種群規模數達到40時,GDOP誤差變化不再明顯;在表2中,迭代次數在40～60誤差變化率為0.341%,而在60～80變化率只有0.125 8%,因此,在迭代次數達到60后誤差下降速度不顯著。綜上所述,在下一節的仿真驗證中,采取種群規模數為40、迭代次數為60,以實現在保證選星準確率的前提下盡量降低選星時間。

4 仿真驗證與結果分析

在定位前進行選星操作可以從多顆冗余星中選出最優的衛星構型,從而保證定位精度。為了驗證HHO算法的選星性能,利用衛星工具包(Satellite Tool Kit,STK)導出BDS、Galileo、GLONASS以及GPS的星歷數據,進行仿真分析。仿真所用軟件為Matlab 2016b和STK 11.2,計算機搭載CPU處理器(i7-11800H,2.3 GHz)、RAM 32 GB。

實驗1:在STK中設置接收機的位置為南京(118.78°,32.10°,0),加入BDS、Galileo、GLONASS和GPS共68顆衛星,起始時間為2022-10-13T04:00:00,導出不同時刻接收機能同時獲取的仰角大于5°的衛星星歷數據。將選星算法的種群規模設置為40,迭代次數設置為60,選7顆星,仿真時長為90 min,仿真步長為1 min。仿真結果如圖10、圖11和表3、表4所示。

圖10 不同選星時間GDOP值誤差變化Fig.10 GDOP value error changes at different time of satellite selection

圖11 不同選星時間耗時變化Fig.11 Time consuming changes at different time of satellite selection

表3 不同算法選星GDOP誤差

表4 不同算法與遍歷法的選星耗時差值

圖10和圖11分別為不同時刻的HHO法、GWO法、IPSO法和遍歷法選星的GDOP和耗時差值。由圖10可以看出,在選星的不同時刻,3種優化算法的選星結果均逼近遍歷法選星,GDOP誤差最大接近0.08,但HHO法選星GDOP誤差普遍低于另外2種算法,結合表3不難發現,在90 min內,HHO法選星結果的GDOP平均誤差為0.008 2,遠低于另外2種優化算法的0.010 1和0.010 5。由圖11可以看出,3種優化算法選星與遍歷法選星耗時差異較大,選星耗時遠低于遍歷法選星耗時,其中HHO法選星耗時高于GWO法,低于IPSO法,主要原因是GWO算法實現最為簡單,算法的復雜度最低,該算法實現僅需3個階段:包圍獵物、追蹤獵物、攻擊與搜索獵物,且迭代公式的復雜度較低。而HHO算法雖也分3個階段,但在第3階段中需要依據獵物的逃逸風格和哈里斯鷹的追逐策略,從4種策略中選擇一種去模擬該階段,且迭代公式的計算復雜度略高于GWO法。而IPSO法由于引入粒子交叉和淘汰替換機制,復雜度高于HHO法。結合表4數據,GWO法耗時差值最大,為0.477 5 s,其次為HHO法,差值為0.342 8 s,最小值為IPSO算法的0.329 3 s。綜上,HHO法耗時雖然略高于結構較為簡單的GWO法耗時,但其GDOP誤差卻遠低于另外2種算法,在實際選星過程中性能滿足準確率和實時性的要求,能夠實現在保證準確率的前提下快速選星。

實驗2:采用實驗1的參數,進行30次重復實驗求均值,仿真HHO法在2022-10-13T04:00:00選擇不同衛星數時的選星性能,此時仰角大于5°的可用星有17顆。在BDS/GPS雙系統時選5顆星,在BDS/GPS/GLONASS三系統時選6顆星,在BDS/GPS/GLONASS/Galileo四系統時選7、8、9顆星。仿真結果如圖12～圖15和表5、表6所示。

圖12 不同選星數GDOP值變化Fig.12 GDOP value changes with different number of selected satellites

圖13 不同選星數GDOP計算誤差變化Fig.13 Calculation error variation of GDOP with different number of selected satellites

圖14 不同選星數耗時變化Fig.14 Time consuming change of different satellite selection number

圖15 不同選星數節省時間變化Fig.15 Different number of satellites to save time change

表5 不同選星數選星GDOP值

表6 不同選星數選星耗時

5 結論

本文提出了一種基于HHO的多GNSS星座選星算法,通過Matlab仿真分析驗證了算法性能。首先給出了HHO算法的模型;接著將HHO算法引入到選星過程中,以GDOP值作為適應度函數來衡量選星準確率,給出了HHO選星算法的實現步驟;之后考慮了HHO算法的參數設置對選星性能的影響,通過仿真來確定合適參數的選取;最后利用STK導出的衛星星歷進行性能驗證。結論如下:

① HHO法選星性能受迭代次數和種群數影響,選星準確率與其成正比關系,但選星效率會下降。選取種群規模為40,迭代數為60可以兼顧選星準確率和效率。

② 對STK導出的90 min內數據,利用HHO法、GWO法、IPSO法與遍歷法對比,HHO法選星GDOP平均誤差為0.008 2,平均耗時差值為0.342 8 s,可見HHO選星性能優異。

③ HHO選星算法對選多星有優勢,選星數越多,性能越好,當種群數量為40,迭代次數為60,選星數達到9顆時,HHO選星算法相較于遍歷法計算效率提升了75.168 4%,而此時GDOP誤差為0。

④ HHO選星算法在實際應用時可根據自身需求,通過改變種群規模數和迭代次數在實時性和準確率之間做取舍。將來的研究將聚焦于自適應選取參數、多算法混合使用和單算法優化等方面,以提高選星性能。