基于遺傳算法的地磁匹配搜索策略

陳勵華 王仕成 劉志國

第二炮兵工程大學(xué)，西安 710025

地磁場是地球的固有資源，場強(qiáng)隨空間與時間變化，地磁場導(dǎo)航正是利用這種地磁場在空間分布的各異性來確定載體所在的地理位置。由于地磁定位與地形定位很相似，都是航跡曲線與數(shù)字地圖的配準(zhǔn)，因此目前地磁場導(dǎo)航技術(shù)采用的導(dǎo)航算法主要是借鑒地形高程導(dǎo)航算法中的TERCOM(Terrain Contour Matching)和SITAN(Sandia Inertial Terrain Aided Navigation),即地磁匹配與地磁濾波2種方式[1-6]。與地磁濾波相比，地磁匹配可斷續(xù)使用，不存在累積誤差，易于獲得更高的導(dǎo)航定位精度，因此逐漸成為地磁導(dǎo)航的主流方法[7]。

地磁匹配(Magnetic Field Contour Matching，MAGCOM)通過對測量序列與基準(zhǔn)圖之間相關(guān)性進(jìn)行度量完成定位。現(xiàn)有的MAGCOM算法在理論上可以只依據(jù)磁測設(shè)備提供信息單獨(dú)實(shí)現(xiàn)定位，但實(shí)際應(yīng)用中往往只能作為輔助導(dǎo)航方式，其中基于推位運(yùn)算的MAGCOM要求航跡為直線，這就最大地限制了地磁匹配的應(yīng)用。本文重點(diǎn)研究載體行進(jìn)路徑形狀未知條件下，如何利用相關(guān)性度量實(shí)現(xiàn)地磁場定位的問題。文中采用了在最優(yōu)化問題中成功運(yùn)用的遺傳算法，并對其中交叉與變異概率的選取方法做出相應(yīng)的改進(jìn)。仿真實(shí)驗(yàn)證實(shí)結(jié)合智能優(yōu)化方法的MAGCOM可以完成地磁匹配導(dǎo)航，相關(guān)結(jié)論亦可用于地形匹配或重力場匹配定位。

1 常規(guī)MAGCOM的應(yīng)用條件

MAGCOM是在預(yù)先已知的基準(zhǔn)地磁圖中尋找與測量序列度量指標(biāo)最優(yōu)的一條對應(yīng)序列作為對測點(diǎn)位置的估計(jì)結(jié)果，其實(shí)質(zhì)是數(shù)據(jù)集的配準(zhǔn)問題。該方法可具體描述如下(參見圖1)。

圖1 MAGCOM原理

預(yù)先測量地磁場特征量，并繪制成基準(zhǔn)圖。一般基準(zhǔn)圖都以網(wǎng)格形式表示，其中橫軸和縱軸為地理位置。實(shí)際匹配時，根據(jù)對載體航行區(qū)域的估計(jì)，在預(yù)存的基準(zhǔn)圖中選擇合適的子圖，完成相關(guān)性匹配。用于匹配的子圖網(wǎng)格數(shù)目設(shè)為ML×NL，網(wǎng)格寬度表征了基準(zhǔn)圖的分辨率，縱向與橫向分辨率可以相同，也可以不同，圖1中基準(zhǔn)圖采用均勻網(wǎng)格，網(wǎng)格大小為d×d，表示不同方向分辨率相同。

匹配時，根據(jù)對當(dāng)?shù)氐卮艌鎏卣髁康膶?shí)際測量值Tt={Tt(i);i=1,…,N}與基準(zhǔn)圖中預(yù)存的地磁場數(shù)據(jù)Tm={Tm(i);i=1,…,N}序列計(jì)算相應(yīng)的相關(guān)性度量函數(shù)。在所有可能的數(shù)據(jù)序列中尋找度量指標(biāo)最優(yōu)的數(shù)據(jù)列，其橫、縱坐標(biāo)即是對真實(shí)航跡的估計(jì)。常用的度量函數(shù)指標(biāo)包括距離與相似性兩類。前者如平均絕對差(MAD)算法、平均平方差(MSD)算法等；后者如積相關(guān)(prod)算法和歸一化的積相關(guān)(Nprod)算法等[4-6]。度量中期望距離指標(biāo)最小或相似性指標(biāo)最大。

