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

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

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

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

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

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

1.1 粒子群算法

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

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

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

1.2 蟻群算法

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

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

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

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

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

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

2 改進(jìn)的粒子群與蟻群混合算法

2.1 搜索空間的確定

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

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

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

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

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

2.3 蟻群算法選擇概率的改進(jìn)

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

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

2.4 混合算法的描述

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

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

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

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

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

2)初始化改進(jìn)蟻群算法和改進(jìn)粒子群算法；

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

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

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

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

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

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

3 實(shí)驗(yàn)及分析

3.1 仿真分析

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

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

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

圖2 是一次搜索中粒子群算法（PSO）、蟻群算法（ACO）和改進(jìn)粒子群和蟻群混合算法（IPSOACO）的目標(biāo)函數(shù)值變化圖，目標(biāo)函數(shù)值越小說明所搜索到的整數(shù)解與最優(yōu)解越接近，并可根據(jù)式(6)計(jì)算出最優(yōu)解對(duì)應(yīng)的最小目標(biāo)函數(shù)值為0.2183，同時(shí)給出本次搜索中三種算法最優(yōu)解的演變過程。結(jié)合圖2 和表2 可以看出PSO 算法收斂速率快，但陷入局部極小且最終并沒有收斂于最優(yōu)解；因?yàn)槌跏夹畔⑺氐膮T乏，ACO算法收斂較慢，在第19 次迭代后收斂于最優(yōu)解；IPSOACO 算法相比于單算法而言就可以快速收斂于最優(yōu)解，說明混合算法相較于單算法而言具有良好的搜索有效性。之后又重復(fù)進(jìn)行了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 搜索算法同時(shí)進(jìn)行1000 個(gè)歷元的對(duì)比仿真實(shí)驗(yàn)，搜索結(jié)果如表4 所示?？梢园l(fā)現(xiàn)在成功率相差不大的情況下，IPSOACO 算法的搜索時(shí)間要明顯優(yōu)于LAMBDA 算法，主要是因?yàn)長(zhǎng)AMBDA算法通常是從解空間的初始點(diǎn)搜索最優(yōu)解，由于是從一個(gè)初始點(diǎn)開始的，所以容錯(cuò)率會(huì)很低，如果這個(gè)點(diǎn)選擇不合理，就很容易產(chǎn)生搜索結(jié)果陷入局部最優(yōu)解的問題；而IPSOACO 算法具有獨(dú)特全局搜索特性，從一個(gè)包含多初始點(diǎn)的種群開始搜索最優(yōu)解，所以理論上IPSOACO 算法的容錯(cuò)率比較高，其搜索效率也更高。

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

3.2 實(shí)例驗(yàn)證

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

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

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

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

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

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

4 結(jié) 論

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