孫妍艷,劉翠芝

(東北大學(xué) 資源與土木工程學(xué)院測(cè)繪工程系,遼寧 沈陽 110819)

0　引　言

整周模糊度解算是實(shí)現(xiàn)快速、高精度定位的關(guān)鍵,一直是全球?qū)Ш叫l(wèi)星系統(tǒng)(GNSS)的研究熱點(diǎn)。在GNSS定位中,定位所需的時(shí)間取決于正確確定整周模糊度所需要的時(shí)間。目前,國際上應(yīng)用最為廣泛的是LAMBDA(Least-square Ambiguity Decorrelation Adjustment)算法。對(duì)高維模糊度解算算法的研究早期主要是基于LAMBDA算法加快去相關(guān)的速度。如Li and Gao提出的高維解算算法只對(duì)7～13維數(shù)據(jù)有效[1]。Teunissen等[2]提出的MCLAMBDA方法,使得LAMBDA算法適用于多基線姿態(tài)測(cè)量。后來,從格理論的角度證明了整數(shù)最小二乘模糊度解算相當(dāng)于格上最近向量問題后,許多學(xué)者提出了LLL規(guī)約算法在模糊度解算中的應(yīng)用[3-7],但LLL算法存在規(guī)約耗時(shí)較長且明顯大于搜索耗時(shí)的問題。

近些年,有學(xué)者提出利用遺傳算法固定整周模糊度[8-9],但都只是對(duì)某一維度的模糊度進(jìn)行解算分析,并沒有對(duì)更高維的模糊度進(jìn)行分析,也沒有對(duì)這種群智能算法在模糊度解算應(yīng)用中的各項(xiàng)參數(shù)設(shè)定進(jìn)行深入的研究。本文利用比遺傳算法更智能的差分進(jìn)化算法對(duì)高維模糊度進(jìn)行固定。

差分進(jìn)化算法(DE)是由美國學(xué)者Store和Price在1995年提出的一種智能計(jì)算方法,初衷是用于求解切比雪夫多項(xiàng)式的問題。與其他進(jìn)化算法大致相同,差分進(jìn)化算法對(duì)函數(shù)的可導(dǎo)性甚至連續(xù)性都沒有要求,適用性很強(qiáng)。Jakob Vester strom和Rene Thomsen將差分進(jìn)化算法、遺傳算法、粒子群優(yōu)化算法進(jìn)行對(duì)比實(shí)驗(yàn)分析,指出差分進(jìn)化算法在解決復(fù)雜優(yōu)化問題方面的收斂速度更快、穩(wěn)定性更強(qiáng)[10]。

但高維問題屬于復(fù)雜的優(yōu)化問題,標(biāo)準(zhǔn)差分進(jìn)化算法無法滿足問題的求解要求。且算法在運(yùn)算后期,很容易陷入局部最優(yōu)解也就是“早熟”的現(xiàn)象或者收斂緩慢致使在有限的迭代次數(shù)中無法收斂到最優(yōu)解的情況。因此本文采用自適應(yīng)差分進(jìn)化算法進(jìn)行高維模糊度解算,并設(shè)計(jì)了一個(gè)更具有普遍適用性的算法。

1　數(shù)學(xué)模型及原理

1.1　整數(shù)最小二乘原理

GNSS整周模糊度的解算一般包括兩部分:模糊度估計(jì)和模糊度確認(rèn)。其中,模糊度估計(jì)分為兩步:首先,通過最小二乘方法或卡爾曼濾波法求出模糊度的浮點(diǎn)解N及其方差協(xié)方差陣QN; 然后,按照一定的規(guī)則確定模糊度整數(shù)解的搜索空間,在此空間中按照模糊度殘差二次型最小的原則利用某種搜索算法固定模糊度。模糊度的殘差二次型為[11]

聯(lián)系人: 孫妍艷E-mail: 767564911@qq.com

min(N-N′)TQN-1(N-N′),

(1)

式中,N′∈Zn,是模糊度的固定解。

1.2　差分進(jìn)化算法原理

差分進(jìn)化算法是一種基于種群的全局搜索算法,通過把一定比例的多個(gè)個(gè)體的差分信息作為個(gè)體的擾動(dòng)量,使得算法在跳躍距離和搜索方向上具有自適應(yīng)性。如圖1所示，在進(jìn)化的早期,因?yàn)榉N群中個(gè)體的差異性較大使得擾動(dòng)量較大,從而使得算法能夠在較大范圍內(nèi)搜索,具有較強(qiáng)的勘探能力;而到了進(jìn)化后期,當(dāng)算法趨于收斂時(shí),種群中個(gè)體的差異性較小,算法在個(gè)體附近搜索,這使得算法具有較強(qiáng)的局部開采能力[12]。

