改進的PSO與ACO混合搜索GNSS整周模糊度算法

尚俊娜，王民頓，劉新華，王奕騰

（1. 杭州電子科技大學 通信工程學院，杭州 310018； 2. 通信信息控制和安全技術重點實驗室，嘉興 314033； 3. 中國電子科技集團公司第三十六研究所，嘉興 314033）

在全球衛星導航系統（Global Navigation Satellite Systems, GNSS）的高精度測姿過程中，確定整周模糊度至關重要。因為如果整周模糊度被準確錨定下來，就可以實現米級定位結果的改善，更有甚者能達到厘米級、毫米級。不能直接求解整周模糊度，因為它涵蓋從實數域到整數域的非線性映射，而是選擇浮點解的相應整數解集作為樣本，最后通過搜索算法尋求真解。

因此整周模糊度的搜索往往取決于算法的質量。文獻[1]中應用蟻群算法在整周模糊度空間內尋優，結果表明在樣本數較少的情況下獲得了很好的搜索結果，并較其他遺傳算法更為可靠。文獻[2]中利用改進粒子群算法搜索固定解，和經典搜索算法LAMBDA的1000 個歷元實驗對比，證明了搜索效率要明顯優于LAMBDA 算法。

本文在單算法的基礎上提出改進粒子群與蟻群混合算法，首先對傳統粒子群和蟻群算法進行了適用于GNSS 整周模糊度搜索的改進，再憑借改進粒子群算法高效率的優勢快速得到次優解，最后利用改進蟻群算法高可靠性的優勢得到最優解。混合算法不僅可以兼具兩種算法的優勢，而且可以彌補它們的劣勢。

1 傳統粒子群與蟻群算法

1.1 粒子群算法

粒子群算法（ Particle Swarm Optimization Algorithm, PSO）是一例基于群智能方法的演化計算算法，它是由Eberhart 和Kennedy 受鳥、魚類群體行為方式啟發而提出的。算法的目的是指導下一步迭代位置，其原理是對粒子的當前位置、個體極值（pbest）和全局極值（gbest）的聯合計算。該算法適用于解決一些連續函數的優化問題[3,4]。

粒子群常規算法中，粒子的速率和位置變化方程為：

式中： i= 1,2… n ，d= 1,2… D ，w 是慣性權值，c1和 c2是自我認知因子和社會認知因子， r1和 r2是[0,1]區間上的隨機數。

1.2 蟻群算法

蟻群算法（Ant Colony Optimization Algorithm, ACO）是以確定最優路徑為目的的一種機率型算法，它是由Marco Dorigo 受螞蟻覓食過程中路徑確定的行為方式啟發而提出的。算法的本質是利用蟻群在其歷史路徑上余留的信息素去指導其他螞蟻尋找食物。該算法適用于解決離散優化問題[5,6]。

在傳統算法中，時間t 任意給定，螞蟻k 從現處位置i 到下一個位置點j 的狀態轉移概率定義為：

式中：α 、β 分別用來調節信息素及啟發式信息所起作用的相對程度，allowedk為螞蟻k 下一步可以選擇的路徑的數組， τij( t )為節點i 和j 之間的信息素濃度， nij（ t ）為螞蟻k 從節點i 到節點j 的啟發信息。

在初期搜索時，每條路徑上具備相同起始條件的信息素，蟻群進行盲目搜索。每次螞蟻集體尋找食物完畢，都將更新所有路徑下的信息素狀況

式中：ρ 為信息素揮發因子，且0＜ ρ＜ 1，m 為螞蟻數量，為螞蟻k 在路徑(i,j)的信息素，可表示為：

式中：Q 為常數， Lk為螞蟻k 在這次循環中經過的總路徑長度，在整周模糊度搜索中將替換成目標函數 J （ N ）：

2 改進的粒子群與蟻群混合算法

2.1 搜索空間的確定

GNSS 搜尋整周模糊度過程中首先要確定的就是搜索空間。在GNSS 短基線解算過程中，在已知基線尺寸的前提下基于GPS 干涉儀測姿原理確定搜索空間。基線設定長度為L 米，雙差整周模糊度的初始取值范圍為：

式中：λ 表示衛星載波波長，[ ]為取整。

2.2 粒子群算法權重的改進

