蟻群算法在輔助導(dǎo)航重力匹配中的應(yīng)用

陳小煒， 姜廣勝， 陳 靜

(陸軍步兵學(xué)院石家莊校區(qū)軍政訓(xùn)練系，石家莊，050083)

衛(wèi)星導(dǎo)航雖然精度高，適用范圍廣，但對(duì)于水下潛器以及需要隱身的裝備而言，慣性導(dǎo)航才是最佳選擇。慣性導(dǎo)航基于慣性元器件解算出自身位置和姿態(tài)，不向外輻射信號(hào)，因此隱蔽性好，實(shí)用性強(qiáng)，但其是一種基于位推算法的定位方式，誤差會(huì)隨時(shí)間積累，長(zhǎng)時(shí)間導(dǎo)航將無(wú)法滿足定位需求，需要外部信息進(jìn)行校對(duì)。由于重力異常容易獲取，通過(guò)重力場(chǎng)特征信號(hào)獲取位置信息，反饋給慣導(dǎo)系統(tǒng)進(jìn)行位置誤差校對(duì)，依然能夠維持慣導(dǎo)系統(tǒng)的隱蔽性和自主性，所以重力匹配仍具備不受外界干擾等優(yōu)點(diǎn)[1]。經(jīng)典的重力匹配方法分為遞推最優(yōu)估計(jì)濾波和相關(guān)值匹配。近幾年，相關(guān)值匹配取得了很大突破，產(chǎn)生很多研究成果，包括神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)、數(shù)據(jù)關(guān)聯(lián)濾波等[2-3]。蟻群算法是一種群智能最優(yōu)搜索算法[4-6]，王曉燕等[7]結(jié)合蟻群算法與人工勢(shì)場(chǎng)法，給不同的柵格位置賦予不同的初始信息素，通過(guò)不同信息素濃度，加速蟻群收斂速度，提高算法的搜索效率。敖邦乾等[8]使用Dubins曲線算法和貝塞爾三階曲線理論，對(duì)水面無(wú)人艇路徑的連接點(diǎn)與路徑進(jìn)行平滑處理，使路徑在滿足最小旋轉(zhuǎn)半徑的同時(shí)也滿足動(dòng)力學(xué)特性。本文將蟻群算法應(yīng)用到重力匹配中，并將速度信息作為約束條件，同時(shí)根據(jù)搜索策略對(duì)蟻群算法的信息素濃度、算法參數(shù)進(jìn)行自適應(yīng)調(diào)整，并與均方差算法進(jìn)行匹配，通過(guò)兩種算法仿真數(shù)據(jù)對(duì)比，驗(yàn)證蟻群算法是否提高了匹配的搜索效率和匹配率。

1 蟻群算法

研究者發(fā)現(xiàn)螞蟻會(huì)在所經(jīng)過(guò)的路徑上釋放出一種特殊的激素，為其他螞蟻提供方向指引，學(xué)者們稱這種特殊的激素為信息素。信息素的濃度會(huì)隨著時(shí)間產(chǎn)生揮發(fā)，所以路徑越長(zhǎng)，信息素濃度就越低，被其他螞蟻察覺(jué)的概率就越小；相反，路徑越短，信息素濃度就高，就會(huì)有更多螞蟻選擇該路徑。螞蟻越多，信息素的濃度就會(huì)不斷加強(qiáng)；螞蟻越少，信息素濃度就難以維持，直至最后因缺少信息素而被遺棄。因此形成了一種基于信息素濃度的正反饋機(jī)制，通過(guò)信息素濃度的變化來(lái)找到一條最優(yōu)路徑。蟻群算法的特性使得它非常適用于組合優(yōu)化問(wèn)題，通過(guò)信息素濃度來(lái)確定最優(yōu)解，并且取得了良好的效果。蟻群算法一般包括參數(shù)初始化、循環(huán)遍歷、信息素更新、判斷是否終止等環(huán)節(jié)，見(jiàn)圖1。

圖1 蟻群算法流程圖

設(shè)C={c1,c2,…,cn}為n個(gè)節(jié)點(diǎn)集合，L={lij|ci,cj∈C}是C集合中不同節(jié)點(diǎn)間的路徑權(quán)值集合。τij(t)是信息素濃度值，表示t時(shí)刻路徑(i,j)上殘留的信息留濃度。Γ={τij(t)|ci,cj∈C}是τij(t)的集合，t=0時(shí)，各路徑上的信息素濃度初始值相等，τij(0)=const。通過(guò)(C,L,Γ)集合組合蟻群算法的有向圖，通過(guò)有向圖G=(C,L,Γ)能夠?qū)崿F(xiàn)蟻群算法，獲得最優(yōu)解。

(1)

