王躍鋼，賈 磊，單 斌,2，嚴 濤

（1.第二炮兵工程大學(xué) 自動控制系，西安 710025；2.西北工業(yè)大學(xué) 自動化學(xué)院，西安 710072）

自適應(yīng)SA-ACO地磁匹配導(dǎo)航算法

王躍鋼1，賈 磊1，單 斌1,2，嚴 濤1

（1.第二炮兵工程大學(xué) 自動控制系，西安 710025；2.西北工業(yè)大學(xué) 自動化學(xué)院，西安 710072）

基本蟻群算法的地磁匹配算法易陷入局部最優(yōu)且算法魯棒性、穩(wěn)定性較低，針對這些不足提出一種改進的地磁匹配導(dǎo)航算法。新算法改進了蟻群算法的信息素更新策略并引入?yún)?shù)自適應(yīng)調(diào)整來避免算法陷入局部最優(yōu)；同時采用帶有記憶功能和自適應(yīng)選擇初始溫度的模擬退火（SA）算法，無論算法是否陷入局部最優(yōu)時通過在本次迭代最優(yōu)路徑上強行隨機擾動以實現(xiàn)繼續(xù)尋優(yōu)。實驗結(jié)果表明，新算法比傳統(tǒng)蟻群優(yōu)化（ACO）算法有更強的魯棒性和穩(wěn)定性。

地磁匹配導(dǎo)航；自適應(yīng)；模擬退火；蟻群優(yōu)化；精英策略

地磁匹配導(dǎo)航是利用地球基本物理場之一的地磁場實現(xiàn)導(dǎo)航定位。其原理是當載體通過適配區(qū)域時，載體上的磁強計實時測出當?shù)氐卮盘卣髦担崪y特征值序列與載體上預(yù)存的地磁基準圖進行相關(guān)性匹配，估算出載體的實際位置坐標，供給導(dǎo)航計算機解算出導(dǎo)航信息[1-2]。傳統(tǒng)的地磁匹配算法有基于相關(guān)極值和基于剛性變換兩種[3-4]，這兩種算法是現(xiàn)在應(yīng)用最為廣泛的地磁匹配算法，但它們都有一定的局限性?；谙嚓P(guān)極值的匹配算法往往采用遍歷搜索的搜索策略，在基準圖上尋找與慣導(dǎo)輸出路徑形狀完全相同且相關(guān)性最優(yōu)的路徑，當慣導(dǎo)輸出路徑的形狀與真實路徑的形狀有偏差時，會造成匹配不可避免的存在偏差，而且在基準圖較大的情況下運算量較大，導(dǎo)致算法匹配時間較長，不利于與慣導(dǎo)進行組合?；趧傂宰儞Q的匹配算法要求磁傳感器沒有量測誤差，且匹配對象與目標對象已經(jīng)很接近，當慣導(dǎo)輸出的路徑誤差較大時，匹配結(jié)果往往偏差很大。傳統(tǒng)的地磁匹配算法的不足要求匹配算法能夠自主的尋找路徑且有一定的抗噪性。

蟻群算法是一種用來在尋找優(yōu)化路徑的機率型技術(shù)，能夠執(zhí)行智能搜索、進行全局優(yōu)化，具有魯棒性、正反饋、分布式計算、易于與其它算法相結(jié)合等特點。將該算法運用到地磁匹配導(dǎo)航當中可以解決當載體行進路徑形狀未知且為非直線的條件下自主匹配定位的問題[5]。

蟻群算法求解運算時表現(xiàn)出收斂速度慢、易陷入局部最優(yōu)的缺點，加之實測的磁場數(shù)值往往含有不同程度的噪聲，相關(guān)函數(shù)計算出的相關(guān)度量值并不能正確反應(yīng)真實航跡與匹配航跡的相似程度，這些將導(dǎo)致匹配的路徑與真實航跡的偏差較大。本文從蟻群算法自身的改進和引入模擬退火算法兩方面著手，提高匹配精度和算法穩(wěn)定性。

