包賢哲 丁穩(wěn)房

(湖北工業(yè)大學(xué)電氣與電子工程學(xué)院 湖北 武漢 430068)

0 引 言

潛艇作為海上軍事力量的重要組成部分之一，已經(jīng)成為各個(gè)國家爭相研究的重要武器裝備。隨著潛艇在海上對抗中的作用日漸顯著，出現(xiàn)了眾多針對潛艇的反潛武器，例如水雷和聲吶探測系統(tǒng)等。此時(shí)潛艇執(zhí)行任務(wù)時(shí)的路徑規(guī)劃顯得十分重要，正確且快速找到潛艇的最優(yōu)前行路徑打擊敵方艦船目標(biāo)對海上戰(zhàn)場局勢起著決定性作用，具有非常重要的研究意義。

近年來，很多學(xué)者嘗試用各種優(yōu)化算法解決路徑規(guī)劃問題且取得了不錯的效果，如陳光榮等[1]通過交替使用兩種凸優(yōu)化算法并結(jié)合經(jīng)典A*算法求解最小路徑并通過仿真實(shí)驗(yàn)驗(yàn)證了算法的有效性。改進(jìn)的A*算法[2-3]在路徑規(guī)劃問題上有較好的效果。Sun等[4]結(jié)合無線傳感器網(wǎng)絡(luò)調(diào)度技術(shù)提出了一種基于模糊神經(jīng)網(wǎng)絡(luò)的最優(yōu)航路規(guī)劃模型，該方法路徑規(guī)劃的可靠性高、收斂性較好。Lo等[5]將油耗作為優(yōu)化函數(shù)，并提出了一種油耗估算方法，通過燃油燃燒量最終搜尋出最省油的路線，該方式能夠很好地節(jié)省企業(yè)成本。王培良等[6]以柵格化地圖為研究背景，提出了蟻群元胞優(yōu)化算法，該算法可以有效提高搜索能力并避免陷入局部最優(yōu)解，但模型中并未考慮障礙物的形狀以及機(jī)器人的體積大小。Zeng等[7]采用步長優(yōu)先級的啟發(fā)信息，并加入不同的信息更新方式來優(yōu)化蟻群算法。占偉等[8]針對蟻群算法的啟發(fā)因子和信息素更新策略進(jìn)行優(yōu)化，提出一種改進(jìn)的蟻群算法解決機(jī)器人路徑規(guī)劃問題，但其設(shè)置的機(jī)器人移動場景較為簡單，實(shí)際應(yīng)用性不強(qiáng)。Viseras等[9]則通過在RRT/RRT*算法中引入蟻群優(yōu)化概念并定義一種新穎的效用函數(shù)來權(quán)衡搜索空間。Sahu等[10]使用自適應(yīng)蟻群算法修改了蟻群算法的基本參數(shù)以增強(qiáng)其控制能力。Yang等[11]則使用同時(shí)運(yùn)行搜索的高效雙層蟻群算法能夠得到較為平滑的曲線，但參數(shù)設(shè)置和算法過于復(fù)雜。Wang等[12]結(jié)合禁忌表和網(wǎng)絡(luò)權(quán)重表來加快算法收斂。改進(jìn)的蟻群算法[13-16]對于路徑搜索問題有著良好的適應(yīng)性。Gao等[17]發(fā)現(xiàn)路徑規(guī)劃中定位精度的限制，導(dǎo)致了機(jī)器人運(yùn)行的高風(fēng)險(xiǎn)性，為解決此問題，提出了一種新的路徑評估方法，首先分析不確定性再通過融合兩者的不確定性來估計(jì)可定位性，最終建立了用于路徑規(guī)劃的新路徑評估功能，該方法可有效提升路徑規(guī)劃的安全性和精度。Ueno等[18]為了解決動態(tài)路徑規(guī)劃中路徑切換中的避障問題，引入虛擬障礙物分配法抑制其帶來的影響并采用魯棒路徑規(guī)劃算法求解路徑，有效避免切換路徑后的障礙物碰撞問題。除此之外，遺傳算法[19-22]、人工勢場法[23-25]和鯨魚算法[26-28]在路徑規(guī)劃問題上也有應(yīng)用。

