李洪剛,王亞琦,李雪晴,亢俊健
(河北地質(zhì)大學(xué),河北 石家莊 050031)
GPS以載波相位觀測(cè)量為依據(jù)進(jìn)行精密定位,迅速又準(zhǔn)確地固定整周模糊度是進(jìn)行高精度相對(duì)定位、縮短工作時(shí)間和擴(kuò)展高精度動(dòng)態(tài)定位的關(guān)鍵.在整周模糊度的解算上,國(guó)內(nèi)外學(xué)者提出了很多解算算法,如基于LAMBDA算法[1]、FARA算法、蟻群算法[2]、人工魚群算法(Artificial Fish Swarm Algorithm,AFSA)[3]和遺傳算法(Genetic Algorithm,GA)[4-5]等.遺傳算法是一種以模擬自然進(jìn)化過程來搜索最優(yōu)解的方法,通過選擇、交叉、變異等操作來尋求最優(yōu)解.在搜索整周模糊度最優(yōu)解的問題上遺傳算法具有全局優(yōu)化、穩(wěn)健、高效等特點(diǎn),但同時(shí)也面臨著搜索空間較大、計(jì)算較為復(fù)雜且容易陷入局部最優(yōu)等問題.模擬退火(Simulated Annealing,SA)[6-8]算法是從某一較高初溫出發(fā),伴隨溫度參數(shù)的不斷下降并結(jié)合概率突跳特性,在解空間中隨機(jī)尋找目標(biāo)函數(shù)的全局最優(yōu)解,從而有效避免陷入局部最優(yōu)解并最終達(dá)到全局最優(yōu)解的優(yōu)化算法.因此,筆者提出利用基于實(shí)數(shù)編碼的模擬退火遺傳算法(Simulated Annealing Genetic Algorithm,SAGA)來求解整周模糊度,利用模擬退火來避免遺傳算法的早熟問題,有望提高搜索質(zhì)量.
對(duì)定位模型進(jìn)行線性處理,即將載波相位雙差模型線性化,得到GPS短基線相位雙差定位模型
y=Aa+Bb+εa∈Zn,b∈Rp.
(1)
其中:y為m維的GNSS觀測(cè)量,一般包括觀測(cè)時(shí)間內(nèi)各頻率的碼觀測(cè)值和載波相位觀測(cè)值;A和B是整周模糊度和基線參數(shù)的設(shè)計(jì)矩陣;ε為觀測(cè)噪聲向量;a是單位為周的雙差整周模糊度向量,b為包含基線向量和其他實(shí)數(shù)參數(shù)的向量.
由(1)式可得
(2)
進(jìn)一步計(jì)算(2)式,可得
(3)
(4)
使用最小二乘法,(4)式可表示為
(5)
(6)
其中N為整周模糊度的組合數(shù).當(dāng)目標(biāo)函數(shù)最小時(shí),可得整周模糊度的固定解.
由(6)式可知,第i個(gè)模糊度值為
遺傳算法根據(jù)目標(biāo)函數(shù)來計(jì)算適應(yīng)度函數(shù),從而確定最優(yōu)解.根據(jù)(6)式,判別函數(shù)可表示為
f(N)=b-lg(J(N)).
遺傳算法是一種有效的尋優(yōu)算法,但僅采用遺傳算法求解整周模糊度效果并不太好[10].因此,改進(jìn)算法一方面采用實(shí)數(shù)編碼來簡(jiǎn)化參數(shù),減小引入模擬退火機(jī)制所產(chǎn)生的計(jì)算量;另一方面,引入模擬退火機(jī)制來避免陷入局部最優(yōu)解,提高遺傳算法的搜索能力.其基本流程為先隨機(jī)產(chǎn)生一個(gè)初始種群,經(jīng)過繁殖、交叉、變異等操作產(chǎn)生新的個(gè)體,這些個(gè)體經(jīng)模擬退火后進(jìn)入新一輪的遺傳迭代運(yùn)算[11].求解整周模糊度時(shí),隨著搜索范圍變得越來越小,遺傳算法易陷入局部最優(yōu).在目標(biāo)函數(shù)最優(yōu)值迭代中,隨著溫度的下降,模擬退火算法可以訪問更多的領(lǐng)域,搜索更大范圍的解空間,從而有效避免遺傳算法的早熟收斂問題.模擬退火的基本流程如下:
Step1初始化模擬退火算法參數(shù),如初始溫度、溫度降低參數(shù)、模擬退火記錄次數(shù).
Step2根據(jù)判別函數(shù)來判定當(dāng)代種群的最優(yōu)值是否比上一代的好,若是,則保留當(dāng)代最好的個(gè)體和適應(yīng)度,并將之代替當(dāng)代最差的個(gè)體和適應(yīng)度,溫度下降,然后轉(zhuǎn)step 5.
Step3若當(dāng)代的最優(yōu)值比上一代最優(yōu)值差,則計(jì)算bh=vlast-vcur,ph= exp(1 000×bh/T).其中:bh是溫度差;ph是降溫的概率;vlast是上一代最優(yōu)值;vcur是當(dāng)代最優(yōu)值;T為當(dāng)前溫度.
Step4當(dāng)rand是0~1的隨機(jī)數(shù),ph大于rand時(shí),保留上一代最好個(gè)體和適應(yīng)度并代替當(dāng)代最差的個(gè)體和適應(yīng)度.
Step5生成新種群迭代更新.
為了加快模糊度的搜索,需要對(duì)整周模糊度的浮點(diǎn)解和協(xié)方差矩陣進(jìn)行Z變換,從而降低模糊度協(xié)方差矩陣的相關(guān)性.針對(duì)高斯分解去相關(guān)運(yùn)算存在數(shù)值計(jì)算不穩(wěn)定、運(yùn)算量是喬里斯基分解的2倍的缺點(diǎn),首先采用Cholesky分解對(duì)協(xié)方差矩陣進(jìn)行去相關(guān)運(yùn)算,然后對(duì)分解矩陣進(jìn)行Z變換.具體過程[6,12]為
很多經(jīng)典的遺傳算法都采用二進(jìn)制編碼.但相比二進(jìn)制編碼,實(shí)數(shù)編碼能夠反映整周模糊度解的結(jié)構(gòu)特征,使得計(jì)算更加簡(jiǎn)單快捷,并且能避免Hamming懸崖問題.如采用二進(jìn)制和7位編碼,整周模糊度的組合有(27)3=2 097 152個(gè),而采用實(shí)數(shù)編碼時(shí)模糊度的組合僅有213=9 261個(gè),遠(yuǎn)遠(yuǎn)小于二進(jìn)制編碼的組合數(shù).
(1)選擇.筆者采用經(jīng)典的輪盤選擇原理來選擇種群的個(gè)體,每個(gè)個(gè)體被選擇的期望值與其適應(yīng)度值和群體平均適應(yīng)值的比值相關(guān)[10].首先計(jì)算適應(yīng)度的累加,個(gè)體的適應(yīng)度越大,占適應(yīng)度累加和的比例就越大,被選擇的概率就越高.
(2)單點(diǎn)交叉.交叉即結(jié)合來自父代交配種群的信息而產(chǎn)生新的個(gè)體.交叉算子的選擇決定了交叉操作的頻率,交叉算子概率越高,收斂速度越快,但也有可能帶來過早收斂的情況.本研究隨機(jī)對(duì)2個(gè)個(gè)體的2點(diǎn)進(jìn)行交叉,經(jīng)多次實(shí)驗(yàn)后取交叉概率為0.6.
(3)變異.變異概率一般選擇較小的數(shù)值,若選擇較高的變異概率,可能會(huì)破壞最優(yōu)解.經(jīng)多次實(shí)驗(yàn)后,本研究的變異概率取0.06.此時(shí)效果最佳.
(4)遺傳退火.隨著遺傳算法的不斷迭代,種群也越來越逼近最優(yōu)解,但由于遺傳算法的交叉、變異等操作可能會(huì)破壞接近最優(yōu)解的個(gè)體,使相對(duì)最差的個(gè)體進(jìn)入下一代,不利于遺傳算法的求解;因此筆者將精華保留與模擬退火相結(jié)合,在交叉變異操作后按照一定的策略選擇最佳個(gè)體以代替最差個(gè)體,從而保證最差個(gè)體不進(jìn)入下一代.
依照文獻(xiàn)[13]中的解算實(shí)例進(jìn)行仿真分析,整周模糊度的取值范圍為[-10,10],選取的三維GPS模糊度浮點(diǎn)解及其相應(yīng)的協(xié)方差矩陣分別為
本實(shí)驗(yàn)以時(shí)間效率、成功率和模糊度固定正確所需的迭代次數(shù)作為評(píng)價(jià)指標(biāo),先后對(duì)比有無去相關(guān)和是否添加模擬退火對(duì)算法性能的影響程度,最后將改進(jìn)算法與經(jīng)典LAMBDA算法進(jìn)行比較.表1列出了部分實(shí)驗(yàn)參數(shù),表2列出了整周模糊度的固定解.
表1 參數(shù)設(shè)置
表2 實(shí)例解算結(jié)果
經(jīng)去相關(guān)處理過的協(xié)方差矩陣較原始協(xié)方差矩陣,其元素之間的相關(guān)性有了明顯的降低,適應(yīng)度的函數(shù)特性發(fā)生了明顯的變化.去相關(guān)前、后適應(yīng)度的函數(shù)分布分別如圖1,2所示.由圖1,2可知,去相關(guān)前的函數(shù)存在多個(gè)極值,求解整周模糊度時(shí)容易陷入局部最優(yōu),而經(jīng)去相關(guān)后的函數(shù)較單調(diào),只有一個(gè)極值,因此能提高求解整周模糊度的正確率和效率.
圖1 去相關(guān)前適應(yīng)度函數(shù)分布Fig. 1 Fitness Function Before Decorrelation
圖2 去相關(guān)后適應(yīng)度函數(shù)分布Fig. 2 Fitness Function After Decorrelation
因?yàn)閷?duì)固定后的整周模糊度的估計(jì)具有不確定性,所以要進(jìn)行模糊度正確性的檢驗(yàn).只有驗(yàn)證了整周模糊度的質(zhì)量即模糊度固定解的可靠性,討論模糊度固定解的正確率才有意義.ratio值作為模糊度得到固定解的置信度指標(biāo),是檢驗(yàn)整周模糊度固定可靠性的最常用方法之一,可以由次優(yōu)的模糊度向量的殘差平方和與最優(yōu)的模糊度向量的殘差平方和的比值得到[14].根據(jù)經(jīng)驗(yàn),ratio值一般可以取2或3,在本實(shí)驗(yàn)中設(shè)ratio值為3,當(dāng)ratio值大于3時(shí),判定模糊度固定解是正確的[15].
為了驗(yàn)證算法的有效性和可靠性,針對(duì)傳統(tǒng)遺傳算法和模擬退火遺傳算法重復(fù)進(jìn)行了100次對(duì)比實(shí)驗(yàn),分別對(duì)比了2種算法的模糊度固定解所需的迭代次數(shù)、適應(yīng)度和運(yùn)行時(shí)間.實(shí)驗(yàn)結(jié)果如圖3—5所示.
圖3 迭代次數(shù)對(duì)比Fig. 3 Comparison of Numbers of Iterations
圖4 適應(yīng)度變化對(duì)比Fig. 4 Comparison of Fitness Values
圖5 運(yùn)行時(shí)間對(duì)比Fig. 5 Comparison of Search Time Between Two Algorithms
由圖3可知,模擬退火遺傳算法的迭代次數(shù)明顯少于傳統(tǒng)遺傳算法,即遺傳算法經(jīng)模擬退火算法改進(jìn)后,能以更快的收斂速度收斂到全局最優(yōu)解,從而以更少的迭代次數(shù)達(dá)到固定的正確解.
由圖4可知,模擬退火遺傳算法的迭代次數(shù)明顯少于傳統(tǒng)遺傳算法,即遺傳算法經(jīng)模擬退火算法改進(jìn)后,能以更高的效率收斂到全局最優(yōu)解,并且更加穩(wěn)定.
由圖5的數(shù)據(jù)計(jì)算可得模擬退火遺傳算法的平均運(yùn)行時(shí)間為0.060 s,收斂速度稍慢于傳統(tǒng)遺傳算法.將模擬退火遺傳算法與經(jīng)典LAMBDA算法、遺傳算法和人工魚群算法的性能進(jìn)行比較,100次實(shí)驗(yàn)的平均值列于表3.表3中:tmean為算法平均運(yùn)行時(shí)間;Nmean為正確固定整周模糊度的平均次數(shù);Smean為模糊度固定解的正確率.
表3 4種算法性能比較
由表3的實(shí)驗(yàn)數(shù)據(jù)可知:模擬退火遺傳算法與LAMBDA算法相比,算法效率和成功率相差不多,但模擬退火遺傳算法在計(jì)算結(jié)果上的穩(wěn)定性和精度遠(yuǎn)遠(yuǎn)優(yōu)于傳統(tǒng)的遺傳算法;在保持極高的固定整周模糊度的成功率下,模擬退火遺傳算法在計(jì)算時(shí)間上遠(yuǎn)遠(yuǎn)小于人工魚群算法.
遺傳算法具有較強(qiáng)的全局搜索能力,但在實(shí)際應(yīng)用中容易出現(xiàn)早熟的問題,而模擬退火機(jī)制可以有效跳出局部最優(yōu),從而幫助遺傳算法快速收斂到全局最優(yōu)解.引入模擬退火思想,筆者對(duì)基于實(shí)數(shù)編碼的遺傳算法進(jìn)行了改進(jìn),并將改進(jìn)的算法應(yīng)用于整周模糊度問題的解算上.實(shí)驗(yàn)結(jié)果表明,改進(jìn)的算法在有效性和穩(wěn)定性方面都有優(yōu)秀的表現(xiàn).
吉首大學(xué)學(xué)報(bào)(自然科學(xué)版)2018年4期