相關(guān)性度量僅對地磁測量值完成，因此理論上MAGCOM方法可單獨(dú)利用磁測計(jì)定位。但是在實(shí)際度量中，僅僅已知地磁場測量序列是不夠的。以MAD度量為例說明如下。地磁場MAD度量指標(biāo)如式(1)所示：

(1)

其中，Tt(i)為第i點(diǎn)實(shí)測磁場數(shù)值，d為網(wǎng)格寬度，Tm(u,v)為基準(zhǔn)圖上存儲的(u,v)位置上地磁數(shù)據(jù)。由于測量航跡序列Tt與基準(zhǔn)數(shù)字地磁圖Tm之間對應(yīng)關(guān)系未知，會造成可行解的MAD指標(biāo)計(jì)算數(shù)目極其巨大，具體分析如下：在已知的基準(zhǔn)圖中搜索指標(biāo)極值時，路徑起點(diǎn)可能是ML×NL中任意一點(diǎn)，假定相鄰測點(diǎn)間距與基準(zhǔn)圖網(wǎng)格寬度d相同，即相鄰點(diǎn)之間存在八鄰域關(guān)系，則對于長度為N的測量序列，測量值與基準(zhǔn)圖之間所有可能的對應(yīng)關(guān)系共有ML×NL×8N-1種，對所有可行解求取MAD指標(biāo)，再尋找指標(biāo)最優(yōu)解，則會由于運(yùn)算量過大而導(dǎo)致難以求解。因此現(xiàn)有的MAGCOM方法一般假定測量航跡形狀已知,即各測點(diǎn)之間的相對距離和方向信息都是已知的。在這種假設(shè)條件下，可行解的個數(shù)為ML×NL，有效地減小了搜索空間。

MAGCOM實(shí)現(xiàn)一般需借助慣導(dǎo)系統(tǒng)。慣性導(dǎo)航系統(tǒng)經(jīng)初始對準(zhǔn)后，可提供測點(diǎn)之間距離與方向的信息，地磁匹配運(yùn)算認(rèn)為真實(shí)航跡和慣導(dǎo)航跡形狀相同(如圖1所示)，以減小可行解數(shù)目。這樣MAGCOM方法就只能作為輔助導(dǎo)航方式，而無法獨(dú)立定位。

采用慣性器件導(dǎo)致導(dǎo)航成本較高，因此有時也會采用里程計(jì)，利用推位計(jì)算為MAGCOM提供航跡信息[8]。由于里程計(jì)只能提供測點(diǎn)之間的距離信息，而無法給出方向信息，所以推位航跡一般設(shè)為直線，因此該方法只適用于載體行進(jìn)路徑為直線的場合，從而限制了地磁匹配的應(yīng)用。

MAGCOM的實(shí)質(zhì)是在可能的解空間中搜索度量指標(biāo)最優(yōu)，遺傳算法是解決搜索問題的一種通用方法，因此本文考慮將遺傳算法應(yīng)用于地磁匹配定位問題。遺傳算法的引入使得MAGCOM不再關(guān)注測點(diǎn)之間的相對方向信息，只需磁測計(jì)和里程計(jì)即可實(shí)現(xiàn)測量，無需慣性器件的參與，減小了匹配成本。與現(xiàn)有基于推位計(jì)算的地磁匹配算法相比，載體行進(jìn)路徑不存在直線約束，可以為任意形狀，因此擴(kuò)大了匹配方法的應(yīng)用范圍。

2 遺傳算法及其在地磁場匹配導(dǎo)航中的應(yīng)用

2.1 遺傳算法

遺傳算法是借鑒生物界中進(jìn)化與遺傳的機(jī)理實(shí)現(xiàn)的智能計(jì)算，它模擬孟德爾遺傳變異理論和達(dá)爾文優(yōu)勝劣汰思想，通過“遺傳-競爭-再遺傳-再競爭”的方式一步步逼近問題的最優(yōu)解。遺傳算法求解是從代表問題可能潛在的解集的一個種群開始的，在每一代根據(jù)問題域中個體的適應(yīng)度大小選擇個體，并借助于自然遺傳學(xué)的遺傳算子進(jìn)行組合交叉和變異，產(chǎn)生出代表新的解集的種群。

