基于改進遺傳算法的多波束水下地形匹配方法

張 濤，張 馳，張佳宇

（1.微慣性儀表與先進導(dǎo)航技術(shù)教育部重點實驗室，南京 210096；2.東南大學(xué) 儀器科學(xué)與工程學(xué)院，南京 210096）

慣性導(dǎo)航系統(tǒng)（Inertial Navigation System,INS）是目前自主水下航行器（Autonomous Underwater Vehicle,AUV）最常用的導(dǎo)航方式，但是由于系統(tǒng)本身特性的原因，導(dǎo)航誤差會隨時間逐漸累積[1]，無法滿足AUV長航時的作業(yè)需求。為解決這一問題，可以利用地形匹配的結(jié)果對INS進行校正。地形匹配是一種利用地球物理信息進行位置定位的方法，將實時測量得到的水深數(shù)據(jù)與預(yù)先存儲的水下地形圖進行匹配，進而確定AUV在地形圖上的位置[2,3]。由于短時間內(nèi)水下地形不會發(fā)生變化，且無需接受其他外部傳感器信號，地形匹配具有很高的可靠性和隱蔽性[4]。

目前，地形輪廓匹配算法（Terrain Contour Matching,TERCOM）和最近等值線迭代算法（Iterative closest contour point,ICCP）是最常用的兩種水下地形匹配方法[5]。TERCOM通過計算測量地形序列和背景地形的相關(guān)性對航跡進行修正，實現(xiàn)簡單，但是該算法精度較低，對航向誤差要求較高，一般要小于2 °，否則會匹配失敗。ICCP在測深序列等值線附近對航跡進行多次迭代變換，逐步靠近真實位置，在初始定位誤差較大時，匹配耗時長，定位精度低甚至失敗[6]。文獻[7]在TERCOM算法的基礎(chǔ)上，引入不規(guī)則三角網(wǎng)模型替代傳統(tǒng)網(wǎng)格化水下地形圖，能夠有效降低誤匹配的概率，同時定位精度高于傳統(tǒng)的TERCOM算法。文獻[8]利用最小二乘對ICCP匹配結(jié)果進行仿射修正，改善ICCP僅能做剛性變換的缺陷，提高匹配定位效果。文獻[9]提出一種聯(lián)合TERCOM和ICCP的匹配算法，利用TERCOM進行粗匹配，ICCP進行精匹配，克服ICCP在初始定位差較大時容易匹配失敗的問題。文獻[10]對ICCP的采樣方式進行改進，結(jié)合滑動窗搜索的方式縮小搜索范圍，提高了ICCP算法的實時性。以上方法都是基于單點測深系統(tǒng)進行匹配，獲取的地形信息有限，在地形相似區(qū)域匹配精度較低。隨著海洋探測技術(shù)的發(fā)展，多波束測深系統(tǒng)在在水下地形探測方面發(fā)揮著重要作用，不同于傳統(tǒng)單波束測深方式，多波束測深系統(tǒng)一次測量能夠獲得多點地形數(shù)據(jù)，探測范圍更廣，精度更高。

本文提出基于改進遺傳算法的多波束水下地形匹配方法，在多波束測深系統(tǒng)采集的水深數(shù)據(jù)中選擇多條水深數(shù)據(jù)，利用遺傳算法進行地形匹配，引入正余弦算法對遺傳算法中的精英個體進行優(yōu)化，加快遺傳算法的收斂速度和改善局部收斂問題，可以有效改善地形匹配算法在初始位置誤差較大時，匹配定位誤差大、成功率低的問題。

1 水下地形匹配模型

水下地形匹配的基本思想是根據(jù)AUV實時測量的地形信息與提前存儲的水下地形圖進行比對，對INS指示的航跡進行變換，從而確定AUV當前位置。在進入地形匹配適配區(qū)之前，由于慣性元件累積誤差的影響，INS指示的航跡與真實航跡之間存在初始平移位置誤差，航向誤差和速度誤差。實際中完成一次地形匹配所需時間較短，可認為在匹配期間航向誤差和速度誤差為定值，因此慣導(dǎo)解算的速度v和航向h可以表示為：

2 基于正余弦算法的改進遺傳算法

2.1 遺傳算法

