基于隱式馬爾科夫模型的艦隊應召搜潛方法

卞大鵬，余珊珊，張詩，余明暉，王云

1 海軍裝備部駐武漢地區(qū)第二軍事代表室，湖北武漢430064

2 華中科技大學自動化學院，湖北武漢430074

3 中國艦船研究設計中心,湖北武漢430064

0 引 言

反潛作戰(zhàn)是水面艦艇主要作戰(zhàn)任務之一，而對潛搜索（以下簡稱“搜潛”）是反潛作戰(zhàn)的重要組成部分［1］，也是水面艦艇對潛跟蹤、防御和打擊的前提。

目前，國內有學者將水面艦艇編隊搜潛與路徑規(guī)劃問題相結合，來研究搜潛過程中的最優(yōu)路徑。趙亮等［2-3］針對多艦協同應召搜索水下運動目標的路徑規(guī)劃問題進行了研究，建立了多個搜索者搜索路徑的規(guī)劃模型，并設計了一種多種群協同進化自適應進化算法，得到了協同搜索的最優(yōu)路徑。沈治河等［4］對水面艦艇搜潛進行了仿真分析，研究了艦艇編隊的優(yōu)化配置和兵力機動方法，對于提高水面艦艇編隊搜潛效率有著重要的意義。國外學者從搜索理論［5］出發(fā)研究了各種搜索優(yōu)化模型。Martins［6］開發(fā)了一種分支定界算法，即通過最大化預期的探測數量來計算搜索路徑解決方案的上限。Kierstead 等［7］研究了將遺傳算法應用到復雜環(huán)境中，對移動目標進行路徑規(guī)劃的問題。上述文獻都是將研究的區(qū)域作為整體，當改變區(qū)域中一個障礙物位置時，必須重復所有的仿真操作，從而增加了仿真的復雜性。

本文擬采用區(qū)域劃分的方法，仿真時改變某塊區(qū)域的條件，只要保證該區(qū)域最優(yōu)路徑的首尾位置不變，就可以只對該區(qū)域進行仿真。

應召搜潛是指我方已知敵方潛艇最后時刻出現的位置，在此基礎上對該位置附近的海域進行搜索。本文擬利用隱式馬爾科夫模型（HMM）對敵方潛艇運動建模，分配搜索者和搜索區(qū)域，規(guī)劃搜索者的路徑，使用進化算法（EA）找到最優(yōu)搜索路徑。

1 應召搜潛潛艇運動模型

水面艦艇編隊應召搜潛時，潛艇運動軌跡是隱藏的，但其狀態(tài)可由反潛系統的觀測來推斷。本文采用HMM 模型對其進行建模分析，過程如圖1 所示。搜潛馬爾科夫鏈符號說明如表1 所示。

圖1 搜潛馬爾科夫鏈Fig.1 Markov chain of searching submarine

表1 搜潛馬爾可夫鏈符號說明Table 1 Symbols used in markov chain of searching submarine

1.1 模型假設

馬爾科夫模型的2 個基本假設：

1）在任意時刻的狀態(tài)只依賴于其前一時刻的狀態(tài)，與其他時刻的狀態(tài)和觀測無關［8］。

2）任意時刻的觀測只依賴于該時刻的狀態(tài)，與其他時刻的觀測和狀態(tài)無關。

1.2 模型建立

在HMM 模型中，利用概率來表示狀態(tài)和觀測時間序列的隨機性，而狀態(tài)時間序列是不可見的，故初始狀態(tài)概率分布、狀態(tài)轉移矩陣和觀測概率都直接給出，最后由狀態(tài)得到觀測時間序列。

建立的HMM 模型中包含有以下參數：概率轉移矩陣Γ、觀測概率矩陣B、目標初始概率φ等。這些參數在初始化時可假定為已知，直接進行計算。

k=0 時，目 標 初 始 概 率 分 布-π( )0|0 為φ，由下式表示示為

式中：p為區(qū)分搜索標號；j 為搜索區(qū)域單元格標號。

概率轉移矩陣Γ為

式中：γgj為目標從單元格g 轉移到單元格j 的概率；j∈Cg，表示目標只能從上一時刻的位置x(k-1) =g移動到其相鄰的單元格。而是否探測到目標與隱式馬爾科夫的觀測概率矩陣相關。

觀測概率矩陣B表示為

式中：ui(k)=j，為在k時刻搜索者i 正在搜索單元格j∈Ai；oi(k)∈{0 ，1} ，為搜索者i 在時刻k的探測結果（探測到目標為1，未探測到目標為0）。

2 基于EA 算法的搜潛路徑優(yōu)化

