基于ICSO的DGPS整周模糊度的求解方法

歐陽利,黃采倫

(湖南科技大學 信息與電氣工程學院,湖南 湘潭 411201)

0 引 言

隨著全球衛星導航系統(GNSS)的不斷完善,空間中可視衛星增加的同時,也增加了模糊度的維度,在進行高精度實時動態(RTK)定位時相應地擴大了模糊度搜索空間的范圍,降低了模糊度搜索的效率,所以如何在高維度的情況下,快速準確地求解差分全球定位系統(DGPS)的整周模糊度,是最為關鍵的問題. 一旦準確求解出模糊度的整數解,就可以得到厘米級甚至毫米級定位精度. 目前,流行的求解整周模糊度方法為最小二乘模糊度降相關平差(LAMBDA)算法,它首先利用最小二乘法或卡爾曼濾波求解出整周模糊度的浮點解及其協方差矩陣,再根據浮點解和協方差矩陣確定模糊度的搜索空間,然后以浮點解為中心,將搜索空間的所有整數點代入,求出整周模糊度的最優解[1-3]. 但由于單個點所能提供的信息不多,沒有實現點與點搜索信息的相互交流,當維度增加時,模糊度搜索空間將變得很大,增加了計算的復雜度與時間,大大降低了模糊度解算的效率與成功率. 因此國內外一些學者將群智能優化算法引入到對整周模糊度的搜索中,如遺傳算法[4-5]、粒子群算法、人工魚群算法[6]等取得了不錯的效果,但仍存在收斂速度慢、容易陷入局部最值、求解成功率不高等問題,研究具有全局尋優特點的模糊度快速解算的新方法仍具有重要意義.

Mend等[7]在2014年國際群體智能會議上提出的雞群優化算法(CSO)是一種現代啟發式尋優算法,其模擬雞群中的層次結構和群體行為,將雞群種群劃分為公雞、母雞和小雞,其中雞群可分為幾組,每組由一只公雞和許多母雞和小雞組成,不同種類的雞遵循不同的運動定律,在特定的等級順序下,不同的雞之間存在競爭. CSO已經被應用到許多不同的場合,如光伏系統[8]、靜止無功補償器模型參數辨識方法[9]、機器人同步定位與建圖方法[10]等,都取得了不錯的效果,是一種具有競爭力和實用性的智能算法.

本文針對DGPS整周模糊度的快速固定問題及雞群優化算法中的不足,提出改進的雞群算法(ICSO)來搜索整周模糊度,并模擬了浮點解和協方差陣,利用LLL變換降低模糊度的相關性,借助收斂速度更快、穩健性更強的ICSO對降相關的模糊度進行搜索,構成了一種DGPS短基線整周模糊度求解的新方法,最后通過仿真驗證了新方法的可靠性和實用性.

1 DGPS解算原理

1.1 整周模糊的浮點解及其搜索空間

在DGPS短基線測量中,由于載波相位雙差能消除接收機和衛星鐘差、衛星星歷誤差,極大程度上削弱對流層和電離層延時誤差,因此采用載波相位雙差觀測方程[11].

(1)

當基站與移動站之間為短基線時,對流層和電離層的誤差可以忽略不計,利用式(1)的載波相位雙差方程可以構成一個方程組,對未知參數線性化后,得到線性方程組:

y=Aa+Bb+e,

(2)

式中:y為n維的載波相位觀測量;a為m×1維的整周模糊度;b為t×1維的基線向量;A、B分別為相應的整周模糊度系數、基線向量系數矩陣；e為包含測量噪聲的矢量.

(3)

(4)

在利用卡爾曼濾波器求得模糊度浮點解和協方差陣后,若協方差陣為對角陣,則直接可以通過四舍五入的方法求得模糊度的整數解,但通過上述方法求得的協方差陣遠不是對角陣,因此必須在搜索解空間中搜索模糊度的整數解N,N能使下面的目標函數值最小.

(5)