標(biāo)準(zhǔn)差分進(jìn)化算法的原理是:首先,隨機(jī)生成初始種群,從種群中隨機(jī)選擇兩個(gè)個(gè)體向量的差分量作為第三個(gè)隨機(jī)基準(zhǔn)向量的擾動(dòng)量,得到變異向量,然后變異向量與基準(zhǔn)向量進(jìn)行雜交,生成試驗(yàn)向量,最后,采用貪婪選擇機(jī)制,將基準(zhǔn)向量與試驗(yàn)向量競(jìng)爭(zhēng),適應(yīng)度高者保存到下一代種群中。從而,種群逐漸聚集到最優(yōu)解的位置。

目前,差分進(jìn)化算法已廣泛應(yīng)用于很多領(lǐng)域,如人工神經(jīng)網(wǎng)絡(luò),化工,電力,機(jī)械設(shè)計(jì),機(jī)器人,信號(hào)處理,生物,運(yùn)籌學(xué),控制工程,數(shù)據(jù)挖掘,調(diào)度問題等并取得了驚人的效果[13]。其缺點(diǎn)是,差分進(jìn)化算法并沒有一個(gè)系統(tǒng)的研究,所以每個(gè)領(lǐng)域都要根據(jù)其自身的特點(diǎn)進(jìn)行算法設(shè)計(jì)。

2　自適應(yīng)差分進(jìn)化算法設(shè)計(jì)

本文參考Brest[14]等提出的自適應(yīng)差分進(jìn)化算法(jDE),使縮放因子F和雜交概率Cr與種群個(gè)體一同編碼和進(jìn)化。 與jDE算法不同是,本文將jDE算法中的F取值條件由rand[0,1]<0.1改為rand[0,1]<0.5,其中rand[0,1]為0～1之間均勻分布的隨機(jī)數(shù)。目的是為了使樣本能夠生成更多的變異個(gè)體,以保證樣本具有足夠的多樣性,從而加快算法的收斂速度。

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

適應(yīng)度函數(shù)是選擇操作中判優(yōu)的參考條件。在模糊度解算中,適應(yīng)度函數(shù)越小越好,即J(N)越小,表明該N′越接近最優(yōu)解。

(2)

2.2　初始化操作

2.3　變異操作

變異操作是指種群個(gè)體中某個(gè)元素發(fā)生改變。設(shè)t為當(dāng)前運(yùn)行次數(shù),V為變異向量,u為試驗(yàn)向量即基準(zhǔn)向量和變異向量交叉生成,Ni為第i個(gè)基準(zhǔn)向量,Ni1、Ni2、Ni3為從當(dāng)前種群中隨機(jī)選擇三個(gè)向量,其中i1、i2和i3是從集合{1,…,NP}中隨機(jī)選擇的相互不同的整數(shù)且不等于i.

F的自適應(yīng)調(diào)整策略的數(shù)學(xué)表達(dá)式:

OldFi(t)=Fi(t).

NewFi(t)=

(3)

變異操作的數(shù)學(xué)表達(dá)式為

Vi(t)=Ni1(t)+NewFi(t)(Ni2(t)-

Ni3(t)) .

(4)

盡管目前提出了許多變異操作的方法,但是通過實(shí)驗(yàn)分析,采用公式(4)更適合模糊度的解算。

2.4　修補(bǔ)操作

修補(bǔ)操作是為了檢查變異后的模糊度分量是否超出其取值范圍。如果超過,對(duì)其進(jìn)行修正。

2.5　雜交操作

雜交操作可以提高種群的多樣性,差分進(jìn)化算法的雜交操作與其他進(jìn)化算法的不同之處在于其采用的是父代的基準(zhǔn)向量和變異向量進(jìn)行操作,而其他進(jìn)化算法是基于多個(gè)來自父代的基準(zhǔn)向量交換基因的雜交操作。本算法采用二項(xiàng)式雜交算子。雜交后得到試驗(yàn)向量u.試驗(yàn)向量與基準(zhǔn)向量和變異向量都不相同。雜交操作是對(duì)個(gè)體中的每一個(gè)元素進(jìn)行操作。

Cr的自適應(yīng)調(diào)整策略的數(shù)學(xué)表達(dá)式:

OldCri(t)=Cri(t),

NewCri(t)=

Cri(t+1)=

(5)

雜交操作的數(shù)學(xué)表達(dá)式:

ui,j(t)=

(6)

2.6　選擇操作

采用貪婪的選擇機(jī)制,如果試驗(yàn)向量的適應(yīng)度值好于基準(zhǔn)向量,則保留試驗(yàn)向量到下一代種群中,否則保留基準(zhǔn)向量。

2.7　終止迭代次數(shù)