1 基本蟻群優(yōu)化的地磁匹配算法

蟻群優(yōu)化是一種用于求解復(fù)雜組合優(yōu)化問題的啟發(fā)式算法。由于地磁基準圖為網(wǎng)格式，因此可將地磁匹配定位看作是多級離散優(yōu)化問題。設(shè)M為螞蟻的數(shù)量，N為測量序列的長度（或稱作匹配長度），為載體軌跡上的實測磁場特征值，為基準圖上j點處的地磁特征值，為量測序列中對應(yīng)在基準圖上j點的第l個實測值。地磁在初始時刻信息素強度相等，螞蟻在運動過程中依據(jù)路徑上信息素強度的大小選擇轉(zhuǎn)移路徑。地磁匹配導(dǎo)航定位中的測量數(shù)據(jù)序列往往含有噪聲，導(dǎo)致啟發(fā)式因子對算法造成干擾，在算法搜索過程中螞蟻始終依據(jù)信息素強度來計算狀態(tài)轉(zhuǎn)移概率，第k級中螞蟻m由當前所在點i轉(zhuǎn)移到點j的狀態(tài)概率為如式(1)所示[6-7]：

其中，allowedi表示螞蟻在點i時可以一步到達的位置，α為信息素啟發(fā)因子，為i點到j(luò)點路徑（稱為路徑(i,j))上的信息素強度，其中點j是點i可一步到達的位置

當每一只螞蟻完成一次一個步長的搜索后利用度量函數(shù)評價該路徑的優(yōu)劣程度，一般采用相似性度量函數(shù)，即判斷螞蟻走過的路徑上的地磁特征值與實時測量的地磁量測序列之間的相似程度。相似性度量函數(shù)有距離度量和相關(guān)度量兩大類。距離度量算法包括平均絕對差（MAD）算法、平均平方差（MSD）算法、Hausdorff距離算法等。相關(guān)度量算法包括積相關(guān)（PROD）算法、歸一化積相關(guān)（NPROD）算法、相位相關(guān)（PC）算法等[8]。實際匹配過程中測量序列往往含有不同程度的噪聲，導(dǎo)致匹配結(jié)果是與含有噪聲的地磁序列最相似的路徑，而不是真實的路徑，這就要求相似性度量函數(shù)能夠有一定的抗噪性。經(jīng)過仿真對比發(fā)現(xiàn)，在噪聲較大的環(huán)境下，MAD的抗噪性要優(yōu)于NPROD，且MAD的匹配時間要遠遠小于其它算法。所以本文選用MAD作為全局相似性度量函數(shù)。全局相似性度量函數(shù)和局部相似性度量函數(shù)如式(2)(3)所示：

式中，N為匹配長度，為基準圖上螞蟻以p點為起始點第i步所經(jīng)過路徑上的地磁值，為一個匹配步長內(nèi)的實測地磁強度值序列。

在每只螞蟻走完一步或者完成對所有N個結(jié)點的遍歷后，要利用度量函數(shù)值對殘留信息進行更新處理，在t+1時刻路徑(i,j)上的信息素可按如下規(guī)則進行調(diào)整更新：

式中，ρ為信息揮發(fā)系數(shù)，1-ρ表示信息殘留因子，△τij為本次循環(huán)中點i到點j路徑上的信息素增量，為本次循環(huán)中第m只螞蟻留在路徑上的信息素，num為螞蟻的總個數(shù)，Q為反應(yīng)信息素更新量的信息素強度因子。信息素更新與相似度評價函數(shù)相結(jié)合，即螞蟻走過路徑上的地磁特征值與地磁量測序列中的特征值越相似信息素增加的越多，反之則越少。

2 模擬退火自適應(yīng)蟻群優(yōu)化的地磁匹配導(dǎo)航算法

雖然基本蟻群算法在解決地磁匹配問題上取得了很好的效果，但該算法仍存在算法穩(wěn)定性不高、抗噪性不強、易陷入局部最優(yōu)等缺點。本文從以下蟻群算法自身的改進和融合模擬退火算法兩個方面改進算法，以提高匹配的精度和算法穩(wěn)定性。