在搜索時,搜索解空間過大會降低搜索效率,太小又可能不包含整數解,因此在DGPS短基線定位中可以利用基線長度來構造如下的搜索空間.

(6)

式中:l為基線長度;λ為載波波長[5].

1.2 模糊度降相關

(7)

(8)

(9)

(10)

(11)

2 ICSO求解整周模糊度

2.1 基本雞群算法

在雞群中存在多個組,根據每個組適應度值的不同將雞群分為公雞、母雞、小雞,其中適應度值最好的為公雞,其次為母雞,小雞的適應度值最差,每組中有且僅有一只公雞;小雞隨機跟隨的母雞為媽媽母雞,小組中的等級順序、母子關系將保持不變. 這些狀態僅每隔幾個時間步更新一次,不同種類的雞有著不同的更新方式.

公雞位置的更新方式為

(12)

(13)

母雞位置的更新方式為

(14)

(15)

C2=exp(fr2-fi).

(16)

式中:rand為[0,1]上的隨機數;r1是母雞i同組的公雞;r2是除r1之外的任何公雞或母雞.

小雞位置的更新方式為

(17)

2.2 雞群算法的改進

由于直接利用CSO求解整周模糊度時,多數情況下會使算法早熟收斂,陷入局部最優解,嚴重影響整周模糊度解的準確性;因此為了更快更準地得到式(5)目標函數的最小值,在CSO的基礎上分別對公雞、母雞、小雞的位置更新方法進行改進,提出了ICSO求解式(5)的最小值.

(18)

(19)

母雞的數量較多,地位較為弱勢,受同組公雞和其它不同組公雞和母雞的影響,同時也影響小雞的位置,對算法的進程有絕對的影響力,為提高算法的收斂速度,通過最優個體的引導,增強母雞的全局搜索能力.

(20)

將小雞的更新方式修改為

(21)

FL(t)=0.4×rand+0.5.

(22)

小雞個體更新的方式既充分利用了最優個體的位置又增加了較差個體的隨機性,加快了收斂速度,避免個體陷入早熟收斂而陷入局部極值.

2.3 適應度函數

適應度函數是區分雞群中個體好壞的標準,根據適應度的大小對雞群的個體進行優勝劣汰,本文的適應度函數是由雞群優化算法根據式(5)的目標函數確定的.

f(N)=b-lg(J(N)),

(23)

式中,b是確保f(N)>0的一個正數[5].

2.4 ICSO的參數分析

ICSO中存在7個參數,分別為維度Dim、種群大小N、最大迭代次數T、重構因子G、公雞占種群百分比rPercent、母雞占種群百分比hPercent、媽媽母雞占母雞百分比mPercent.

1) 維度Dim

維度是根據具體問題設置的,本文實例解空間為3維,故Dim=3.

2)種群大小N

種群大小N為種群中所有個體的數量,N設置較大,產生的個體越多,就越容易找到全局最優解,但同時也會降低搜索效率.

3) 最大迭代次數T

最大迭代次數T是算法終止的條件,應該合理設置.T太小,算法還未找到全局最優解時就已經停止了,T太大,算法搜索時間大大增加,影響了搜索效率.

4) 重構因子G

重構因子G是雞群重新分組并更新組內的關系的迭代次數,如果G的值很大,則不利于算法快速收斂到全局最優值,如果G的值很小,則該算法可能會陷入局部最優.

5) rPercent、hPercent、mPercent

根據文獻[7]規定,母雞的數量大于公雞,媽媽母雞的數量小于母雞,成年雞(母雞加公雞)的數量 大于小雞,具體的比例可由實驗確定,一般設置公雞和小雞數量相等時,可取得較好的效果.

2.5 算法原理與流程

