基于實數編碼自適應遺傳算法的整周模糊度快速解算*

易清明 易夕冬 石 敏

暨南大學信息科學技術學院，廣州510632

基于實數編碼自適應遺傳算法的整周模糊度快速解算*

易清明 易夕冬 石 敏

暨南大學信息科學技術學院，廣州510632

針對整周模糊度解算中實時性不強的問題,提出了一種基于實數編碼的自適應遺傳算法。首先利用卡爾曼濾波求解整周模糊度的浮點解，然后采用排序和多次(逆)雙喬里斯基分解對浮點解及其協方差陣進行降相關處理，降低整周模糊度各分量之間的相關性，最后利用已知基線確定模糊度搜索空間，基于實數編碼，將自適應遺傳算法應用在整周模糊度的搜索解算過程中，求得整周模糊度的最優解。仿真結果表明，本文算法與Lambda算法相比,耗時更少；與簡單遺傳算法相比,具有更強的收斂能力，是一種高效的整周模糊度快速解算方法。 關鍵詞 整周模糊度；卡爾曼濾波；喬里斯基分解；實數編碼；自適應遺傳算法

整周模糊度的快速解算是利用GPS載波相位作為觀測量進行高精度實時相對定位的關鍵[1]。目前，求解整周模糊度的方法中理論體系最完備、應用最廣的是Lambda算法[2]。但是其搜索空間較大，計算相對復雜，搜索效率并不高。遺傳算法是由美國J Holland教授提出，具有內在并行性，全局優化性和穩健性的特點，但在實際搜索過程中，由于其交叉概率和變異概率保持不變，使得算法容易陷入局部最優[3]。因此本文提出一種基于實數編碼的自適應遺傳算法，簡化搜索過程，提高尋優能力。

1 整周模糊度浮點解及其搜索空間

為了消除載波相位中電離層誤差、對流層誤差、衛星鐘差和接收機鐘差等大部分誤差，在GPS精密定位中，常采用載波相位雙差觀察值進行處理。設t時刻，k,i兩接收機觀測了j,o兩顆衛星，則載波相位雙差觀測方程為[4]:

(1)

為方便計算機建模與仿真，將其線性化后[5]建立常加速度模型下的卡爾曼濾波器,其狀態方程和量測方程分別為：

Xk=Φk,k-1Xk-1+Гk-1Wk-1

(2)

Zk=HkXk+Vk

(3)

其中，Xk為包含接收機位置參數和雙差模糊度的狀態向量，Φk,k-1為狀態轉移矩陣，Гk-1為系統噪聲矩陣；Zk為雙差模式下的觀測值向量，Hk為量測矩陣，Vk為觀測噪聲。根據平差測量原理[6]，當有t個歷元j+1顆衛星時，估計參數的協方差矩陣為：

Q=σ2(HTM-1H)-1

(4)

其中，σ為估計參數的單位權均方差，M為載波相位雙差觀測量的權矩陣。

(5)

其中，N為j個雙差整周模糊度組成的向量。對于長度為L的基線，每個雙差整周模糊度Nn(n=1,2,…, j)的取值范圍都在以浮點解為中心的L米基線范圍內[7]，即:

-L/λ≤Nn≤L/λ

(6)

其中，λ=19.03cm，為L1載波。由式(6)可知，當L=2m時，整周數取[-10,10]間的21個整數。

2 基于實數編碼自適應遺傳算法的整

周模糊度求解

實數編碼自適應遺傳算法是一種高效穩健、并行全局的搜索算法，它能簡化所求參數，并在搜索過程中自適應地調整遺傳算法的交叉概率和變異概率，以求得全局最優解。在求得整周模糊度浮點解及式(6)搜索空間的基礎上，通過設計本文的遺傳算法，包括編碼，設定適應度函數和遺傳算子等操作，對式(5)的目標函數進行搜索尋優。

2.1 基于排序的Cholesky分解降相關

(7)

由式(5)和(7)可以得到降相關后的目標函數式(8)：

