基于改進蝴蝶搜索算法的DGPS 整周模糊度快速解算

尚俊娜，羅照旺

（杭州電子科技大學 通信工程學院，杭州 310018)

在差分全球定位系統（Differential Global Positioning System,DGPS）定位方式中，載波相位觀測值[1]是否能夠達到厘米級甚至毫米級的定位結果，關鍵在于能否正確快速地解算出整周模糊度。通常解算整周模糊度的關鍵步驟為：首先通過最小二乘估計得到模糊度的浮點解[2]和協方差矩陣；其次，利用去相關操作處理協方差矩陣，從而降低模糊度間的相關性；最后通過搜索算法得到模糊度固定解[3-5]。

近年來，大量學者在模糊度解算方法上不斷探索，在提高搜索效率和降低模糊度之間的相關性方面進行了研究，尤其在搜索算法方面采用了現代啟發式算法。劉新華等[6]提出了一種改進蟻群算法（Improved Ant Colony Optimization,IACO），在傳統蟻群算法的基礎上引入自反饋因子，改善了傳統蟻群的尋優性能，將整周模糊度解算成功率提升了3%。然而，蟻群算法容易缺乏初始信息素，從而導致模糊度解算時間較長。歐陽利等[7]提出了一種基于短基線整周模糊度求解的改進雞群優化算法（Improved Chicken Swarm Optimization,ICSO），對模糊度解算過程進行優化，提高了搜索速度和求解成功率，但是在基線不固定時或者在長基線環境下存在搜索空間變大、搜索效率下降和模糊度搜索速度變慢的問題。針對模糊度解算時間長、效率低的問題，張波等[8]提出了改進粒子群（Improved Particle Swarm Optimization,IPSO）的模糊度解算優化算法，通過引入sin 函數對慣性權重進行改進，縮短了模糊度解算時間。上述算法在模糊度解算問題上雖然取得了一定的性能提升，但現代啟發式算法自身所固有的尋優精度不高、收斂速度慢、易于早熟收斂等問題還有待進一步解決，這使得在提高模糊度搜索效率和模糊度解算成功率等問題上仍然有進一步的優化空間。

為了提高模糊度固定解的搜索成功率，本文提出了一種改進的蝴蝶搜索算法（Improved Butterfly Optimization Algorithm,IBOA）來求解整周模糊度。首先，引入動態切換概率來權衡蝴蝶搜索算法（Butterfly Optimization Algorithm,BOA）中全局搜索和局部搜索的比例，從而提高全局搜索能力；其次，在BOA 算法的香味系數中加入一個自適應權重，在全局搜索和局部搜索階段引入新的位置更新策略，不僅提升了全局尋優精度，還改善了跳出局部最優的能力；最后，通過實驗對比IBOA 算法與LAMBDA 算法解算的整周模糊度。

1 載波相位模型分析

載波相位觀測量是通過接收機捕獲到的相位與自身生成的相位之差得到的，載波相位觀測量的觀測精度比偽距觀測量更高，但其中包含著未知的整周模糊度，如何快速準確地求解這個未知數是實現高精度載波相位相對定位的關鍵所在。

1.1 模糊度最小二乘估計模型

在實現高精度載波相位相對定位時，通常對站星間載波相位雙差觀測方程進行處理[9]。假設接收機q和r同步觀測衛星s和k，那么在接收機q和r之間求得單差觀測值后，再在衛星s和k之間作差求得雙差觀測值，其方程為：

將式(1)進行載波相位雙差模型線性化，其數學模型為：

其中，y為載波相位觀測值；N為整周模糊度向量；b為兩接收機之間的基線向量；A、B均為設計矩陣；ε為觀測噪聲；D(y)和Qy分別為觀測量y的方差陣和協方差陣，是其單位先驗方差。

在GPS 領域，一般采用最小二乘方法或Kalman濾波方法[10]求解式(2)。由于式(2)中不僅包含未知的實數參數，還包含未知的整數信息，因此，式(2)被稱為混合整數模型[11]。通過最小二乘估計準則求解式(2)，有：

如果先不考慮整周模糊度N的整數特性，利用標準最小二乘方法來解算，可以得到整周模糊度N和基線向量b各自的浮點解及其協方差矩陣和：