雖然上述算法在解決路徑規(guī)劃問題上有著不錯的效果，但都存在著一些如參數(shù)設(shè)置復(fù)雜、收斂效果不佳、未考慮移動物體的體積、障礙物體積形狀等缺點(diǎn)。針對這些問題，提出一種變異擴(kuò)散蟻群算法(Mutation Diffusion Ant Colony Algorithm,MDACO)，該算法運(yùn)用極值限制策略限制信息素濃度防止算法過早停滯，運(yùn)用變異策略增加例子多樣性擴(kuò)大搜索范圍提高算法精度，再采用信息素?cái)U(kuò)散策略加大距離較近螞蟻之間的溝通協(xié)作，加快算法收斂。最后通過四個(gè)三維空間內(nèi)的戰(zhàn)區(qū)潛艇路徑規(guī)劃問題對變異擴(kuò)散蟻群算法、傳統(tǒng)蟻群算法、遺傳算法和粒子群算法進(jìn)行求解，結(jié)果證明該算法擁有良好的性能，且對三維路徑規(guī)劃問題有著良好的適應(yīng)性。

1 問題分析與模型建立

設(shè)定一個(gè)海域Q∈[m×n×p]的三維空間中，有一艘潛艇P要從海域內(nèi)某一點(diǎn)前往另外一點(diǎn)實(shí)施打擊任務(wù)，在該海域內(nèi)存在敵方布置的各式水雷阻礙潛艇行進(jìn)，且在海域近海底部分存在暗礁巖石等障礙物，潛艇需要在避開這些障礙物且不被敵方發(fā)現(xiàn)的情況下盡可能快速地到達(dá)指定位置完成打擊任務(wù)。

將處于海域不同位置和深度的水雷簡化為不同大小的球形障礙物，在海域內(nèi)，其函數(shù)表達(dá)為：

(x-x0)2+(y-y0)2+(z-z0)2=R

(x0,y0,z0)∈Q

(1)

式中：點(diǎn)(x0,y0,z0)為水雷的中心位置坐標(biāo)，水雷在水域中是隨機(jī)分布的。

除此之外，近海底區(qū)域還存在著暗礁以及海底巖石等障礙物，將這些障礙物簡化為一個(gè)個(gè)單峰函數(shù)來表示，其表達(dá)式為：

(2)

式中：Zi(x,y)表示在(x,y)點(diǎn)上障礙物的高度；(xi,yi)則表示海底暗礁等障礙物的中心坐標(biāo)位置；k為常參數(shù)；xsi表示障礙物在x方向上的陡度；ysi表示障礙物在y方向上的陡度。

根據(jù)題意，潛艇在前行的過程中不能與障礙物發(fā)生碰撞即：

(3)

式中：P(x,y)表示潛艇的中心位置坐標(biāo)；Zo(xc,yc)表示不同深度和位置的水雷中心坐標(biāo)；Dk表示海底障礙物投影在還地面的區(qū)域集合；Qk則表示水雷投影在海底面的區(qū)域集合。式(3)表示潛艇前行時(shí)中心位置的高度必須高于海底障礙物在該點(diǎn)的高度，而對于水雷來說，潛艇可以以低于水雷位置的高度穿過，也可從位置較深的水雷上方通過。

但在實(shí)際情況中，潛艇有固定形狀和體積，若按照式(3)的約束條件潛艇與水雷或暗礁等仍然會發(fā)生碰撞，將潛艇簡化為一個(gè)長為a、寬為b、高為c的長方體，其在海域航行時(shí)的斷面圖如圖1所示。

圖1 潛艇海域航行斷面圖