(8)

2.2 實數編碼

2.3 適應度函數和遺傳算子

經過編碼后，通過設定適應度函數和遺傳算子對目標函數進行尋優。遺傳算法是以目標函數為基礎確定適應度函數，以確定最優解。對于式(8)的目標函數，通常選取式(9)作為適應度函數[11]:

f(N)=b-lg(G(N))

(9)

其中，b為一個足夠大的正數，保證f(N)>0,對目標函數取對數是為了縮小各整周數組合之間的差值，避免遺傳算法早熟，陷入局部最優。

在確定適應度函數后，利用輪盤選擇算子進行最優值的選取。模擬輪盤的轉盤，每個個體被選擇的期望數量與其適應度值和群體平均適應值的比例有關。按照適應度比例選擇，個體的適應度值越大，則被選中的概率越大[12]；交叉是結合來自父代交配種群中的信息產生新的個體，本文采用的是文獻[13]中的交叉算子；變異是子代基因按小概率擾動產生的變化，本文采用的是對稱變異和隨機變異相結合的變異算子[14]。

2.4 自適應調整

Srinvivas等提出了一種自適應遺傳算法(AGA)[15]。適應度高于群體平均適應度favg的個體對應較低的交叉概率Pc和變異概率Pm，使該解得以保護進入下一代；而低于favg的個體則對應較高的Pc和Pm，使該解被淘汰。其原理如圖1所示。

圖1 自適應遺傳算法原理圖

圖1中， fmax為每代群體中的最大適應度， f ′為要交叉的2個個體中較大的適應度值， f為要變異個體的適應度，k和k′在(0,1)間取值。為了使群體中最大適應度個體的Pc和Pm不為0，分別將它們提高到Pc2和Pm2，這就相應地提高了群體中表現優良個體的Pc和Pm，減小了群體進化初期陷入局部最優的可能性。綜上，Pc和Pm計算表達式如下[12]：

(10)

(11)

其中，Pc1=0.9, Pc2=0.6, Pm1=0.1， Pm2=0.001。經過自適應調整后，Pc和Pm能提供相對某個解的最佳Pc和Pm，在保證群體多樣性的同時，也保證了算法的收斂性。

2.5 解算流程

首先利用基于排序的Cholesky分解,對雙差方程求解出的整周模糊度浮點解及其協方差陣進行降相關處理，然后在確定了以上實數編碼自適應遺傳算法的各項參數后，利用本文算法對整周模糊度進行解算，其解算流程如圖2所示。

圖2 解算流程圖

3 仿真及結果分析

對上述方法進行仿真，采用文獻[16]的解算實例,基線長為2m,由式(6)可知，每個整周模糊度的取值范圍為[-10,10]。為了分析本文降相關算法的有效性，采用去相關系數R和矩陣的譜條件數E作為評價變換后協方差陣的去相關程度的衡量標準[9]，其參數如表1所示。

表1 去相關程度對比分析結果

由表1可知，去相關前，R很小，趨近于0，說明模糊度間存在較強的相關性；E很大，表明搜索橢球被拉得非常扁長，也反映了模糊度間的強相關。去相關后，R明顯增大，接近于1，同時E大幅減小，協方差陣越接近于對角陣，各模糊度之間的相關性得到降低，說明本文算法具有較好的去相關效果，適合采用遺傳算法搜索得到最優解。

設種群大小為20，最大進化代數為200[12]，利用本文的遺傳算法對整周模糊度進行搜索和解算實驗，仿真結果如圖3所示。

圖3 仿真結果

由圖3可知(橫坐標表示進化代數，縱坐標表示群體適應度值),本文算法能搜索到正確的最優解,進化到算法終止子代時,只有極小部分的結果陷入局部最優解，且在20代以內就能收斂到全局最優解，即大部分的個體在20代以內就收斂了，而簡單遺傳算法[17]在第100代才收斂到最優值。取20代收斂，其搜索空間為400(20×20)，占問題空間(213)的4.3%，這表明本文算法在整周模糊度的尋優求解上具有較高的搜索效率。

