基于天牛須種群算法的整周模糊度解算算法

扶篤雄, 紀元法,3*, 孫希延,3,4, 陳紫強

(1.桂林電子科技大學廣西精密導航技術與應用重點實驗室, 桂林 541004; 2.桂林電子科技大學信息與通信學院, 桂林 541004;3.衛(wèi)星導航定位與位置服務國家地方聯(lián)合工程研究中心, 桂林 541004; 4.南寧桂電電子科技研究院有限公司, 南寧 530031)

偽距觀測值和載波觀測值是衛(wèi)星導航定位中兩個最基本的距離觀測值,然而偽距測量精度較低[1-3],因此高精度定位通常是基于載波相位差分定位技術實現(xiàn)[4-6],而載波相位差分技術最難以解決的問題是無法正確確定衛(wèi)星至接收機間的載波相位整周數,即存在整周模糊度問題[7]。

自20世紀80年代提出整周模糊度解算算法以來,中外大量學者對其進行了研究,在此基礎上提出了各類整周模糊度解算算法[8-12]。AFM(ambiguity function method)算法搭建了模糊度函數,避免了周跳對解算結果的影響,但是其運算量過于巨大,無法滿足實時性的要求[13]。LAMBDA(least-square ambiguity decorrelation adjustment)是整周模糊度解算中最常用的算法[14],但其搜索范圍過廣,搜索效率較低。在LAMBDA算法基礎上產生了許多的優(yōu)化算法,MLAMBDA(modified least-square ambiguity decorrelation adjustment)算法通過相關措施降低了算法的計算復雜度,提高了解算效率[15],但無法跳出局部最優(yōu)情況。AWDE(adaptive weighting differential evolution algorithm)算法對DE算法中的差分算子進行自適應調節(jié),避免了早熟、中斷等問題[16],但當參考衛(wèi)星發(fā)生改變時會影響模糊度搜索效率以及模糊度固定率成功率。

為了解決整周模糊度搜索范圍過廣、搜索效率低、易陷入局部最優(yōu)等問題,在天牛須搜索算法(beetle antennae search, BAS)的基礎上,現(xiàn)進行補充和改進,產生一種基于天牛須種群算法的整周模糊度解算算法,有效避免模糊度搜索陷入局部最優(yōu)情況,同時縮短模糊度搜索時間。通過與LAMBDA和MLAMBDA等算法進行比較,并將該算法應用到實際的工程解算當中,以此來驗證該算法的可行性。

1 模糊度代價損失函數

1.1 雙差觀測方程

在RTK定位中,需要使用至少兩個接收機同時觀測多個衛(wèi)星的信號。假設將基準站接收機定義為b,移動站接收機定義為r,兩臺接收機同時接收到衛(wèi)星i與衛(wèi)星j的信號,則可建立載波相位雙差觀測方程為

(1)

(2)

1.2 代價損失函數

在實時動態(tài)測量定位技術(real time kinematic,RTK)流程中,通常采用最小二乘(least squares, LS)或擴展卡爾曼濾波(extended Kalman filter, EKF)的方式對雙差觀測方程進行求解。最小二乘求解時只考慮當前時刻所得數據,割裂了衛(wèi)星定位中的時間相關性,易受到噪聲及其他誤差的影響;而擴展卡爾曼濾波即有考慮當前時刻的數據信息,也融合了前一時刻的定位結果,更能準確反映物體的位置情況[17-18]。EKF在求解雙差觀測方程中的雙差整周模糊度浮點值及其協(xié)方差矩陣時更具優(yōu)勢。

在EKF中,將雙差觀測方程進行線性化,得到狀態(tài)方程為

y=Bb+AN+ε,Qy

(3)

式(3)中:y為載波相位雙差觀測值向量;b為待求解的坐標及時間等參數的參數向量;B為相應的系數矩陣;N為待求解的模糊度參數向量;A為相應的系數矩陣;ε為觀測值的殘差向量;Qy為觀測量的誤差協(xié)方差矩陣。

(4)

2 BACS算法

2.1 標準天牛須搜索算法