圖1中矩形代表潛艇，底部起伏曲線代表海底巖石和暗礁，圓形則是處于海上不同位置和深度的水雷。依據(jù)式(3)若不考慮體積問題，潛艇中心位置大于障礙物高度或潛艇中心位置不屬于水雷所在區(qū)域內(nèi)時(shí)，在該點(diǎn)依然發(fā)生了碰撞如虛線矩形所示，所以若想要滿足潛艇在任何時(shí)刻的位置都不與障礙物碰撞，要使?jié)撏先我庖稽c(diǎn)都不在障礙物表面或障礙物體內(nèi)?？紤]到暗礁巖石等物體的表面坡度并不是固定不變的，無法對每一個(gè)障礙物都進(jìn)行細(xì)致建模。因此，以潛艇所在最小長方體的體對角線的一半為半徑作一個(gè)外包裹球體，將其放入這個(gè)球體內(nèi)，使得球體上的任意一點(diǎn)都不在障礙物表面或體內(nèi)即可滿足潛艇在任意時(shí)刻不與障礙物發(fā)生碰撞的要求，具體情況如圖2所示。

圖2 潛艇防撞模型示意圖

圖2中的長方體代表潛艇，外側(cè)的球體半徑R為潛艇體對角線的一半即OF1，其球體半徑表達(dá)式為：

(4)

以潛艇的中心位置為坐標(biāo)原點(diǎn)，將整個(gè)球體的極坐標(biāo)形式引入為：

(5)

根據(jù)式(5)即可得到最終的約束條件為：

(6)

式中：C(x,y)表示以潛艇體對角線為半徑的球體表面點(diǎn)的縱坐標(biāo)。若潛艇前行滿足式(6)，則在任何情況下都不會與水雷或暗礁發(fā)生碰撞。

一般評價(jià)路徑優(yōu)劣的評價(jià)指標(biāo)包括路徑長短、路徑平滑度、高度等，為了能夠找到最合適的行進(jìn)路線，將綜合考慮所有因素用以區(qū)別線路的優(yōu)劣。潛艇在海域中潛行時(shí)到達(dá)的前后兩點(diǎn)間的距離為：

(7)

根據(jù)式(7)可以得到潛艇前行的路徑全長為：

(8)

潛艇航行時(shí)路徑的平滑程度取決于潛艇每次前進(jìn)改變的角度大小，改變角度越大越頻繁則路徑越曲折，反之路徑越平滑，潛艇在海域三維空間前后兩次轉(zhuǎn)過的角度如圖3所示。

圖3 空間潛艇轉(zhuǎn)角示意圖

圖3中θ表示螞蟻經(jīng)過的三點(diǎn)A、B、C組成的AB空間向量與BC空間向量之間的夾角。根據(jù)圖3可得潛艇在海域前行的路徑總的平滑程度為：

(9)

式中：Ai表示潛艇經(jīng)過的第i個(gè)點(diǎn)與第i+1個(gè)點(diǎn)組成的空間向量；Bi+1表示第i+1個(gè)點(diǎn)與第i+2個(gè)點(diǎn)組成的空間向量；潛艇在一條完整路徑中共經(jīng)過M個(gè)點(diǎn)。

為了能夠盡量躲避海面敵方目標(biāo)的偵察和聲吶探測，在保證線路安全的前提下盡可能使得潛水的深度更深，總路徑的平均深度為：

(10)

式中：Zi表示潛艇在第i個(gè)點(diǎn)的縱坐標(biāo)。

將變量進(jìn)行歸一化處理，并根據(jù)重要性為三個(gè)指標(biāo)分配不同的權(quán)重，由式(8)-式(10)可得到最終的目標(biāo)函數(shù)為：

(11)

式中：Lmax=m+n+p即潛艇沿著長方體作戰(zhàn)區(qū)域的長、寬、高邊界三條直線潛行到達(dá)目的地的最長路徑；Hmax=π表示轉(zhuǎn)角的最大值；Umax=p則表示最大深度；α1、α2、α3三個(gè)權(quán)重的數(shù)值則根據(jù)目標(biāo)函數(shù)的重要性確定，α1+α2+α3=1。

