基于AWDE算法的整周模糊度解算算法

鄧洪高，程 歸，紀(jì)元法，孫希延

(桂林電子科技大學(xué)，廣西 桂林 541004)

1 引言

隨著北斗全球組網(wǎng)的成功，中國的衛(wèi)星導(dǎo)航定位技術(shù)進(jìn)一步提升。然而，在利用衛(wèi)星通過載波相位實(shí)現(xiàn)高精度定位時(shí)，載波相位的整數(shù)部分是一個(gè)未知的隨機(jī)整數(shù)，稱為整周模糊度，需要在計(jì)算載波相位之前進(jìn)行固定[1]。根據(jù)國際大地測量協(xié)會的統(tǒng)計(jì)，早在20世紀(jì)80年代初，整周模糊度的解算方法就已經(jīng)被提出[2]。在1981年，Counselman提出了模糊度函數(shù)法(Ambiguity Function Method，AFM)，該方法具有對周跳不敏感的優(yōu)點(diǎn)，但是計(jì)算效率有待提升[3]；靜態(tài)模糊度快速解法(Fast Ambiguity Resolution Approach，F(xiàn)ARA)是E.Frei和G.Beutler提出的，采用數(shù)理統(tǒng)計(jì)代進(jìn)行數(shù)據(jù)預(yù)處理，在靜態(tài)處理上有著顯著效果，但是該方法在動(dòng)態(tài)處理中并不適用[4]。LAMBDA(Least-Square Ambiguity Decorrelation Adjustment)算法是由Teunissen提出的經(jīng)典算法[5，6]，LAMBDA算法具有良好的解算能力，但是算法中的搜索部分屬于遍歷搜索，搜索效率可以進(jìn)一步提高；在Teunissen的基礎(chǔ)上，后人針對搜索效率問題提出MLAMBDA-LAMBDA算法[7]，有效提高了整周模糊度的解算效率。由于整數(shù)模糊度的解決方案是從實(shí)數(shù)區(qū)域到整數(shù)區(qū)域的非線性映射，所以可以圍繞浮點(diǎn)解設(shè)置一個(gè)整數(shù)解決方案集合，使用全局搜索來固定整周模糊度。本文基于標(biāo)準(zhǔn)差分進(jìn)化算法(Differential Evolution Algorithm，DE)的強(qiáng)大全局搜索能力和快速收斂能力，對差分算子進(jìn)行了自適應(yīng)調(diào)整，避免了早熟，中斷等問題，并通過ratio值對搜索完成的固定解進(jìn)行質(zhì)量檢驗(yàn)。

2 載波相位雙差模型

2.1 構(gòu)建載波相位雙差模型

在GNSS精密定位中，假設(shè)有衛(wèi)星信號接收機(jī)r，b，在某時(shí)刻同時(shí)觀測到i，j兩顆衛(wèi)星，則雙差觀測方程如下

(1)

(2)

通過雙差觀測模型可知，一個(gè)雙差載波相位觀測方程有3個(gè)未知數(shù)，而每多一個(gè)共視衛(wèi)星將會多一個(gè)雙差整周模糊度，所以，在可用共視衛(wèi)星較多的情況下，會導(dǎo)致多維整周模糊度，而多維整周模糊度的解算也是一個(gè)難點(diǎn)。

2.2 浮點(diǎn)解求解與處理

同時(shí)，對于短基線的實(shí)時(shí)定位來說，事先利用精密測量取得基線向量的精確值，可以有效地縮小搜索空間范圍[10]。在基線長度為l對應(yīng)的雙差整周模糊度的取值范圍如下

(3)

(4)

(5)

圖1 定位流程簡圖

3 自適應(yīng)加權(quán)的DE算法

3.1 標(biāo)準(zhǔn)DE算法