2.1 目標函數

當路徑規(guī)劃周期為給定值時，將目標函數最大化，從而得到全部m 個搜索者的搜索區(qū)域分配情況，以及每個搜索者i 的搜索路徑，如式（8）和式（9）所示。

2.2 分配限制

對于m 個搜索者，將全部搜潛海域劃分為m塊搜潛區(qū)域，在k時刻，搜索者i被劃分到Ai（k）（i=1，2，…，m）區(qū)域，該過程為隨機分配，只需保證每個區(qū)域有且僅有一個搜索者，以及所有區(qū)域加起來為整個搜潛海域的面積且區(qū)域之間未發(fā)生重疊。此外，還需要保證每個搜索者在每個時間周期內劃分的區(qū)域是連續(xù)的。具體限制條件如下：

式（10）表示所有搜潛區(qū)域的總和為整個搜潛海域的面積；式（11）表示各搜潛區(qū)域之間無重疊，式（12）表示在k-1 時刻搜索者i 所在位置ui(k-1)的相鄰單元格Cui(k-1)，其部分或全部屬于搜索者i在k時刻所在的搜潛區(qū)域A（ik）。

2.3 網絡流限制

網絡流約束確保了在第1 次搜索開始時，每個搜索者的啟動單元都使用約束式（13）初始化，即搜潛者i 第1 次的搜潛位置必須在被分配的搜潛區(qū)域Ai( )1 之內。

在最后一個搜潛時刻，所有的搜索者都到達終止單元格，且此單元格在對應的搜潛區(qū)域之內，該約束由式（15）表示。式（14）所示的約束保證了搜索者下一次只能移動到分配區(qū)域內上一次所處位置的相鄰單元格之內。

3 兩階段啟發(fā)式求解方法

由于搜索者分配和搜潛路徑規(guī)劃是NP-hard問題，在復雜約束條件下，若在龐大的搜索空間中尋求最優(yōu)解，傳統的搜索方法幾乎不可能做到［9］。因此，在準備階段和路徑規(guī)劃階段都采用啟發(fā)式求解方法來解決此問題。準備階段是在搜潛周期開始時將搜潛海域劃分成小的區(qū)域。為保證m 個搜索者搜索路徑的限制，需要把搜潛區(qū)域劃分成空間相鄰的m 個不重疊區(qū)域，且為每個區(qū)域分配1 個搜索者。路徑規(guī)劃階段是在所有的搜潛周期內為每一個搜索者在其搜潛區(qū)域內規(guī)劃一條搜潛路徑。

3.1 準備階段

此階段包括搜潛區(qū)域劃分及搜索者的分配。

首先，將搜潛海域A 劃分為互不重疊的m 個搜潛區(qū)域An(k)。在自然社會中，通常某個對象受其近鄰的影響是不同的，通常是距離越近的對象對其影響越大，故在本文中采用距離最近鄰算法［10］，最近鄰算法需要在整個搜潛海域內先選取m 個質心。然后，計算剩余的單元格到質心的歐氏距離，并將單元格歸并到最近的質心所在類。每個質心對應于EA 算法中的1 個基因，m 個質心，其中對應m 個個體。最后，在每個搜索周期初始階段進行規(guī)劃，每個個體的搜索區(qū)域通過計算與搜潛中心單元格j之間的距離來生成。

在k∈{1 ，T+1，2T+1，…，K-T+1} 時刻，首先得到劃分好的搜潛區(qū)域An(k)，然后對搜索者進行分配，即將m 個搜索者分配到m 個搜索區(qū)域中。搜索者分配問題描述為

約束條件為

其中，

通常該函數可以寫為

式中：Φ為累積正態(tài)分布；σ(|Ai|)為線性組合后的縮放比例因子，即文中仿真使用的參數。其中b 和β是縮放比例因子，一般β為2 m，b 的值是為了保證累積正態(tài)分布的方差在合適的范圍內，按照本文仿真中的取值即可。

為了在特定k時刻將m 個搜索者在m 個搜潛區(qū)域內進行分配，首先令搜索者和搜潛區(qū)域兩兩組合，通過式（16）的目標函數計算得到m×m的增益矩陣，然后找到一個最優(yōu)的分配方案。上述雙向分配問題可以用排列組合和EA 算法相結合來解決，式（16）的目標函數即為分配方案對應的適應度值。

本文采用十進制EA 算法的編碼方式，染色體長度為質心數量m。在選取質心時，要求m 個質心在空間上不相鄰，以避免在區(qū)域劃分時出現極端搜潛區(qū)域過大的情況，并且可加速整個算法找到最優(yōu)個體，避免產生適應度極差的個體。