式中：α為信息啟發(fā)因子，表示信息素對(duì)于螞蟻選擇該路徑影響大小，α越大，影響越大，群體之間協(xié)作性越強(qiáng)；ηij(t)為啟發(fā)函數(shù)，表示在t時(shí)刻螞蟻從i轉(zhuǎn)移到j(luò)的期望程度，代表了螞蟻的主觀性；β為期望啟發(fā)因子，表示啟發(fā)函數(shù)對(duì)于路徑選擇的重要性，β值越大，表示螞蟻選擇主觀性更強(qiáng)，更接近于貪心規(guī)則；allowedk(i)代表了螞蟻k的可選擇集合，即位于節(jié)點(diǎn)i上的螞蟻在進(jìn)行下一步轉(zhuǎn)移是可以到達(dá)的節(jié)點(diǎn)集合。

信息素濃度與啟發(fā)信息都對(duì)轉(zhuǎn)移概率有很大影響，且兩者是對(duì)立的。所以，在搜索過(guò)程中要不斷進(jìn)行更新，防止信息素和啟發(fā)信息數(shù)值相差過(guò)大，淹沒(méi)對(duì)方。t+n時(shí)刻在路徑(i,j)上的信息素更新如下：

(2)

式中：ρ為信息素?fù)]發(fā)因子，(1-ρ)則為信息素殘留因子，其中ρ∈(0,1)；Δτij(t)為t時(shí)刻路徑(i,j)信息素量的增量，其中Δτij(0)=0。

2 重力匹配相關(guān)方法

重力信息實(shí)時(shí)測(cè)量和重力場(chǎng)背景圖測(cè)繪能力是重力匹配的基礎(chǔ)[9-11]。重力匹配是將航跡上的重力測(cè)量值與參考重力進(jìn)行運(yùn)算，通過(guò)求取極值或最優(yōu)解來(lái)確定對(duì)應(yīng)的位置信息。

匹配分為粗匹配和精匹配，分別對(duì)應(yīng)搜索模式和跟蹤模式。初始匹配是在搜索模式下進(jìn)行的，此時(shí)慣導(dǎo)因誤差較大需要校對(duì)，借助慣導(dǎo)系統(tǒng)可以確定載體的大致范圍，同時(shí)根據(jù)重力基準(zhǔn)圖確定匹配范圍。此時(shí)系統(tǒng)進(jìn)入跟蹤模式，通過(guò)載體軌跡上的測(cè)量值確定載體的真實(shí)位置。

因?yàn)閼T導(dǎo)系統(tǒng)誤差過(guò)大，所以在搜索模式下，需要擴(kuò)大搜索范圍，因此匹配范圍也較大，保證載體真實(shí)位置在匹配范圍內(nèi)。此時(shí)需要載體采集一定的重力數(shù)據(jù)，通過(guò)連續(xù)的測(cè)量值確定載體的粗略位置。

進(jìn)入跟蹤模式后，載體將搜索模式得到的位置作為已知位置，從該位置出發(fā)，間隔固定時(shí)間沿某一方向進(jìn)行采樣，記錄該時(shí)刻對(duì)應(yīng)的重力測(cè)量值。最后將慣導(dǎo)指示航跡和載體行進(jìn)過(guò)程中的的真實(shí)軌跡記錄到重力圖上，如圖2所示。其中Ai表示載體在ti時(shí)刻的真實(shí)位置，Ci是該時(shí)刻慣導(dǎo)平臺(tái)輸出的位置。gi是重力儀在該時(shí)刻的測(cè)量值，也就是Ai處的重力值。因此存在3個(gè)點(diǎn)集：

圖2 真實(shí)航跡與INS指示航跡關(guān)系

A={Ai},C={Ci},G={gi},i=0,1,…,m

載體航跡重力測(cè)量值由點(diǎn)集C構(gòu)成，點(diǎn)集A是載體的真實(shí)軌跡。本文將通過(guò)點(diǎn)集C和點(diǎn)集G，依據(jù)蟻群算法找到點(diǎn)集A。

根據(jù)測(cè)量位置，將搜索區(qū)域柵格化。將測(cè)量點(diǎn)Ci作為搜索中心，以距離Ri為搜索半徑，在重力圖劃分網(wǎng)格點(diǎn)搜索區(qū)域，Ri要確保網(wǎng)格區(qū)域應(yīng)包含Ai，也就是載體對(duì)應(yīng)的真實(shí)位置。在網(wǎng)格范圍內(nèi)搜索測(cè)量值gi的等值點(diǎn)，搜索范圍以Ci為中心向外輻射，其中dij表示搜索范圍內(nèi)測(cè)量值gi的第j個(gè)等值點(diǎn)，標(biāo)記為網(wǎng)格點(diǎn)。半徑Ri根據(jù)慣性單元的漂移誤差來(lái)確定，慣性元件導(dǎo)航時(shí)間越長(zhǎng)，精度就越低，半徑也越大，同時(shí)Ri要考慮重力異常對(duì)慣性導(dǎo)航系統(tǒng)定位精度的影響[12-13]。dij的對(duì)應(yīng)經(jīng)緯度坐標(biāo)為(λij,φij)，通過(guò)基準(zhǔn)數(shù)據(jù)庫(kù)獲取該地理位置的重力值為gij，Ci的地理經(jīng)緯度為(λci,φci)，Ri的單位為網(wǎng)格數(shù)，網(wǎng)格之間的距離為ρ。所以，等值點(diǎn)集Di可以由式(3)確定：

