基于自適應差分進化算法的高維模糊度搜索

孫妍艷,劉翠芝

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

0　引　言

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

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

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

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

1　數學模型及原理

1.1　整數最小二乘原理

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

聯系人: 孫妍艷E-mail: 767564911@qq.com

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

(1)

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

1.2　差分進化算法原理

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

標準差分進化算法的原理是:首先,隨機生成初始種群,從種群中隨機選擇兩個個體向量的差分量作為第三個隨機基準向量的擾動量,得到變異向量,然后變異向量與基準向量進行雜交,生成試驗向量,最后,采用貪婪選擇機制,將基準向量與試驗向量競爭,適應度高者保存到下一代種群中。從而,種群逐漸聚集到最優解的位置。

目前,差分進化算法已廣泛應用于很多領域,如人工神經網絡,化工,電力,機械設計,機器人,信號處理,生物,運籌學,控制工程,數據挖掘,調度問題等并取得了驚人的效果[13]。其缺點是,差分進化算法并沒有一個系統的研究,所以每個領域都要根據其自身的特點進行算法設計。

2　自適應差分進化算法設計

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

2.1　適應度函數

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

(2)

2.2　初始化操作

2.3　變異操作

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

F的自適應調整策略的數學表達式:

OldFi(t)=Fi(t).

NewFi(t)=

(3)

變異操作的數學表達式為

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

Ni3(t)) .

(4)

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

2.4　修補操作

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

2.5　雜交操作

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

Cr的自適應調整策略的數學表達式:

OldCri(t)=Cri(t),

NewCri(t)=

Cri(t+1)=

(5)

雜交操作的數學表達式:

ui,j(t)=

(6)

2.6　選擇操作

采用貪婪的選擇機制,如果試驗向量的適應度值好于基準向量,則保留試驗向量到下一代種群中,否則保留基準向量。

2.7　終止迭代次數

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

3　實驗結果與分析

3.1　實驗方案

差分進化算法無論是參數的設定還是每一代種群的產生都具有一定的隨機性,但這種隨機性并不是盲目的隨機,而是基于上一代種群的隨機。所以,最終一定可以得到最優解。如果算法連續獨立運行一定的次數,且每一次都能得到全局最優解,則說明該算法具有一定的穩定性。所以本實驗的每組數據都連續做50次的伯努利實驗;將結果與LAMBDA算法的結果進行對比,若兩種算法結果相同,則表明該自適應差分進化算法得到的是正確解,從而可以驗證算法的正確性。本文分別基于實測和模擬數據進行統計分析本算法的正確性、穩定性及平均運算速率。

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

3.2　實驗1

采用的是文獻[17]中3維整周模糊度的解算實例,目的是為了驗證本文算法的可行性。圖2示出了一共進行50次實驗,每次實驗搜索到最優解時的迭代次數以及最優解所對應的模糊度殘差二次型數值。從圖2可以看出50次實驗中搜索到最優解的最大迭代次數為8,且每次實驗模糊度殘差二次型都收斂于同一個值,說明算法具有較好的穩定性。并與LAMBDA算法進行了結果對比,二者結果一致。解算結果如表1所示。

N=[5.4500,3.1000,2.9700];

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

3.3　實驗2

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

3.4　實驗3

為了分析算法的普遍適用性程度,分別模擬生成15、20以及40、50、60維數據。采用文獻[18]的模擬方法進行實驗數據模擬。模糊度的浮點解構造為

N=100×randn(n,1) ，

(7)

其中,n為模糊度的維數,randn(n,1)為隨機生成的n個服從標準正態分布的數值。

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

QN=LTDL，

(8)

式中：L為隨機生成的n維正交矩陣;D為隨機生成的n維對角矩陣。

圖4(b)表明平均速度比圖4(c)快,是因為圖4(c)所示的模糊度浮點解的精度沒有圖4(b)所示好,所以,圖4(c)表明收斂到最優解的速度比圖4(b)慢些。解算結果如表3所示。

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

20維和40維的數據找到最優解的平均迭代次數大約在13和36次,如圖5和圖6所示。20維數據的尋優速度明顯比15維圖4(b)、圖4(c)要快,是因為其模糊度浮點解的精度比較好。解算結果如表4、表5所示。

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

表6示出了本文算法與LAMBDA算法在運行效率上的對比，說明該算法在運行效率上略優于LAMBDA算法。

表6　本文算法與LAMBDA算法運算效率比較

最后,筆者試算了50維和60維的模糊度,對于模糊度精度比較高的數據可以在運算50次之內找到最優解,但是算法的穩定性不是很好。即使增加迭代的步數,穩定性也沒有明顯的改善。

4　結束語

本文將智能算法中的DE算法應用于整周模糊度的搜索中,并根據整周模糊度解算過程中數據的特點,將Brest等提出的自適應差分進化算法進行改進,使其更適用于模糊度最優解的搜索。通過實測和模擬多組高維數據,對本算法進行了效果驗證與分析。可以得出以下結論:

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

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

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

[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]盧立果, 劉萬科, 李江衛. 降相關對模糊度解算中搜索效率的影響分析 [J]. 測繪學報, 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]. 測繪學報, 2016(2): 147-156.

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

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

[9]陽仁貴,歐吉坤,王振杰, 等. 用遺傳算法搜索GPS單頻單歷元整周模糊度 [J]. 武漢大學學報(信息科學版), 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]武志峰. 差異演化算法及其應用研究 [D]. 北京交通大學, 2009.

[13]汪慎文,丁立新,張文生, 等. 差分進化算法研究進展 [J]. 武漢大學學報(理學版), 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.