在搜索到正確的整周模糊度值的前提下，Lambda算法和簡單遺傳算法[17]與本文算法用時如表2所示。

表2 3種算法用時對比分析結果

由表1可知，本文算法的用時明顯少于Lambda法和簡單遺傳算法。這是因為Lambda是圍繞某一初始浮點解開始搜索解算過程的，因此這一初始點的選擇關乎整個搜索過程的效率。而單個點所能提供的搜索信息不多，當觀測數據較多時，Lambda的搜索空間較大、計算也較為復雜且計算時間較長。在去相關過程中，Lambda采用的高斯分解也存在數值不穩定和運算量大的缺點。簡單遺傳算法的編碼模式是二進制編碼，漢明懸崖問題不可避免，且編碼參數較多，而在遺傳算子部分，恒定的交叉和變異概率等都大大影響了遺傳算法的搜索效率。

4 結論

系統地研究了DGPS定位模型中整周模糊度的求解問題。在浮點解的求解過程中采用了卡爾曼濾波，在去相關的過程中采用了基于排序的Cholesky分解，最后在基線長度已知的情況下，基于實數編碼，將自適應遺傳算法引入到DGPS整周模糊度的搜索解算中。通過對算法的仿真分析和比較可知，本文算法的求解時間遠小于Lambda算法，收斂速度遠高于簡單遺傳算法，是一種高效的整周模糊度快速解算方法，對于實時動態定位技術的研究具有一定的參考意義。

[1] 劉經南.GNSS整周模糊度確認理論方法研究進展[J].武漢大學學報,2014,39(9):1009-1016.(Liu Jingnan.Review of GNSS Ambiguity Validation Theory[J].Geomatics and Information Science of Wuhan University,2014,39(9):1009-1016.)

[2] Teunissen P J G.The Least-squares Ambiguity Decorrelation Adjustment:A Method for Fast GPS Integer Ambiguity Estimation[J].Journal of Geodesy,1995,70(1-2):65-82.

[3] 邢喆.利用改進遺傳算法求解整周模糊度[J].測繪科學,2011,36(3):110-113.(Xing Ji. Ambiguity Resolution Based on Improved Genetic Algorithm[J].Science of Surveying and Mapping,2011,36(3):110-113.)

[4] Teunissen P J G.The Invertible GPS Ambiguity Transformations[J].Manuscript Geodesy,1995,20(6):489-497.

[5] 李征航.GPS測量與數據處理[M].武漢:武漢大學出版社,2005:135-14.(Li Zhenghang.GPS Surveying and Data Processing [M].Wuhan:Wuhan University Press,2005:135-141.)

[6] Teunissen P J G.Integer Ambiguity Estimation with the Lambda Method[J].Proceedings of IEEE Symposium on Position Location and Navigation,1996,21(7):280-284.

[7] 劉經南.附有基線長度約束的單頻數據單歷元LAMBDA方法整周模糊度確定[J].武漢大學學報，2005,30(5):444-446.(Liu Jingnan. Ambiguity Resolution of Single Epoch Single Frequency Data with Baseline Length Constraint Using LAMBDA Algorithm [J]. Geomatics and Information Science of Wuhan University,2005,30(5):444-446.)

[8] Zhou Yangmei.A New Practical Approach to GNSS High-dimensional Ambiguity Decorrelation[J].GPS Solutions,2011,15(4):325-331.

[9] 黃張裕.一種改進的GPS模糊度白化濾波算法[J].西南交通大學學報,2010,45(1):150-155.(Huang Zhangyu. Modified GPS Ambiguity White-filtering Algorithm [J].Journal of Southwest Jiaotong University,2010,45(1):150-155.)

[10] Goldberg D E.Genetic Algorithms in Search Optimization and Machine Learning[M].New York:Addision Wesley,1989.