本 文 選 取Order-Based Crossover（OBX）［11］交叉方式來對染色體進行交叉操作。首先，隨機選擇1 對染色體（父代）中的1 個基因，這些基因在雙親中的位置相同但可以不連續(xù)。在選取的基因中要保證在對方的染色體中基因不相同，以避免交叉操作后出現1 個染色體有2 個相同的基因的情況，即指選取的質心重疊。然后，對這些基因進行交叉替換操作。突變選取常用的單點突變，隨機選取要突變的基因位點，并突變?yōu)榕c剩余的其他基因不同的基因。圖2 所示為EA 算法的流程。

圖2 EA 算法流程圖Fig.2 Flow chart of evolutionary algorithms

當排列組合與EA 算法相結合時，每個個體的適應度值對應的是與搜索者分配到搜索區(qū)域的分配問題相關的目標函數值。在下次迭代中，新的個體基于現在個體的適應度值生成，重復此過程直到分配解決方案收斂。預測目標概率(k|k-1) 在搜索者分配時是不更新的，并且只有在第1 次將搜索者分配到搜潛區(qū)域時才需要對搜索者進行排列組合分配。對于搜索者的重新分配只使用最近鄰算法，它基于搜索者當前的位置，并確保每個搜索者只能被分配到1 個區(qū)域來生成劃分范圍。這個過程確保了每個搜索者的搜索路徑約束。在實驗中，不考慮不可穿越的單元或障礙。

3.2 路徑規(guī)劃階段

在此階段，有些路徑規(guī)劃的限制需要明確表述。例如：搜索者從當前單元格開始搜潛，下一步只能搜索與當前單元格鄰近的8 個單元格中的一個。在每個時刻，該問題可以表示為

約束條件為：

其中，

目標函數可以用來計算新個體的適應度值，它表示要在本搜索周期內找到一條使搜潛體目標命中期望值（ED）最大的路徑。預測的目標分布概 率(k|k-1) 可以在各時刻根據種群中最優(yōu)個體的搜索序列進行更新。為了確保搜索者的移動被限制在鄰近單元格之內，目標函數要遵守網絡流限制和鄰近限制。在上述約束條件中，式（19）表示在本搜索周期開始時搜索者都在自己劃分的搜潛區(qū)域內；式（20）表示本周期第1 個搜索位置與上一個周期最后一個搜索位置是相鄰的，這保證了在2 個周期之間搜索路徑是相連的；式（21）表示在本周期之內同一個搜索者在任意相鄰時刻的搜索位置在空間上是相鄰的，保證了搜索路徑是連續(xù)性的；式（22）表示在下一個周期開始時搜索者都在自己劃分的搜潛區(qū)域內。

最優(yōu)搜索路徑的問題可以由EA 算法來求解，每個個體代表了整個搜索時間內所有搜索者的一種可能的搜索路徑。種群大小和具體搜潛海域相關，種群的下一次迭代可以通過交叉和變異操作來完成。若被選中的雙親進行交叉操作而且二者含有相同的基因，則其后代可以通過交換基因片段來完成。

1）編碼。如圖3 所示，Pi為第i 個搜索者（i=1，2，…，M）；Tk為第k個時刻（k=1，2，3…，N）；xik為搜索者i 在k時刻的位置。因為搜索者的速度限制了其只能在下個時刻移動到與其鄰近的單元格位置，所有同一個搜索者內基因體之間是有聯系的，每個基因都取決于其前一個基因，第1 個基因的位置與最初的分配位置有關，而且每個搜索者的位置還要限制在其搜潛區(qū)域內。即

式中，Ri(k)為搜索者i 在k+1 時刻能夠移動到的區(qū)域。

圖3 染色體編碼示意圖Fig.3 Chromosome coding

2）交叉操作。本文中，交叉操作時需要雙親對應的搜索者在某一基因位點有相同值，即都搜索過此單元格區(qū)域，這是對其進行交叉操作的前提。每個搜索者在進行交叉操作后需要保證長度不變，如此才能保證交叉操作后子代的染色體的長度與雙親是一樣的。但往往雙親是在不同時刻對同一單元格進行搜潛，故交叉操作后搜潛路徑會有加長和縮短的現象，為保證染色體長度不變，需對染色體進行剩余切割操作和不足增添操作，單個搜索者搜索步長為8 單元的染色體交叉如圖4 所示。

圖4 染色體交叉過程圖Fig.4 The process of chromosome crossover