在解算出N和b的浮點解后，再考慮整周模糊度的整數特性，式(3)可以進一步展開：

由于b為實數向量，所以當，且取最小值時取得最小值。因此，式(3)的最小問題就轉化為：

1.2 模糊度降相關

由式(4)得到的N和b的浮點解存在非常強的相關性，若不采用降相關方法處理就直接進行整周模糊度的搜索，會造成模糊度搜索時間過長。為了獲得更好的搜索效率，在搜索前需要先進行模糊度降相關操作。本文采用Z 變化[12]的降相關處理方法：

其中，z和Q分別為N和經整數變化后的向量，為經整數變化后的浮點解。注意的是，為保證N和z之間的變化是整數變換，z? Zn×1,Z?Zn×n，Z和Z-1中的元素均為整數。

式(6)轉換成一個新的整數最小二乘問題：

通過Z 變化降低協方差矩陣之間的相關性，這樣能夠減少一些搜索時間，由于Z 變化自身的運算量增加了模糊度解算的整體計算時間，因此，想進一步提升搜索效率，需要使用一個高效的搜索算法。

2 IBOA 算法求解整周模糊度

模糊度搜索的本質是在搜索空間中找到J(z)的最小值。為了進一步提升模糊度的搜索效率，本文提出了一種IBOA 算法進行模糊度搜索。BOA 算法是一種模擬覓食行為的新型優化技術[13-15]，蝶群中的每個蝴蝶通過感知其他蝴蝶散發出的香味進行位置更新，并且每個蝴蝶的位置是解空間中的一個解。

2.1 BOA 算法的基本原理

2.1.1 初始化種群位置

假設在一個D維搜索空間中，存在n只蝴蝶，第i只蝴蝶在D維空間中的位置為：

其中，1≤i≤n，1≤d≤D，xi,d是第i只蝴蝶在d維空間的位置。

為了更好地解算整周模糊度，搜索空間的邊界條件可以設置為：

其中，Xmin和Xmax分別表示搜索空間的下限和上限。

蝴蝶Xi的第j維參數的初始化公式為：

其中，R是[0,1]之間的隨機數。

蝴蝶在進行位置更新時，需要保證位置更新后的向量元素處于預先設定的搜索空間之內。若超出范圍，則需要進行修正。修正方法為：

2.1.2 更新蝴蝶位置

蝴蝶位置更新分為兩個階段：在全局搜索階段，蝴蝶個體會朝著產生香味最濃的蝴蝶進行位置更新；在局部搜索階段，當蝴蝶個體感知不到其它蝴蝶的香味時，就會隨機移動。在迭代階段，為了控制全局搜索和局部搜索的占有比例，傳統的BOA 算法采用一個切換概率p=0.8的固定值與每次迭代產生的一個隨機數rand進行判斷。如果rand＜p，則進行全局搜索；反之則進行局部搜索。蝴蝶的位置更新為：

其中，c表示感覺模態；α表示功率指數，反映蝴蝶香味吸收程度的變化。α和c的取值范圍都在[0,1]之間。I表示刺激強度，在整周模糊度搜索[14,15]中將I替換成目標函數J(z)，其中z用蝴蝶位置Xi表示：

2.1.3 搜索空間的構建

BOA 算法尋優本質是在備選空間中搜索能夠使目標函數J(Xi)取得最小值的一組解向量，所以搜索空間中必須包含正確的模糊度整數解。因此，在DGPS基線定位中可以利用基線長度構造搜索空間[16,17]。搜索空間為：

基線長度可以約束搜索空間，通過多次測量取平均值來減小基線長度的測量誤差。例如1.0 m 長的基線，L1 載波波長為19.03 cm，則。其中，l為基線長度，[l/λ]表示向上取整。因此，邊界條件確定為xmax,j=[zj]+6，xmin,j=[zj] -6。通過基線長度來約束搜索空間，一般基線長度測量誤差比較小，如果出現基線長度測量誤差大的情況，會造成搜索空間變大和候選值冗余的問題。因此，下文提出的IBOA算法搜索速度較快，即使搜索空間變大了，對解算效率影響很小。

2.2 IBOA 算法