在粒子群算法內，文獻[7]指出慣性權重w 是能代表粒子的搜索能力，權重越大時下一步探索能力越強，適用于全局搜索，反之則適合局部搜索。因此可以通過對w 值的調整實現對全局搜索和局部搜索能力的權衡。在混合算法中，粒子群算法主要起到快速尋找次優解的作用，因此可在迭代初期適當加大w 值，從而達到加快向全局最優解聚集的效果。采用一種慣性權重遞減策略，它是基于sin 函數并已在室內定位中起到很好效果[8]。

式中：k 是指算法當前的迭代次數， kmax是算法最大迭代次數， wmax是最大的慣性權重， wmin是最小的慣性權重。

2.3 蟻群算法選擇概率的改進

傳統蟻群算法在整周模糊度解算過程中，不可避免地存在著易陷入局部最優、收斂速率慢的問題，因此對選擇概率進行改進，加入自反饋因子f ，通過仿真發現，其可以加快收斂速度和解決陷入局部極小時解無法繼續進行的問題，選擇概率改進為：

式中：傳統蟻群系統中的ηij( t )改為適用于混合算 法的，m 為搜索空間的半徑，f 為自反饋因子， 其表達式不固定，但必須滿足條件：一是在最小目標函數值不斷降低的情況下，不干預選擇概率；二是在一定循環次數后最小目標函數值發生停滯時，逐漸降低信息素的作用，從而提高啟發式信息作用；三是保存信息素的作用，不能使其降至0；四是若在自反饋因子作用一段時間后，最小目標函數值仍未降低，就將信息素作用程度立刻降至最低。本文選取的表達式為f =e(-g/4)，每次循環結束，根據目標函數值是否降低對g 做出相應調整：

2.4 混合算法的描述

改進的粒子群與蟻群混合算法(IPSOACO)首先根據GPS 干涉儀測姿原理建立搜索空間，然后使用改進PSO 快速找到一組次優解，根據式(5)(6)轉化為改進ACO 初始信息增量，并根據式(11)得到改進ACO 的初始信息素分布，最后采用改進ACO 搜尋整周模糊度，以此得到最優解：

式中：τp為改進PSO 找到的次優解轉化為的信息素增量，τa為混合前信息素初始分布，τi為改進ACO搜索前的信息素初始分布。

圖1 IPSOACO 算法整體流程圖Fig.1 Overall flow chart of IPSOACO algorithm

算法的具體實現步驟如下：

1)根據基線長度通過式(7)建立搜索空間；

2)初始化改進蟻群算法和改進粒子群算法；

3)運用改進粒子群算法，按照式(6)計算個體最優和全局最優目標函數；

4)達到迭代次數，生成次優解，并按式(5)(6)轉化為信息素增量。否則轉3)；

5)根據信息素增量按照式(11)生成改進蟻群算法的信息素初始分布；

6)根據式(9)計算螞蟻的選擇概率，根據概率移動螞蟻達到搜索目的；

7)更新最小目標函數及其相應的整周模糊度；

8)達到迭代次數，輸出最優解。否則轉6)。

3 實驗及分析

3.1 仿真分析

為了驗證改進的粒子群與蟻群混合算法在整周模糊度搜索上的性能，與單算法進行對比仿真分析，主要參考的指標有2 個：搜索有效性和搜索可靠性。搜索有效性是指目標函數值能否在一定迭代次數內快速收斂于最優解；100 次重復實驗中獲取最優解的次數代表著搜索可靠性。借用文獻[9]中的經典算例，降相關處理后的整周模糊度浮點解和協方差矩陣為：

粒子群和蟻群的種群數量均設置為10，其他主要參數設置如表1，由于協方差矩陣接近對角陣，說明降相關效果較好，最優解就在浮點解周圍，為了更直接地看出仿真結果，不采用GPS 干涉儀測姿原理建立搜索空間，而是對浮點解進行取整并外擴4 個整數解作為搜索空間，因此搜索空間的大小為53。

表1 算法主要參數設置Tab.1 Main parameters setting of the algorithm