遺傳算法（Ggenetic Algorithm,GA）是一種借鑒自然界生物進化過程而構(gòu)造出的優(yōu)化搜索算法，根據(jù)“優(yōu)勝劣汰”原則，迭代更新種群，使得種群向著最優(yōu)的方向進化[11]。遺傳算法從初始種群出發(fā)，根據(jù)建立的適應(yīng)度函數(shù)對種群中個體的優(yōu)劣進行評價，通過選擇、交叉、變異等遺傳操作對種群中個體進行變換以產(chǎn)生整體性能更優(yōu)的新種群，多次迭代后找到全局最優(yōu)解。為保證算法的收斂性，一般在種群更新過程中加入精英策略，對于每代個體中的最優(yōu)個體，不進行更改，直接保留到下一代種群中，讓每代種群的最優(yōu)個體能夠順利進入后續(xù)的迭代計算中。

以INS指示位置為搜索中心，在搜索空間內(nèi)生成多組仿射變換參數(shù)(tx,ty,α,θ)，對INS指示航跡進行變換，利用遺傳算法對變換參數(shù)進行迭代計算，最后得到最優(yōu)變換參數(shù)，對應(yīng)航跡即為最接近真實位置的匹配航跡。

2.2 正余弦算法

正余弦算法（Sine Cosine Algorithm,SCA）是一種基于正弦和余弦數(shù)學(xué)模型的優(yōu)化算法，利用正弦余弦函數(shù)震蕩性特點來趨近最優(yōu)解[12]。其算法過程與傳統(tǒng)的基于種群的優(yōu)化算法類似，根據(jù)建立的適應(yīng)度函數(shù)，對初始生成的候選解進行多次循環(huán)迭代，最終得到最優(yōu)個體。正余弦優(yōu)化算法計算簡單，方便實現(xiàn)，調(diào)節(jié)參數(shù)少，收斂速度快，因此非常適用于參數(shù)的快速尋優(yōu)。

SCA在待搜索區(qū)間內(nèi)隨機初始化生成候選解種群，設(shè)種群規(guī)模為N，包括N個個體(X1,X2...XN)，根據(jù)適應(yīng)度函數(shù)計算適應(yīng)度值fSCA(Xi)，記錄最優(yōu)個體位置，通過正余弦函數(shù)與隨機因子對候選解更新，生成下代種群，具體更新方程為：

式中，k為待優(yōu)化參數(shù)的第k維，t為當前迭代次數(shù)，Xt+1為下一代個體，Xt當代個體，Pt為當代最優(yōu)個體：三個參數(shù)是隨機因子，均服從均勻分布，r1為轉(zhuǎn)換參數(shù)，控制SCA從全局開發(fā)轉(zhuǎn)向局部開發(fā)，取值為：

其中，a為常數(shù)，T為設(shè)定的最大迭代次數(shù)。

2.3 基于SCA改進的遺傳算法

GA為保證算法的收斂性，通常加入精英策略，但是在精英個體是局部最優(yōu)的情況下，精英策略則加劇局部最優(yōu)個體對整體種群的影響，種群中其他個體向局部最優(yōu)靠攏，導(dǎo)致算法快速收斂于局部最優(yōu)。針對這個問題，引入SCA對每代種群的精英個體進行優(yōu)化。

設(shè)GA搜索區(qū)域大小為(εx,εy,εα,εθ)，分別對應(yīng)橫向平移、縱向平移、縮放量和旋轉(zhuǎn)角的最大變化量。SCA以每一代種群中的精英個體為搜索中心，設(shè)定搜索區(qū)間大小為(0.1εx,0.1εy,0.2εα,0.2εθ)，在此區(qū)間內(nèi)生成候選集，利用更新方程對其進行候選解更新，得到最優(yōu)解。SCA的最優(yōu)解替換GA原來的精英個體，并將SCA的候選解種群作為外部種群，與遺傳算法的種群合并，一起進行后面的遺傳操作，使得種群向最優(yōu)方向進行進化。

3 基于改進GA的多波束地形匹配方法

3.1 多波束水深數(shù)據(jù)選擇

傳統(tǒng)利用單波束系統(tǒng)進行地形匹配的方法，每次測量只能獲得單點水深信息，進行多次測量之后，得到多個位置點的水深信息與INS數(shù)據(jù)，組成單條水深序列，利用水深序列與水下地形圖進行比對，確定載體在地圖上的位置。當INS指示航跡與真實航跡初始定位誤差較大時，由于需要搜索的范圍擴大，非常容易出現(xiàn)地形相似的地方，利用單條水深序列進行地形匹配的方法精度會大大下降甚至發(fā)生誤匹配。

