GAOWei，ZHAO Bo，ZHOU Guangtao

(College of Automation，Harbin Engineering University，Harbin 150001，China)

Gravity Matching Method Based on Artificial Bee Colony Algorithm with Restriction and MHD*

GAOWei，ZHAO Bo，ZHOU Guangtao*

(College of Automation，Harbin Engineering University，Harbin 150001，China)

Gravity matching algorithm is one of the key technologies for gravity aided inertial navigation system. However，there are lots of defects such as high complexity and small range of applications for the traditionalmatchingmethods，so it is difficult to obtain a accurate and fastmatching result.This article will introduce artificial bee colony algorithm with restriction into the searching process of gravitymatching and take the velocity information provided by DVL as a restriction condition to restrict the searching process of artificial bee colony.On this basis，modified Hausdorff distance(MHD)is introduced in order to select thematching results.As a result，the mismatch rate will decrease with the accuracy of the gravity anomaly in gravity database under certain conditions.The simulation results show that the algorithm has a highmatch rate and can obtain accurate and fast positioning in the gravity zone with significant feature in order to realize gravity aided inertial navigation.

gravitymatching;modified hausdorff distance;artificial bee colony;external restriction

20世紀80年代～90年代美國和前蘇聯(lián)便相繼開始了研制戰(zhàn)略水下潛器的無源導航輔助系統(tǒng)。最初的輔助方法是基于圖形匹配，包括與海底地形圖、磁場圖的匹配，但由于需要用聲納測量海底輪廓，導致海底地形匹配的隱蔽性較弱;同時由于磁場變化復雜目前還難以真正運用到水下潛器導航中，因此重力異常和重力梯度數(shù)據(jù)成為水下潛器導航的主要無源信息資源。重力輔助導航具有精度高、隱蔽性強、自主性強等優(yōu)點，是潛艇等水下航行器理想的水下輔助導航定位手段［1－2］。經(jīng)典的重力匹配方法有遞推最優(yōu)估計濾波和相關(guān)值匹配方法兩大類。近幾年，在相關(guān)值匹配方向有較多研究成果，包括神經(jīng)網(wǎng)絡(luò)、支持向量機、數(shù)據(jù)關(guān)聯(lián)濾波等［3－5］。但是在匹配精度上沒有太大提高。

2005年，Karaboga模仿蜜蜂行為提出了人工蜂群算法，該算法是集群智能思想的一個具體應(yīng)用［6］。它只需要對問題進行優(yōu)劣的比較，最終在群體中使全局最優(yōu)值突現(xiàn)出來，在很大程度上避免了局部最優(yōu)的缺陷，適用于區(qū)域目標搜索過程。為此，本文將人工蜂群算法引入到重力匹配搜索過程中，并將外部速度信息作為約束條件，對匹配點進行限制，在一定程度上減少了誤配。同時，考慮到匹配結(jié)果的多值性，本文采用平均Hausdorff距離對匹配結(jié)果進行篩選。平均Hausdorff距離一般用于圖像匹配過程中測量兩個點集的匹配程度，利用這一準則以獲取最優(yōu)的匹配結(jié)果。

1 人工蜂群算法

在人工蜂群算法中，蜂群產(chǎn)生群體智慧的最小搜索模型包含基本的3個組成要素:蜜源、被雇傭的蜜蜂和未被雇傭的蜜蜂。被雇用的蜜蜂也稱為引領(lǐng)蜂，其與所采集的蜜源一一對應(yīng)，引領(lǐng)蜂儲存有某一個蜜源的相關(guān)信息并以一定的概率與其他蜜蜂分享。未被雇用的蜜蜂的主要任務(wù)是尋找和開采蜜源。有兩種未被雇用的蜜蜂:偵察蜂和跟隨蜂。偵察蜂搜索蜂巢附近的新蜜源;跟隨蜂在蜂巢里面并通過與引領(lǐng)蜂分享相關(guān)信息找到蜜源。