終止迭代次數(shù)不宜過小或過大,過小時(shí)搜索不到全局最優(yōu)解,過大時(shí)增加搜索時(shí)間,降低搜索效率。終止迭代次數(shù)建議值為100～200.

3　實(shí)驗(yàn)結(jié)果與分析

3.1　實(shí)驗(yàn)方案

差分進(jìn)化算法無論是參數(shù)的設(shè)定還是每一代種群的產(chǎn)生都具有一定的隨機(jī)性,但這種隨機(jī)性并不是盲目的隨機(jī),而是基于上一代種群的隨機(jī)。所以,最終一定可以得到最優(yōu)解。如果算法連續(xù)獨(dú)立運(yùn)行一定的次數(shù),且每一次都能得到全局最優(yōu)解,則說明該算法具有一定的穩(wěn)定性。所以本實(shí)驗(yàn)的每組數(shù)據(jù)都連續(xù)做50次的伯努利實(shí)驗(yàn);將結(jié)果與LAMBDA算法的結(jié)果進(jìn)行對(duì)比,若兩種算法結(jié)果相同,則表明該自適應(yīng)差分進(jìn)化算法得到的是正確解,從而可以驗(yàn)證算法的正確性。本文分別基于實(shí)測(cè)和模擬數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析本算法的正確性、穩(wěn)定性及平均運(yùn)算速率。

本算法的參數(shù)設(shè)置如下:縮放因子F的初值設(shè)為0.5,雜交概率Cr的初值為0.9,終止迭代次數(shù)為50.

3.2　實(shí)驗(yàn)1

采用的是文獻(xiàn)[17]中3維整周模糊度的解算實(shí)例,目的是為了驗(yàn)證本文算法的可行性。圖2示出了一共進(jìn)行50次實(shí)驗(yàn),每次實(shí)驗(yàn)搜索到最優(yōu)解時(shí)的迭代次數(shù)以及最優(yōu)解所對(duì)應(yīng)的模糊度殘差二次型數(shù)值。從圖2可以看出50次實(shí)驗(yàn)中搜索到最優(yōu)解的最大迭代次數(shù)為8,且每次實(shí)驗(yàn)?zāi)：葰埐疃涡投际諗坑谕粋€(gè)值,說明算法具有較好的穩(wěn)定性。并與LAMBDA算法進(jìn)行了結(jié)果對(duì)比,二者結(jié)果一致。解算結(jié)果如表1所示。

N=[5.4500,3.1000,2.9700];

表1　3維模糊度的固定解及其二次型數(shù)值

3.3　實(shí)驗(yàn)2

表2　14維模糊度的固定解及其二次型數(shù)值

3.4　實(shí)驗(yàn)3

為了分析算法的普遍適用性程度,分別模擬生成15、20以及40、50、60維數(shù)據(jù)。采用文獻(xiàn)[18]的模擬方法進(jìn)行實(shí)驗(yàn)數(shù)據(jù)模擬。模糊度的浮點(diǎn)解構(gòu)造為

N=100×randn(n,1) ，

(7)

其中,n為模糊度的維數(shù),randn(n,1)為隨機(jī)生成的n個(gè)服從標(biāo)準(zhǔn)正態(tài)分布的數(shù)值。

由于方差協(xié)方差陣為實(shí)對(duì)稱矩陣,所以按照公式(8)生成QN：

QN=LTDL，

(8)

式中：L為隨機(jī)生成的n維正交矩陣;D為隨機(jī)生成的n維對(duì)角矩陣。

圖4(b)表明平均速度比圖4(c)快,是因?yàn)閳D4(c)所示的模糊度浮點(diǎn)解的精度沒有圖4(b)所示好,所以,圖4(c)表明收斂到最優(yōu)解的速度比圖4(b)慢些。解算結(jié)果如表3所示。

表3　15維模糊度的固定解及其二次型數(shù)值

20維和40維的數(shù)據(jù)找到最優(yōu)解的平均迭代次數(shù)大約在13和36次,如圖5和圖6所示。20維數(shù)據(jù)的尋優(yōu)速度明顯比15維圖4(b)、圖4(c)要快,是因?yàn)槠淠：雀↑c(diǎn)解的精度比較好。解算結(jié)果如表4、表5所示。

表4　20維模糊度的固定解及其二次型數(shù)值

表6示出了本文算法與LAMBDA算法在運(yùn)行效率上的對(duì)比，說明該算法在運(yùn)行效率上略優(yōu)于LAMBDA算法。

表6　本文算法與LAMBDA算法運(yùn)算效率比較

最后,筆者試算了50維和60維的模糊度,對(duì)于模糊度精度比較高的數(shù)據(jù)可以在運(yùn)算50次之內(nèi)找到最優(yōu)解,但是算法的穩(wěn)定性不是很好。即使增加迭代的步數(shù),穩(wěn)定性也沒有明顯的改善。

