一種改進混沌蟻群的地磁匹配算法

王崇兵，范榮雙，李大偉，任 偉

（1.遼寧工程技術大學, 測繪與地理科學學院，遼寧 阜新 123000；2.中國測繪科學研究院, 北京 100039；3.山東科技大學，測繪與空間信息學院，山東 青島 266590；4.北京博維航空設施管理有限公司，北京 101317）

0 引言

現代導航技術在當今社會發展中扮演者重要角色，無論是在民用還是在軍事領域，都離不開導航定位技術。目前已有多種較為成熟的導航系統和組合導航系統，包括全球定位系統（global positioning system, GPS）、慣性導航系統（inertial navigation system, INS）、GPS/INS組合導航系統等，但它們都存在不足之處并且通過自身系統難以克服，例如，GPS信號易受干擾、慣性導航系統具有累積誤差、地形導航在平緩地區地形起伏不明顯的情況下，導航會受到限制。隨著科技的進步及人們對導航的需求不斷加大，以上這些系統難以滿足長航時高精度導航的需求，地磁導航系統具有全天候可觀測、無源、誤差不隨時間累積等特點，可以較好地彌補現有的某些導航系統所存在的不足，因此，將地磁導航系統作為輔助糾正手段，是一種較好的選擇。早在 20世紀 60年代中期，美國的一家公司就提出了基于地磁輪廓匹配（magnetic contour matching, MAGCOM）算法，受當時條件限制，研究人員無法獲取地磁場數據，MAGCOM算法無法進行實驗驗證，但為后續地磁匹配研究奠定了基礎，具有深遠意義。

近年來，對MAGCOM算法的研究取得了許多成果：文獻[3]提出一種改進的基于等值線約束（contour constraint matching, CCM）相關匹配算法，采用粗匹配和精匹配結合的方式，有效消除了載體的初始位置誤差；文獻[4]提出一種改進型地形輪廓匹配（terrain contour matching, TERCOM）算法，用于水下地磁匹配導航，將基于平均豪斯多夫（Hausdorff）距離（modified Hausdorff distance,MHD）的匹配準則引入該算法中，有效提高了水下地磁匹配導航的精度和可靠性；基于相關性度量的地磁匹配算法存在匹配精度低，抗干擾能力弱等問題，但因其原理簡單、計算量小等優勢在地磁匹配導航領域仍受學者青睞；文獻[5]提出一種基于平均絕對距離（mean absolute difference, MAD）的地磁匹配導航算法，將維納濾波（Wiener filter,WF)、卡爾曼濾波（Kalman filter, KF）算法與MAD相融合后，來進行相關計算并最后確定載體位置，動態定位效果較好；將仿射變換模型引入地磁匹配算法中的應用也較為廣泛，隨著不斷地研究與探索，該類算法在匹配導航中效果較為明顯。文獻[6]針對匹配精度和算法效率相互制約問題，建立關于初始誤差、初始航向誤差、初始速度誤差的仿射變換模型，在提高算法精度的同時縮短了算法時間；文獻[7]將匹配軌跡與實測數據進行相關性約束，對約束函數進行離散化后引入仿射變換模型中，有效解決了慣導系統長時間定位過程中誤差累積問題；文獻[8]提出一種基于蟻群優化（ant colony optimization, ACO）的地磁場匹配改進算法，將地磁匹配看作為多級優化問題，采用多級蟻群優化算法進行匹配定位，在算法尋優過程中，利用雙重適應度函數進行計算，有效解決了無法利用任意形狀路徑的匹配導航問題；文獻[9]提出一種自適應模擬退火-蟻群地磁匹配導航算法，將模擬退火（simulated annealing, SA）算法與ACO算法融合并改變信息素更新策略，有效解決了算法輸出次優解問題；文獻[10]針對參考軌跡存在速度誤差的問題，提出一種基于仿射遺傳的地磁匹配導航算法，實現了參考軌跡存在速度誤差下的地磁匹配；文獻[11]提出一種基于粒子約束的粒子群地磁匹配算法，利用地磁基準圖和地磁測量冗余信息，計算待匹配點為實際位置的置信概率，有效提高算法的匹配速度及匹配概率。

