一種改進(jìn)混沌蟻群的地磁匹配算法

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

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

0 引言

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

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

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

1 MAGCOM地磁導(dǎo)航匹配算法研究

地磁輪廓線匹配算法匹配思路簡(jiǎn)單，匹配原理易于理解，實(shí)現(xiàn)相對(duì)容易。在對(duì)導(dǎo)航精度要求不高的情況下，是一種較好的選擇。

1.1 MAGCOM算法搜索原理

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

1.2 基于Hausdorff距離的地磁匹配

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

當(dāng)利用平均Hausdorff距離作為匹配軌跡與實(shí)測(cè)軌跡之間的度量函數(shù)時(shí)，根據(jù)地磁匹配原理和特點(diǎn)，該函數(shù)可具體定義為

式中：為待匹配區(qū)；為由Hausdorff距離函數(shù)求出每條序列適應(yīng)值；H為地磁實(shí)時(shí)測(cè)量序列值。(,)為地磁實(shí)時(shí)測(cè)量序列值到待匹配序列的單向Hausdorff距離；(,)為待匹配序列到地磁實(shí)時(shí)測(cè)量序列值的單向Hausdorff距離；當(dāng)MHD計(jì)算結(jié)果整體為極小值時(shí)，判定對(duì)應(yīng)的點(diǎn)即為最佳匹配點(diǎn)位。

2 基于改進(jìn)蟻群優(yōu)化的地磁匹配算法

針對(duì)MAGCOM算法的優(yōu)缺點(diǎn)，結(jié)合地磁匹配特點(diǎn)，本節(jié)提出一種改進(jìn)蟻群優(yōu)化算法。該算法能夠進(jìn)行智能全局優(yōu)化搜索，精度高并且具有強(qiáng)的抗干擾能力。

2.1 改進(jìn)蟻群優(yōu)化算法

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

1）初始化各個(gè)參數(shù)，即在計(jì)算之前對(duì)相關(guān)參數(shù)初始化。

2）隨機(jī)放置螞蟻到各個(gè)城市并利用概率轉(zhuǎn)移公式為螞蟻隨機(jī)選擇下一次去往的城市，利用該算法進(jìn)行地磁匹配時(shí)，載體上的傳感器在匹配區(qū)域測(cè)得的數(shù)據(jù)是存在一定噪聲的，導(dǎo)致啟發(fā)式因子對(duì)算法造成干擾，所以，將轉(zhuǎn)移概率公式中的啟發(fā)式因子部分去除，計(jì)算螞蟻從當(dāng)前點(diǎn)到點(diǎn)的轉(zhuǎn)移概率為

式中：為螞蟻在點(diǎn)時(shí)可以一步到達(dá)的位置；為經(jīng)過此路徑螞蟻的個(gè)數(shù)；為信息素啟發(fā)因子；()為時(shí)刻在點(diǎn)上的信息素濃度。

3）利用度量函數(shù)求出每次迭代的最優(yōu)解并記錄下來。

4）根據(jù)當(dāng)前最優(yōu)解進(jìn)行混沌局部再搜索，此步驟將混沌優(yōu)化算法與蟻群優(yōu)化算法融合，利用混沌優(yōu)化算法具有遍歷性和隨機(jī)性等特點(diǎn)，解決傳統(tǒng)蟻群優(yōu)化算法易陷入局部最優(yōu)問題。

5）更新信息素濃度，本文在信息素更新上主要做了三點(diǎn)改進(jìn)：①信息素更新方式，傳統(tǒng)蟻群算法是將信息素更新到兩個(gè)節(jié)點(diǎn)的路徑上，將兩點(diǎn)連線作為信息素存儲(chǔ)載體，該存儲(chǔ)方式大大增加了算法的空間復(fù)雜度。根據(jù)地磁匹配以及地磁基準(zhǔn)圖的特點(diǎn)，本文將信息素更新到各個(gè)節(jié)點(diǎn)上，每個(gè)點(diǎn)上信息素濃度的高低決定對(duì)螞蟻的吸引程度，該方式可有效降低算法的空間復(fù)雜性；②將混沌優(yōu)化算法的混動(dòng)擾動(dòng)因子加到信息素更新公式中，進(jìn)行全局信息素更新；③利用自適應(yīng)揮發(fā)因子()替換，傳統(tǒng)蟻群算法中揮發(fā)因子為(0,1)范圍內(nèi)的常量，算法在進(jìn)行匹配時(shí)，很容易存在未被搜索到的點(diǎn)的情況，當(dāng)?shù)欢ù螖?shù)后，由于蟻群算法的正反饋?zhàn)饔茫苋菀紫萑刖植孔顑?yōu)解。因此，本文設(shè)置揮發(fā)因子的最大最小值，利用()替換進(jìn)行自適應(yīng)調(diào)節(jié)，再利用混沌因子和() 改變信息素更新方法，并將混沌優(yōu)化算法中的變尺度混沌局部再搜索策略，引到蟻群算法尋優(yōu)過程中，使算法跳出局部最優(yōu)并加快算法收斂速度。其計(jì)算公式為

式中：為最小揮發(fā)系數(shù)；為最大揮發(fā)系數(shù)；為隨機(jī)數(shù)；()為自適應(yīng)揮發(fā)系數(shù)；為揮發(fā)因子調(diào)整系數(shù)，且∈(0,1)。

6）輸出最優(yōu)解。

2.2 改進(jìn)蟻群地磁匹配算法設(shè)計(jì)

