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

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

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

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

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

本文在單算法的基礎(chǔ)上提出改進粒子群與蟻群混合算法，首先對傳統(tǒng)粒子群和蟻群算法進行了適用于GNSS 整周模糊度搜索的改進，再憑借改進粒子群算法高效率的優(yōu)勢快速得到次優(yōu)解，最后利用改進蟻群算法高可靠性的優(yōu)勢得到最優(yōu)解?；旌纤惴ú粌H可以兼具兩種算法的優(yōu)勢，而且可以彌補它們的劣勢。

1 傳統(tǒng)粒子群與蟻群算法

1.1 粒子群算法

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

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

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

1.2 蟻群算法

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

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

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

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

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

式中：Q 為常數(shù)， Lk為螞蟻k 在這次循環(huán)中經(jīng)過的總路徑長度，在整周模糊度搜索中將替換成目標(biāo)函數(shù) J （ N ）：

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

2.1 搜索空間的確定

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

式中：λ 表示衛(wèi)星載波波長，[ ]為取整。

2.2 粒子群算法權(quán)重的改進

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

式中：k 是指算法當(dāng)前的迭代次數(shù)， kmax是算法最大迭代次數(shù)， wmax是最大的慣性權(quán)重， wmin是最小的慣性權(quán)重。

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

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

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

2.4 混合算法的描述

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

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

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

算法的具體實現(xiàn)步驟如下：

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

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

3)運用改進粒子群算法，按照式(6)計算個體最優(yōu)和全局最優(yōu)目標(biāo)函數(shù)；

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

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

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

7)更新最小目標(biāo)函數(shù)及其相應(yīng)的整周模糊度；

8)達到迭代次數(shù)，輸出最優(yōu)解。否則轉(zhuǎn)6)。

3 實驗及分析

3.1 仿真分析

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

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

表1 算法主要參數(shù)設(shè)置Tab.1 Main parameters setting of the algorithm

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

圖2 目標(biāo)函數(shù)值的變化Fig. 2 Change of objective function value

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

表3 100 次搜索結(jié)果Tab.3 100 search results

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

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

3.2 實例驗證

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

圖3 測試環(huán)境Fig.3 Test environment

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

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

圖5 基線解算結(jié)果Fig.5 Baseline solution results

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

4 結(jié) 論

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