關于地磁匹配算法還有很多新穎的算法，如基于神經網絡的地磁匹配算法、三角匹配算法等，在不同的應用背景下有著不同的創新方法，本文只敘述了地磁匹配算法在不斷演進過程中，比較具有代表性的一些算法。在前人研究的基礎上，針對MAGCOM算法過于依賴慣導系統導致算法具有的局限性，且抗噪效果差、匹配精度較低問題，提出一種改進混沌蟻群的地磁匹配算法，該算法改進了蟻群算法的概率轉移公式及信息素的表示方式，將混沌優化算法嵌到蟻群算法尋優過程中，有效提高了匹配精度及匹配效率。最后通過實驗證明該算法在地磁匹配導航中的可行性和有效性。

1 MAGCOM地磁導航匹配算法研究

地磁輪廓線匹配算法匹配思路簡單，匹配原理易于理解，實現相對容易。在對導航精度要求不高的情況下，是一種較好的選擇。

1.1 MAGCOM算法搜索原理

MAGCOM算法的原理與 TERCOM有很多相同之處，它們都是利用相關度量算法進行相關性判別，相關性度量算法介紹可參考文獻[11]，采用批量遍歷搜索的方式進行匹配。即在一定時間內累積一定長度的軌跡，獲取該軌跡上若干個軌跡點并獲取相應的特征值進行相關匹配。不同的是，基于MAGCOM的地磁匹配算法是以地磁值作為特征量進行判別，而地形輪廓匹配算法的特征量為地形數據，具體搜索過程也可參考文獻[11]。

1.2 基于Hausdorff距離的地磁匹配

Hausdorff距離已在圖像識別領域得到了廣泛應用，該算法最常用作比較兩組點集的相似度，用極大極小值最為評判準則，抗干擾能力較強，計算速度快，具有較好的穩定性和魯棒性。并且，該算法非常適用于任意曲線形狀的匹配。因此，選取該函數作為改進的地磁匹配算法匹配序列與實測序列之間的度量函數。文獻[4]給出了平均Hausdorff距離函數基本概念。

當利用平均Hausdorff距離作為匹配軌跡與實測軌跡之間的度量函數時，根據地磁匹配原理和特點，該函數可具體定義為

式中：為待匹配區；為由Hausdorff距離函數求出每條序列適應值；H為地磁實時測量序列值。(,)為地磁實時測量序列值到待匹配序列的單向Hausdorff距離；(,)為待匹配序列到地磁實時測量序列值的單向Hausdorff距離；當MHD計算結果整體為極小值時，判定對應的點即為最佳匹配點位。

2 基于改進蟻群優化的地磁匹配算法

針對MAGCOM算法的優缺點，結合地磁匹配特點，本節提出一種改進蟻群優化算法。該算法能夠進行智能全局優化搜索，精度高并且具有強的抗干擾能力。

2.1 改進蟻群優化算法

蟻群優化算法是受自然界螞蟻尋找食物過程的啟發，提出的一種尋找最優路徑的智能隨機搜索算法。將該算法運用到地磁匹配導航中，可以解決當載體運行軌跡不明確且為任意形狀的情況下，自主匹配定位的問題，但該算法存在計算量大，受噪聲影響大，前期因初始濃度相同，未發揮出正反饋效果導致收斂效率低下，以及在搜索過程中次優解占據優勢，使算法陷入局部最優等問題。針對以上問題，本文對該算法進行一定的改進。改進蟻群優化算法的實現主要分為以下幾部分：

1）初始化各個參數，即在計算之前對相關參數初始化。

2）隨機放置螞蟻到各個城市并利用概率轉移公式為螞蟻隨機選擇下一次去往的城市，利用該算法進行地磁匹配時，載體上的傳感器在匹配區域測得的數據是存在一定噪聲的，導致啟發式因子對算法造成干擾，所以，將轉移概率公式中的啟發式因子部分去除，計算螞蟻從當前點到點的轉移概率為

式中：為螞蟻在點時可以一步到達的位置；為經過此路徑螞蟻的個數；為信息素啟發因子；()為時刻在點上的信息素濃度。