標準天牛須搜索算法是一種仿生學啟發(fā)式算法[19-22]。算法模仿了天牛捕食行為:用兩根觸須探索自身左右兩側的食物濃度信息,并不斷向食物濃度高的地方進行移動,最終找到食物。標準天牛須算法的主要流程如下。

(1)假設天牛位于任意位置,且其朝向隨機,并對D維朝向向量進行歸一化處理。

(5)

式(5)中:dir為天牛須的朝向向量;rand為隨機數函數;‖‖為取模函數。

(2)根據天牛所處位置及天牛兩須距離d0表示出天牛左右兩須所處位置。

(6)

式(6)中:xleft為天牛左須所在位置;xm為天牛當前所處位置;xright為天牛右須所在位置。

(3)在天牛左右須所處位置計算完成后,即可通過代價損失函數計算天牛左右兩須所在位置的適應度值f(xleft)和f(xright)。

之后,需要模仿天牛的覓食規(guī)律進行天牛位置的更新,天牛位置的更新可采用以下函數,即

(7)

(4)通過不斷進行迭代,最終找到食物所在位置,即最優(yōu)適應度值所在位置。

2.2 天牛須種群搜索算法

在標準天牛須搜索算法中,由于其自身只需要一個天牛就可完成搜索過程,因此程序設計比較簡單,計算量小于其他算法,復雜度也低。但是天牛須算法中的步長的選擇對最終結果的影響較大,喪失了種群多樣性,對于算法的穩(wěn)定性及算法的尋優(yōu)能力是一個極大的考驗。

針對以上問題,結合整周模糊度求解的實際情況提出了BACS算法。BACS算法首先將單個天牛擴展為天牛種群,將單個天牛的移動尋優(yōu)行為變?yōu)榱朔N群遷徙尋優(yōu),并隨機生成每一只天牛的初始朝向,增加物種的多樣性,降低后期搜索陷入局部最優(yōu)解的概率;其次,采用Nadam算法更正步長,既保證了算法尋找最優(yōu)解的速度,也避免了一部分天牛陷入局部最小值;最后,采用模擬退火算法進行天牛種群的遷徙判斷,提高了種群跳出局部最優(yōu)解的能力,保證了最終解算結果的可靠性。具體改進如下。

2.2.1 天牛種群

單個天牛進行天牛須搜索算法時,由于朝向是完全隨機的,因此其搜索到的結果可能是局部最小值也可能是最優(yōu)值,這一問題在高維度的復雜問題上表現(xiàn)尤為明顯。為了避免算法陷入局部最小值,同時也為了擴展種群的多樣性,將單個天牛擴展為天牛種群進行搜索。

天牛種群可以用矩陣表示,即

(8)

式(8)中:n為求解整周模糊度問題的模糊度維數;m為第m次遷徙。

同時,針對每一個天牛個體,隨機生成其的初始朝向,保證種群擁有朝最優(yōu)值逐步進化的能力。

2.2.2 Nadam算法

Nesterov加速自適應矩估計算法是由斯坦福大學的Timothy Dozat教授在自適應矩估計算法的基礎上加入Nesterov動量形成的[23]。Nadam在保留了ADAM優(yōu)點的基礎上,通過Nesterov動量約束梯度,保證梯度下降的可靠性,可以確保尋優(yōu)方向正確并抑制震蕩[24]。

在Nadam算法中,假設待估計變量為θt,則在t時刻,適應度函數f關于變量θt的梯度函數gt可以表示為

(9)

此時,可以將適應度函數的一階動量和二階動量的更新過程表述為

(10)

式(10)中:mt-1和vt分別為一階和二階動量偏差修正前的值;mt為一階動量偏差修正后的值;vt為二階動量偏差修正后的值。β1為一階動量衰減因子,在深度學習領域默認取值0.9;β2為二階動量衰減因子,在深度學習領域默認取值0.99。β1和β2為變量,取值靈活性較大,在后續(xù)出現(xiàn)時引入上標t表示不同時刻的β1和β2。

(11)

(12)

將一階動量及二階動量同時修正后,即可得到下一時刻待估計變量的值為

(13)

式(13)中:η為全局學習率;σ為無限小的值,在深度學習領域默認取值10-7。

在BACS算法中,采用Nadam算法求解每一只天牛的步長大小。變量θ為天牛的步長值,適應度函數f為天牛須搜索算法的最終適應度函數。之后采用Nadam算法求解出天牛每一次移動的步長。