不同于單波束系統(tǒng)，多波束測深系統(tǒng)一次測量能夠得到一條與航向垂直的水深條帶，包含幾十甚至上百個水下地形深度信息，因此可以選擇測量數(shù)據(jù)中的多個測深數(shù)據(jù)點同時進行地形匹配，提高算法在初始位置誤差較大或相似地形區(qū)域的匹配定位精度?？紤]算法復(fù)雜度，在每次測深數(shù)據(jù)的中心位置和兩側(cè)間隔為dΔ的位置各選擇一個水深點，組成三條水深序列。間隔dΔ根據(jù)地形標準差進行自適應(yīng)計算得到：

其中，μ1和μ2為調(diào)節(jié)系數(shù)，grid為地形圖網(wǎng)格間距，σ為M×N個網(wǎng)格的地形標準差，hw(i,j)為位置(i,j)處的測量水深，為該地區(qū)的平均水深。

3.2 適應(yīng)度計算

適應(yīng)度函數(shù)用于反映匹配航跡和真實航跡之間的相似度，相似度越大，意味著匹配航跡越靠近真實航跡。GA中的適應(yīng)度函數(shù)由三條多波束測量水深與匹配航跡在水下地形圖上插值得到水深的差值的加權(quán)和構(gòu)成，根據(jù)多波束測深系統(tǒng)的測深特性，中間區(qū)域的測量數(shù)據(jù)誤差最小，越靠近兩側(cè)邊緣測量數(shù)據(jù)誤差越大，所以給三條水深序列分配不同的權(quán)重：

式中，1ω為中間序列權(quán)重，2ω和3ω分別為左右兩側(cè)序列權(quán)重，均為常值。

考慮到匹配過程中，INS的累計誤差逐漸增加，導(dǎo)致航跡后期的位置可信度逐漸降低，因此加入衰減系數(shù)λ，逐漸減小水深序列中數(shù)據(jù)點所占權(quán)重，適應(yīng)度函數(shù)具體形式為：

式中，i對應(yīng)三條水深序列，j對應(yīng)每條序列上的匹配點，ijc為匹配航跡在水下地形圖上映射的水深，*ijc為實際測量水深，N為測量序列點數(shù)。匹配航跡水深與實際測量水深的差值越小，適應(yīng)度函數(shù)值越大，適應(yīng)度函數(shù)值取得最大值時，此時匹配航跡最接近真實航跡。

與GA不同，SCA的適應(yīng)度函數(shù)值越小，表示待優(yōu)化參數(shù)越接近最佳值。在進行SCA優(yōu)化時，種群中的個體均在精英個體附近，較為接近真實航跡位置，此時對最大水深誤差更加敏感，SCA的適應(yīng)度函數(shù)為：

3.3 基于SCA改進GA的多波束地形匹配步驟

根據(jù)上述分析，基于SCA改進GA的多波束水下地形匹配方法的具體步驟如下：

步驟一：在多波束測深系統(tǒng)的測深數(shù)據(jù)中選取三條水深序列，分別賦予不同權(quán)重。

步驟二：以INS指示航跡位置為搜索中心，設(shè)定搜索區(qū)間，在搜索區(qū)間內(nèi)隨機生成GA初始種群。

步驟三：對INS指示的初始航跡進行仿射變換，在水下地形圖上進行雙線性插值，得到變換后航跡對應(yīng)的水深，計算變換航跡的適應(yīng)度函數(shù)值。

步驟四：判斷迭代是否停止，滿足終止條件則輸出結(jié)果，否則，使用精英策略，保留精英個體。

步驟五：利用SCA對精英個體進行優(yōu)化，生成外部種群與GA種群合并進行遺傳操作。

步驟六：更新種群，跳轉(zhuǎn)至步驟三。

圖2 改進GA的多波束地形匹配流程圖Fig.2 Flow chart of multi-beam terrain matching based on improved GA

4 仿真驗證