圖4 中：黃色表示某搜索者的初始位置，第1個基因需要根據此位置生成；紅色表示2 個搜索者都對此位置進行了搜索，所以可以對染色體進行交叉操作。由于交叉點在雙親中的位置不同，為了保證交叉操作后染色體長度不變，需要在此操作后的染色體末端進行基因刪除以及基因隨機生成的操作。鑒于一條染色體對應了多個搜索者，所以一條染色體最多可以進行m 次交叉操作。

3）變異操作。對選中的基因進行操作，根據該基因的前、后基因，決定是否對其刪除或者進行上、下、左、右平移。若前基因和后基因在同一行或者同一列，則上、下、左、右移動，否則刪除。在進行這些操作后，基因在對應的空間位置會出現不連續(xù)情況，需要對基因進行增添操作使其連續(xù)，這樣又可能造成染色體變長，故還需要對染色體末端進行刪除部分基因的操作。圖5 所示的是一個搜索路徑步長為6 單元的染色體且共有2 種可能的變異過程，圖6 所示為變異操作的總體流程。

圖5 染色體變異過程Fig.5 The process of chromosome mutation

圖6 變異操作總體流程Fig.6 Flow chart of overall mutation

4 仿真實驗

4.1 單艦搜潛

限定整個搜潛過程總的時間步長K=10，定義每個步長為搜索者從一個單元格到相鄰單元格所需的時間，搜潛范圍為3×3 的9 個單元格，從左到右、從上到下編號依次為1～9。以下基于此設定進行單艦搜潛路徑的仿真。

考慮簡單的單個搜索者搜潛情況，且此搜索者探測范圍僅限制其所在單元格，即(k)=j。因為整個搜潛范圍內只有一個搜索者，故不需要對搜潛范圍進行區(qū)域劃分。實驗中，對搜索者的搜潛速度進行限制，速度大小是每個步長只能移動到相鄰的單元格內。假設搜索者有非常良好的搜潛能力，當潛艇和搜索者處于同一單元格內時，即認為搜索者搜索到了該潛艇。

設定潛艇目標最開始時在第9 個單元格，潛艇每步留在原地的概率為0.4，向其他相鄰單元格轉移的概率之和為0.6，且向每個單元柵格轉移的概率相同。

設定進化算法種群大小為40，迭代次數為1 000，交叉概率和變異概率分別為0.8 及0.2，經過多次試驗，可以得到從不同單元格作為初始位置時的搜潛路徑。表2 所示為初始位置為第1 個～第9 個單元格的實驗結果。

表2 單艦搜潛實驗結果Table 2 Results of single ship searching for submarine

4.2 多艦搜潛

在本節(jié)中，有多個搜索者在搜潛區(qū)域內對移動的目標潛艇進行搜索，設定搜索區(qū)域被劃分為10×10 的單元格，總的搜潛時間步長K=16。

假設現有3 個搜索者，每個搜索者的觀測范圍為包括其所在單元格和周圍的8 個單元格。實驗中，假定搜索者的速度為一個步長，且只能移動到相鄰單元格，搜索者在被劃分到的區(qū)域內的搜索概率為0.8。懲罰函數中的參數設置為b=2.5 ，β=6 ，搜索者自身信號強度SE=4.3 dB，周圍8 個單元格的信號強度為3.4 dB。

在整個搜潛區(qū)域分布均勻的情況下，初始化概 率 分 布 為-π( )0|0 ，最大化搜潛命中概率的期望值。每個搜索者在被分配的區(qū)域內對目標進行探測，并且只考慮搜索者在每個時間間隔內向四周相鄰單元格移動的情況，目標留在原地概率為0.2，向其他單元格移動的總概率為0.8，且向各個方向移動的概率相同。

實驗中，種群的最小值為40，最大值為60，交叉概率為0.8，分割次數為2 次，變異概率為0.2，迭代次數為1 000。圖7 所示為某次實驗得到的搜潛路徑。在直覺上，搜索者都是朝概率分布更高的方向移動，總體上搜潛路徑符合此直覺，但仍然有小部分搜潛路徑效率不高，隨著迭代次數增加，可能會得到更好的路徑。

最優(yōu)基因的適應度值，即整個搜潛過程的目標命中概率期望值為0.9358，第1 個搜索者的搜潛路徑為：

[7，2][8，2][8，3][7，3][7，2][6，2][5，2][5，1]

[6，1][6，0][7，0][8，0][8，1][8，2][9，2][9，3]

第2 個搜索者的路徑為：

[1，2][1，1][1，0][2，0][2，1][2，2][1，2][1，3]

[1，4][1，5][1，6][1，7][1，8][2，8][2，7][2，6]