2.1 蟻群算法自身的改進

1）信息素更新策略的改進。信息素的正反饋原理是蟻群算法的核心之一，是螞蟻判斷如何選擇路徑的重要依據(jù)，信息素的分布情況直接影響到蟻群的搜索能力[9]。本文采用以下兩種方法改進信息素更新策略，以避免算法過早陷入局部最優(yōu)、提高算法的尋優(yōu)能力和抗噪性。

一是采用基于精英策略的全局更新與局部更新相結(jié)合更新信息素。全局更新中由于整條中的某一段可能是真實路徑的一部分，但因為搜索到的這條路徑度量值較差，導(dǎo)致本屬于真實路徑的一部分路徑上信息素增加量不大（甚至不增加），下次迭代時螞蟻選擇這段路徑的機率明顯下降。為此在全局更新的基礎(chǔ)上采用改進的局部更新，加強局部路徑的相似度判別。與為了適當增強較優(yōu)螞蟻釋放的信息素的正反饋，以加強較優(yōu)解在下次循環(huán)中對螞蟻的吸引力而引入精英策略，在每次循環(huán)后給全局度量函數(shù)值大于本次迭代平均全局度量函數(shù)值的路徑進行信息素更新，而對小于本次迭代平均全局度量值的路徑不進行信息素更新。依據(jù)度量函數(shù)的變化，在第NC次迭代中信息素的全局和局部兩重更新：

二是設(shè)置信息素及信息素增量的上下限以減小路徑上信息素的過大差異。蟻群算法陷入局部最優(yōu)的直接原因就是路徑上的信息素差異過大，導(dǎo)致在以后迭代中選擇其它路徑的概率過小，大量螞蟻集中在某一相同路徑上。將各條路徑上的信息素強度限制于區(qū)間內(nèi)，同時在每次更新信息素時將信息素增量限制于區(qū)間。當信息素更新使得超出允許范圍時可強制地將差異設(shè)置在允許的范圍內(nèi)，這樣可有效地避免了由算法的正反饋所引起的信息素強度差異過大而陷入局部最優(yōu)。

綜合以上兩點，信息素自適應(yīng)更新的總表達式為

2）參數(shù)的自適應(yīng)調(diào)整。蟻群算法在不同階段需要完成的任務(wù)不同，所以不同階段算法對參數(shù)的取值要求也不相同，這就需要算法在不同的階段自適應(yīng)調(diào)整參數(shù)。影響算法隨機性的參數(shù)主要有信息素啟發(fā)因子α和信息素揮發(fā)因子ρ。信息素啟發(fā)因子α反應(yīng)算法中隨機因素作用的強度，其值越小搜索的隨機性越大；信息素揮發(fā)因子ρ反應(yīng)螞蟻之間相互影響的強弱，其值越小信息素揮發(fā)的越慢，算法的隨機性和全局搜索能力越強。當算法求得的單次迭代的最優(yōu)路徑在若干次內(nèi)沒有明顯改進時適當減小啟發(fā)因子α和信息素揮發(fā)系數(shù)ρ。α和ρ按式(8)和式(9)作自適應(yīng)調(diào)整。

2.2 模擬退火算法與搜索路徑

模擬退火算法（SA）的實質(zhì)是不斷地在當前解的鄰域中找出一個適合當前解的過程，而適當?shù)泥徲蚰軌蚴顾惴ㄌ霎斍暗木植孔顑?yōu)解，從而趨于全局最優(yōu)。模擬退火算法的執(zhí)行策略為：從一個任意選擇的初始解開始探測整個搜索空間，并且通過一個擾動產(chǎn)生一個新解，利用Mertopolis接受準則判斷是否接受新解，相應(yīng)的下降控制溫度。以解j代替解i的Mertopolis接受準則如式(3)：