2.2.3 模擬退火算法

模擬退火算法以固體溫度下降過程為藍本,通過Metropolis準則判斷是否接受新的結果[25]。模擬退火算法具有快速搜索到全局最優(yōu)解的能力,同時在搜索過程中也能夠進行突變,極大地增加了算法跳出局部最優(yōu)值的能力。關于Metropolis準則的描述如下。

首先,計算該時刻與上一時刻的溫度差值,即適應度函數的差值公式為

ΔT=f(xt+1)-f(xt)

(14)

若ΔT<0,則接受t+1時刻的解作為新的解;否則,計算是否選擇該解作為新解的概率,概率計算公式為

(15)

式(15)中:p為接受t+1時刻的解作為新的解的概率;e為自然常數。

在BACS算法中,采用模擬退火算法來判斷天牛群體是否發(fā)生遷徙,通過計算適應度函數的差值對應模擬退火算法中的ΔT值,同時借助模擬退火算法跳出局部最優(yōu)值的能力來增強BACS算法全局尋優(yōu)的能力。

2.2.4 BACS算法流程

BACS算法求解整周模糊度流程如下。

(1)系統(tǒng)初始化。對天牛種群的個體數量、個體維數、迭代次數、天牛朝向、兩須距離及搜索空間進行初始化。

(2)種群初始化。模糊度浮點解的四舍五入值作為天牛種群的初始位置。

資本市場不僅對各產業(yè)部門提升效率具有重要意義，對實現(xiàn)整體金融業(yè)的高質量發(fā)展也極為重要。資本市場效率低下，就會降低自身應對內外部挑戰(zhàn)的能力。現(xiàn)在很多人都在談中國股市發(fā)展脫離了經濟的基本面，這倒可以反過來問，一個不能反映經濟基本面的股市還能叫股市嗎？

(3)記錄單個天牛的搜索過程。采用Nadam算法優(yōu)化天牛的步長設計,記錄每個天牛的搜索過程。

(4)計算當前時刻天牛群的最優(yōu)值。將當前時刻中所有天牛搜索到的數據進行整理,得出下一時刻天牛的可能遷徙位置。

(5)確認下一時刻天牛群所在位置。將當前時刻天牛群所在位置與所有可能遷徙的位置進行對比,利用模擬退火算法判斷遷徙是否有效,若遷徙有效,采用遷徙后的位置作為新的天牛群所在地,若遷徙無效,繼續(xù)采用當前天牛群所在位置。

(6)判斷循環(huán)是否達到最大次數n,若沒有達到,返回步驟(3);若達到則結束循環(huán),并輸出最優(yōu)解。

BACS算法流程框圖如圖1所示。

圖1 BACS算法流程圖Fig.1 Flowchart of BACS algorithm

3 算例仿真與分析

3.1 三維整周模糊度解算實驗

本文研究采用《GPS測量與數據處理》中的經典實驗數據進行仿真[26]。對比LAMBDA算法、MLAMBDA算法、BAS算法、BAS-Nadam算法、BACS算法共5種算法,分析其解算性能。三維下的雙差整周模糊度浮點解及協(xié)方差矩陣為

(16)

(17)

設初始天牛種群數為20,種群維度為3,最大迭代次數為100。單次運行BAS算法、BAS-Nadam算法和BACS算法,得到三種算法的適應度值進化曲線如圖2所示。

圖2 各算法適應度值進化曲線對比Fig.2 Comparison of fitness evolution curves of various algorithms

由圖2可知,在模糊度搜索過程中,隨著天牛種群向最優(yōu)模糊度區(qū)域的不斷逼近, BAS算法和BAS-Nadam算法的適應度值會不斷減小。經過多次實驗表明,BAS算法經過迭代30次左右后可到達最優(yōu)適應度值區(qū)域附近,BAS-Nadam算法經過改進天牛搜索步長,迭代20次左右即可到達最優(yōu)適應度值區(qū)域附近。而BACS算法為避免陷入局部最優(yōu)情形,引入了模擬退火算法,在適應度值到達最優(yōu)值區(qū)域附近后會跳出該區(qū)域,然后重新進行搜索,以此保證最優(yōu)解的準確性。