圖2 是一次搜索中粒子群算法（PSO）、蟻群算法（ACO）和改進粒子群和蟻群混合算法（IPSOACO）的目標函數值變化圖，目標函數值越小說明所搜索到的整數解與最優解越接近，并可根據式(6)計算出最優解對應的最小目標函數值為0.2183，同時給出本次搜索中三種算法最優解的演變過程。結合圖2 和表2 可以看出PSO 算法收斂速率快，但陷入局部極小且最終并沒有收斂于最優解；因為初始信息素的匱乏，ACO算法收斂較慢，在第19 次迭代后收斂于最優解；IPSOACO 算法相比于單算法而言就可以快速收斂于最優解，說明混合算法相較于單算法而言具有良好的搜索有效性。之后又重復進行了100 次搜索，結果如表3 所示，可以發現IPSOACO 算法搜索可靠性要明顯優于單算法。

圖2 目標函數值的變化Fig. 2 Change of objective function value

表2 三種算法最優解的演變Tab.2 evolution of optimal solution of three algorithms

表3 100 次搜索結果Tab.3 100 search results

與經典的LAMBDA 搜索算法同時進行1000 個歷元的對比仿真實驗，搜索結果如表4 所示。可以發現在成功率相差不大的情況下，IPSOACO 算法的搜索時間要明顯優于LAMBDA 算法，主要是因為LAMBDA算法通常是從解空間的初始點搜索最優解，由于是從一個初始點開始的，所以容錯率會很低，如果這個點選擇不合理，就很容易產生搜索結果陷入局部最優解的問題；而IPSOACO 算法具有獨特全局搜索特性，從一個包含多初始點的種群開始搜索最優解，所以理論上IPSOACO 算法的容錯率比較高，其搜索效率也更高。

表4 兩種算法搜索成功率和解算時間對比Tab.4 Comparison of search success rate and calculation time of two algorithms

3.2 實例驗證

為了檢驗該混合算法在實際搜索中的性能，采用一組基線長度約為4 m 的GPS/BDS 實測數據，測試環境如圖3 所示，采樣頻率為1 s，取中間連續100 s的實驗數據做分析解算。首先對兩個天線做單點定位，經過雙差處理，借助加權最小二乘估計得到浮點解及其協方差矩陣，最后采用混合算法搜索雙差后的整周模糊度，以固定的整周模糊度修正基線[10]。在搜索整周模糊度的過程中，參考衛星選取高度角最高的5 號衛星，與7 號、11 號、13 號及20 號衛星構成雙差模糊度，搜索結果如圖4 所示。

圖3 測試環境Fig.3 Test environment

圖4 雙差整周模糊度解算結果Fig.4 Ambiguity resolution results of double difference integer

由于無法直接檢驗整周模糊度搜索結果，但基線的長度是已知的，因此采用基線解算結果反驗搜索結果的方法。已知衛星L1 載波，其波長為0.1903 m，這也代表了模糊度 1 個整周對于基線的影響是0.1903 m，因此如果基線解算結果穩定且精度在其范圍內，就可以暫定搜索結果無誤。圖5 為基線解算結果，可見三個方向的相對坐標解算結果都較為穩定。圖6 為基線解算誤差，這里的誤差是指基線L 的誤差， 其中誤差的極差范圍在0.1903 m 以內，并且通過計算其均方根誤差，得到其精度為2.63 mm，由于它的影響遠遠小于一個整周誤差，因此判定整周模糊度搜索無誤，說明改進的混合算法可以很好地處理短基線解算中的整周模糊度搜索問題。

圖5 基線解算結果Fig.5 Baseline solution results

圖6 基線解算誤差Fig.6 Baseline solution error

4 結 論

本文提出一種用于搜索GNSS 整周模糊度的新方法。首先在已知基線長情況下，基于GPS 干涉儀測姿原理確定搜索空間，然后使用改進粒子群算法快速搜索次優解，并以此來初始化改進蟻群算法的信息素分布，最后使用改進蟻群算法確定最優解。改進的混合算法理論上可以解決傳統粒子群算法局部尋優能力差的問題，并且也可以彌補蟻群算法初始信息素匱乏的缺點。通過對經典算例的仿真，驗證了改進的混合算法較單算法可以更快更可靠地收斂于最優解，且搜索效率要明顯優于經典的LAMBDA 算法，并經實測數據檢驗，該算法可以很好地解決短基線解算中的整周模糊度搜索問題。在滑坡和鋼架結構沉降監測方面有良好應用場景，降低了危險發生的可能性。但改進的混合算法還有很多地方需要深入探討，比如在基線較長情況下會因搜索空間較大導致搜索效率低下等，都是本文需要進一步研究的問題。