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

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

(河北地質(zhì)大學，河北 石家莊 050031)

GPS以載波相位觀測量為依據(jù)進行精密定位，迅速又準確地固定整周模糊度是進行高精度相對定位、縮短工作時間和擴展高精度動態(tài)定位的關鍵.在整周模糊度的解算上，國內(nèi)外學者提出了很多解算算法，如基于LAMBDA算法[1]、FARA算法、蟻群算法[2]、人工魚群算法(Artificial Fish Swarm Algorithm,AFSA)[3]和遺傳算法(Genetic Algorithm，GA)[4-5]等.遺傳算法是一種以模擬自然進化過程來搜索最優(yōu)解的方法，通過選擇、交叉、變異等操作來尋求最優(yōu)解.在搜索整周模糊度最優(yōu)解的問題上遺傳算法具有全局優(yōu)化、穩(wěn)健、高效等特點，但同時也面臨著搜索空間較大、計算較為復雜且容易陷入局部最優(yōu)等問題.模擬退火(Simulated Annealing,SA)[6-8]算法是從某一較高初溫出發(fā)，伴隨溫度參數(shù)的不斷下降并結合概率突跳特性，在解空間中隨機尋找目標函數(shù)的全局最優(yōu)解，從而有效避免陷入局部最優(yōu)解并最終達到全局最優(yōu)解的優(yōu)化算法.因此，筆者提出利用基于實數(shù)編碼的模擬退火遺傳算法(Simulated Annealing Genetic Algorithm,SAGA)來求解整周模糊度，利用模擬退火來避免遺傳算法的早熟問題，有望提高搜索質(zhì)量.

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

1.1 GPS短基線整周模糊度

對定位模型進行線性處理，即將載波相位雙差模型線性化，得到GPS短基線相位雙差定位模型

y=Aa+Bb+εa∈Zn,b∈Rp.

(1)

其中：y為m維的GNSS觀測量，一般包括觀測時間內(nèi)各頻率的碼觀測值和載波相位觀測值；A和B是整周模糊度和基線參數(shù)的設計矩陣；ε為觀測噪聲向量；a是單位為周的雙差整周模糊度向量，b為包含基線向量和其他實數(shù)參數(shù)的向量.

由(1)式可得

(2)

進一步計算(2)式,可得

(3)

(4)

使用最小二乘法，(4)式可表示為

(5)

(6)

其中N為整周模糊度的組合數(shù).當目標函數(shù)最小時，可得整周模糊度的固定解.

1.2 解算模型

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

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

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

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

2.1 模擬退火算法

遺傳算法是一種有效的尋優(yōu)算法，但僅采用遺傳算法求解整周模糊度效果并不太好[10].因此，改進算法一方面采用實數(shù)編碼來簡化參數(shù)，減小引入模擬退火機制所產(chǎn)生的計算量；另一方面，引入模擬退火機制來避免陷入局部最優(yōu)解，提高遺傳算法的搜索能力.其基本流程為先隨機產(chǎn)生一個初始種群，經(jīng)過繁殖、交叉、變異等操作產(chǎn)生新的個體，這些個體經(jīng)模擬退火后進入新一輪的遺傳迭代運算[11].求解整周模糊度時，隨著搜索范圍變得越來越小，遺傳算法易陷入局部最優(yōu).在目標函數(shù)最優(yōu)值迭代中，隨著溫度的下降，模擬退火算法可以訪問更多的領域，搜索更大范圍的解空間，從而有效避免遺傳算法的早熟收斂問題.模擬退火的基本流程如下：

Step1初始化模擬退火算法參數(shù)，如初始溫度、溫度降低參數(shù)、模擬退火記錄次數(shù).

Step2根據(jù)判別函數(shù)來判定當代種群的最優(yōu)值是否比上一代的好，若是，則保留當代最好的個體和適應度，并將之代替當代最差的個體和適應度，溫度下降，然后轉step 5.

Step3若當代的最優(yōu)值比上一代最優(yōu)值差，則計算bh=vlast-vcur，ph= exp(1 000×bh/T).其中：bh是溫度差；ph是降溫的概率；vlast是上一代最優(yōu)值；vcur是當代最優(yōu)值；T為當前溫度.

Step4當rand是0～1的隨機數(shù),ph大于rand時，保留上一代最好個體和適應度并代替當代最差的個體和適應度.

Step5生成新種群迭代更新.

2.2 Cholesky降相關處理

為了加快模糊度的搜索，需要對整周模糊度的浮點解和協(xié)方差矩陣進行Z變換，從而降低模糊度協(xié)方差矩陣的相關性.針對高斯分解去相關運算存在數(shù)值計算不穩(wěn)定、運算量是喬里斯基分解的2倍的缺點，首先采用Cholesky分解對協(xié)方差矩陣進行去相關運算，然后對分解矩陣進行Z變換.具體過程[6，12]為

2.3 實數(shù)編碼

很多經(jīng)典的遺傳算法都采用二進制編碼.但相比二進制編碼，實數(shù)編碼能夠反映整周模糊度解的結構特征，使得計算更加簡單快捷,并且能避免Hamming懸崖問題.如采用二進制和7位編碼，整周模糊度的組合有(27)3=2 097 152個，而采用實數(shù)編碼時模糊度的組合僅有213=9 261個，遠遠小于二進制編碼的組合數(shù).

2.4 遺傳算子設計及算法過程

(1)選擇.筆者采用經(jīng)典的輪盤選擇原理來選擇種群的個體，每個個體被選擇的期望值與其適應度值和群體平均適應值的比值相關[10].首先計算適應度的累加，個體的適應度越大，占適應度累加和的比例就越大，被選擇的概率就越高.