(3)

i=0,1,…,m;j=1,2,…,Ni

式中：Di為等值點(diǎn)集合，Ni為點(diǎn)數(shù)，δ為等值點(diǎn)的誤差閾值，在該閾值范圍內(nèi)視為等值點(diǎn)。

3 匹配算法

3.1 相關(guān)值搜索匹配

根據(jù)慣性導(dǎo)航輸出的位置，通過(guò)搜索查詢基準(zhǔn)重力數(shù)據(jù)庫(kù)，可以得到對(duì)應(yīng)的重力異常值g'N=[g'1,g'2,…,g'N]。通過(guò)重力儀或重力梯度儀可以測(cè)得載體航跡上的重力異常值gN=[g1,g2,…,gN]。搜索模式下，根據(jù)慣性元件的誤差及位置信息確定搜索區(qū)域，也就是匹配區(qū)域。為保證實(shí)際航跡在搜索區(qū)域內(nèi)，在不犧牲收斂速度的前提下，盡量擴(kuò)大搜索范圍。以短時(shí)間內(nèi)航跡作為實(shí)驗(yàn)數(shù)據(jù)，只要時(shí)間足夠短，便可得到與實(shí)際軌跡相平行的慣導(dǎo)輸出軌跡。在搜索區(qū)域，可以得到S個(gè)與慣導(dǎo)輸出軌跡平行的軌跡簇，假設(shè)平行軌跡簇中有S個(gè)軌跡，在重力數(shù)據(jù)庫(kù)中提取重力異常值，得到S個(gè)數(shù)據(jù)向量。把重力儀測(cè)量值向量和數(shù)據(jù)庫(kù)中提取的數(shù)據(jù)向量進(jìn)行相關(guān)極值運(yùn)算，可以確定航行體的位置。本文相關(guān)極值匹配算法選用常用的均方誤差(MSD)算法，把搜索區(qū)域中得到的S個(gè)數(shù)據(jù)向量與觀測(cè)值向量分別按式(4)計(jì)算均方誤差JMSD, 最小的JMSD對(duì)應(yīng)的即為匹配位置。

(4)

式中：k=1,2,…,N。

3.2 蟻群搜索匹配

當(dāng)螞蟻從起點(diǎn)到終點(diǎn)遍歷完所有點(diǎn)，該集合便是一條匹配路徑。如果螞蟻到達(dá)某一節(jié)點(diǎn)，而該節(jié)點(diǎn)無(wú)法進(jìn)行到下一節(jié)點(diǎn)，也是一次完整的遍歷，即是匹配中的一個(gè)解，當(dāng)足夠數(shù)量的螞蟻?zhàn)咄晁锌赡艿穆窂剑惆俗顑?yōu)解。

節(jié)點(diǎn)D0為已知點(diǎn)，當(dāng)螞蟻從D0到達(dá)D1時(shí)有N1(N1為點(diǎn)集D1中等值點(diǎn)數(shù))條有向線段。當(dāng)螞蟻從D1到達(dá)D2時(shí)，根據(jù)自由組合的可能路線，便形成N1×N2條路線。所以，以此類推，螞蟻從Di到Di+1有Ni×Ni+1條路線。α[i,j]為每只螞蟻從i到i+1選擇的有向線段(j=1,2,…,Ni×Ni+1)。螞蟻遍歷的所有路徑中，只有一條路徑與真實(shí)路徑最接近，以此作為目標(biāo)函數(shù)，并通過(guò)速度信息進(jìn)行約束，便能找到蟻群搜索路徑得到最優(yōu)解。

實(shí)驗(yàn)中通過(guò)多普勒測(cè)速儀等設(shè)備可以獲得作為外部約束條件的速度信息，以此建立的目標(biāo)函數(shù)為：

s.t.x=(x1j,x2j,…,xnj)∈S?D

(5)

螞蟻k在選擇路徑前往下一節(jié)點(diǎn)時(shí)，如果點(diǎn)集D中沒(méi)有滿足約束條件的節(jié)點(diǎn)，則螞蟻k將自動(dòng)死亡，也就是完成了一些遍歷。螞蟻k死亡后，更新禁忌表tabuk中的數(shù)字為{1,2,…,i,…}，禁忌表代表螞蟻完成的遍歷，且{1,2,…,i,…}?{1,2,…,n}，則螞蟻k得到的解為：

