自適應SA-ACO地磁匹配導航算法

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

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

自適應SA-ACO地磁匹配導航算法

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

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

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

地磁匹配導航；自適應；模擬退火；蟻群優化；精英策略

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

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

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

1 基本蟻群優化的地磁匹配算法

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

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

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

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

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

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

2 模擬退火自適應蟻群優化的地磁匹配導航算法

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

2.1 蟻群算法自身的改進

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

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

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

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

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

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

模擬退火算法（SA）的實質是不斷地在當前解的鄰域中找出一個適合當前解的過程，而適當的鄰域能夠使算法跳出當前的局部最優解，從而趨于全局最優。模擬退火算法的執行策略為：從一個任意選擇的初始解開始探測整個搜索空間，并且通過一個擾動產生一個新解，利用Mertopolis接受準則判斷是否接受新解，相應的下降控制溫度。以解j代替解i的Mertopolis接受準則如式(3)：

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

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

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

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

2.3 算法實現步驟與流程

以下給出模擬退火自適應蟻群優化的地磁匹配導航算法的具體步驟：

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

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

4）判斷算法是否陷入局部最優，若是則轉到步驟5)，若不是則轉入步驟6)；

5）按式(8)(9)進行參數的自適應調整；

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

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

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

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

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

3 仿真試驗與分析

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

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

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

圖2 改進蟻群優化的匹配結果Fig.2 Matching result of improved ant colony e-optimization

圖3 模擬退火蟻群優化的匹配結果Fig.3 Matching result of simulated algorithm annealing ant colony optimization

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

4 結 論

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

（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]單斌，王躍鋼，楊波.地磁多特征量匹配定位關鍵技術研究[C]//第二屆信息、電子與計算機工程國際學術會議.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]陳勵華，王仕成，喬玉坤.基于蟻群優化的地磁場匹配改進算法[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]陳衛兵.幾種圖像相似性度量的匹配性能比較[J].計算機應用，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]鄭衛國，田其沖，張磊.基于信息素強度的改進蟻群算法[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

國防預研（103030203）

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