遺傳算法基本上不用搜索空間的知識或其它輔助信息，而僅用適應(yīng)度函數(shù)值來評估個體，在此基礎(chǔ)上進(jìn)行遺傳操作。適應(yīng)度函數(shù)不僅不受連續(xù)可微的約束，而且其定義域可以任意設(shè)定。這一特點(diǎn)使得遺傳算法的應(yīng)用范圍大大擴(kuò)展。

2.2 遺傳算法在地磁匹配導(dǎo)航中的應(yīng)用

以下算法的約束條件為測量序列的各測點(diǎn)之間間距已知，該信息可由里程計(jì)測量得到。按照測點(diǎn)間距調(diào)整基準(zhǔn)地磁圖網(wǎng)格的大小，相應(yīng)的序列比對中，某點(diǎn)的相鄰測點(diǎn)位置只需在基準(zhǔn)圖中該點(diǎn)的八鄰域中搜索。

2.2.1 初始種群

基于遺傳算法的MAGCOM中，基準(zhǔn)圖上每一條長度為N的序列都對應(yīng)一個可行解，即種群中的一個染色體，可表示為有序點(diǎn)連接而成的折線：

path=[x1,y1;x2,y2;...;xN,yN]

(2)

其中xi,yi表示路徑上第i點(diǎn)在基準(zhǔn)圖上的坐標(biāo)，設(shè)xi,yi取值為1～ML和1～NL范圍的實(shí)數(shù)，且相鄰點(diǎn)滿足八鄰域關(guān)系：

(xi-xi-1,yi-yi-1)∈{(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)}

根據(jù)相鄰點(diǎn)的鄰域關(guān)系，染色體亦可用相對坐標(biāo)表示為

path1=[0,0;x2-x1,y2-y1;...;

(3)

相鄰點(diǎn)的鄰域關(guān)系僅有8種，因此path1的表達(dá)形式比path簡單，但缺少起始點(diǎn)的信息。

初始解path的產(chǎn)生可以通過以下3個步驟完成：

1) 序列的起始點(diǎn)(x1,y1)產(chǎn)生。起始點(diǎn)可能在已知基準(zhǔn)圖中任何一點(diǎn)，因此可以隨機(jī)的產(chǎn)生取值為1～ML的任意實(shí)數(shù)x1和1～NL的任意實(shí)數(shù)y1；

2) 相對坐標(biāo)序列path1的產(chǎn)生。隨機(jī)產(chǎn)生長度為N-1的相鄰點(diǎn)八鄰域關(guān)系，并按式(3)的規(guī)則產(chǎn)生path1；

3) 根據(jù)式(2)和(3)關(guān)系可計(jì)算得到初始解path。

按照以上步驟可以產(chǎn)生m個初始解，形成初始種群。

2.2.2 適應(yīng)度函數(shù)

其中， bij（0-t）表示在時間段 （0-t） 內(nèi)， i地區(qū)j產(chǎn)業(yè)的增長速度，表示在時間段（0-t）內(nèi)j產(chǎn)業(yè)在全國的增長速度。

解的優(yōu)劣可以通過該路徑與測量值的相似性程度來體現(xiàn)。適應(yīng)度函數(shù)選為相似性度量指標(biāo)如MAD，NPROD等。MAD指標(biāo)對應(yīng)的適應(yīng)度函數(shù)如下：

NPROD指標(biāo)對應(yīng)的適應(yīng)度函數(shù)如下：

適應(yīng)度函數(shù)根據(jù)某一染色體path中每一個點(diǎn)對應(yīng)的基準(zhǔn)圖中地磁場強(qiáng)度大小Tm與實(shí)際測量序列中對應(yīng)的磁測值Tt進(jìn)行比較、計(jì)算得到。對某染色體而言，以上2個適應(yīng)度指標(biāo)越大，則意味著該染色體適應(yīng)能力越強(qiáng)。

