基于實(shí)數(shù)編碼自適應(yīng)遺傳算法的整周模糊度快速解算*

易清明 易夕冬 石 敏

暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632

基于實(shí)數(shù)編碼自適應(yīng)遺傳算法的整周模糊度快速解算*

易清明 易夕冬 石 敏

暨南大學(xué)信息科學(xué)技術(shù)學(xué)院，廣州510632

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

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

1 整周模糊度浮點(diǎn)解及其搜索空間

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

(1)

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

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

(2)

Zk=HkXk+Vk

(3)

其中，Xk為包含接收機(jī)位置參數(shù)和雙差模糊度的狀態(tài)向量，Φk,k-1為狀態(tài)轉(zhuǎn)移矩陣，Гk-1為系統(tǒng)噪聲矩陣；Zk為雙差模式下的觀測(cè)值向量，Hk為量測(cè)矩陣，Vk為觀測(cè)噪聲。根據(jù)平差測(cè)量原理[6]，當(dāng)有t個(gè)歷元j+1顆衛(wèi)星時(shí)，估計(jì)參數(shù)的協(xié)方差矩陣為：

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

(4)

其中，σ為估計(jì)參數(shù)的單位權(quán)均方差，M為載波相位雙差觀測(cè)量的權(quán)矩陣。

(5)

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

-L/λ≤Nn≤L/λ

(6)

其中，λ=19.03cm，為L(zhǎng)1載波。由式(6)可知，當(dāng)L=2m時(shí)，整周數(shù)取[-10,10]間的21個(gè)整數(shù)。

2 基于實(shí)數(shù)編碼自適應(yīng)遺傳算法的整

周模糊度求解

實(shí)數(shù)編碼自適應(yīng)遺傳算法是一種高效穩(wěn)健、并行全局的搜索算法，它能簡(jiǎn)化所求參數(shù)，并在搜索過(guò)程中自適應(yīng)地調(diào)整遺傳算法的交叉概率和變異概率，以求得全局最優(yōu)解。在求得整周模糊度浮點(diǎn)解及式(6)搜索空間的基礎(chǔ)上，通過(guò)設(shè)計(jì)本文的遺傳算法，包括編碼，設(shè)定適應(yīng)度函數(shù)和遺傳算子等操作，對(duì)式(5)的目標(biāo)函數(shù)進(jìn)行搜索尋優(yōu)。

2.1 基于排序的Cholesky分解降相關(guān)

(7)

由式(5)和(7)可以得到降相關(guān)后的目標(biāo)函數(shù)式(8)：

(8)

2.2 實(shí)數(shù)編碼

2.3 適應(yīng)度函數(shù)和遺傳算子

經(jīng)過(guò)編碼后，通過(guò)設(shè)定適應(yīng)度函數(shù)和遺傳算子對(duì)目標(biāo)函數(shù)進(jìn)行尋優(yōu)。遺傳算法是以目標(biāo)函數(shù)為基礎(chǔ)確定適應(yīng)度函數(shù)，以確定最優(yōu)解。對(duì)于式(8)的目標(biāo)函數(shù)，通常選取式(9)作為適應(yīng)度函數(shù)[11]:

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

(9)

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

在確定適應(yīng)度函數(shù)后，利用輪盤選擇算子進(jìn)行最優(yōu)值的選取。模擬輪盤的轉(zhuǎn)盤，每個(gè)個(gè)體被選擇的期望數(shù)量與其適應(yīng)度值和群體平均適應(yīng)值的比例有關(guān)。按照適應(yīng)度比例選擇，個(gè)體的適應(yīng)度值越大，則被選中的概率越大[12]；交叉是結(jié)合來(lái)自父代交配種群中的信息產(chǎn)生新的個(gè)體，本文采用的是文獻(xiàn)[13]中的交叉算子；變異是子代基因按小概率擾動(dòng)產(chǎn)生的變化，本文采用的是對(duì)稱變異和隨機(jī)變異相結(jié)合的變異算子[14]。

2.4 自適應(yīng)調(diào)整

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

圖1 自適應(yīng)遺傳算法原理圖

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

(10)

(11)

其中，Pc1=0.9, Pc2=0.6, Pm1=0.1， Pm2=0.001。經(jīng)過(guò)自適應(yīng)調(diào)整后，Pc和Pm能提供相對(duì)某個(gè)解的最佳Pc和Pm，在保證群體多樣性的同時(shí)，也保證了算法的收斂性。

2.5 解算流程

首先利用基于排序的Cholesky分解,對(duì)雙差方程求解出的整周模糊度浮點(diǎn)解及其協(xié)方差陣進(jìn)行降相關(guān)處理，然后在確定了以上實(shí)數(shù)編碼自適應(yīng)遺傳算法的各項(xiàng)參數(shù)后，利用本文算法對(duì)整周模糊度進(jìn)行解算，其解算流程如圖2所示。

圖2 解算流程圖

3 仿真及結(jié)果分析

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

表1 去相關(guān)程度對(duì)比分析結(jié)果

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

設(shè)種群大小為20，最大進(jìn)化代數(shù)為200[12]，利用本文的遺傳算法對(duì)整周模糊度進(jìn)行搜索和解算實(shí)驗(yàn)，仿真結(jié)果如圖3所示。

圖3 仿真結(jié)果

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

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

表2 3種算法用時(shí)對(duì)比分析結(jié)果

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

4 結(jié)論

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

[1] 劉經(jīng)南.GNSS整周模糊度確認(rèn)理論方法研究進(jìn)展[J].武漢大學(xué)學(xué)報(bào),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ìn)遺傳算法求解整周模糊度[J].測(cè)繪科學(xué),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測(cè)量與數(shù)據(jù)處理[M].武漢:武漢大學(xué)出版社,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] 劉經(jīng)南.附有基線長(zhǎng)度約束的單頻數(shù)據(jù)單歷元LAMBDA方法整周模糊度確定[J].武漢大學(xué)學(xué)報(bào)，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] 黃張?jiān)?一種改進(jìn)的GPS模糊度白化濾波算法[J].西南交通大學(xué)學(xué)報(bào),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].國(guó)防科技大學(xué)學(xué)報(bào),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] 王小平,曹立明.遺傳算法-理論、應(yīng)用與軟件實(shí)現(xiàn)[M].西安:西安交通大學(xué)出版社,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] 夏傳甲.基于實(shí)數(shù)編碼遺傳算法的GPS短基線整周模糊度搜索[J].大地測(cè)量與地球動(dòng)力學(xué)，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] 劉經(jīng)南.遺傳算法解算GPS短基線整周模糊度的編碼方法研究[J].武漢大學(xué)學(xué)報(bào),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動(dòng)態(tài)整周模糊度解算中的應(yīng)用[J].系統(tǒng)仿真學(xué)報(bào),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

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

2016-11-02

易清明(1965-)，女，湖南岳陽(yáng)人，博士，教授，主要從事衛(wèi)星導(dǎo)航信號(hào)處理的教學(xué)與科研工作；易夕冬(1992-)，男，湖南岳陽(yáng)人，碩士研究生，主要研究方向?yàn)樾l(wèi)星導(dǎo)航信號(hào)處理；石 敏(1977-)，女，湖北襄樊人，博士，副教授，主要從事多媒體技術(shù)和信息安全的教學(xué)與科研工作。

V556.1

A

1006-3242(2017)03-0014-05