DE算法是由Kenneth Price和Rainer Storn最先提出的，其本身是一種隨機(jī)模型，通過反復(fù)迭代以保存適應(yīng)環(huán)境的個(gè)體。同時(shí)，DE特殊的記憶能力使其可以動(dòng)態(tài)跟蹤當(dāng)前的搜索情況調(diào)整其搜索策略，具有較強(qiáng)的全局收斂能力和魯棒性[11]。標(biāo)準(zhǔn)DE算法的主要流程如下：

1) 初始化

首先確定差分算法的控制參數(shù)，包括種群大小Popsize，最大迭代數(shù)Max＿generation，加權(quán)因子F和交叉概率CR。

2) 編碼

實(shí)數(shù)編碼是DE算法的特點(diǎn)所在，相較于二進(jìn)制編碼，兩者均能夠有效的搜索的雙差整周模糊度固定值，但二進(jìn)制編碼無法反映問題本身的固有結(jié)構(gòu)特點(diǎn)，個(gè)體長度較大，穩(wěn)定性低于實(shí)數(shù)編碼，也無法避免hamming懸崖問題。

3) 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是利用最小二乘準(zhǔn)則，用模糊度浮點(diǎn)解去擬合固定解，使得浮點(diǎn)解達(dá)到在最小二乘準(zhǔn)則下整數(shù)最優(yōu)。在最小二乘準(zhǔn)則下，代價(jià)函數(shù)為

(6)

適應(yīng)度函數(shù)為

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

(7)

4) 變異

一個(gè)變異個(gè)體的產(chǎn)生是根據(jù)變異公式vi，g=xr1，g+Fi，g*(xr2，g-xr3g)，其中i≠r1≠r2≠r3，F(xiàn)是控制差異變化的整數(shù)常量，通常取值為[0，2]；

5) 交叉

6) 選擇

7) 更新

將更新之后的個(gè)體作為新的種群，重新迭代，重復(fù)4-7，直到滿足終止條件或者最大迭代數(shù)。

3.2 標(biāo)準(zhǔn)DE算法中存在的問題

DE算法是根據(jù)父代個(gè)體間的差分矢量進(jìn)行變異、交叉和選擇操作，盡管在非線性優(yōu)化問題上有強(qiáng)穩(wěn)健性，但是同樣容易由于本身的最優(yōu)聚集性質(zhì)而陷入早熟。當(dāng)算法控制參數(shù)F，CR等設(shè)置不當(dāng)?shù)臅r(shí)候，一旦將其應(yīng)用于整周模糊度解算中，即便是單頻單模情況下，即模糊度維數(shù)較低的情況下，也會陷入早熟或者停滯問題。而在實(shí)際情況中，衛(wèi)星數(shù)目的更迭導(dǎo)致模糊度維數(shù)的變化對于標(biāo)準(zhǔn)DE算法而言，更是無法適用。針對以上問題，提出了一種新的AWDE算法。

3.3 AWDE算法

新的AWDE算法，在進(jìn)行固定模糊度之前，先對浮點(diǎn)解與協(xié)方差矩陣進(jìn)行降相關(guān)處理，以增加算法的搜索效率；在DE算法之中，對迭代情況進(jìn)行實(shí)時(shí)的評估，變異算子，交叉算子，種群大小均是隨著種群適應(yīng)度進(jìn)行自適應(yīng)調(diào)整。在搜索開始，變異和交叉算子較大，較大交叉算子和種群能夠使得全局搜索的范圍更大，較大的變異算子能夠豐富種群多樣性；而在迭代后期，種群所有個(gè)體的適應(yīng)度都較高，此時(shí)，較小的交叉算子變異算子能夠使迭代更快收斂，較小種群數(shù)量能夠使得種群迭代的速度更快。在算法搜索完成之時(shí)，對此時(shí)的搜索值進(jìn)行ratio值檢驗(yàn)，用于判斷算法是否陷入局部最優(yōu)解。具體改進(jìn)如下：

1)降相關(guān)