在整周模糊度解算問題上傳統的BOA 算法還存在很多問題，比如收斂速度慢和容易陷入局部最優值等。為了解決這些問題，本文從搜索策略上對傳統BOA 算法進行改進，提出一種IBOA 算法。該算法引入非線性遞減函數P改進切換概率，有效地平衡了全局搜索和局部搜索的比例，提升了算法的收斂性；引入自適應權重S對香味公式進行改進，增強算法的尋優能力。

2.2.1 動態切換概率策略

在BOA 算法中，采用了一個固定值切換概率p與每次迭代產生的一個隨機數進行比較，從而實現全局搜索和局部搜索之間的切換比例。如果p的取值越大，進行全局搜索的概率就越大；反之，局部搜索的概率就越大。為了更有效地平衡全局搜索和局部搜索的比例，本文基于cos 函數的權重遞減方法[18]對BOA算法的開關概率進行改進，改進后的開關概率P是一個遞減函數，前期函數下降速度慢，后期函數下降速度快，保證了前期全局搜索可以充分進行，后期局部搜索也可以更好地二次精細尋優。

其中，t和Tmax分別為當前迭代次數和最大迭代次數。

2.2.2 自適應權重和新的位置更新策略

為了減小BOA 中香味系數fi,d的隨機性和盲目性[19]，在香味系數fi,d中加入自適應權重S，使香味分布范圍越來越小，算法能夠越來越仔細地搜索。當搜索過程開始時，初始香味分布范圍很大。隨著迭代過程的進行，香味分布范圍逐漸減小，保證了收斂速度和跳出局部極值點的能力。

新的香味系數fnew：

理想的尋優過程包括前期的高搜索能力和后期的高精度能力。對于全局搜索階段，IBOA 算法通過調整全局最優位置g*與當前迭代的每個蝴蝶位置之間的差異來進行位置更新。因此，IBOA 算法使每個個體圍繞當前迭代的最優位置有一個更加仔細和徹底的搜索機制。全局搜索階段新的位置更新公式為：

對于局部搜索階段，IBOA 算法使用每次迭代中最優位置g*和最差位置w*的平均值來更新每只蝴蝶的下一個位置，減少隨機選擇兩只蝴蝶的盲目性。新的局部搜索階段的位置更新公式為：

由于整周模糊度具有整數特性，IBOA 算法的位置更新公式需要進行四舍五入：

其中，round(?)是四舍五入函數。

2.2.3 IBOA 算法的流程圖

IBOA 算法的流程如圖1 所示，輸入值為經過Z變化后的浮點解和協方差矩陣Q，通過IBOA 算法搜索后輸出整周模糊度固定解。

圖1 IBOA 算法搜索流程圖Fig.1 Flow chart of the search of the IBOA algorithm

3 實驗與結果分析

3.1 仿真實驗

為了驗證IBOA 算法解算整周模糊度的性能，利用最小二乘估計得到模糊度浮點解和協方差矩陣，如式(25)所示，再根據經典算例[20]進行仿真處理。

為了有更好的搜索效率，在搜索前先進行降相關處理和矩陣變化，即對進行 Z 變化（z=ZTN），運算步驟及結果為和經過處理后的浮點解和協方差為：

為了驗證IBOA 算法的有效性，與IACO 算法、ICSO 算法、IPSO 算法和傳統BOA 算法進行對比。將降相關處理后的數據進行整周模糊度解算，五種算法的種群數量都為80，最大迭代次數Tmax=30。表1 為五種算法的參數設置，圖2 是以J(Xi)為目標函數的五種算法解算整周模糊度的收斂過程，表2 是五種算法的最優解演變過程。

表1 五種算法參數設置Tab.1 Parameter setting of five algorithms

表2 最優解的演變Tab.2 Evolution of the optimal solution

圖2 五種算法的收斂曲線Fig.2 Convergence curves of five algorithms