Lk=|‖αij-α1j‖-vt|

(6)

當(dāng)m只螞蟻都完成遍歷后，禁忌表更新完成，此時(shí)根據(jù)矩陣方程，可求得m組可行解。本次遍歷取得的最優(yōu)解優(yōu)于當(dāng)前解的話，則將本次最優(yōu)解作為當(dāng)前最優(yōu)解。如果遍歷次數(shù)小于最大循環(huán)次數(shù)，根據(jù)式(1)～(2)更新路徑上的信息素，并進(jìn)入下一次搜索。如果遍歷次數(shù)大于或等于最大循環(huán)次數(shù)，則遍歷結(jié)束，當(dāng)前最優(yōu)解即最終解。

4 仿真結(jié)果與分析

本文模擬生成慣性導(dǎo)航系統(tǒng)軌跡包括INS指示軌跡和載體真實(shí)軌跡。為了能夠驗(yàn)證算法有效性，提前設(shè)定一條位置已知的軌跡，作為理論軌跡。慣導(dǎo)系統(tǒng)輸出的軌跡是根據(jù)慣導(dǎo)仿真模型獲得的軌跡，通過(guò)與真實(shí)慣導(dǎo)對(duì)比，該模型參數(shù)符合實(shí)際要求。取經(jīng)度為125°～126.5°，緯度為45°～ 45.6°，高程為水平面組成的面內(nèi)的所有重力異常數(shù)據(jù)。重力異常數(shù)據(jù)是由EGM2008重力異常數(shù)據(jù)庫(kù)生成，分布圖見(jiàn)圖3。根據(jù)提前設(shè)定，將載體的航跡預(yù)設(shè)在該區(qū)域內(nèi)，慣導(dǎo)系統(tǒng)的仿真數(shù)據(jù)就是按照提前設(shè)定軌跡進(jìn)行仿真，從而得到該軌跡上INS指示軌跡。

圖3 重力異常曲面圖

在搜索模式下，通過(guò)式(3)計(jì)算獲取重力異常測(cè)量值的等值點(diǎn)，將等值點(diǎn)作為蟻群遍歷節(jié)點(diǎn)，根據(jù)表1的參數(shù)進(jìn)行設(shè)置仿真計(jì)算。實(shí)驗(yàn)中采用的慣導(dǎo)數(shù)據(jù)模型為光纖陀螺的參數(shù)，誤差包含初始位置誤差、常值漂移和隨機(jī)噪聲3種。其中，通過(guò)轉(zhuǎn)臺(tái)實(shí)驗(yàn)測(cè)得設(shè)備的常值漂移誤差為0.01°/h，隨機(jī)噪聲均值為0，標(biāo)準(zhǔn)差為0.001的高斯分布白噪聲。重力儀的實(shí)時(shí)量測(cè)數(shù)據(jù)是利用真實(shí)航跡在重力數(shù)據(jù)庫(kù)中的采樣值加上一定的測(cè)量噪聲得到的。蟻群算法的參數(shù)設(shè)置見(jiàn)表1。

表1 蟻群算法參數(shù)設(shè)置

對(duì)蟻群算法進(jìn)行仿真，得到匹配最優(yōu)解。同時(shí)通過(guò)MSD算法進(jìn)行仿真，并對(duì)兩種算法仿真結(jié)果進(jìn)行對(duì)比。圖4慣導(dǎo)輸出航跡、理論航跡、MSD匹配算法仿真航跡和蟻群匹配算法仿真航跡。圖5為不同算法匹配的誤差圖。

圖4 航跡軌跡仿真圖

圖5 匹配誤差圖

從圖4和圖5能夠看出，慣導(dǎo)誤差呈發(fā)散趨勢(shì)，而MSD算法和蟻群誤差相對(duì)穩(wěn)定，且匹配效果優(yōu)于慣導(dǎo)輸出軌跡。表2為通過(guò)蟻群算法和MSD算法獲得的匹配精度。從結(jié)果可以看出，相比于MSD算法，蟻群搜索算法誤差均值更小，更加平穩(wěn)，匹配精度更高，匹配效果更好。

表2 經(jīng)緯度誤差 單位：km

5 結(jié)語(yǔ)

本文探索了基于蟻群算法的重力匹配，并建立仿真環(huán)境對(duì)該算法進(jìn)行測(cè)試，將蟻群算法與相關(guān)極值算法中的MSD算法進(jìn)行對(duì)比分析。仿真結(jié)果表明，蟻群算法匹配精度更高，能夠找到一條更接近真實(shí)航跡的路線，有效避免誤匹配的情況。