(2)單點交叉.交叉即結合來自父代交配種群的信息而產(chǎn)生新的個體.交叉算子的選擇決定了交叉操作的頻率，交叉算子概率越高，收斂速度越快，但也有可能帶來過早收斂的情況.本研究隨機對2個個體的2點進行交叉，經(jīng)多次實驗后取交叉概率為0.6.

(3)變異.變異概率一般選擇較小的數(shù)值，若選擇較高的變異概率，可能會破壞最優(yōu)解.經(jīng)多次實驗后，本研究的變異概率取0.06.此時效果最佳.

(4)遺傳退火.隨著遺傳算法的不斷迭代，種群也越來越逼近最優(yōu)解，但由于遺傳算法的交叉、變異等操作可能會破壞接近最優(yōu)解的個體，使相對最差的個體進入下一代，不利于遺傳算法的求解；因此筆者將精華保留與模擬退火相結合，在交叉變異操作后按照一定的策略選擇最佳個體以代替最差個體，從而保證最差個體不進入下一代.

3 實驗分析

依照文獻[13]中的解算實例進行仿真分析，整周模糊度的取值范圍為[-10,10]，選取的三維GPS模糊度浮點解及其相應的協(xié)方差矩陣分別為

本實驗以時間效率、成功率和模糊度固定正確所需的迭代次數(shù)作為評價指標，先后對比有無去相關和是否添加模擬退火對算法性能的影響程度，最后將改進算法與經(jīng)典LAMBDA算法進行比較.表1列出了部分實驗參數(shù)，表2列出了整周模糊度的固定解.

表1 參數(shù)設置

表2 實例解算結果

經(jīng)去相關處理過的協(xié)方差矩陣較原始協(xié)方差矩陣，其元素之間的相關性有了明顯的降低，適應度的函數(shù)特性發(fā)生了明顯的變化.去相關前、后適應度的函數(shù)分布分別如圖1，2所示.由圖1，2可知，去相關前的函數(shù)存在多個極值，求解整周模糊度時容易陷入局部最優(yōu)，而經(jīng)去相關后的函數(shù)較單調(diào)，只有一個極值，因此能提高求解整周模糊度的正確率和效率.

圖1 去相關前適應度函數(shù)分布Fig. 1 Fitness Function Before Decorrelation

圖2 去相關后適應度函數(shù)分布Fig. 2 Fitness Function After Decorrelation

因為對固定后的整周模糊度的估計具有不確定性，所以要進行模糊度正確性的檢驗.只有驗證了整周模糊度的質(zhì)量即模糊度固定解的可靠性，討論模糊度固定解的正確率才有意義.ratio值作為模糊度得到固定解的置信度指標，是檢驗整周模糊度固定可靠性的最常用方法之一，可以由次優(yōu)的模糊度向量的殘差平方和與最優(yōu)的模糊度向量的殘差平方和的比值得到[14].根據(jù)經(jīng)驗，ratio值一般可以取2或3，在本實驗中設ratio值為3，當ratio值大于3時，判定模糊度固定解是正確的[15].

為了驗證算法的有效性和可靠性，針對傳統(tǒng)遺傳算法和模擬退火遺傳算法重復進行了100次對比實驗，分別對比了2種算法的模糊度固定解所需的迭代次數(shù)、適應度和運行時間.實驗結果如圖3—5所示.

圖3 迭代次數(shù)對比Fig. 3 Comparison of Numbers of Iterations

圖4 適應度變化對比Fig. 4 Comparison of Fitness Values

圖5 運行時間對比Fig. 5 Comparison of Search Time Between Two Algorithms

由圖3可知，模擬退火遺傳算法的迭代次數(shù)明顯少于傳統(tǒng)遺傳算法，即遺傳算法經(jīng)模擬退火算法改進后，能以更快的收斂速度收斂到全局最優(yōu)解，從而以更少的迭代次數(shù)達到固定的正確解.

由圖4可知，模擬退火遺傳算法的迭代次數(shù)明顯少于傳統(tǒng)遺傳算法，即遺傳算法經(jīng)模擬退火算法改進后，能以更高的效率收斂到全局最優(yōu)解，并且更加穩(wěn)定.

由圖5的數(shù)據(jù)計算可得模擬退火遺傳算法的平均運行時間為0.060 s，收斂速度稍慢于傳統(tǒng)遺傳算法.將模擬退火遺傳算法與經(jīng)典LAMBDA算法、遺傳算法和人工魚群算法的性能進行比較，100次實驗的平均值列于表3.表3中：tmean為算法平均運行時間；Nmean為正確固定整周模糊度的平均次數(shù)；Smean為模糊度固定解的正確率.

表3 4種算法性能比較

由表3的實驗數(shù)據(jù)可知：模擬退火遺傳算法與LAMBDA算法相比，算法效率和成功率相差不多，但模擬退火遺傳算法在計算結果上的穩(wěn)定性和精度遠遠優(yōu)于傳統(tǒng)的遺傳算法；在保持極高的固定整周模糊度的成功率下，模擬退火遺傳算法在計算時間上遠遠小于人工魚群算法.

4 結語

遺傳算法具有較強的全局搜索能力，但在實際應用中容易出現(xiàn)早熟的問題，而模擬退火機制可以有效跳出局部最優(yōu)，從而幫助遺傳算法快速收斂到全局最優(yōu)解.引入模擬退火思想，筆者對基于實數(shù)編碼的遺傳算法進行了改進，并將改進的算法應用于整周模糊度問題的解算上.實驗結果表明，改進的算法在有效性和穩(wěn)定性方面都有優(yōu)秀的表現(xiàn).