采用DE算法的實(shí)質(zhì)是從搜索近似全局最優(yōu)解來代替最優(yōu)解，所以浮點(diǎn)解之間的強(qiáng)相關(guān)性將使搜索過程變得復(fù)雜。本文采用逆整數(shù)Cholesky變換對協(xié)方差矩陣進(jìn)行降相關(guān)處理，在進(jìn)行降相關(guān)處理后，適應(yīng)度函數(shù)分布由原本的非單調(diào)函數(shù)變成了只有一個(gè)極值的單調(diào)函數(shù)[12]，從而降低了算法陷入局部最優(yōu)的可能性。

2)變異

變異式vi，g=xr1，g+Fi，g*(xr2，g-xr3g)，更一般的可以寫成如下形式

vi，g=Ai，g*xr1，g+Fi，g*(xr2，g-xr3g)

(8)

式中，i和r代表種群中的個(gè)體，g是迭代次數(shù)；Ai，g是對個(gè)體xr1，g的加權(quán)因子；于是針對于加權(quán)因子Ai，g和Fi，g提出的自適應(yīng)改進(jìn)為

(9)

Fi，g=0.5*(1.5-pi，g)

(10)

其中，i=[1，2，…，Popsize]，Popsize是種群大小，g是迭代數(shù)，ni是第i個(gè)個(gè)體未更新的次數(shù)，max是個(gè)體允許的最大未更新次數(shù)。其中pi，g的值為

(11)

其中，maxF(xg)代表在第g代中，最優(yōu)個(gè)體的適應(yīng)度函數(shù)值。通過pi，g來對種群適應(yīng)度情況進(jìn)行判斷。對加權(quán)因子Fi，g的變化可以使得算法在種群整體適應(yīng)度較差時(shí)，將變異個(gè)體迅速重新迭代得到更好的變異個(gè)體；而在種群適應(yīng)度好的時(shí)候，可以使得變異個(gè)體與原個(gè)體差別減小，從而使得算法快速收斂。

3)交叉

標(biāo)準(zhǔn)DE算法采用的是貪婪策略。貪婪策略雖然有利于加快算法的收斂速度，但是其本質(zhì)是逐漸向某最優(yōu)值靠攏，導(dǎo)致了種群多樣性的減小，即導(dǎo)致了早熟收斂的風(fēng)險(xiǎn)。好的搜索策略應(yīng)該是在搜索初期保持著搜索空間的完整性，以確保包含最優(yōu)解，而在搜索階段的后期，應(yīng)當(dāng)加快搜索能力，增加搜索效率。新的交叉策略如下：

CR=CRmin+time(CRmax-CRmin)/Max＿generation

(12)

式子中CRmin為最大交叉率，CRmax為最小交叉率，time為當(dāng)前迭代次數(shù)，Max＿generation為最大迭代次數(shù)。

4)種群大小變化

由于在解算整周模糊度固定解時(shí)，每個(gè)歷元所觀測到的衛(wèi)星數(shù)是變化的，而可用共視衛(wèi)星數(shù)目越多，所形成的雙差載波相位方程也就越多，浮點(diǎn)解的維數(shù)也就越多。在模糊度搜索過程中，高維問題一直是難點(diǎn)。在DE算法中，不確定的浮點(diǎn)解意味著不確定的個(gè)體維數(shù)，當(dāng)種群數(shù)量較小，浮點(diǎn)解維數(shù)較高時(shí)，極易陷入局部最優(yōu)解；雖然可以通過增大種群數(shù)量解決這一問題，但是種群數(shù)量過大時(shí)，又會導(dǎo)致搜索效率降低。在本文中，初始種群數(shù)量的大小由個(gè)體維數(shù)確定，即popsize = 4*Dim，同時(shí)初始種群的分布采用均勻設(shè)計(jì)，后續(xù)種群數(shù)量將隨著種群適應(yīng)度的提高而縮小。

5)質(zhì)量控制