初始時刻，每個引領(lǐng)蜂對應(yīng)一個確定的蜜源，蜜源的花蜜量是由相應(yīng)解的適應(yīng)度值來決定的。初始化之后，引領(lǐng)蜂根據(jù)記憶中的局部信息產(chǎn)生一個新的位置并檢查新位置的花蜜量。若新位置的花蜜量比原來的多，則該蜜蜂更新記憶并記住新的位置。待所有的引領(lǐng)蜂搜索結(jié)束，將花蜜源信息傳遞給跟隨蜂。跟隨蜂根據(jù)引領(lǐng)蜂所找的蜜源的花蜜量，按概率選擇一只引領(lǐng)蜂并跟隨它，在這只引領(lǐng)蜂所在的蜜源附近再搜索到新的位置，并檢查新候選位置的花蜜量。若新位置優(yōu)于原來的位置，則更新并記住新的位置。不斷重復尋找到花蜜量最多的位置［8］。

人工蜂群算法的流程圖如圖1所示。

圖1 人工蜂群算法流程圖

其中，xij為引領(lǐng)蜂對應(yīng)的位置變量，cij為隨機數(shù)rand(－1，1)，隨機數(shù)i，k∈(1，N)，N為蜜蜂種群數(shù)量，j為隨機選取的某一位置變量下標。

跟隨蜂確定跟蹤引領(lǐng)蜂的概率按下式計算:

其中，fiti是第i個解的適應(yīng)度值，對應(yīng)蜜源的豐富程度。

如果經(jīng)過一定次數(shù)迭代后，得到的最優(yōu)解沒有改進，為了避免局部最優(yōu)解，要舍去該位置對應(yīng)的解，同時由偵察蜂代替引領(lǐng)蜂產(chǎn)生一個新的位置。這樣改進是為了增加種群的多樣性和隨機性。此時，按下式更新位置［9］。

2 平均Hausdorff距離

經(jīng)典Hausdorff距離是一種極大極小距離，用來描述兩組點集之間的相似程度。它的引入使重力匹配基于一種新的測度，能更為有效地表征點集之間相似性，從而對匹配點進行篩選［10］。

有限點集A={a1，a2，…，ap}和B={b1，b2，…，bq}之間的Hausdorff距離定義為:

其中:

式中‖·‖為在點集A和B上的某種距離范數(shù); dh(A，B)稱為A和B之間的Hausdorff距離，表示點集A中所有的點到點集B的距離的最大值;dH(A，B)取dh(A，B)和dh(B，A)中較大值，從而可以得到點集A和B之間的匹配程度。

考慮到經(jīng)典Hausdorff距離容易受到外部干擾，必將導致計算結(jié)果存在較大誤差，從而影響匹配的效果，故引入平均Hausdorff距離的定義:

其中，

式中，NA表示點集A中的點個數(shù);NB表示點集B中的點個數(shù)。

3 重力匹配算法

本文采用雙人工蜂群搜索方式，依據(jù)相同的搜索策略分別在相鄰慣導指示位置周圍尋找匹配點。但是兩個匹配點之間的距離受到外部速度信息的約束，盡管這樣，得到匹配結(jié)果仍具有多值性，針對這一問題，本文利用平均Hausdorff距離對匹配點對進行篩選，從而實現(xiàn)重力匹配定位［11－12］。

如圖2所示，Pk－1、Pk和Pk+1分別表示INS在k－1、k和k+1時刻指示載體的位置，同時，重力儀可以輸出每個時刻的重力異常值Δgk－1、Δgk和Δgk+1。以k－1和k時刻為例，最終確定的最佳匹配點對(~Pk－1和~Pk)需同時滿足下面的條件:

式中，Δgobs(k)表示k時刻重力儀輸出的重力異常值;Δg(~Pk)表示k時刻搜索點~Pk－1在重力數(shù)據(jù)庫(EGM2008)中插值得到的重力異常值;σd和σg分別表示距離和重力異常差的閾值。

圖2 引入外部速度信息的重力匹配原理圖