2.2.3 遺傳算子

遺傳算法的選擇算子采用輪盤賭的方式，適應(yīng)度越高的個體被選中的概率越大。在交叉與變異中為保證運(yùn)算后能滿足相鄰點(diǎn)的八鄰域要求，執(zhí)行運(yùn)算時區(qū)分起點(diǎn)和其余各點(diǎn)。起點(diǎn)的交叉和變異對path中的第1組坐標(biāo)(x1,y1)進(jìn)行，其余各點(diǎn)則利用path1表達(dá)式，即改變點(diǎn)之間的鄰域關(guān)系。經(jīng)過交叉與變異后，路徑上點(diǎn)間的鄰域關(guān)系發(fā)生變化，獲得新個體。

遺傳算法中交叉概率Pc和變異概率Pm的選擇是影響算法性能的關(guān)鍵。交叉概率Pc過小會導(dǎo)致搜索過程變慢，過大會破壞優(yōu)秀個體的結(jié)構(gòu)；變異用于表現(xiàn)基因的突變，可使求解過程跳出局部搜索空間，變異概率Pm過小不易產(chǎn)生新的全局極值，過大則遺傳算法會成為純粹的隨機(jī)搜索。因此Pc和Pm需要反復(fù)試驗(yàn)確定。Srinvivas等人提出根據(jù)適應(yīng)度大小自適應(yīng)調(diào)整Pc和Pm的方法[9]，如式(6)和(7)所示：

(6)

(7)

式中，fmax為群體中最大的適應(yīng)度，favg為每代群體平均適應(yīng)度，f′為交叉的兩個體中較大適應(yīng)度，f為變異個體的適應(yīng)度。

本文研究的長度為N的有序點(diǎn)集配準(zhǔn)問題，實(shí)際是個多級尋優(yōu)問題。結(jié)合多級尋優(yōu)具有可加性特點(diǎn)，提出以局部適應(yīng)度函數(shù)對以上自適應(yīng)調(diào)整Pc和Pm的方法作進(jìn)一步改進(jìn)。最優(yōu)解從起點(diǎn)開始，以小于等于N的任何一級作為終點(diǎn)，得到的序列仍應(yīng)是該長度下的優(yōu)解。為保護(hù)優(yōu)秀基因不在交叉和變異中遭到破壞，設(shè)置局部適應(yīng)度函數(shù)。以MAD指標(biāo)為例，第n級局部適應(yīng)度函數(shù)如式(8)所示，其中n為[1,N]中的任意整數(shù)。

(8)

與式(4)相同，式(8)的分母部分表示的也是被搜索序列與測量序列相比平均每點(diǎn)的距離偏差，因此可以將局部適應(yīng)度與整條序列的適應(yīng)度比較。

交叉可單點(diǎn)進(jìn)行，也可多點(diǎn)進(jìn)行。本文采用單點(diǎn)交叉的方式，隨機(jī)選擇交叉點(diǎn)，依據(jù)式(8)計(jì)算擬交叉的2條序列在該點(diǎn)的局部適應(yīng)度d1和d2，令f′=max(d1,d2)，由式(6)計(jì)算可得Pc，同理以局部適應(yīng)度取代序列適應(yīng)度計(jì)算Pm。

局部適應(yīng)度的作用是針對那些包含優(yōu)秀基因的劣解，能在減小優(yōu)秀基因段被改變概率的同時盡量增大不良基因交叉和變異的可能。

2.2.4 迭代終止條件

遺傳算法循環(huán)迭代搜索，迭代次數(shù)是影響計(jì)算量的重要因素。只要滿足以下任一條件，即停止迭代：1)設(shè)定最大遺傳代數(shù)Gn，當(dāng)?shù)螖?shù)到達(dá)Gn，即停止迭代，以當(dāng)前最佳個體作為匹配結(jié)果； 2)迭代到一定程度可能已無法得到適應(yīng)度更優(yōu)的結(jié)果，若連續(xù)g代最優(yōu)適應(yīng)度未有改進(jìn)，即停止迭代。