3）利用度量函數求出每次迭代的最優解并記錄下來。

4）根據當前最優解進行混沌局部再搜索，此步驟將混沌優化算法與蟻群優化算法融合，利用混沌優化算法具有遍歷性和隨機性等特點，解決傳統蟻群優化算法易陷入局部最優問題。

5）更新信息素濃度，本文在信息素更新上主要做了三點改進：①信息素更新方式，傳統蟻群算法是將信息素更新到兩個節點的路徑上，將兩點連線作為信息素存儲載體，該存儲方式大大增加了算法的空間復雜度。根據地磁匹配以及地磁基準圖的特點，本文將信息素更新到各個節點上，每個點上信息素濃度的高低決定對螞蟻的吸引程度，該方式可有效降低算法的空間復雜性；②將混沌優化算法的混動擾動因子加到信息素更新公式中，進行全局信息素更新；③利用自適應揮發因子()替換，傳統蟻群算法中揮發因子為(0,1)范圍內的常量，算法在進行匹配時，很容易存在未被搜索到的點的情況，當迭代一定次數后，由于蟻群算法的正反饋作用，很容易陷入局部最優解。因此，本文設置揮發因子的最大最小值，利用()替換進行自適應調節，再利用混沌因子和() 改變信息素更新方法，并將混沌優化算法中的變尺度混沌局部再搜索策略，引到蟻群算法尋優過程中，使算法跳出局部最優并加快算法收斂速度。其計算公式為

式中：為最小揮發系數；為最大揮發系數；為隨機數；()為自適應揮發系數；為揮發因子調整系數，且∈(0,1)。

6）輸出最優解。

2.2 改進蟻群地磁匹配算法設計

通過對基于改進蟻群優化算法的相關介紹，本節將給出詳細的地磁匹配算法設計，具體流程如圖2所示。

圖1 基于改進ACO的地磁匹配算法流程

1）初始化改進蟻群優化算法相關參數，具體包括（最大迭代次數）、（信息素揮發因子）、（信息素因子）、（信息素常數）、（蟻群數量）等

2）設置初始信息素濃度，各節點初始信息素濃度采用非等值劃分，確保算法前期信息素作用明顯，同時設置最大最小初始信息素區間[,]，防止各節點初始信息素差異較大導致算法停滯。

3）將只螞蟻隨機放置到各個起點，根據改進的概率轉移公式為每只螞蟻選擇下一節點，直至達到搜索節點個數為止。

4）利用度量函數求出本次迭代的最佳匹配序列，將該序列與上一次迭代求出的最優解進行對比更新并記錄下來，然后，以當前最優解為基礎進行變尺度混沌局部再搜索，搜索點集的計算公式為

式中：為當前最優解；α為調節系數；為偽隨機數；γ為混沌變量，由烏拉姆-馮·諾伊曼（Ulam-von Neumann）映射產生，該映射的引入可以彌補邏輯斯蒂（Logistic）映射的不足，使搜索點在最優解兩側的鄰域內搜索。將可變調節系數α引入函數式中，可以更靈活地改變搜索范圍，同時引入偽隨機數的三次方縮小搜索范圍，加快算法收斂，其計算公式為

式中：為衰減系數；為混沌迭代系數；為當前迭代次數。

5）利用改寫的信息素更新公式，全局信息素更新的計算方法為

式中：Δ()為時刻螞蟻從當前點到點信息素變化量；τ為信息素變化總量；N表示蟻群數目；(+1)為Ulam_von Neumann映射產生的混沌因子。

6）將當前迭代次數下的最優解進行保存，迭代次數=+1，將螞蟻隨機放置到各個節點并重新設置初始信息素濃度，進行下一次迭代。當達到最大迭代次數時，結束算法輸出最優匹配序列。

3 實驗分析

為驗證上述算法的有效性，本文選取北京市某區域開展仿真實驗。首先，利用CB-3銫光泵磁力儀和GPS導航設備在實驗區域內獲取200個采樣點的地磁屬性信息和經緯度信息。然后，對其進行空間結構分析，確定地磁圖網格間距（本文地磁圖網格間距為50 m，網格大小為50 m×50 m），最后通過克里金插值法構建該區域地磁，如圖2所示。