4　結(jié)束語

本文將智能算法中的DE算法應(yīng)用于整周模糊度的搜索中,并根據(jù)整周模糊度解算過程中數(shù)據(jù)的特點(diǎn),將Brest等提出的自適應(yīng)差分進(jìn)化算法進(jìn)行改進(jìn),使其更適用于模糊度最優(yōu)解的搜索。通過實(shí)測(cè)和模擬多組高維數(shù)據(jù),對(duì)本算法進(jìn)行了效果驗(yàn)證與分析?？梢缘贸鲆韵陆Y(jié)論:

1) 該自適應(yīng)算法可以用于整周模糊度的固定。對(duì)于40維以下的整周模糊度,該算法可以達(dá)到99.9%的固定,算法具有較好的穩(wěn)定性和通用性。但對(duì)于更高維的模糊度,解算效果不是很好,需要進(jìn)一步改善算法,以加快算法的收斂速度。

2) 通過比較本文算法和LAMBDA算法的平均運(yùn)算效率,發(fā)現(xiàn)本文算法基本上略快于LAMBDA算法。說明本算法可以用于模糊度的快速搜索。

3) 對(duì)于算法在迭代的后期容易出現(xiàn)“早熟”問題,通過設(shè)置較大的迭代次數(shù),并不能從根本上解決此問題。應(yīng)該深入研究變異算子和雜交算子,才能加快收斂速度。

[1]LI Z, GAO Y. A method for the construction of high-dimensional transformation matrices in Lambda [J].Geomatica,1998(52):433-439.

[2]TEUNISSEN P J G. A General multivariate formulation of the multi-antenna GNSS attitude determination problem [J]. Artificial Satellites, 2008, 42(2): 97-111.

[3]盧立果, 劉萬科, 李江衛(wèi). 降相關(guān)對(duì)模糊度解算中搜索效率的影響分析 [J]. 測(cè)繪學(xué)報(bào), 2015, 44(5): 481-487.

[4]BORNO M A, CHANG X W, XIE X H. On ‘decorrelation’ in solving integer least-squares problems for ambiguity determination [J]. Survey Review, 2013, 46(334): 37-49.

[5]CHANG X W, YANG X, ZHOU T. MLAMBDA: a modified LAMBDA method for integer least-squares estimation [J]. Journal of Geodesy, 2005, 79(9): 552-65.

[6]劉萬科,盧立果,單弘煜. 一種快速解算高維模糊度的LLL分塊處理算法 [J]. 測(cè)繪學(xué)報(bào), 2016(2): 147-156.

[7]盧立果,劉萬科,李江衛(wèi). 一種有效的LLL規(guī)約算法 [J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2016(8): 1118-1124.

[8]劉智敏,劉經(jīng)南,姜衛(wèi)平, 等. 遺傳算法解算GPS短基線整周模糊度的編碼方法研究 [J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2006(7): 607-609，631.

[9]陽仁貴,歐吉坤,王振杰, 等. 用遺傳算法搜索GPS單頻單歷元整周模糊度 [J]. 武漢大學(xué)學(xué)報(bào)(信息科學(xué)版), 2005(3): 251-254,259.

[10]VESTERSTROM J, THOMSEN R. A comparative study of differential evolution, particle swarm optimization, and evolutionary algorithms on numerical benchmark problems[C]// Evolutionary Computation, 2004. CEC2004. Congress on. IEEE, 2004(2):1980-1987.

[11]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.

[12]武志峰. 差異演化算法及其應(yīng)用研究 [D]. 北京交通大學(xué), 2009.

[13]汪慎文,丁立新,張文生, 等. 差分進(jìn)化算法研究進(jìn)展 [J]. 武漢大學(xué)學(xué)報(bào)(理學(xué)版), 2014(4): 283-92.

[14]BREST J, GREINER S, BOSKOVIC B,etal. Self-Adapting Control Parameters in Differential Evolution: A Comparative Study on Numerical Benchmark Problems [J]. IEEE Transactions on Evolutionary Computation, 2006, 10(6): 646-57.

[15]JONGE P D, TIBERIUS C. Integer Ambiguity Estimation with the Lambda Method [M]. Springer Berlin Heidelberg, 1996.

[16]TEUNISSEN P J G, JONGE P J D, TIBERIUS C C J M. The least-squares ambiguity decorrelation adjustment: its performance on short GPS baselines and short observation spans [J]. Journal of Geodesy, 1997, 71(10): 589-602.

[17]DE JONGE P J, TIBERIVS C C J M. The LAMBDA method for integer ambiguity estimation: Implementation aspects [R]. Dekft Geodetic Computing Centre, Delft University of Technology, 1996.

[18]XU P. Random simulation and GPS decorrelation [J]. Journal of Geodesy, 2001, 75(7-8): 408-23.