為驗證本文所提方法的有效性，對基于改進遺傳算法的多波束地形匹配方法進行仿真實驗。實驗基于我國某地區(qū)實際測量的水下地形數(shù)據(jù)，地形圖的網(wǎng)格數(shù)為1484 1157×，網(wǎng)格間距為1 m，選擇其中兩塊不同地形特征區(qū)域設(shè)置仿真航跡，圖3和圖4為航跡對應(yīng)的水下投影點和地形圖，兩處地形的特征參數(shù)如表1所示。

圖4 航跡B及對應(yīng)地形圖Fig.4 Track B and corresponding topographic map

表1 地形特征參數(shù)Tab.1 Terrain feature parameters

圖3 航跡A及對應(yīng)地形圖Fig.3 Track A and corresponding topographic map

仿真中AUV移動速度為3 m/s，每隔4 s進行一次采樣，15個采樣點組成一個匹配序列，測量水深為真實水深增加標準差為0.3 m的白噪聲。航跡A的起始位置為(942,405)m，航向為北偏西60°；航跡B的起始位置為(775,245)m，航向為正東方向。慣性元件參數(shù)如表2所示。

表2 慣性器件誤差Tab.2 Inertial device error

根據(jù)上述仿真條件，仿真驗證文獻[13]提出的多路徑并行ICCP算法和本文提出的基于改進遺傳算法的多波束地形匹配方法，分別對航跡A和航跡B設(shè)置兩種不同大小的初始誤差，進行匹配定位，其匹配結(jié)果如圖5-8所示。

圖5 航跡A初始誤差較小時匹配結(jié)果Fig.5 Matching results of small initial error of track A

圖6 航跡A初始誤差較大時匹配結(jié)果Fig.6 Matching results of large initial error of track A

圖7 航跡B初始誤差較小時匹配結(jié)果Fig.7 Matching results of small initial error of track B

圖8 航跡B初始誤差較大時匹配結(jié)果Fig.8 Matching results of large initial error of track B

圖中紅色實線為真實航跡位置，同時對應(yīng)于中間水深序列，紅色虛線為實測多波束水深數(shù)據(jù)中選取的兩側(cè)水深點對應(yīng)的位置；藍色實線代表慣導(dǎo)指示航跡，對應(yīng)于中間水深序列的指示位置，兩側(cè)的虛線為另外兩條水深序列指示位置；綠色實線和天藍色實線分別為多路徑并行ICCP匹配航跡和本文方法匹配航跡。從仿真結(jié)果圖可知，在初始誤差較小時，多路徑并行ICCP與本文所提方法均能成功匹配，匹配航跡均在真實航跡附近；在初始位置誤差較大時，由于慣性累積誤差的影響，導(dǎo)致航跡變形嚴重，并且搜索范圍增大，多路徑并行ICCP匹配效果較差，匹配航跡與真實航跡之間誤差較大，而本文所提方法匹配結(jié)果仍然在真實航跡附近，對初始誤差的大小不敏感。

仿真結(jié)果數(shù)據(jù)如表3所示，從表中可以看出，多路徑并行ICCP在初始位置誤差較大時，匹配航跡的平均誤差在10 m左右，而本文所提方法在不同初始位置誤差的條件下，匹配航跡的平均誤差在2 m左右，航跡上的最大匹配誤差小于4 m，定位精度大大優(yōu)于多路徑并行ICCP算法，能夠更好實現(xiàn)不同初始位置誤差條件下的地形匹配。

表3 匹配結(jié)果對比Tab.3 Comparison of matching results

為進一步驗證改進遺傳算法的效果，在航跡A(150,150)m初始位置誤差的條件下進行航跡A四組匹配定位實驗：實驗A使用本文所提算法進行地形匹配；實驗B在傳統(tǒng)遺傳算法的基礎(chǔ)上，使用本文提出的適應(yīng)度函數(shù)；實驗C在傳統(tǒng)遺傳算法上加入SCA進行優(yōu)化；實驗D使用傳統(tǒng)遺傳算法進行匹配，使用三條水深序列的水深差值直接累加和作為適應(yīng)度函數(shù)。每組實驗獨立進行50次，分別計算每組實驗的平均定位誤差、算法最終收斂時的平均迭代次數(shù)和平均運行時間，實驗結(jié)果如表4所示。

表4 遺傳算法對比實驗Tab.4 Comparative experiments of GA