由于智能優(yōu)化算法本身是通過交叉，變異等方法去用全局近似最優(yōu)解去擬合全局最優(yōu)解，這就導(dǎo)致了算法本身具有一定的不確定性。而在實(shí)際情況下，由于可用共視衛(wèi)星變動(dòng)導(dǎo)致雙差整周模糊度維數(shù)的頻繁變化在一定程度上增大了這種不確定性。所以，解算之后的質(zhì)量檢測尤為重要。Ratio值檢驗(yàn)法是以固定解中次優(yōu)解和最優(yōu)解的殘差平方和的比值作為檢驗(yàn)值，將其與設(shè)定的閾值比較，閾值通常取2或3，當(dāng)ratio值大于閾值時(shí)，判定模糊度固定解正確[13]。

圖2 AWDE算法流程圖

4 算例與分析

4.1 算例1(3維情況下六種算法對比試驗(yàn))

本例將對上述六種模糊度固定方法進(jìn)行仿真，比較相互的解算性能。選取3維的雙差載波相位方程的模糊度浮點(diǎn)解和協(xié)方差矩陣為

通過高斯整數(shù)變換進(jìn)行降相關(guān)之后，浮點(diǎn)解和協(xié)方差矩陣為：

初始種群大小為Popsize=4*3=12，DE算法終止迭代數(shù)為50，基線長度為1米，遺傳算法終止迭代數(shù)為100，利用簡單遺傳算法GA，自適應(yīng)遺傳算法AGA，LAMBDA算法MLAMBDA-LAMBDA算法，標(biāo)準(zhǔn)DE算法和AWDE算法對整周模糊度進(jìn)行搜索和比較。仿真結(jié)果如下圖所示。

圖3 簡單GA算法 圖4 AGA算法注：圖中紅色表示最大適應(yīng)度，綠色表示平均適應(yīng)度，藍(lán)色表示最小適應(yīng)度，下圖一致

簡單遺傳算法的參數(shù)需要在解算整周模糊度之前需要根據(jù)模糊度浮點(diǎn)解和協(xié)方差矩陣進(jìn)行適應(yīng)性調(diào)整，當(dāng)參數(shù)不合適時(shí)，算法效果十分差。而且由于其遺傳算子的值是固定值，沒有辦法隨著迭代而更新，導(dǎo)致算法容易陷入停滯與早熟；在算法迭代至最優(yōu)值解時(shí)，又無法及時(shí)降低交叉變異概率，增加了解算時(shí)間。經(jīng)過對遺傳算子進(jìn)行自適應(yīng)調(diào)整之后，算法能夠準(zhǔn)確的迭代出全局最優(yōu)解，但是搜索效率和成功率還有提升空間。

圖5 DE算法(未降相關(guān)) 圖6 DE算法(降相關(guān))

圖7 AWDE(未降相關(guān)) 圖8 AWDE(降相關(guān))

通過對標(biāo)準(zhǔn)DE算法和AWDE算法分別進(jìn)行了降相關(guān)和未降相關(guān)的比較，如圖5，6，7，8所示。在經(jīng)過降相關(guān)之后，標(biāo)準(zhǔn)DE算法的收斂代數(shù)由23代左右升級到了17代左右，AWDE算法由12代升級到了7代左右。從圖中可以明顯看出，在經(jīng)過降相關(guān)之后，AWDE算法的最小適應(yīng)度并未陷入局部最優(yōu)，減少了解算時(shí)間，提高了搜索效率。

在采用自適應(yīng)加權(quán)的DE算法之后，對于3維雙差整周模糊度，在10次迭代以內(nèi)就能準(zhǔn)確解算出全局最優(yōu)解，算法具有良好的全局搜索能力和較快的收斂速度。即使在未降相關(guān)的情況下，也不會陷入局部最優(yōu)解。

