蟻群算法在遠程魚雷航路規劃中的應用?

鄧新文 鄧南明

（中國人民解放軍91388部隊 湛江 524022）

1 引言

遠程魚雷的設計理念是增加魚雷的航程，利用魚雷的機動替代發射平臺的機動，從而極大地減少了發射平臺被敵方發現的概率，是實現水下“不接觸，零傷害”遠程打擊的重要作戰手段［1］。相對于普通魚雷，遠程魚雷最大的特點為航程遠，通常在百公里或者百公里以上［2］。使用時，需要對遠程魚雷進行航路規劃，魚雷出管后首先按照規劃的航路航渡至目標區域，然后像普通魚雷一樣按預定的搜索彈道與自導方式進行目標搜索與攻擊［3］。航路規劃的優劣對于遠程魚雷的戰力發揮具有重要影響，而蟻群算法是一種元啟發式的隨機搜索方法，非常適用于解決組合優化問題，而遠程魚雷的航路規劃就是典型的組合優化問題（安全、最短），易于描述但求解困難，本文對如何應用蟻群算法解決遠程魚雷航路規劃問題進行研究。

2 遠程魚雷航路規劃問題描述與環境建模

2.1 應用條件

文章主要研究遠程魚雷的二維航路規劃。遠程魚雷發射后通常是進入一定深度自主航行，所以研究遠程魚雷的二維航路規劃具有較大的現實意義［4］。

航路規劃的基礎是威脅區域已知。遠程魚雷水下航行面臨的安全威脅主要考慮島礁、碼頭以及敵方固定探測區域的威脅，而這些威脅區域的范圍可以通過海圖、偵察等手段事先獲取［5］，這些威脅區域在魚雷航行深度上的投影即為威脅區域分布平面，因此可以在已知威脅區域的基礎上開展遠程魚雷航路規劃研究。

2.2 航路規劃問題描述

航路規劃的目的是為了在魚雷起點位置與目標點位置之間，尋找到最優路徑［6］。最優路徑包含兩個方面:一方面要保證魚雷的航行安全，即避開威脅區域；另一方面要最有利于魚雷到達目標點后的戰力發揮，即預留充足的能源，由于魚雷航深與航速一定的情況下，路徑越短則能耗越小，所以路徑越短越有利。最優路徑可以認為是保證魚雷航行安全基礎上從起點到目標點的最短路徑。

2.3 建立柵格化海圖

假設魚雷的起點位置為S(x0,y0)，目標點為E(xe,ye)，以S(x0,y0)為坐標原點，以正東方向為X軸正向，以正北方向為Y軸正向構建坐標系XOY。假定規劃的海域大小為M×N米，將該海域地圖按照步長da柵格化，則可以將規劃的范圍分為(M/da)×(N/da)個柵格，柵格海圖中魚雷從起始點到目標點的航路規劃完成了，就說明魚雷找到了起始點到目的點的航路。假設威脅區域某點坐標為g(x,y)，則其對應的柵格格坐標g(c,r)，其中c為列號與r為行號，g(c,r)可以根據式（1）確定:

柵格的編號可以根據式（2）確定:

在進行柵格劃分時，無論是威脅區域柵格還是非威脅區域柵格不滿一個時，將其填滿，按一個柵格計算，而且為了確保魚雷的航行安全，威脅區域柵格應該將威脅區域邊緣外擴dw（dw為確保魚雷航行安全，距離威脅區域邊緣的最小安全距離）。安全信息由黑白柵格表示。黑色柵格代表威脅區域，即不可行區域，定義黑色柵格集合為tabuk；白色柵格代表可通行區域，定義白色柵格集合為allowedk。柵格地圖將不可行區域和可通行區域用一個二進制矩陣表示，矩陣中1代表不可通行柵格，0代表可通行柵格，由此在建立了一個融合威脅區域信息的柵格化海圖。

3 蟻群算法航路規劃

蟻群算法是通過觀察螞蟻覓食過程，提出的一種基于信息正反饋的進化算法［7］。蟻群算法的基本思想是，螞蟻尋找食物時，會在走過的路上釋放信息素，信息素會隨著時間推移而逐漸揮發，一定時間內其他螞蟻會覺察到信息素的存在，因而相同食物位置的情況下，一群螞蟻自由覓食，某只螞蟻走的路徑越短，則該路徑信息素越濃，更濃的信息素會吸引更多的螞蟻前來按照該路徑行進，某一路徑上通過螞蟻數量就會越多，則該路徑信息素會越濃，最終所有的螞蟻都會選擇信息素濃度最大的路徑，該路徑也是最短路徑［8］。另外，螞蟻選擇信息素濃度較高的路徑時，可能會發生新路線的探索行為，如果探索過程中發現了更短的路徑，那么更多的螞蟻就會被吸引過去，這樣就避免了局部最優解，達到尋找到蟻穴與食物之間最短路徑的目的［9］。

