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

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

1 人工蜂群算法

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

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

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

圖1 人工蜂群算法流程圖

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

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

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

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

2 平均Hausdorff距離

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

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

其中:

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

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

其中，

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

3 重力匹配算法

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

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

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

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

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

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

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

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

圖3 匹配流程圖

4 仿真分析

4.1 仿真條件及過(guò)程

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

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

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

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

4.2 仿真結(jié)果

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

圖5 不同條件下匹配軌跡效果對(duì)比

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

表2 匹配精度對(duì)比

5 結(jié)論

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

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

［1］李?yuàn)檴?水下重力輔助慣性導(dǎo)航的理論與方法研究［D］.武漢:解放軍信息工程大學(xué)，2010.

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

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

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

［5］李?yuàn)檴?，吳曉平，馬彪.水下重力異常相關(guān)極值匹配算法［J］.中國(guó)慣性技術(shù)學(xué)報(bào)，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］黎竹娟.人工蜂群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的應(yīng)用［J］.計(jì)算機(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距離的地磁匹配導(dǎo)航算法［J］.航空兵器，2011，26(4):26－29.

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

［12］李牧東，熊偉，梁青.基于人工蜂群改進(jìn)算法的無(wú)線傳感器網(wǎng)絡(luò)定位算法［J］.傳感技術(shù)學(xué)報(bào)，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－)，男，博士，教授，研究方向?yàn)檩d體姿態(tài)及運(yùn)動(dòng)參數(shù)測(cè)量技術(shù)，現(xiàn)代船舶綜合導(dǎo)航技術(shù)，慣性儀表測(cè)試及建模技術(shù)，水下導(dǎo)航技術(shù)，gaowei407 @yahoo.com.cn;

趙博(1988－)，男，碩士，研究方向?yàn)榻萋?lián)慣性導(dǎo)航技術(shù)，重力輔助導(dǎo)航技術(shù)，重力儀誤差補(bǔ)償技術(shù)，zhaobo880928 @126.com;

周廣濤(1981－)，男，博士，講師，研究方向?yàn)榻萋?lián)慣性導(dǎo)航技術(shù)，組合導(dǎo)航技術(shù)，信息融合技術(shù)，計(jì)算機(jī)仿真技術(shù)，zhougt@hrbeu.edu.cn。

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

高偉，趙博，周廣濤*

(哈爾濱工程大學(xué)自動(dòng)化學(xué)院，哈爾濱150001)

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

重力匹配;平均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

項(xiàng)目來(lái)源:國(guó)家自然科學(xué)基金項(xiàng)目(51179039)