蟻群算法在遠(yuǎn)程魚雷航路規(guī)劃中的應(yīng)用?

鄧新文 鄧南明

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

1 引言

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

2 遠(yuǎn)程魚雷航路規(guī)劃問題描述與環(huán)境建模

2.1 應(yīng)用條件

文章主要研究遠(yuǎn)程魚雷的二維航路規(guī)劃。遠(yuǎn)程魚雷發(fā)射后通常是進(jìn)入一定深度自主航行，所以研究遠(yuǎn)程魚雷的二維航路規(guī)劃具有較大的現(xiàn)實意義［4］。

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

2.2 航路規(guī)劃問題描述

航路規(guī)劃的目的是為了在魚雷起點位置與目標(biāo)點位置之間，尋找到最優(yōu)路徑［6］。最優(yōu)路徑包含兩個方面:一方面要保證魚雷的航行安全，即避開威脅區(qū)域；另一方面要最有利于魚雷到達(dá)目標(biāo)點后的戰(zhàn)力發(fā)揮，即預(yù)留充足的能源，由于魚雷航深與航速一定的情況下，路徑越短則能耗越小，所以路徑越短越有利。最優(yōu)路徑可以認(rèn)為是保證魚雷航行安全基礎(chǔ)上從起點到目標(biāo)點的最短路徑。

2.3 建立柵格化海圖

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

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

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

3 蟻群算法航路規(guī)劃

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

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

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

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

4 遠(yuǎn)程魚雷航路規(guī)劃的流程

步驟1:建立柵格化海圖。在海圖上標(biāo)注出威脅區(qū)域，并將威脅區(qū)域邊緣外擴(kuò)dw，按照2.3的方法建立柵格化海圖。

步驟2:參數(shù)設(shè)置。涉及的參數(shù)主要有螞蟻數(shù)量m，信息素強(qiáng)度影響因子α，啟發(fā)函數(shù)因子β，信息素?fù)]發(fā)因子ρ，以及信息素強(qiáng)度Q，最大迭代次數(shù)等。

步驟3:狀態(tài)初始化。當(dāng)前節(jié)點初始化為起始點，航行路徑長度初始化為0，禁忌表初始化為M×N全1矩陣并排除起始點（即起始點對應(yīng)矩陣位置設(shè)為0），鄰接矩陣初始化。

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

步驟5:計算各個螞蟻行走的路徑長度，記錄當(dāng)前迭代結(jié)果中路徑的最優(yōu)解（即最小值），同時對路徑上信息素濃度進(jìn)行更新［12］。

步驟6:是否達(dá)到最大迭代次數(shù)，若沒有則重復(fù)執(zhí)行步驟2。

步驟7:得到最優(yōu)路徑結(jié)果。

5 計算機(jī)仿真

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

圖1 航渡區(qū)域柵格化海圖

圖2 一次規(guī)劃最優(yōu)路徑

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

圖3 一次規(guī)劃收斂曲線

圖4 二次規(guī)劃最優(yōu)路徑

圖5 二次規(guī)劃收斂曲線

該航路規(guī)劃方法不僅能用于發(fā)射前的一次航路規(guī)劃，當(dāng)目標(biāo)點移動時，若遠(yuǎn)程魚雷還能接收遙控規(guī)劃，還能實現(xiàn)動態(tài)規(guī)劃。假定魚雷航行至柵格（10，8）時，戰(zhàn)場情況有變，需更改目標(biāo)點，新的目標(biāo)點柵格坐標(biāo)為（30，1），則可以進(jìn)行二次規(guī)劃，二次規(guī)劃結(jié)果最優(yōu)航路為圖4所示，收斂曲線如圖5所示，最短路徑長度為22.9*L m，收斂次數(shù)為35次。

6 結(jié)語

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