影響蟻群算法性能的主要是啟發式信息及信息素濃度［10］，t時刻當魚雷處于某個柵格i時，此時魚雷可行柵格的集合為allowedk(ct,rt)。魚雷下一步到達的柵格為j，其坐標為 (cj,rj)，其中(cj,rj)∈allowedk(ct,rt)。目標點E(xe,ye)對應的柵格坐標為E(ce,re)，則所有可行柵格的全局啟發式信息為ηij(t)，ηij(t)的計算公式如式（3）所示。

式中，Ik為可通行柵格集合。α為信息素強度影響因子，其值越大代表信息素強度的影響越大［11］。β為啟發函數因子，其值越大代表啟發式信息的影響越大。τij(t)為t時刻柵格i與j連接路徑上的信息素濃度。在螞蟻行走的過程中，螞蟻釋放信息素的同時，信息素也在揮發，為了描述信息素的揮發情況，我們定義揮發因子 ρ(0＜ρ＜1)來表示信息素揮發程度，則螞蟻遍歷所有地點后，各地點相連路徑的信息素濃度可表示為

式中，Δτij為所有螞蟻在柵格i與柵格j連接路徑上釋放信息素所增加的濃度。

4 遠程魚雷航路規劃的流程

步驟1:建立柵格化海圖。在海圖上標注出威脅區域，并將威脅區域邊緣外擴dw，按照2.3的方法建立柵格化海圖。

步驟2:參數設置。涉及的參數主要有螞蟻數量m，信息素強度影響因子α，啟發函數因子β，信息素揮發因子ρ，以及信息素強度Q，最大迭代次數等。

步驟3:狀態初始化。當前節點初始化為起始點，航行路徑長度初始化為0，禁忌表初始化為M×N全1矩陣并排除起始點（即起始點對應矩陣位置設為0），鄰接矩陣初始化。

步驟4:計算可以前往的節點。隨機將螞蟻放置于不同的地點，對螞蟻計算其下一個訪問地點，直至所有螞蟻訪問完所有可通行地點。

步驟5:計算各個螞蟻行走的路徑長度，記錄當前迭代結果中路徑的最優解（即最小值），同時對路徑上信息素濃度進行更新［12］。

步驟6:是否達到最大迭代次數，若沒有則重復執行步驟2。

步驟7:得到最優路徑結果。

5 計算機仿真

假設魚雷需要航渡的海域融合威脅區域信息后的柵格化海圖如圖1所示。其中步長為Lm。

圖1 航渡區域柵格化海圖

圖2 一次規劃最優路徑

為驗證蟻群算法在進行遠程魚雷航路規劃問題中的性能，筆者采用Matlab，進行了模擬仿真試驗。試驗中根據蟻群算法路徑規劃的經驗，設置初始化參數如下:螞蟻數量m=80，信息素強度影響因子α=1，啟發函數因子 β=7，信息素揮發因子ρ=0.3，以及信息素強度Q=10，最大迭代次數為500次。得到最優航路如圖2所示，收斂曲線如圖3所示，最短路徑長度為43.4*Lm，收斂次數為196次。

圖3 一次規劃收斂曲線

圖4 二次規劃最優路徑

圖5 二次規劃收斂曲線

該航路規劃方法不僅能用于發射前的一次航路規劃，當目標點移動時，若遠程魚雷還能接收遙控規劃，還能實現動態規劃。假定魚雷航行至柵格（10，8）時，戰場情況有變，需更改目標點，新的目標點柵格坐標為（30，1），則可以進行二次規劃，二次規劃結果最優航路為圖4所示，收斂曲線如圖5所示，最短路徑長度為22.9*L m，收斂次數為35次。

6 結語

航路規劃對于遠程魚雷非常重要，是影響魚雷能力發揮的一個重要環節。筆者針對遠程魚雷航路規劃問題，基于安全基礎上最短路徑長度的原則，采用蟻群算法進行了求解計算。通過仿真結果可見，蟻群算法能有效解決遠程魚雷航路規劃問題。該航跡規劃方法不僅可以用于遠程魚雷的航路規劃，還可以應用于UUV以及無人機等裝備的二維最優路徑規劃。在遠程魚雷的試驗過程中，進行航路規劃時應該考慮以該方法規劃的航路作為試驗航路，以貼近實際使用的方式來進行航路規劃功能以及導航精度等指標的考核驗證。