對比實驗A和實驗D結(jié)果可知，本文所提算法匹配結(jié)果相比于傳統(tǒng)遺傳算法定位精度提高42.4%，平均迭代次數(shù)降低35.27%，平均運行時間減少45.25%。對比實驗B和實驗D可知，使用本文提出的適應(yīng)度函數(shù)，遺傳算法的定位精度得到顯著提高，表明本文提出的適應(yīng)度函數(shù)能夠更好地衡量匹配航跡與真實航跡之間的相似度，有利于提高算法定位精度。對比實驗C和實驗D可知，加入SCA優(yōu)化后，遺傳算法收斂時的迭代次數(shù)和運行時間明顯降低，算法的運行效率得到提高。通過以上四組重復(fù)性實驗的統(tǒng)計結(jié)果可以得出，在遺傳算法中加入SCA優(yōu)化和改進適應(yīng)度函數(shù)能夠有效提高遺傳算法的匹配定位精度，加快收斂速度，遺傳算法的改進效果得到驗證。

5 船載驗證

為進一步驗證本文所提方法在實際應(yīng)用中的效果，在千島湖某水庫區(qū)域進行實際船載實驗。圖9為本次實驗的實驗船，船上搭載的主要設(shè)備有IMU、多波束測深系統(tǒng)和GPS-RTK接收機。其中，IMU輸出頻率為200 Hz，其中陀螺儀零偏小于0.02/h°，隨機游走小于，加速度計零偏小于100μg，隨機游走小于，實驗區(qū)域地形圖的網(wǎng)格分辨率為1 m，多波束測深系統(tǒng)為中海達公司的iBeam 8140，具體參數(shù)如表5所示。

圖9 試驗船及相關(guān)試驗設(shè)備Fig.9 Experimental ship and related equipments

表5 多波束聲吶主要技術(shù)參數(shù)Tab.5 Main technical parameters of multibeam sonar

本次實驗選取三條航跡，分別設(shè)置不同大小INS初始位置誤差，分別為(50,50)m、(150,150)m和(200,200)m。試驗中船速約為1.5 m/s，每間隔8秒選擇一個匹配點，15個匹配點組成一次航跡。為方便表示，隱去試驗區(qū)域的經(jīng)緯度，使用直角坐標系表示位置坐標，由IMU和GPS-RTK進行松組合得到的位置作為真實參考航跡。

圖10-12分別為三種不同初始誤差條件下的匹配結(jié)果，表6為匹配結(jié)果數(shù)據(jù)對比，從匹配結(jié)果可以看出，本文所提方法在不同初始位置誤差下，匹配航跡的平均位置誤差在3 m以內(nèi)，匹配航跡的最大誤差小于8 m，定位結(jié)果不受初始位置誤差的影響。而多路徑ICCP算法的精度要低于本文算法，并且在初始誤差增大時，匹配誤差也逐漸增大，當初始誤差達到200 m時，匹配失敗。船載試驗結(jié)果表明本文所提方法在不同大小的初始誤差條件下，均能達到較高的定位精度，方法的實際效果得到驗證。

圖1 INS指示航跡與真實航跡示意圖Fig.1 INS indicated track and real track diagram

圖10 (50,50)m初始位置誤差匹配結(jié)果Fig.10 Matching results of (50,50)m initial position error

圖11 (150,150)m初始位置誤差匹配結(jié)果Fig.11 Matching results of (150,150)m initial position error

圖12 (200,200)m初始位置誤差匹配結(jié)果Fig.12 Matching results of (200,200)m initial position error

表6 船載實驗匹配結(jié)果Tab.6 Matching results of shipboard experiments

6 結(jié)論

本文針對水下地形匹配問題，提出基于SCA改進遺傳算法的多波束地形匹配方法，根據(jù)地形特征自適應(yīng)選擇三條水深數(shù)據(jù)進行匹配，保證算法在相似地形處的定位精度，降低誤匹配率；在適應(yīng)度函數(shù)中加入收斂因子，減小后期慣導(dǎo)累積誤差的影響；引入SCA對遺傳算法進行優(yōu)化，加快算法收斂速度，降低陷入局部最優(yōu)的風險。仿真和船載實驗結(jié)果表明，本文提出的基于改進遺傳算法的多波束水下地形匹配方法不受初始誤差大小的影響，相比ICCP方法，定位精度更高。