通過對(duì)基于改進(jìn)蟻群優(yōu)化算法的相關(guān)介紹，本節(jié)將給出詳細(xì)的地磁匹配算法設(shè)計(jì)，具體流程如圖2所示。

圖1 基于改進(jìn)ACO的地磁匹配算法流程

1）初始化改進(jìn)蟻群優(yōu)化算法相關(guān)參數(shù)，具體包括（最大迭代次數(shù)）、（信息素?fù)]發(fā)因子）、（信息素因子）、（信息素常數(shù)）、（蟻群數(shù)量）等

2）設(shè)置初始信息素濃度，各節(jié)點(diǎn)初始信息素濃度采用非等值劃分，確保算法前期信息素作用明顯，同時(shí)設(shè)置最大最小初始信息素區(qū)間[,]，防止各節(jié)點(diǎn)初始信息素差異較大導(dǎo)致算法停滯。

3）將只螞蟻隨機(jī)放置到各個(gè)起點(diǎn)，根據(jù)改進(jìn)的概率轉(zhuǎn)移公式為每只螞蟻選擇下一節(jié)點(diǎn)，直至達(dá)到搜索節(jié)點(diǎn)個(gè)數(shù)為止。

4）利用度量函數(shù)求出本次迭代的最佳匹配序列，將該序列與上一次迭代求出的最優(yōu)解進(jìn)行對(duì)比更新并記錄下來，然后，以當(dāng)前最優(yōu)解為基礎(chǔ)進(jìn)行變尺度混沌局部再搜索，搜索點(diǎn)集的計(jì)算公式為

式中：為當(dāng)前最優(yōu)解；α為調(diào)節(jié)系數(shù)；為偽隨機(jī)數(shù)；γ為混沌變量，由烏拉姆-馮·諾伊曼（Ulam-von Neumann）映射產(chǎn)生，該映射的引入可以彌補(bǔ)邏輯斯蒂（Logistic）映射的不足，使搜索點(diǎn)在最優(yōu)解兩側(cè)的鄰域內(nèi)搜索。將可變調(diào)節(jié)系數(shù)α引入函數(shù)式中，可以更靈活地改變搜索范圍，同時(shí)引入偽隨機(jī)數(shù)的三次方縮小搜索范圍，加快算法收斂，其計(jì)算公式為

式中：為衰減系數(shù)；為混沌迭代系數(shù)；為當(dāng)前迭代次數(shù)。

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

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

6）將當(dāng)前迭代次數(shù)下的最優(yōu)解進(jìn)行保存，迭代次數(shù)=+1，將螞蟻隨機(jī)放置到各個(gè)節(jié)點(diǎn)并重新設(shè)置初始信息素濃度，進(jìn)行下一次迭代。當(dāng)達(dá)到最大迭代次數(shù)時(shí)，結(jié)束算法輸出最優(yōu)匹配序列。

3 實(shí)驗(yàn)分析

為驗(yàn)證上述算法的有效性，本文選取北京市某區(qū)域開展仿真實(shí)驗(yàn)。首先，利用CB-3銫光泵磁力儀和GPS導(dǎo)航設(shè)備在實(shí)驗(yàn)區(qū)域內(nèi)獲取200個(gè)采樣點(diǎn)的地磁屬性信息和經(jīng)緯度信息。然后，對(duì)其進(jìn)行空間結(jié)構(gòu)分析，確定地磁圖網(wǎng)格間距（本文地磁圖網(wǎng)格間距為50 m，網(wǎng)格大小為50 m×50 m），最后通過克里金插值法構(gòu)建該區(qū)域地磁，如圖2所示。

圖2 地磁等值線基準(zhǔn)

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

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

對(duì)上述算法進(jìn)行實(shí)驗(yàn)時(shí)，所涉及的參數(shù)設(shè)置如表1、表2所示。

表1 傳統(tǒng)ACO參數(shù)設(shè)置

表2 改進(jìn)ACO參數(shù)設(shè)置

3.2 實(shí)驗(yàn)結(jié)果分析

通過對(duì)基于MAD的地磁匹配算法、傳統(tǒng)蟻群優(yōu)化算法及改進(jìn)蟻群算法的地磁匹配算法進(jìn)行實(shí)驗(yàn)，得到匹配結(jié)果如圖2、圖3所示（注：圖2、圖3為地磁圖局部放大部分）。

圖3 傳統(tǒng)ACO匹配結(jié)果圖

由圖3和圖4匹配結(jié)果圖可知，在加入20nT磁場(chǎng)測(cè)量白噪聲的條件下，傳統(tǒng)蟻群優(yōu)化算法和MAD匹配算法匹配航跡均明顯偏離真實(shí)航跡，定位精度較差，MAD匹配算法偏離最為明顯，而改進(jìn)蟻群優(yōu)化算法匹配航跡仍在真實(shí)航跡附近，依然具有較高的匹配精度。

圖4 改進(jìn)ACO匹配結(jié)果圖

通過導(dǎo)航系統(tǒng)得到的20個(gè)采樣點(diǎn)的匹配誤差值進(jìn)行統(tǒng)計(jì)，并將各采樣點(diǎn)東向和北向誤差取絕對(duì)值求平均，得到統(tǒng)計(jì)結(jié)果如圖5所示。

圖5 采樣點(diǎn)匹配誤差數(shù)值曲線

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

通過每一次實(shí)驗(yàn)計(jì)算匹配航跡的東向和北向誤差取絕對(duì)值求平均后進(jìn)行統(tǒng)計(jì)，得到匹配結(jié)果如表3所示。

表3 不同算法匹配結(jié)果

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

4 結(jié)束語(yǔ)

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