變異擴散蟻群算法求解戰區潛艇三維路徑規劃問題

包賢哲 丁穩房

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

0 引 言

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

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

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

1 問題分析與模型建立

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

將處于海域不同位置和深度的水雷簡化為不同大小的球形障礙物，在海域內，其函數表達為：

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

(x0,y0,z0)∈Q

(1)

式中：點(x0,y0,z0)為水雷的中心位置坐標，水雷在水域中是隨機分布的。

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

(2)

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

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

(3)

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

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

圖1 潛艇海域航行斷面圖

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

圖2 潛艇防撞模型示意圖

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

(4)

以潛艇的中心位置為坐標原點，將整個球體的極坐標形式引入為：

(5)

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

(6)

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

一般評價路徑優劣的評價指標包括路徑長短、路徑平滑度、高度等，為了能夠找到最合適的行進路線，將綜合考慮所有因素用以區別線路的優劣。潛艇在海域中潛行時到達的前后兩點間的距離為：

(7)

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

(8)

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

圖3 空間潛艇轉角示意圖

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

(9)

式中：Ai表示潛艇經過的第i個點與第i+1個點組成的空間向量；Bi+1表示第i+1個點與第i+2個點組成的空間向量；潛艇在一條完整路徑中共經過M個點。

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

(10)

式中：Zi表示潛艇在第i個點的縱坐標。

將變量進行歸一化處理，并根據重要性為三個指標分配不同的權重，由式(8)-式(10)可得到最終的目標函數為：

(11)

式中：Lmax=m+n+p即潛艇沿著長方體作戰區域的長、寬、高邊界三條直線潛行到達目的地的最長路徑；Hmax=π表示轉角的最大值；Umax=p則表示最大深度；α1、α2、α3三個權重的數值則根據目標函數的重要性確定，α1+α2+α3=1。

2 算法設計

2.1 傳統蟻群算法

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

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

(12)

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

(13)

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

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

(14)

式中：δ為信息素濃度揮發系數。線路在沒有螞蟻經過時信息素濃度會揮發逐漸下降，螞蟻經過該路段帶來的信息素濃度變化為：

(15)

2.2 變異擴散蟻群算法

2.2.1極值限制策略

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

(16)

式中：ω為常數；Lbest表示當前全局最優路徑長度，即當前螞蟻搜尋到的最短路徑。

(17)

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

2.2.2變異策略

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

(18)

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

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

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

(19)

2.2.3交叉策略

假設存在另外一只當前全局最優螞蟻m，其所經過的路徑為：

(20)

為了能夠讓優質個體對其他螞蟻起引導作用，采用交叉策略對其某部分路徑進行交換。設定交叉起止點i，j∈[1,n]，當i=2、j=5時其交叉示意圖如圖4所示。

圖4 路徑交叉示意圖

(21)

2.2.4擴散策略

蟻群個體是不具備任何關聯性的獨立個體，這樣單獨搜索的方式容易讓某些個體偏離最優路徑且迭代收斂速度較慢，為克服此問題引入信息素擴散策略。

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

圖5 信息素擴散三維空間模型

圖5所示擴散源為O點，R表示信息素擴散最大半徑，隨著離擴散源距離的增大，信息素濃度不斷降低。β和h為常數，其關系為：

htanβ=R

(22)

假設某螞蟻經過路段ij，但并不經過在其擴散最大半徑內的路徑im，在其擴散范圍內路徑im接收到的由路徑ij擴散的信息素濃度為：

(23)

式中：Lim表示路段im的長度；θ為一常數；Lk為第k只螞蟻的路徑全長。由此路徑im上的信息素濃度變為：

(24)

任意路徑上的信息濃度都是由該路徑上原本的信息素濃度與周圍有螞蟻走過的路徑擴散至此的信息素濃度組合而成，通過擴散策略可以加強不同螞蟻之間的協作交流，讓優質個體引導其他個體的搜索方向，加快算法收斂。改進算法流程如圖6所示。

圖6 改進算法流程

如圖6所示，初始化參數后確定起點和終點讓螞蟻迭代尋找路徑，完成路徑尋優過程后得到所有螞蟻路徑信息以及全局最優螞蟻路徑信息。此時采用變異策略和交叉策略優化路徑，再根據信息素限制策略和信息素擴散策略計算此次迭代后各個地點的信息素濃度，根據新的信息素濃度更新選擇概率矩陣，在此基礎上再進行第二次路徑尋優。直到達到最大迭代次數時算法終止，輸出最優路徑信息。

3 實驗與結果分析

假設存在四個不同的戰區海域P∈[10×10×1] km3(海域深度1 km),需要派遣潛艇從某區域出發前往指定區域實施打擊任務，在該海域內存在敵方部隊埋下的各式水雷以及突起的暗礁和其他障礙物，潛艇需要在保證自身不被發現的前提下以最快速度安全到達指定位置完成任務。相關任務參數設置見表1。

表1 各項參數表

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

(a) 海域1潛艇軌跡圖

(b) 海域2潛艇軌跡圖

(c) 海域3潛艇軌跡圖

(d) 海域4潛艇軌跡圖

表2 三種基礎算法結果對比表

表3 傳統蟻群算法與變異擴散蟻群算法結果對比表情形編號

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

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

可以看出，MDACO在30次左右就已經收斂，其迭代收斂速度相對于其他三種算法更快，在作戰中能夠更快速地為潛艇在復雜環境中提供最優路徑，滿足戰時對潛艇實施打擊任務快速響應的要求。

4 結 語

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