當蟻群算法陷入局部最優(yōu)，通過算法自身的自適應(yīng)調(diào)整不能夠跳出局部最優(yōu)時，就要通過“外界算法”強行地使蟻群算法跳出，以達到繼續(xù)尋優(yōu)的目的。同時，為增強算法的尋優(yōu)能力，算法未陷入局部最優(yōu)時也利用模擬退火算法。在蟻群算法本次迭代搜索到的最優(yōu)路徑上隨機選取一個結(jié)點，通過隨機擾動使該結(jié)點與最優(yōu)螞蟻未選擇的一個隨機結(jié)點交換以產(chǎn)生新路徑，比較新路徑與該次迭代的最優(yōu)路徑上的度量函數(shù)值。若新路徑比最優(yōu)路徑的相似度值更優(yōu)則用新路徑替代最優(yōu)路徑，否則采用Mertopolis接受準則決定接受還是放棄[10]。在新路徑的基礎(chǔ)上繼續(xù)進行擾動，直至達到終止條件。在退火算法中加入記憶功能[11]，即在接受準則判定是否接受新路徑時，不用新路徑代替最優(yōu)路徑，以保證最優(yōu)路徑變量存儲的永遠是度量值最優(yōu)的路徑。

初始溫度的設(shè)置。退火溫度決定算法的性能，因此在進行模擬退火時，先計算該次迭代中螞蟻走過所有路徑的度量函數(shù)值fm，判斷是否有度量函數(shù)值小于fmax的，若有則初始溫度，若沒有則初始溫度。

退火方案。溫度下降過快會導(dǎo)致算法產(chǎn)生淬火現(xiàn)象，使搜索不完全。這里采用指數(shù)降溫方案，即，其中0.95＜μ＜1，本文取μ=0.97。

終止條件。為了簡化計算，當溫度降到某一預(yù)先設(shè)定值時算法便停止計算。

2.3 算法實現(xiàn)步驟與流程

以下給出模擬退火自適應(yīng)蟻群優(yōu)化的地磁匹配導(dǎo)航算法的具體步驟：

2）將num只螞蟻放到起始點上，每只螞蟻按式(1)選擇路徑，選擇路徑并進行一步轉(zhuǎn)移后按式(3)計算局部度量函數(shù)值，通過迭代完成一個匹配步長的搜索；

3）將每只螞蟻走過的路徑按式(2)計算全局度量函數(shù)值fm，并計算全局度量函數(shù)平均值fave及全局度量函數(shù)最優(yōu)值fbest；

4）判斷算法是否陷入局部最優(yōu)，若是則轉(zhuǎn)到步驟5)，若不是則轉(zhuǎn)入步驟6)；

5）按式(8)(9)進行參數(shù)的自適應(yīng)調(diào)整；

6）按模擬退火算法的初始溫度設(shè)置方案設(shè)置初始溫度；

依據(jù) AAS-1996 結(jié)果的進一步分析，3 種不同的不安全型依戀模式對 PTSD 的影響也存在差異：回避型依戀模式的個體 PTSD 的發(fā)生率最低，僅有14.3%（1/7）；焦慮型依戀模式的個體 PTSD 發(fā)生率其次，為 46.4%（13/28）；而恐懼型依戀模式的個體 PTSD 發(fā)病率最高，達到 66.7%（8/12），3 種不同的不安全型依戀模式個體的 PTSD 發(fā)生率差異有統(tǒng)計學(xué)意義（χ2＝13.859，P＜0.01），表明恐懼型依戀模式的失獨個體更容易患 PTSD。

7）在此次迭代的最優(yōu)路徑上隨機選取一個結(jié)點，將該結(jié)點與最優(yōu)螞蟻可以選擇但未走過的一個隨機結(jié)點交換，并按式(1)完成一個匹配步長的搜索，計算擾動后的路徑度量函數(shù)值f′；

9）判斷是否達到退火終止條件，若未達到則采用退火方案進行降溫并轉(zhuǎn)到步驟7)，若達到終止條件則將算法本次迭代最終得到的最優(yōu)路徑作為本次迭代的最優(yōu)路徑；