第3 個搜索者的路徑為：

[6，7][6，6][7，6][8，6][9，6][9，7][8，7][8，8]

[7，8][6，8][6，7][5，7][5，6][5，5][6，5][7，5]

在此最大搜潛目標命中概率下，上述3 個搜索者的路徑即為它們各自的最優(yōu)路徑。

圖7 給出了k=1，6，11，16 時刻的目標概率分布。其中，黃色格子的是搜索者所在的單元格。k=1 時，搜索者周圍的藍色格子表明每個搜索者的探測區(qū)域，在接下來的幾個時刻，搜潛目標概率較低的藍色區(qū)域表明此區(qū)域剛剛被搜索者探測過，而紅色則表明目標存在于此地的概率較高。

4.3 常規(guī)方法對比研究

對于常規(guī)搜潛方法，即指水面艦艇編隊以間隔均勻的橫隊隊形排列后進行搜潛。該方法的搜潛效能由式（23）［12］評估得到。由此公式可以計算艦艇編隊對目標的搜索概率，并得到艦艇編隊搜潛的效率。

式中：U搜索為編隊整體搜索能力；T延誤為搜潛行動開始前延誤的時間；T搜索為搜潛時長；V潛艇為估計的潛艇最大速度。在保證其他參數相同的情況下，可以得到2 艘艦艇在常規(guī)搜索模式下。搜潛目標的命中概率為0.703 4，當有5 艘艦艇在常規(guī)模式下搜索時，相應的概率為0.917 2。而采用本文方法得到的最優(yōu)搜潛路徑進行搜索時，使用3 艘艦艇對潛艇目標搜索到的概率可以達0.935 8。這表明本文方法可以用更少數量的艦艇搜潛取得更高的目標命中概率，大幅提高了水面艦艇編隊的搜潛效率。

圖7 在k=1，6，11，16 時刻的搜潛目標命中概率分布圖Fig.7 The detecting probability distribution of searching submarine when k=1.6，11，16

4.4 分割次數比較

為了確定分割次數對搜潛命中概率期望值的影響，在總的搜潛時間步長為K=16，在搜潛海域為10×10 和16×16 的單元格區(qū)域內，實驗中采用不同的分割策略來研究分割次數對優(yōu)化目標的影響。實驗采用4 種不同的分割策略如下：不分割；在K=1 時 分 割1 次；在K=1，9 時 分 割2 次；在K=1，5，9，13 時分割4 次。

實驗中設置3 個搜索者，全部參數均與多艦仿真采用的相同。

EA 算法種群數量為40，交叉和變異概率分別為0.8 和0.2，迭代次數在1 000/Q～10 000/Q之間，其中Q表示對應的分割次數，采用4 種分割策略分別做100 次試驗，得到實驗的統計結果如表3 所示，其中ED 表示搜潛目標命中概率期望值。

從表3 可以看出，在沒有分割時，得到了比分割一次更好的結果，因為在沒有分割時搜索者在整個搜潛范圍內沒有移動區(qū)域限制，但會因整個搜潛范圍過大，搜潛周期過長而很難找到最優(yōu)路徑；而當對區(qū)域進行分割時，搜索者可以很容易得到在搜索區(qū)域范圍內的近似最優(yōu)路徑［13］，但這也限制了搜索者的移動范圍，所以單次分割情況下未取得比不分割時更好的方案。

綜上，為了得到更優(yōu)的搜潛路徑，需要在搜潛過程中不時地重新劃分搜潛區(qū)域，這樣不但限制了搜索者的搜潛區(qū)域范圍，還有利于找到被劃分區(qū)域內的最優(yōu)路徑，以及保證搜索者有更多的移動方向，從而在整體上得到更優(yōu)的搜潛路徑。

表3 分割次數比較Table 3 The effect of different times of divisions on experimental results

5 結 語

本文利用隱式馬爾科夫鏈建立了水面艦艇編隊應召搜潛模型，對搜索區(qū)域進行隨機劃分，并且將艦艇分配到不同子區(qū)域，每艘艦艇在被劃分的區(qū)域內以最大搜索目標命中概念期望值為優(yōu)化方向，得到在該區(qū)域內的最優(yōu)搜潛路徑。此外，采用EA 算法，通過交叉和變異操作過程生成新的可行解，避免了陷入局部最優(yōu)，使最后得到的搜索路徑整體最優(yōu)。本文將所提方法與常規(guī)搜潛方法對比，證明該方法的搜潛概率更高，并且實驗也證明了使用不同的分割策略可以得到更優(yōu)的搜潛路徑。