從圖2 可知，在解算整周模糊度的收斂過程中，BOA 算法在第9 次迭代時進入局部最優，在第15 次迭代時才跳出，最后仍然沒有達到最優解。IPSO 算法在第18 次迭代時達到最優解，目標函數值J(Xi)達到最小，不再變化；ICSO 算法在第19 次迭代時達到最優解，目標函數值J(Xi)達到最小，不再變化；IACO 在第15 次迭代時達到最優解，目標函數值J(Xi)達到最小，不再變化；IBOA 算法在第5 次迭代時就達到最優解，目標函數值J(Xi)達到最小，且不再發生變化。IPSO、ICSO、IACO 和IBOA 算法都能夠尋到最優解，但是IBOA 收斂效果比其他三種算法要好。此外，IBOA 算法具有不錯的全局尋優能力，解決了BOA 算法無法跳出局部最優的問題，進一步提升了整周模糊度解算的效率。表2 的最優解演變過程證明了IBOA 算法求解整周模糊度固定解的有效性。

3.2 實驗分析

本文實驗分為兩次測試：第一次測試使用武漢大學IGS（International GPS service for Geodynamics）數據中心下載的觀測值文件進行測試，第二次測試是在蘇州市科技城中科地理信息產業園進行。由于兩次測試的數據量不同，為了方便進行比較，統一從各自數據量中按順序選取其中1000 個歷元進行解算。

武漢大學IGS 數據中心是由國際地球動力學服務機構組織授權建立，可免費下載國際IGS 基準站觀測數據、GNSS 衛星精密軌道和精密誤差等數據服務。本次測試數據來自香港基站hkws 和hksl，其中hkws基站作為流動站，hksl 基站作為基準站，基線長度為42.7 km。下載兩個基站同一天的數據文件，使用RTKLIB（Real-Time Kinematic Library）程序進行數據解析。采用傳統LAMBDA、BOA、IPSO、ICSO、IACO和IBOA 算法進行整周模糊度解算，一天的數據總計2347 歷元，選取其中1000 個歷元進行解算，對六種算法的成功率和解算時間進行對比，如表3 所示。

表3 六種算法解算結果Tab.3 Solution results of six algorithms

第二次測試的實驗數據是使用兩個GPS/BDS 雙模天線進行不同距離的短基線解算，基線長度分別為0.43 m 和3.45 m，可以從接收模塊中得到載波相位和偽距等數據，然后利用串口把數據傳輸給計算機，最后在MATLAB 上運行六種算法程序進行整周模糊度解算。實驗總共采集了兩次數據，第一次采集的是GPS數據，總共觀測了3875 個歷元；第二次采集的是BDS數據，總共觀測了3627 個歷元。兩次數據都取前1000個歷元進行解算，表4 和表5 是六種算法分別使用GPS 和BDS 數據的解算結果。

表4 六種算法使用GPS數據的解算結果Tab.4 Solution results of six algorithms using GPS data

表5 六種算法使用BDS數據的解算結果Tab.5 Solution results of six algorithms using BDS data

由表3～表5 可知，長基線的解算成功率比短基線的低很多，因為基線長度的增加使得模糊度范圍增大，導致解算成功率降低。本文提出的IBOA 算法在解算整周模糊度的性能上依然有一定的提升，解算時間比LAMBDA、IPSO、ICSO 和IACO 四種算法都要快，成功率也優于其他五種算法。其中，IBOA 算法成功率比LAMBDA 算法平均高5.07%，比IPSO 算法平均高5.77%，比ICSO 算法平均高4.90%，比BOA 算法平均高24.13%，比IACO 算法平均高3.37%。雖然BOA算法解算平均時間在六種算法中最少，但其解算成功率在六種算法中最低。IBOA 算法在GPS 和BDS 雙模模糊度解算結果上比較接近，因此將IBOA 算法應用于整周模糊度解算，在理論研究和實際應用上都有很大的優勢，適用于GPS 差分和BDS 差分。

4 結論

本文主要研究了IBOA 算法在DGPS 整周模糊度求解中的應用。首先，采用動態切換概率平衡全局搜索和局部搜索的比例，改善了傳統BOA 算法搜索能力弱的缺點；其次，引入自適應權重使香味分布因子范圍越來越小，同時通過調整最優解與每個解之間的差值來更新位置，改善了傳統BOA 算法易于陷入局部最優的問題；最后，采用IBOA 算法求解整周模糊度固定解。仿真結果表明，IBOA 算法比BOA、IPSO、ICSO 和IACO 算法的收斂速度更快、效果更好。實驗結果表明IBOA 算法的解算成功率更高，也進一步驗證了IBOA 算法在GPS 和BDS 雙模模糊度固定中的有效性和應用可行性。