ICSO求解整周模糊度的原理是,在由固定基線確定的解空間中,根據種群大小隨機生成相應數量的解,并將解根據適應度值分類,每只雞對應一個解,其中公雞對應適應度值大的解,母雞其次,小雞對應適應度值最小的解. 不同類的解有自己對應的更新方式,公雞在靠近最優解的附近移動,尋優能力強;母雞在公雞周圍移動,擴大尋優范圍;小雞跟隨母雞移動,保持種群多樣性. 每隔G代再重新分組,即再根據適應度值的大小,重新劃分公雞、母雞、小雞,不斷更新個體最優位置和全局最優位置,直到達到最大迭代次數,輸出最優解,即為所求的整周模糊度.

由于適應度函數不是單調的,除最優解外,還存在多個局部極值,容易使算法陷入局部最優解.因此在利用ICSO求解整周模糊度之前需要對模糊度及其協方差陣進行降相關,減少函數的極值點,使算法更容易搜索到最優解.

ICSO求解整周模糊度的算法流程如圖1所示.

圖1 算法流程圖

圖1具體步驟如下:

1)線性化載波相位雙差觀測方程,利用卡爾曼濾波器對觀測方程狀態更新和參數估計求解出模糊度的浮點解以及協方差矩陣.

2)利用基線約束確定搜索空間.

3)通過LLL降相關算法對模糊度的浮點解以及協方差矩陣進行降相關.

4)根據目標函數,構造適應度函數.

5)設置雞群算法相關參數,如迭代次數、種群大小、維度、重構因子、公雞比例、母雞比例、媽媽母雞比例等.

6)由種群大小按照各比例分別計算公雞、母雞、媽媽母雞、小雞的數量,初始化雞群(在解空間里隨機生成所有個體初始位置)并根據式(23)計算每只雞的適應度值,初始化個體此時的最優位置(解)和最佳適應度值、全局最優位置(解)和全局最佳適應度值.

7)開始迭代,判斷是否滿足重新分組條件(每隔G代重新分組),若滿足,則對雞群個體的適應度值進行排序,將雞群按公雞個數重新分組,并確定小雞與母雞的關系,母雞和公雞關系,根據式(18)、(20)、(21)分別更新公雞、母雞、小雞位置,不滿足,則直接更新個體位置.

8)計算個體新位置的適應度值,若新位置(解)的適應度值比原位置大就用新位置替換原位置,否則保留原位置,放棄新位置.

9)更新全局最優位置(解).

10)判斷迭代是否結束,若結束輸出全局最優解否則返回步驟7)進行循環迭代.

3 仿真與實驗分析

為驗證上述方法的有效性,設基線長度為2 m,波長λ=19 cm為L1波長,采用文獻[5]的模糊度浮點解及其協方差矩陣進行解算,其具體值分別如下:

表1 降相關前后對比

去相關系數介于0～1,去相關系數越接近0,表明模糊度間相關性越強,越接近1表明模糊度間相關性越弱,譜條件數的幾何含義是表示超橢球的扁度,數值越大,橢球的扁度越大,模糊度間的相關性越強,需要搜索的模糊度就越多.

從表1可以看出,去相關前,R=0.110 9接近于0,說明模糊度間相關性很強;E=321.932 7遠大于降相關后的7.479 5,說明搜索橢球被拉得非常扁長. 去相關后,R=0.976 7接近于1約為去相關前的9倍,同時E減小為原來的2.3%,極大地改善了搜索橢球的空間結構,降低了模糊度間的相關性,說明LLL降相關算法具有良好的去相關效果,可以采用ICSO搜索得到最優解.

ICSO既有群智能算法的優點,又創新性地對種群進行分類,不同的種類的個體有自己獨特的進化方式,能最大程度找到最優解,也沒有遺傳算法復雜的編碼方式,所以在尋找最優解的效率上應該高于遺傳算法,為與文獻[5]的自適應遺傳算法進行公平比較,將種群大小N、最大迭代次數T設置為40、300與文獻[5]一致,將測試維度Dim、重構因子G、公雞占種群百分比rPercent、母雞占種群百分比hPercent、媽媽母雞占母雞百分比mPercent分別設為3、20、0.2、0.6、0.1，能取得很好的效果.

