李洪剛，王亞琦，李雪晴，亢俊健

(河北地質(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ì)量.

1 GPS短基線整周模糊度與解算數(shù)學(xué)模型

1.1 GPS短基線整周模糊度

對(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í)，可得整周模糊度的固定解.

1.2 解算模型

由(6)式可知，第i個(gè)模糊度值為

遺傳算法根據(jù)目標(biāo)函數(shù)來計(jì)算適應(yīng)度函數(shù)，從而確定最優(yōu)解.根據(jù)(6)式，判別函數(shù)可表示為

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

2 基于模擬退火遺傳算法的整周模糊度求解

2.1 模擬退火算法

遺傳算法是一種有效的尋優(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生成新種群迭代更新.

2.2 Cholesky降相關(guān)處理

為了加快模糊度的搜索，需要對(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]為

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

很多經(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ù).

2.4 遺傳算子設(shè)計(jì)及算法過程

(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)入下一代.

3 實(shí)驗(yà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)小于人工魚群算法.

4 結(jié)語

遺傳算法具有較強(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).