2 算法設(shè)計(jì)

2.1 傳統(tǒng)蟻群算法

蟻群系統(tǒng)(Ant System或Ant Colony System)是由意大利學(xué)者Dorigo等[29]于20世紀(jì)90年代首先提出來的。他們在研究螞蟻覓食的過程中，發(fā)現(xiàn)單個(gè)螞蟻的行為比較簡單，但是蟻群整體卻可以體現(xiàn)一些智能的行為。螞蟻能根據(jù)前行道路上的信息素濃度不斷向離食物最近的道路靠攏直到找到食物。

螞蟻如何移動取決于線路上的信息素濃度水準(zhǔn)，信息素濃度越高，螞蟻選擇該路徑的概率越大，反之越小。螞蟻k在時(shí)刻t從區(qū)域i向區(qū)域j前進(jìn)的概率為：

(12)

式中：σij(t)表示時(shí)刻t線路ij上的信息素濃度；μ為信息素啟發(fā)因子，代表了信息素濃度對選擇概率的影響程度；γij(t)表示啟發(fā)信息；λ為期望啟發(fā)因子表示啟發(fā)因子對概率選擇的影響程度；G則表示螞蟻k能夠選擇的剩余的區(qū)域地點(diǎn)組成的集合。啟發(fā)因子的表達(dá)式為：

(13)

式中：Lij表示區(qū)域i與區(qū)域j之間的距離。在所有螞蟻完成路徑地區(qū)的遍歷之后，將會更新每條道路上的信息素濃度，其信息素濃度更新公式為：

σij(t+1)=(1-δ)σij(t)+Δσij

(14)

式中：δ為信息素濃度揮發(fā)系數(shù)。線路在沒有螞蟻經(jīng)過時(shí)信息素濃度會揮發(fā)逐漸下降，螞蟻經(jīng)過該路段帶來的信息素濃度變化為：

(15)

2.2 變異擴(kuò)散蟻群算法

2.2.1極值限制策略

蟻群算法前進(jìn)的過程主要依賴于信息素濃度，但在迭代過程中很容易造成某些路段螞蟻經(jīng)過次數(shù)太多導(dǎo)致信息素濃度過高，而某些路段螞蟻基本不經(jīng)過信息素?fù)]發(fā)后濃度太低，這樣會導(dǎo)致算法在早期陷入停滯。因此，對螞蟻信息素濃度的最大值和最小值分別做出以下限定：

(16)

式中：ω為常數(shù)；Lbest表示當(dāng)前全局最優(yōu)路徑長度，即當(dāng)前螞蟻搜尋到的最短路徑。

(17)

式中：t為迭代次數(shù)；Dbest表示最優(yōu)個(gè)體占全部個(gè)體的比例即個(gè)體收斂率。通過此方式能夠很好地限制信息素濃度的過分升高或降低，保證算法前期不陷入停滯。

2.2.2變異策略

蟻群算法存在著收斂速度較慢的問題，這與算法的搜索方式有關(guān)，為了克服該缺點(diǎn)，采取變異策略改良蟻群算法，假設(shè)第k只螞蟻所走過的路徑為：

(18)

首先確定變異區(qū)域，設(shè)定變異起止點(diǎn)分別為i,j∈[1，n]，將變異區(qū)域即[Li(i+1)，L(j-1)j]內(nèi)的路徑順序打亂重組q次。若每次新的路徑順序滿足式(19)，則用新的路徑順序代替原有的路徑順序，否則仍然采用原有的路徑順序。

L(i-1)i+Lm(m+1)+…+Lj(j-1)

Li(i+1)+…+Lj(j-1)

(19)

2.2.3交叉策略