2.2.5 算法的復(fù)雜度分析

算法效率可用時間復(fù)雜度分析。以比較運(yùn)算作為基本操作，在本文的約束條件下，現(xiàn)有MAGCOM方法時間復(fù)雜度為o(ML×NL×8N-1)，上述遺傳算法中，種群大小m序列長度為N的染色體，最大迭代次數(shù)為Gn，整個計(jì)算過程的時間復(fù)雜度為o(m.N.Gn)。當(dāng)序列長度較大時，遺傳算法的計(jì)算量優(yōu)勢明顯。

2.3 仿真驗(yàn)證

為了驗(yàn)證本文提出算法的有效性，在實(shí)測地磁圖上進(jìn)行仿真試驗(yàn)。該圖來自我國西部某地區(qū)實(shí)地測量結(jié)果。地磁圖網(wǎng)格數(shù)為30×30，網(wǎng)格間距為20m×20m，對應(yīng)測點(diǎn)間距亦為20m。仿真中適應(yīng)度函數(shù)取MAD 指標(biāo)，序列長度取N=10，交叉概率Pc與變異概率Pm如前所述自適應(yīng)獲得，初始種群大小m=50，遺傳代數(shù)Gn=100。

在不考慮噪聲的條件下，對某測量序列在整個基準(zhǔn)圖中搜索，定位結(jié)果如圖2所示。圖中序列的10個測點(diǎn)中有8個完全匹配，整個序列的總誤差為2.828網(wǎng)格，且誤差隨種群規(guī)模和迭代次數(shù)的增大、參數(shù)設(shè)置的改進(jìn)還有望減小。這表示遺傳算法能夠在已知測點(diǎn)間距的條件下，利用相似性比較獲得測量路徑的形狀，因此不必依賴慣性系統(tǒng)信息，即可完成定位。

圖2 仿真結(jié)果

3 主要影響因素分析

遺傳算法中解的生成具有不確定性，而且地磁匹配定位還需考慮測量噪聲與基準(zhǔn)圖制備等誤差因素影響，因此很難保證定位結(jié)果足夠理想。本節(jié)從基準(zhǔn)圖大小、序列長度、噪聲條件等方面對地磁匹配進(jìn)行仿真，尋找以上因素對算法影響的規(guī)律以及改進(jìn)措施。以下仿真中，如未作特殊說明，仿真條件同2.3節(jié)。

3.1 基準(zhǔn)圖大小

在不考慮噪聲的條件下，選取序列長度為N=10，在不同基準(zhǔn)圖大小條件下完成匹配?；鶞?zhǔn)圖網(wǎng)格數(shù)分別為10×10，20×20，30×30，經(jīng)過500次匹配，計(jì)算所得的平均誤差如表1所示。表中誤差亦指整個序列誤差。

表1 基準(zhǔn)圖網(wǎng)格數(shù)的影響

由于遺傳算法參數(shù)選取一致，因此表1中3種情況搜索的運(yùn)算量是相同的。然而基準(zhǔn)圖越大，會導(dǎo)致匹配空間越大，因此遺傳算法越容易落入指標(biāo)的局部極小值點(diǎn)而無法實(shí)現(xiàn)序列的準(zhǔn)確比對，造成誤差隨基準(zhǔn)圖增大而增大。對于本例而言，如表1所示，即使在基準(zhǔn)圖為30×30的仿真條件下，整個序列的定位誤差仍可達(dá)到5個網(wǎng)格左右，相應(yīng)的平均單點(diǎn)誤差僅有0.5個網(wǎng)格，定位精度比較理想。

3.2 序列長度與噪聲

綜合分析序列長度與噪聲的影響。在N=5，N=10兩種序列長度下，匹配基準(zhǔn)圖選為20×20，分別疊加如上所述高斯噪聲和均勻噪聲，其它參數(shù)設(shè)置不變。對各種情況測試500次，平均結(jié)果如表2所示。

表2 序列長度與噪聲的影響