在蜂群搜索過程中，適應(yīng)度函數(shù)值按下式計算:

根據(jù)平均Hausdorff距離準則對多組匹配結(jié)果(~Pk－1(i)和~Pk(i))進行篩選，確定一個最優(yōu)的位置作為最終匹配結(jié)果，滿足下式:

其中，N為待篩選的匹配點個數(shù);~Pk－1、k(i)為第i個匹配點對;Pk－1、k為INS輸出的位置點對;^Pk－1、k為篩選后輸出的匹配點對。

根據(jù)前面的匹配過程可知，每個時刻都要經(jīng)過兩次匹配，并取兩次匹配平均值作為最終結(jié)果，類似于估計理論中的“估計”和“平滑”兩個過程。在有些情況下，可以提供載體準確的位置信息或者匹配過程中初始位置誤差較小，可以考慮簡化匹配模型，即用Pk－1來代替~Pk－1。這樣減少了一個約束條件，有效縮短了匹配時間。在實際過程中，可以間隔一定步長按簡化前模型匹配，在獲取較準確位置后，再進行簡化模型匹配，這樣既保證了匹配精度，又縮短了匹配時間［13］。匹配算法的工作原理如圖3所示。

圖3 匹配流程圖

4 仿真分析

4.1 仿真條件及過程

模擬生成慣導系統(tǒng)的運動軌跡包括INS指示軌跡和載體真實軌跡，其中載體真實軌跡為一段直線;建立重力異常數(shù)據(jù)庫，利用模擬的載體真實位置信息通過插值可以得到載體所在位置的真實重力異常值，在此基礎(chǔ)上加上一定量測噪聲(0.1 mgal)來模擬重力敏感器輸出;人工峰群算法的參數(shù)設(shè)置為如表1。

表1 人工峰群算法參數(shù)

根據(jù)EGM2008重力異常數(shù)據(jù)庫，獲取INS指示軌跡和載體真實軌跡附近的重力異常分布如圖4。

圖4 匹配區(qū)域的重力異常變化

4.2 仿真結(jié)果

按以上條件進行仿真，如圖5所示，對重力匹配前后的運動軌跡進行對比，其中匹配過程分為未引入和引入Hausdorff距離兩種情況，重力輔助導航系統(tǒng)的定位誤差小于一個重力基準網(wǎng)格。

圖5 不同條件下匹配軌跡效果對比

引入Hausdorff距離前后的匹配精度見表2所示。從表中的試驗數(shù)據(jù)可以看出，與引入Hausdorff距離前相比，引入Hausdorff距離進行篩選后，經(jīng)度誤差和緯度誤差都明顯減小，說明引入Hausdorff距離對該匹配算法的精度有了較大的提高。

表2 匹配精度對比

5 結(jié)論

重力匹配導航問題是一個多解的復雜優(yōu)化問題，不僅要求匹配精度足夠高，而且要求匹配時間短，在考慮現(xiàn)有匹配算法不足基礎(chǔ)上，本文提出的一種帶約束人工蜂群算法和平均Hausdorff距離的重力匹配方法，并建立仿真環(huán)境對該重力匹配算法進行測試。仿真表明，該重力匹配方法可以有效地快速地進行匹配定位，有效地避免了誤配情況。盡管傳統(tǒng)的人工蜂群算法已經(jīng)很好地應(yīng)用到重力匹配中，但是其搜索速度和收斂精度仍有較大提升空間，

同時，還可以將外部航向信息作為約束條件，希望獲取更好的匹配效果。

［1］李姍姍.水下重力輔助慣性導航的理論與方法研究［D］.武漢:解放軍信息工程大學，2010.

［2］童余德，邊少鋒，蔣東方，等.基于局部連續(xù)場的重力匹配輔助導航［J］.中國慣性技術(shù)學報2011，19(6):682－685.

［3］程力，蔡體菁.基于模式識別神經(jīng)網(wǎng)絡(luò)的重力匹配算法［J］.東南大學學報(自然科學版)，2007，37(5):839－843.