為了準(zhǔn)確統(tǒng)計(jì)算法的準(zhǔn)確性和可靠性，對3維雙差整周模糊度用以上六種算法進(jìn)行100次的重復(fù)試驗(yàn)，最大迭代次數(shù)為50代。對比各算法的解算時(shí)間與解算成功率，統(tǒng)計(jì)結(jié)果如表1所示。

表1 六種算法對比情況

為了更加直觀的展示每一次試驗(yàn)的解算時(shí)間，將DE，AWDE，AGA算法的運(yùn)算時(shí)間用柱狀圖顯示如圖9所示。

圖9 各算法運(yùn)行時(shí)間比較圖

從上面的圖表可知，在六種算法中，AWDE算法有著99%的解算成功率和0.0142秒的解算時(shí)間。而GA算法由于本身的不穩(wěn)定，統(tǒng)計(jì)結(jié)果無效，DE算法的成功率只有86%，AGA算法的成功率達(dá)到了96%，但是平均解算時(shí)間到了0.2459秒。AWDE相對于LAMBDA算法和MLABDA-LAMBDA算法，解算成功率相差無幾，但是解算時(shí)間比LAMBDA和MLABDA-LAMBDA算法分別快了0.0479秒和0.0083秒。

同時(shí)，在AWDE算法中加入了ratio值檢驗(yàn)，檢驗(yàn)閾值為2，當(dāng)每次檢驗(yàn)的ratio值大于或等于閾值時(shí)，代表固定解可用。在本次的100次重復(fù)實(shí)驗(yàn)中，檢驗(yàn)結(jié)果如圖所示，在100次的迭代試驗(yàn)中，只有剛開始的第一次ratio值小于檢驗(yàn)閾值，解算成功率達(dá)到了99%。

圖10 3維下的AWDE算法100代ratio檢驗(yàn)

4.2 算例2(多維解算實(shí)驗(yàn))

對于目前最常用的單頻接收機(jī)ublox接收機(jī)來說，為保證低成本與高精度，通常采用單頻雙模工作模式，理論上最大衛(wèi)星數(shù)為59顆(北斗35顆，GPS24顆)，而在實(shí)際觀測中，單頻雙模接收機(jī)能夠獲得20顆左右的可用共視衛(wèi)星。

圖7 一天內(nèi)觀測到的衛(wèi)星數(shù)

而隨著可用共視衛(wèi)星的增多，意味著浮點(diǎn)解維數(shù)的增加，對固定模糊度的難度增加。所以在此算例中選取了3維，6維，12維的雙差模糊度進(jìn)行解算速度和可靠性的比較，其中3維浮點(diǎn)解與算例1一致。6維浮點(diǎn)解和12維浮點(diǎn)解分別為：

9.9955 -43.0015]T

-297.6589 -22201 51236 30258 3899.4

-22749 -159.2788]T

解算結(jié)果如下所示：

圖12 6維AWDE 圖13 12維AWDE

表2 AWED算法在不同維數(shù)下的比較

通過上述圖表可以看出，隨著維數(shù)的增長，雙差整周模糊度的解算難度增加。6維，12維的平均收斂代數(shù)變成了11代和20代，解算時(shí)間也由3維的0.0142秒增長到0.0352秒和0.1659秒，解算成功率有稍微下降，但是解算速度和精度依舊能夠滿足解算的實(shí)時(shí)性。

5 結(jié)語

DE算法具有很強(qiáng)的全局搜索能力和極快收斂速度，但是由于本身的貪婪算法和差分加權(quán)本質(zhì)上屬于尋優(yōu)迭代，且本身的變異，交叉因子，種群數(shù)量均是定值，無法滿足實(shí)際解算中的變化情況，更無法適應(yīng)雙模甚至三模情況下的多維模糊度情況。本文針對整周模糊度解算問題對迭代算子進(jìn)行自適應(yīng)優(yōu)化，并通過ratio值進(jìn)行解算質(zhì)量控制。實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的AWDE算法在有效性和穩(wěn)定性方面均有不錯(cuò)的表現(xiàn)。