圖2 地磁等值線基準

利用載有CB-3銫光泵磁力儀和GPS導航設備的汽車作為真實軌跡；根據真實軌跡加入初始位置誤差（100 m,300 m）、陀螺儀零偏誤差0.01(°)/h、加速度計零偏誤差 5 0× 1 0×（=9.806 65 m/s）等慣導系統常見誤差計算生成慣導軌跡；實測序列中加入 20nT白噪聲，增強隨機測量噪聲干擾；軌跡形狀在地磁圖中隨機生成；匹配后的軌跡分別由傳統蟻群算法、基于蟻群算法改進的地磁匹配算法以及MAD算法匹配得到。MAD算法是由文獻[6]中提出的一種地磁匹配算法，MAD算法是MAGCOM匹配算法中較為經典且具有代表性，因此，利用該算法的匹配結果作參考可使實驗分析結果更具有說服力。

3.1 實驗參數設置

對上述算法進行實驗時，所涉及的參數設置如表1、表2所示。

表1 傳統ACO參數設置

表2 改進ACO參數設置

3.2 實驗結果分析

通過對基于MAD的地磁匹配算法、傳統蟻群優化算法及改進蟻群算法的地磁匹配算法進行實驗，得到匹配結果如圖2、圖3所示（注：圖2、圖3為地磁圖局部放大部分）。

圖3 傳統ACO匹配結果圖

由圖3和圖4匹配結果圖可知，在加入20nT磁場測量白噪聲的條件下，傳統蟻群優化算法和MAD匹配算法匹配航跡均明顯偏離真實航跡，定位精度較差，MAD匹配算法偏離最為明顯，而改進蟻群優化算法匹配航跡仍在真實航跡附近，依然具有較高的匹配精度。

圖4 改進ACO匹配結果圖

通過導航系統得到的20個采樣點的匹配誤差值進行統計，并將各采樣點東向和北向誤差取絕對值求平均，得到統計結果如圖5所示。

圖5 采樣點匹配誤差數值曲線

通過圖5可知：利用平均絕對差（MAD）進行匹配，各采樣點匹配誤差較大，虛線變化幅度較為明顯，匹配效果差；傳統蟻群算法匹配精度優于MAD地磁匹配算法，但受測量噪聲影響較大，曲線震蕩也較為明顯，說明該算法抗噪能力弱，穩定性差。改進蟻群優化算法與MAD和傳統蟻群優化算法相比較而言，整體匹配誤差小，而且匹配誤差曲線變化較為平緩，說明該算法抗噪能力強，穩定性較好，可以進行地磁匹配導航。

通過每一次實驗計算匹配航跡的東向和北向誤差取絕對值求平均后進行統計，得到匹配結果如表3所示。

表3 不同算法匹配結果

由表3可知：在測量噪聲較為明顯的條件下，基于蟻群改進的地磁匹配算法較 MAD地磁匹配算法精度提高了約171 m；較傳統的蟻群優化算法精度提高了約74 m。由此可知，該算法抗干擾能力較強，具有一定的魯棒性，具有更高的定位精度和更好的匹配效果。

4 結束語

隨著社會的快速發展，人們對地磁匹配導航算法也提出了更高的要求，匹配速度快、精度高、穩定性好是判斷地磁匹配算法優劣的先決條件。因此，為了讓地磁匹配導航技術在導航定位領域發揮更大的作用，提出該算法以Hausdorff距離作為度量函數并利用該函數配合進行信息素更新，改進概率轉移公式及信息素表示方式，將混沌優化算法與基本蟻群算法融合進行地磁匹配，有效彌補了 MAGCOM 算法存在的缺陷，減少測量噪聲對地磁匹配結果的影響，實現了地磁匹配算法精度的提高。文中選取北京某區域地磁基準圖進行實驗，實驗結果表明：該算法不僅可以在任意軌跡下進行匹配定位，而且在抗噪能力和匹配精度方面都優于傳統蟻群優化算法和 MAD的地磁匹配算法，可以利用該算法進行匹配導航。