將表1和表2中序列長度N=10，基準(zhǔn)圖20×20的結(jié)果對比可以發(fā)現(xiàn)，均勻噪聲的影響非常小，有無噪聲條件下誤差差別不大；高斯噪聲則影響明顯，會引起匹配精度的顯著下降。另一方面，序列長度會引起整條序列誤差的增加，但平均每個點(diǎn)所引起的誤差隨序列長度增長并無明顯增大的表現(xiàn)。

4 結(jié)論

本文提出利用遺傳算法實(shí)現(xiàn)的地磁匹配。該方法有效解決解空間過大的難題，計(jì)算量較小。具體實(shí)現(xiàn)中以相似性度量作為適應(yīng)度函數(shù)，采用相對路徑完成交叉和變異，并對交叉變異的概率自適應(yīng)調(diào)整方法實(shí)現(xiàn)了改進(jìn)。通過仿真討論了基準(zhǔn)圖大小、噪聲、匹配序列長度對算法的影響，發(fā)現(xiàn)基準(zhǔn)圖增大、高斯噪聲會引起匹配誤差的明顯增加，而序列長度影響不明顯。結(jié)果表明，該方法降低了現(xiàn)有MAGCOM方法在使用中的約束條件，在僅提供測點(diǎn)地磁場信息和相對距離信息的條件下，能依靠算法獲得路徑形狀，以較小誤差實(shí)現(xiàn)定位。

參 考 文 獻(xiàn)

[1] Mu Hua, Wu Mei-ping. Geomagnetic Surface Navigation Using Adaptive EKF[C].2007 IEEE Conference on Industrial Electronics and Application,Harbin,2007.

[2] E R Benson,T S Stombaugh,N Noguchi, et al. An Evaluation of a Geomagnetic Direction Sensor for Vehicle Guidance in Precision Agriculture Applications[C]. ASAE Paper 983203, ASAE.St. Joseph,MI,1998.

[3] Mohammad Nizam Filipski,Ermira Junita Abduliah. Nanosatellite Navigation with the WMM2005 Geomagnetic Field Model[J].Turkish Journal of Environmental Sciences, 2006,30(1): 43-55.

[4] 劉穎,吳美平.地磁匹配中的匹配長度估計(jì)方法[J].中國慣性技術(shù)學(xué)報(bào),2010,18(4):439-443.(Liu Ying, Wu Mei-ping.Match Length Estimation in Geomagnetic Matching System [J]. Journal of Chinese Inertial Technology, 2010,18(4):439-443.)

[5] 劉飛,周賢高,等.相關(guān)地磁匹配定位技術(shù)[J].中國慣性技術(shù)學(xué)報(bào),2007,15(1):59-62.(Liu Fei, Zhou Xian-gao,et al. Geomagnetic Matching Location Using Correlation Method[J]. Journal of Chinese Inertial Technology, 2007,15(1):59-62.)

[6] 任治新，楊功流，李士心.基于向量搜索的地磁導(dǎo)航匹配算法[J].中國慣性技術(shù)學(xué)報(bào),2008,16(4)：424-427.(Ren Zhixin,Yang Gongliu,Li Shixin.Geomagnetic Matching Algorithm Based on Vector Search[J]. Journal of Chinese Inertial Technology, 2008,16(4)：424-427.)

[7] 周軍,葛致磊,施桂國,等.地磁導(dǎo)航發(fā)展與關(guān)鍵技術(shù)[J].宇航學(xué)報(bào),2008,29(5):1467-1742.(Zhou Jun, Ge Zhilei, Shi Guiguo, et al. Key Technique and Development for Geomagnetic Navigation[J]. Journal of Astronautics, 2008, 29(5):1467-1742.)

[8] 喬玉坤.地磁導(dǎo)航基準(zhǔn)圖制備與數(shù)學(xué)仿真方法研究[D].西安：第二炮兵工程學(xué)院，2011.(Qiao Yukun.Study on the Preparation and Numerical Simulation of Reference Maps for Geomagnetic Navigation[D]. Doctor Dissertation of Second Artillery Engineering Institute,Xi-an,2011.)

[9] Srinivas M,Patnaik L M.Adaptive Probabilities of Crossover and Mutations in Gas[J]. IEEE Transactions on SMC,1994,24(4):656-667.