［4］程力，蔡體菁.基于支持向量機的重力匹配算法［J］.系統(tǒng)仿真學報，2008，20(21):5953－5962.

［5］李姍姍，吳曉平，馬彪.水下重力異常相關(guān)極值匹配算法［J］.中國慣性技術(shù)學報，2011，40(4):464－469.

［6］Karabogad.An Idea Based on Honey Bee Swarm for Numerical Optimization［R］.Turkey:Erciyes University，2005.

［7］KamalamBal.A Comprehensive Review of Artificial Bee Colony Algorithm［J］.International Journal of Computers Technology，2013，5(1):15－28.

［8］黎竹娟.人工蜂群算法在移動機器人路徑規(guī)劃中的應(yīng)用［J］.計算機仿真，2012，29(12):247－251.

［9］Faiza Abdulsalam M，Azuraliza Abu Bakar.A Cluster－Based Deviation Detection Task Using the Artificial Bee Colony Algorithm［J］.International Journal of Soft Computing，2012，7(2):71－78.

［10］孔亞男，魯浩，徐劍蕓.基于Hausdorff距離的地磁匹配導航算法［J］.航空兵器，2011，26(4):26－29.

［11］馬玉良，馬云鵬，張啟忠，等.GA－BP神經(jīng)網(wǎng)絡(luò)在下肢運動步態(tài)識別中的應(yīng)用研究［J］.傳感技術(shù)學報，2013，26(9):1183－1187.

［12］李牧東，熊偉，梁青.基于人工蜂群改進算法的無線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學報，2013，26(2):241－245.

［13］Wang Hubiao，Wang Yong，F(xiàn)ang Jian，et al.Simulation Research on a Minimum Root－Mean－Square Error Rotation－Fitting Algorithm for Gravity Matching Navigation［J］.Science China Earth Sciences，2012，55(1):90－97.

高偉(1977－)，男，博士，教授，研究方向為載體姿態(tài)及運動參數(shù)測量技術(shù)，現(xiàn)代船舶綜合導航技術(shù)，慣性儀表測試及建模技術(shù)，水下導航技術(shù)，gaowei407 @yahoo.com.cn;

趙博(1988－)，男，碩士，研究方向為捷聯(lián)慣性導航技術(shù)，重力輔助導航技術(shù)，重力儀誤差補償技術(shù)，zhaobo880928 @126.com;

周廣濤(1981－)，男，博士，講師，研究方向為捷聯(lián)慣性導航技術(shù)，組合導航技術(shù)，信息融合技術(shù)，計算機仿真技術(shù)，zhougt@hrbeu.edu.cn。

基于帶約束人工蜂群算法和平均Hausdorff距離的重力匹配方法*

高偉，趙博，周廣濤*

(哈爾濱工程大學自動化學院，哈爾濱150001)

重力匹配算法是實現(xiàn)重力輔助慣性導航系統(tǒng)的關(guān)鍵技術(shù)之一。但是，傳統(tǒng)重力匹配方法存在復雜度高、應(yīng)用范圍小等缺陷，一般很難實現(xiàn)精確、快速匹配的效果。將人工蜂群算法用于重力匹配的搜索過程，并將多普勒測速儀提供的速度信息作為限制條件對蜂群搜索過程進行約束。在此基礎(chǔ)上，利用平均Hausdorff距離對匹配結(jié)果進行篩選，在重力數(shù)據(jù)庫中重力異常精度一定的條件下，可降低誤配率。仿真結(jié)果表明，該匹配算法在重力特征顯著的區(qū)域具有較高的匹配率，可以達到精確、快速的匹配定位，從而實現(xiàn)重力輔助導航。

重力匹配;平均Hausdorff距離;人工蜂群算法;外界約束

U666.12

A

1004－1699(2014)01－0074－05

2013－10－30修改日期:2013－12－16

C:7230J

10.3969/j.issn.1004－1699.2014.01.014

項目來源:國家自然科學基金項目(51179039)