在模糊度解算過程中,存在局部最優(yōu)情況,當模糊度最優(yōu)解無法被正確解算出來時,會從局部最優(yōu)中選擇一個最佳結果作為模糊度最優(yōu)解,這些局部最優(yōu)情況加上模糊度實際最優(yōu)一起組成模糊度最優(yōu)解備選組。為了更清楚模糊度最優(yōu)解備選組在空間中的分布情況,對模糊度解最優(yōu)解備選組進行繪圖如圖3所示。

圖3 各算法模糊度最優(yōu)解備選組對比Fig.3 Comparison of candidate groups of optimal ambiguity solutions of each algorithm

BAS算法搜索過程存在較大的偶然性,由圖3可以得知,其模糊度最優(yōu)解備選組包含28種可能的模糊度解算結果,增大了模糊度搜索的難度。BAS-Nadam算法通過引入Nadam算法,優(yōu)化搜索天牛須搜索步長后,模糊度最優(yōu)備選組中只包含9種可能,大大降低模糊度搜索難度。在BACS算法的模糊度最優(yōu)解備選組中,只包含2種可能,且其中一種為正確的模糊度最優(yōu)解。

BAS、BAS-Nadam、BACS算法的運算時間情況用柱狀圖顯示如圖4所示。

圖4 各算法運行時間對比Fig.4 Comparison of running time of each algorithm

由圖4可以看出,通過對三種算法每次運行時間進行對比,BAS算法解算時間最短,每次運行時間集中在0.005 s附近;BAS-Nadam算法解算時間略長,每次運行時間集中在0.009 5 s左右;BACS算法解算時間最長,每次解算時間在0.015 s左右。

為對比分析三維下各算法解算的準確性及可靠性,重復實驗以上5種算法100次,每次最大迭代次數為100。其解算結果,平均解算時間(此處平均解算時間與3.2節(jié)實驗的平均解算時間均為100次重復實驗的收斂時間總和取平均)及解算成功率如表1所示。

表1 5種算法對比情況Table 1 Comparison of five algorithms

由表1可知,BAS算法雖然解算速度快,但解算過程隨機性過大,解算結果不穩(wěn)定,導致解算成功率不高。BAS-Nadam算法雖然能有效減小解算過程中偶然性的影響,但會陷入局部最優(yōu)情況,錯誤的將局部最優(yōu)解當作模糊度最優(yōu)解,導致模糊度解算失敗,從而降低模糊度解算成功率。BACS算法由于引入模擬退火算法,即使搜索過程中陷入局部最優(yōu)情況,也能及時跳出局部最優(yōu)區(qū)域,然后重新搜索更優(yōu)的模糊度最優(yōu)解。通過與LAMBDA算法以及MLAMBDA算法進行對比,BACS在解算時間方面略優(yōu)于LAMBDA算法和MLAMBDA算法,比LAMBDA算法快了0.047 3 s,比MLAMBDA算法快了0.007 7 s;在解算成功率方面與兩種算法處于伯仲之間。

BACS算法雖然能很好地解決3維模糊度問題,但隨著多頻多系統(tǒng)的應用,在實際的RTK定位過程中,會普遍存在高維模糊度解算問題,因此在下文進行了高維模糊度解算實驗。

3.2 多維整周模糊度解算實驗

隨著不同各國衛(wèi)星系統(tǒng)的發(fā)展,支持多系統(tǒng)的高精度定位板卡成為主流,多系統(tǒng)的引入,大大增大了參與解算的衛(wèi)星數,提高了模糊度搜索解算的復雜度。因此,多維的整周模糊度解算性能是整周模糊度解算算法的關鍵指標之一。針對BACS算法,進行了3維、6維及12維的模糊度解算實驗。其中3維實驗數據與3.1節(jié)實驗一致,12維和6維浮點解矩陣為

(18)

其解算過程的適應度變化曲線如圖5所示。

圖5 高維BACS算法適應度值進化曲線Fig.5 Fitness evolution curve of high-dimensional BACS algorithm

不管是對于6維還是12維整周模糊度解算,BACS算法即使短時間內陷入局部最優(yōu),也能在后續(xù)的時間內重新搜索到模糊度最優(yōu)解,從而跳出局部最優(yōu)。