10）按式(5)~(7)更新信息素并限制信息素及信息素增量的上下限，判斷是否達到最大迭代次數(shù)，若未達到則轉(zhuǎn)到步驟2)，若達到最大迭代次數(shù)轉(zhuǎn)到步驟(11)；

3 仿真試驗與分析

假設(shè)匹配的起始點已知，且載體每一步運動只能夠移動到當前點周圍的四個鄰域點。仿真時試驗的地磁基準圖采用某地區(qū)實測高精度X分量基準圖，地磁基準圖180×180個網(wǎng)格的地磁圖，網(wǎng)格大小為15.3 m ×9.9 m。設(shè)載體從起始點A點沿預(yù)定路徑運動到終點B點，實測地磁強度值序列tT由真實路徑上的地磁基準值和噪聲相疊加構(gòu)成，其中噪聲為均值為 0，標準差為10、20、30的高斯分布白噪聲。將300只螞蟻放在起始點A點上，設(shè)置如下參數(shù)：匹配步長N=10，蟻群算法最大迭代次數(shù)，，模擬退火的迭代次數(shù)為 20次，按照算法的流程開始運行。如圖 1至圖 3為仿真結(jié)果對比圖，為了便于觀察匹配結(jié)果，將匹配結(jié)果圖顯示范圍縮小為原地磁圖的一部分。

圖1至圖3為噪聲標準差為30 nT的高斯白噪聲環(huán)境下三種算法的一次匹配結(jié)果。采用模擬退火蟻群優(yōu)化的地磁匹配算法在穩(wěn)定性和抗噪性方面均有很大程度地提高。如表1所示，三種算法分別在標準差為10 nT、20 nT、30 nT高斯分布白噪聲情況下各仿真100次。由仿真結(jié)果可以看出，基本蟻群算法與改進的蟻群優(yōu)化算法在完全匹配概率和導(dǎo)航定位精度方面幾乎相同，其完全匹配概率最優(yōu)為27%和28%，終點導(dǎo)航定位偏差的標準差最小為83.64 m和78.29 m。而自適應(yīng)模擬退火優(yōu)化的地磁匹配導(dǎo)航算法完全匹配概率和終點導(dǎo)航定位偏差標準差最小能達到94%和22.74 m。

圖1 基本蟻群算法的匹配結(jié)果Fig.1 Matching result of the basic ant colony algorithm

圖2 改進蟻群優(yōu)化的匹配結(jié)果Fig.2 Matching result of improved ant colony e-optimization

圖3 模擬退火蟻群優(yōu)化的匹配結(jié)果Fig.3 Matching result of simulated algorithm annealing ant colony optimization

表1 不同算法匹配精度比較Tab.1 Matching precision of different algorithms

4 結(jié) 論

本文研究了自由任意路徑的地磁匹配導(dǎo)航算法，在基本蟻群算法的基礎(chǔ)上，提出了基于自適應(yīng)模擬退火蟻群優(yōu)化的地磁匹配導(dǎo)航算法，從蟻群算法自身的改進和加入模擬退火算法強行繼續(xù)尋優(yōu)兩個方面改進匹配算法。在蟻群算法自身改進方面，改進了信息素更新規(guī)則，并采用算法參數(shù)的自適應(yīng)調(diào)整；在模擬退火算法中加入記憶功能和依據(jù)蟻群算法尋優(yōu)結(jié)果自適應(yīng)選擇初始溫度。實驗結(jié)果表明，基于模擬退火蟻群優(yōu)化的地磁匹配導(dǎo)航算法能夠防止蟻群算法陷入局部最優(yōu)，較大程度地增強了算法的尋優(yōu)能力以及算法的抗噪性和穩(wěn)定性。

（References）：

[1]Guo Caifa,Li Anliang,Cai Hong,et al.Algorithm for geomagnetic navigation and its validity evaluation[C]//IEEE International Conference on Computer Science and Automation Engineering.Shanghai,2011:573-577.