[11] 鄭慶暉.基于遺傳算法的整周模糊度OTF解算[J].國防科技大學學報,2001,23(3):12-17.(Zheng Qinghui.OTF Ambiguity Resolution Based on Genetic Algorithm[J].Journal of National University of Defense Technology,2001,23(3):12-17.)

[12] 王小平,曹立明.遺傳算法-理論、應用與軟件實現[M].西安:西安交通大學出版社,2002:18-38,73-74.(Wang Xiaoping, Cao Liming.Genetic Algorithm-Theory,Application and Software Implementation [M].Xi’an: Xi’an Jiaotong University Press,2002:18-38,73-74.)

[13] 夏傳甲.基于實數編碼遺傳算法的GPS短基線整周模糊度搜索[J].大地測量與地球動力學，2012,32(1):136-140.(Xia Chuanjia.Integer Ambiguity Resolution of GPS Short-baseline Based on Real-coded Genetic Algorithm[J].Journal of Geodesy and Geodynamics,2012,32(1):136-140.)

[14] 劉經南.遺傳算法解算GPS短基線整周模糊度的編碼方法研究[J].武漢大學學報,2006,31(7):607-609.(Liu Jingnan. Ambiguity Resolution of GPS Short Baseline Using Genetic Algorithm[J].Geomatics and Information Science of Wuhan University,2006,31(7):607-609.)

[15] Srinvivas M,Patnaik L M. Adaptive Probabilities of Crossover and Mutations in Genetic Algorithms[J].IEEE Trans.on SMC,1994,24(4):656-667.

[16] Paul de Jonge.The LAMBDA Method for Integer Ambiguity Estimation:Implementation Aspects[J].Delft Geodetic Computing Center LGR Series,1996,12:1-49.

[17] 楊寧.遺傳算法在DGPS動態整周模糊度解算中的應用[J].系統仿真學報,2005,17(8):2025-2026. (Yang Ning.Application of Genetic Algorithm in DGPS Integer Ambiguity Resolution[J].Journal of System Simulation,2005,17(8):2025-2026.)

Fast Integer Ambiguity Resolution Based on Real-Coded Adaptive Genetic Algorithm

Yi Qingming， Yi Xidong， Shi Min

School of Information Science and Technology, Jinan University, Guangzhou 510632, China

Aimingattheweakreal-timeperformanceinintegerambiguityresolution,anadaptivegeneticalgorithmbasedonreal-codingisproposedinthispaper.ThefloatsolutionofintegerambiguityiscalculatedbyapplyingKalmanfiltermethod,theorderingandmulti-time(inverse)pairedCholeskydecompositionareadoptedtodecorrelatethefloatsolutionanditscovariancematrix,Thus,thecorrelationofeachambiguityfloatestimationcanbeeliminated.Withthegivenbaseline,theintegerambiguitysearchspaceandtheintegerambiguityoptimizationresultscanbedeterminedbyusingadaptivegeneticalgorithmonthebasisofreal-coding.Thenumericalsimulationresultsshowthat,theintegerambiguitiescanberesolvedbyusingthisproposemethodinashortertimethanLambdamethod,andstrongerconvergentabilityisacquired,whichiscomparedwithsimplegeneticalgorithm.Itisproventhatthisalgorithmisefficientforfastintegerambiguityresolution.

Integerambiguity; Kalmanfilter; Choleskydecomposition;Real-coding;Adaptivegeneticalgorithm

*廣東省科技計劃資助項目(2015B090910001)；廣州市科技計劃資助項目(201604010007)

2016-11-02

易清明(1965-)，女，湖南岳陽人，博士，教授，主要從事衛星導航信號處理的教學與科研工作；易夕冬(1992-)，男，湖南岳陽人，碩士研究生，主要研究方向為衛星導航信號處理；石 敏(1977-)，女，湖北襄樊人，博士，副教授，主要從事多媒體技術和信息安全的教學與科研工作。

V556.1

A

1006-3242(2017)03-0014-05