假設(shè)存在另外一只當(dāng)前全局最優(yōu)螞蟻m，其所經(jīng)過的路徑為：

(20)

為了能夠讓優(yōu)質(zhì)個(gè)體對其他螞蟻起引導(dǎo)作用，采用交叉策略對其某部分路徑進(jìn)行交換。設(shè)定交叉起止點(diǎn)i，j∈[1,n]，當(dāng)i=2、j=5時(shí)其交叉示意圖如圖4所示。

圖4 路徑交叉示意圖

(21)

2.2.4擴(kuò)散策略

蟻群個(gè)體是不具備任何關(guān)聯(lián)性的獨(dú)立個(gè)體，這樣單獨(dú)搜索的方式容易讓某些個(gè)體偏離最優(yōu)路徑且迭代收斂速度較慢，為克服此問題引入信息素?cái)U(kuò)散策略。

任何揮發(fā)性的物質(zhì)都會在空間中發(fā)生擴(kuò)散現(xiàn)象，且其擴(kuò)散濃度與其距擴(kuò)散源的距離服從正態(tài)分布，將二維平面的擴(kuò)散模型簡化后擴(kuò)展到三維空間如圖5所示。

圖5 信息素?cái)U(kuò)散三維空間模型

圖5所示擴(kuò)散源為O點(diǎn)，R表示信息素?cái)U(kuò)散最大半徑，隨著離擴(kuò)散源距離的增大，信息素濃度不斷降低。β和h為常數(shù)，其關(guān)系為：

htanβ=R

(22)

假設(shè)某螞蟻經(jīng)過路段ij，但并不經(jīng)過在其擴(kuò)散最大半徑內(nèi)的路徑im，在其擴(kuò)散范圍內(nèi)路徑im接收到的由路徑ij擴(kuò)散的信息素濃度為：

(23)

式中：Lim表示路段im的長度；θ為一常數(shù)；Lk為第k只螞蟻的路徑全長。由此路徑im上的信息素濃度變?yōu)椋?/p>

(24)

任意路徑上的信息濃度都是由該路徑上原本的信息素濃度與周圍有螞蟻?zhàn)哌^的路徑擴(kuò)散至此的信息素濃度組合而成，通過擴(kuò)散策略可以加強(qiáng)不同螞蟻之間的協(xié)作交流，讓優(yōu)質(zhì)個(gè)體引導(dǎo)其他個(gè)體的搜索方向，加快算法收斂。改進(jìn)算法流程如圖6所示。

圖6 改進(jìn)算法流程

如圖6所示，初始化參數(shù)后確定起點(diǎn)和終點(diǎn)讓螞蟻迭代尋找路徑，完成路徑尋優(yōu)過程后得到所有螞蟻路徑信息以及全局最優(yōu)螞蟻路徑信息。此時(shí)采用變異策略和交叉策略優(yōu)化路徑，再根據(jù)信息素限制策略和信息素?cái)U(kuò)散策略計(jì)算此次迭代后各個(gè)地點(diǎn)的信息素濃度，根據(jù)新的信息素濃度更新選擇概率矩陣，在此基礎(chǔ)上再進(jìn)行第二次路徑尋優(yōu)。直到達(dá)到最大迭代次數(shù)時(shí)算法終止，輸出最優(yōu)路徑信息。

3 實(shí)驗(yàn)與結(jié)果分析

假設(shè)存在四個(gè)不同的戰(zhàn)區(qū)海域P∈[10×10×1] km3(海域深度1 km),需要派遣潛艇從某區(qū)域出發(fā)前往指定區(qū)域?qū)嵤┐驌羧蝿?wù)，在該海域內(nèi)存在敵方部隊(duì)埋下的各式水雷以及突起的暗礁和其他障礙物，潛艇需要在保證自身不被發(fā)現(xiàn)的前提下以最快速度安全到達(dá)指定位置完成任務(wù)。相關(guān)任務(wù)參數(shù)設(shè)置見表1。