按照上述參數設置,在相同參數設置的情況下利用CSO和ICSO對整周模糊度進行搜索和解算實驗,其仿真中結果分別如圖2、3所示.

圖2 CSO解算整周模糊度

圖3 ICSO解算整周模糊度

由圖2、3可知(橫坐標代表迭代次數,縱坐標代表適應度值),CSO和ICSO都能搜索到全局最優解,但顯然ICSO的收斂速度大于CSO的收斂速度,說明了ICSO的搜索效率高于CSO,證明了ICSO的有效性.

為進一步驗證算法性能,避免偶然性影響,按照前文參數設置,在相同條件下分別采用CSO和ICSO在Matlab R2014a中對前文實例進行100次獨立重復的仿真實驗. 實驗結果統計表明,在利用ICSO進行100次解算實驗過程中有99次得到全局最優解,只有1次陷入局部最優解,解算正確率為99%,CSO的解算正確率為94%. 故ICSO的解算正確率不僅高于CSO的解算正確率,也高于文獻[5]自適應遺傳算法的87.5%的解算正確率,進一步證明了ICSO在求解整周模糊度上的可靠性,同時對比CSO和ICSO在100次實驗中收斂到最優解的收斂代數,如圖4所示.

圖4 CSO與ICSO收斂代數對比

從圖4可知,ICSO的絕大部分收斂代數都明顯低于CSO的收斂代數,且收斂代數范圍較穩定,證明了ICSO的收斂速度比CSO快,穩定性比CSO高. 采用ICSO進行解算時,大部分收斂代數位于20代以下,僅一個點高于40代,平均收斂代數為14.99,按照四舍五入取整,算法搜索平均收斂代數為15,則搜索空間為600(15×40),占問題空間(21)3的6.48%,而CSO搜索平均收斂代數為28,搜索空間為1120(28×40),占問題空間(21)3的12.09%,ICSO的搜索空間大大低于CSO的12.09%以及文獻[5]自適應遺傳算法的12.96%,而且ICSO平均搜索時間為1.442 s低于CSO的1.502 s和自適應遺傳算法的12.6 s,這表明與CSO以及自適應遺傳算法相比,ICSO能提高整周模糊度的搜索效率和速度.

表2示出了整周模糊度一次解算中最佳個體的演變過程.

表2 迭代過程中最佳個體的演變

圖5示出了迭代前后雞群的空間分布情況.

圖5 雞群空間分布圖

結合圖3、5和表2可以看出在ICSO的一次解算實驗中雞群的演變過程. 初始時雞群散亂分布在搜索空間的四周,此時的最大適應度值僅為8.955 0, 隨著迭代次數的增加,雞群逐漸靠攏到一起,在幾次跳出局部最優解后逼近全局最優解,于迭代15次后收斂到了全局最優解,且收斂后的適應度值未再發生變化,穩定性較高;這說明了算法具有良好的尋優特點,實現了快速準確求解整周模糊度的目的.

4 結束語

本文利用已知的基線長度確定模糊度的搜索空間,為減少需要搜索的點數和改善搜索空間結構,使用LLL降相關算法對浮點模糊度和協方差矩陣進行去相關. 此外對CSO進行一定程度上的改進,提出了ICSO,改善了算法的尋優性能并將ICSO與整周模糊度的求解結合,實現了對整周模糊度的快速求解,并取得了不錯的效果,驗證了ICSO的有效性. 通過與文獻[5]比較可知,本文算法的搜索效率和準確率均高于自適應遺傳算法,在雷場探測中,當基線固定時可以直接利用基線長度確定模糊度搜索空間,當基線不固定時,可以根據實際情況對基線取適當范圍限制,從而確定模糊度搜索空間,進而利用ICSO在搜索空間中搜索整周模糊度的最優解,對小型無人機探測器的RTK定位技術有一定的積極意義.