[2]單斌，王躍鋼，楊波.地磁多特征量匹配定位關(guān)鍵技術(shù)研究[C]//第二屆信息、電子與計算機工程國際學(xué)術(shù)會議.2010，11：721-725.SHAN Bin,WANG Yue-gang,YANG Bo.Study on key technologies of multi geomagnetic elements matching localization[C]//Proceedings of The 2010 International Conference on Information Electronic and Computer Science.2010,11:721-725.

[3]Zhao Jianhu.Study on underwater navigation system based on geomagnetic match technique[C]//The Ninth International Conference on Electronic Measurement ＆Instruments.Beijing,China,2009.

[4]Kato N,Shigetomi T.Underwater navigation for longrange autonomous underwater vehicles using geomagnetic and bathymetric information[J].Advanced Robotics，2009,23(7):787-803.

[5]陳勵華，王仕成，喬玉坤.基于蟻群優(yōu)化的地磁場匹配改進算法[J].電光與控制，2010，17(8)：49-52.CHEN Li-hua,WANG Shi-cheng,QIAO yu-kun.An improved magnetic field contour matching algorithm based on ant colony optimization[J].Electronics Optics and Control,2010,17(8):49-52.

[6]Fuellerer G,Doerner K F,Richard F,et al.Ant colony optimization for the two-dimensional loading vehicle routing problem[J].Computers and Operations Research,2009,36(3):655-673.

[7]Zhu Jingwei,Rui Ting,Jiang Xinsheng,Juelong Li.Ant colony algorithm based on simulated annealing method[C]//2010 International Conference on Circuit and Signal Processing.2010-12:290-293.

[8]陳衛(wèi)兵.幾種圖像相似性度量的匹配性能比較[J].計算機應(yīng)用，2010，30(1)：98-101.CHEN Wei-bing.Comparison of matching capabilities in similarity measurements[J].Journal of Computer Applications,2010,30(1):98-101.

[9]鄭衛(wèi)國，田其沖，張磊.基于信息素強度的改進蟻群算法[J].計算機仿真，2010，27(7)：191-194.ZHENG Wei-guo,TIAN Qi-chong,ZHANG Lei.An improved ant colony algorithm based on pheromone intensity[J].Computer Simulation,2010,27(7):191-194.

[10]ZHU Jing-wei,RUI Ting,LIAO Ming,ZHANG Jin-lin.Multi-group ant colony algorithm based on simulated annealing method[J].Journal of Shanghai University (English Edition),2010,14(6):464-468.

[11]ZHU Zhan-long,YANG Gong-liu,SHAN You-dong,et al.Comprehensive evolution method of geomagnetic map suitability analysis[J].Journal of Chinese Inertial Technology,2013,21(3):375-380.

Adaptive SA-ACO geomagnetic matching navigation algorithm

WANG Yue-gang1,JIA Lei1,SHAN Bin1,2,YAN Tao1
(1.Department of Automation,The Second Artillery Engineering University,Xi’an 710025,China;2.School of Automation,Northwestern Polytechnical University,Xi’an 710072,China)

In view that the geomagnetic matching algorithm based on the basic ant colony algorithm tends to fall in local optimum and the robust and stability of the basic algorithm are low,an improved geomagnetic matching navigation algorithm is proposed.To avoid the algorithm fall in the local optimum,the strategy of pheromone updating is improved and the adaptive adjustment of parameters are introduced.Meanwhile,the simulated annealing algorithm with memory function and adaptive determination of initial temperature is also introduced.So whether the algorithm fall in local optimum or not,it could continue to search better route by applying random disturbances on the best route of this iteration to achieve continued optimization.The experiment results show that the new algorithm is more robust and stability than traditional ant colony optimization.

geomagnetic matching navigation;adaptive;simulated annealing;ant colony optimization;elitist strategy

V249.32

：A

1005-6734(2014)01-0089-05

10.13695/j.cnki.12-1222/o3.2014.01.018

2013-10-14；

：2013-12-09

國防預(yù)研（103030203）

王躍鋼（1958—），男，教授，博士生導(dǎo)師，從事導(dǎo)航與制導(dǎo)技術(shù)研究。E-mail：wangyueg@163.com