6維和12維BACS算法運行時間如圖6所示。由圖6可知,隨著模糊度維數的增加,模糊度解算復雜度提升,導致解算時間相應增加。6維模糊度解算,BACS算法單次運行時間集中在0.031 s附近,而對于12維模糊度解算,BACS算法單次運行時間集中在0.068 s附近。

圖6 高維BACS算法運行時間圖Fig.6 Running timediagram of high-dimensional BACS algorithm

為對比分析不同維度下BACS算法解算的準確性及可靠性,針對3維、6維以及12維模糊度,重復實驗BAC種算法100次,每次最大迭代次數為100。其平均解算時間、解算成功率如表2所示。

表2 BACS算法在不同維數下的比較Table 2 Comparison of BACS algorithm in different dimensions

由表2可知,隨著模糊度維數增加,算法的平均收斂時間由3維的0.014 8 s增加至6維的0.312 s,12維的平均解算時間增至0.068 s;模糊度解算成功率也由3維的99%降低至6維97%,再到12維的92%。

雖然隨著模糊度維數的增加,BACS算法平均解算時間也相應增加,解算成功率也有所下降。但BACS算法的解算速度和解算成功率仍然高精度實時定位的要求。

3.3 實際工程推廣應用

為檢驗算法在實際工程應用環(huán)境下的性能,將BACS算法引入RTK實驗。采用單頻U-blox接收機進行數據采集,共采集693個歷元數據,基準站和移動站間距離為2.1 m,采集地點為桂林電子科技大學金雞嶺校區(qū)圖書館樓頂。

利用RTKlib軟件安裝包中的“pos2kml.exe”將位置文件轉換成.kml文件,再經Google Earth展現(xiàn),得到數據采集地點示意圖如圖7所示。

通過對移動站數據進行分析,采用衛(wèi)星仰角截止角為15°,移動站可見衛(wèi)星情況如圖8所示,圖中的橫坐標為時間,縱坐標為GPS衛(wèi)星編號。

圖8 移動站可見衛(wèi)星情況Fig.8 Satellite visible in mobile station

本次實驗中只采用單頻GPS數據參與解算,由圖8可知。在采集數據的時間段內共有8顆GPS衛(wèi)星可見,可見的8顆衛(wèi)星在后續(xù)解算過程中全部參與解算。

利用BACS算法進行RTK定位實驗,其最終的定位結果如圖9所示。由圖9可知,BACS算法在x、y、z方向上的誤差分別為±0.008、±0.01、±0.01 m,可以實現(xiàn)厘米級定位。

圖9 定位結果Fig.9 Positioning results

對于單頻單GPS系統(tǒng)而言,BACS算法的解算速度夠快,能很好地保證RTK解算的實時性,解算成功率和定位精度使得RTK解算的魯棒性也能得到保證,該算法能很好地滿足單頻單系統(tǒng)工程解算要求,實現(xiàn)單頻單系統(tǒng)下的高精度實時定位。

4 結論

通過利用BACS算法進行不同維度下的模糊度解算實驗以及將該算法引入單頻單系統(tǒng)的工程解算當中,從BACS算法的運行時間、解算成功率和定位精度等方面進行分析,得出以下結論。

(1)針對3維模糊度解算情況,BACS算法能在保證解算成功率的情況下,解算時間略優(yōu)于LAMBDA算法和MLAMBDA算法。

(2)針對高維模糊度解算情況,隨著模糊度維度的增加,模糊度解算難度增加,BACS算法的成功率略有下降,但12維模糊度解算成功率仍能穩(wěn)定保持在92%及以上;此外,BACS算法的運算時間隨著模糊度維度的增加而變長,但解算時間仍能滿足實時性的需求。

(3)將BACS算法引入單頻單GPS系統(tǒng)的工程解算當中,能很好地實現(xiàn)定位過程的實時性和魯棒性,定位結果能達到厘米級。

在后續(xù)的研究工作中,將進一步針對BACS算法對于高維模糊度解算成功率有所下降的問題進行完善。同時,也會將BACS算法引入多頻多系統(tǒng)工程解算應用當中。