表1 各項(xiàng)參數(shù)表

根據(jù)上述參數(shù)設(shè)定，設(shè)立種群最大迭代次數(shù)tmax=100，種群個(gè)體數(shù)量N=200，潛艇的長a=90 m,寬b=8 m,高c=5 m，目標(biāo)函數(shù)中權(quán)重取α1=0.5、2=0.4、α3=0.1。將數(shù)據(jù)代入變異擴(kuò)散蟻群算法、傳統(tǒng)蟻群算法、遺傳算法、粒子群算法四種算法中計(jì)算得到的最終路徑結(jié)果如圖7所示，最終數(shù)據(jù)如表2、表3所示。

(a) 海域1潛艇軌跡圖

(b) 海域2潛艇軌跡圖

(c) 海域3潛艇軌跡圖

(d) 海域4潛艇軌跡圖

表2 三種基礎(chǔ)算法結(jié)果對比表

表3 傳統(tǒng)蟻群算法與變異擴(kuò)散蟻群算法結(jié)果對比表情形編號

表2和表3中Min代表算法搜索到的最優(yōu)結(jié)果，Time表示算法迭代時(shí)間，Rate則表示收斂到最優(yōu)結(jié)果的粒子個(gè)體占總個(gè)體的比例即粒子收斂率。根據(jù)圖7以及表2的數(shù)據(jù)可以看出，在三種基礎(chǔ)算法中ACO能夠搜尋到更短更平滑、更安全的路徑，且迭代時(shí)間更短，粒子收斂率更高，綜合三個(gè)指標(biāo)其整體性能更加優(yōu)秀，對路徑優(yōu)化問題的適應(yīng)性也較好，所以理論上對ACO改進(jìn)能夠得到更好的改進(jìn)效果。由表3可知，改進(jìn)后的MDACO相比于傳統(tǒng)ACO性能更加優(yōu)秀，在四個(gè)算例下得到的結(jié)果更好，迭代速度和收斂率也有明顯提升，實(shí)驗(yàn)證明了該算法改進(jìn)的有效性，改進(jìn)算法對三維空間路徑優(yōu)化問題有著良好的適應(yīng)性。四個(gè)算例中的算例1的迭代過程如圖8所示。

圖8 1號海域算例算法迭代圖

可以看出，MDACO在30次左右就已經(jīng)收斂，其迭代收斂速度相對于其他三種算法更快，在作戰(zhàn)中能夠更快速地為潛艇在復(fù)雜環(huán)境中提供最優(yōu)路徑，滿足戰(zhàn)時(shí)對潛艇實(shí)施打擊任務(wù)快速響應(yīng)的要求。

4 結(jié) 語

針對戰(zhàn)區(qū)潛艇三維路徑規(guī)劃問題，提出一種變異擴(kuò)散蟻群算法。該算法首先通過極值限定策略限制信息素的增長和揮發(fā)以防止算法由于路徑信息素差別過大陷入停滯。而后采用變異交叉策略將螞蟻個(gè)體的路徑順序打亂重組，對不同螞蟻個(gè)體的路徑順序進(jìn)行交叉產(chǎn)生新的變異個(gè)體，從而增加粒子多樣性加速算法收斂。再采用信息素?cái)U(kuò)散策略加強(qiáng)距離較近螞蟻之間的交流合作，增強(qiáng)優(yōu)質(zhì)螞蟻對其他螞蟻的引導(dǎo)作用以提升算法搜索速度和精度。最后采用四個(gè)不同海域的作戰(zhàn)算例對該算法進(jìn)行了檢驗(yàn)，結(jié)果表明改進(jìn)算法相對于傳統(tǒng)算法有著更好的性能，對三維路徑避障優(yōu)化問題有著良好的適應(yīng)性。下一步將研究將該算法與其他算法結(jié)合，進(jìn)一步提升算法的性能并運(yùn)用到實(shí)際作戰(zhàn)系統(tǒng)和場景中。