改進蟻群算法在飛機突防航線規(guī)劃問題中的應用

陶 楊，周 益

（解放軍92728 部隊，上海 200436）

0 引言

在航空兵突擊作戰(zhàn)中，航線規(guī)劃是任務規(guī)劃的重要組成部分，也是實施作戰(zhàn)任務的重要保障，其要求為在戰(zhàn)場迷霧的眾多約束和限定條件下，根據(jù)任務區(qū)域特定戰(zhàn)場環(huán)境（主要包括地形地貌等自然環(huán)境和敵方布勢兵力等威脅環(huán)境）及我方兵力突擊能力，設置一條符合戰(zhàn)場敵我雙方態(tài)勢和作戰(zhàn)飛機飛行能力的最優(yōu)飛行航線。航線規(guī)劃的本質是路徑規(guī)劃，近年來，國內外學者提出了很多針對該問題的求解方法，既有解析法［1］、人工勢場法［2］、A* 算法［3］、Floyd［4］等傳統(tǒng)算法，也有蟻群算法［5］、遺傳算法［6］、螢火蟲算法［7］、粒子群算法［8］、智能體［9］等智能算法。相比傳統(tǒng)算法，智能算法獨有的自我學習、自我更新、自我進化和記憶保存等能力［10］，能夠處理更為復雜的路徑規(guī)劃問題，而受到極高的關注度。其中，由于蟻群算法的螞蟻覓食行為與路徑規(guī)劃有著高度的相似性［5］，采用蟻群算法求解路徑規(guī)劃問題也成為了相對最為合理的，同時也是適應度最高的解決方案。因此，本文也在蟻群算法的基礎上開展了相關的研究工作。

1 算法實現(xiàn)

1.1 威脅區(qū)域設置

飛機突防航線規(guī)劃，可類比理解為路徑尋優(yōu)問題，即在存在若干不可跨越區(qū)域的有限大小的地圖上，尋找一條從起點到終點的距離短、平滑度高的最佳路徑。在忽略自然環(huán)境影響的前提下，不可跨越區(qū)域即為作戰(zhàn)前期由相關作戰(zhàn)部門針對威脅對象等確定的戰(zhàn)場威脅區(qū)域。本文根據(jù)威脅對象的可移動屬性，將威脅區(qū)域分為兩類：一類是以預警雷達、防空導彈和電子干擾等固定式或慢速移動式裝備，該類裝備的威脅區(qū)域是以裝備位置為圓心，以探測距離、導彈射程和干擾距離為半徑的圓形區(qū)域；另一類是以飛機、車輛等移動式防空裝備，該類裝備的威脅區(qū)域是以巡邏線+探測/攻擊距離構成的跑道型區(qū)域。

1.2 解空間建模

建立解空間，常用方法有基于圖形規(guī)劃法、基于柵格規(guī)劃法等，本文采用基于圖形規(guī)劃法，建立自由空間（makline 圖論）［11］，通過各威脅區(qū)邊界點之間的連線以及與威脅區(qū)與地圖邊界的連線，生成makline 線段，以makline 線段中點作為途經(jīng)點，構成用于尋找初始航線規(guī)劃的無向網(wǎng)絡圖。通過人工篩選，生成n 條從起點O 到終點O*的可行路徑集合。

1.3 初始路徑選擇

1.4 蟻群算法尋優(yōu)

在得到次優(yōu)路徑后，需對次優(yōu)路徑擴容形成次優(yōu)路徑帶，再通過蟻群算法進行深度優(yōu)化，求得更優(yōu)的最佳路徑。

1.4.1 次優(yōu)路徑擴容

假設Dijkstra 算法得到次優(yōu)路徑dmin需經(jīng)過O、P1、P2，…，Pn、O*點，其中，Pn點對應的makline 線段端點為、，離散化后，線段中任意節(jié)點Pi可表示為

其中，L 為線段等分數(shù)。這樣就形成了以次優(yōu)路徑為中心的沿線條帶區(qū)域——次優(yōu)路徑帶。

1.4.2 節(jié)點選擇

通過識別次優(yōu)路徑帶上各條路徑上的信息素濃度，螞蟻確定爬行過程中的移動方向。移動過程中，在Li條線段上的螞蟻，通過式（2）選擇Li+1條線段的j 節(jié)點

當q＜q0時，先依次計算當前位置的螞蟻到Li+1條線段的j 節(jié)點的狀態(tài)轉移概率pi，j，再通過輪盤賭的方式選擇出j 節(jié)點。

其中，allowedk表示第k 只螞蟻下一步可選的節(jié)點集合，α 為信息啟發(fā)因子。根據(jù)文獻［12］的研究結論，考慮算法收斂速度和全局搜索效率，一般取α=1、β∈［3，5］。在算法初期，應盡量選擇較小的β值，以避免算法過早收斂、陷入局部最優(yōu)；而在算法后期，應盡量選擇較大的β 值，以降低算法隨機搜索概率、提高收斂速度。因此，本文考慮采取自適應的期望啟發(fā)因子。通過判斷一定迭代運算下最優(yōu)路徑的偏離程度，動態(tài)調整β 值。具體為：設置β 值初始值為3，在計算過程中，若出現(xiàn)5 次迭代結果的標準差變化范圍都在5%以內，則令β 值在其定義域內增加1.1 倍。

1.4.3 信息素更新

蟻群的信息素更新包括兩部分，1）實時更新，指每只螞蟻在選擇某個節(jié)點后對該節(jié)點信息素更新；2）路徑更新，全部螞蟻遍歷完所有路徑后，選擇最優(yōu)螞蟻的爬行路徑，更新該條路徑上每個途徑節(jié)點的信息素。在路徑信息素更新中，相比傳統(tǒng)蟻群算法，本文引入了兩種改進方案：

1）精英篩選策略，通過增加最優(yōu)螞蟻的信息素濃度、減少最差螞蟻的信息素濃度，保障種群的總體優(yōu)秀程度，提升算法尋優(yōu)能力。信息素實時更新和路徑更新的表示式如式（4）和式（5）所示：

2）自適應信息素揮發(fā)因子調整策略。信息素揮發(fā)因子ρ 對蟻群的影響主要是以下兩個方面：①ρ過大時，再次選擇被搜索過的節(jié)點概率增大，算法隨機性減弱，易陷入局部最優(yōu)；②ρ 過小時，節(jié)點殘留信息素濃度較高，算法隨機性增強，收斂速度減慢。因此，最佳方案為根據(jù)每次迭代結果對ρ 值動態(tài)調整。為方便起見，在ρ∈［0.3，1）的定義域內，參考期望啟發(fā)因子β 的調整策略執(zhí)行。

2 算法步驟

算法主要通過以下步驟實現(xiàn)，流程如圖1 所示。

圖1 算法流程Fig.1 Algorithm flowchart

Step 1 根據(jù)不可跨越區(qū)域范圍，離散地圖形成解空間；

Step 2 根據(jù)解空間途經(jīng)點，生成所有從起點到終點的可行路徑；

Step 3 通過Dijkstra 算法，遍歷所有可行路徑并得到次優(yōu)路徑；

Step 4 擴展次優(yōu)路徑為次優(yōu)路徑帶，通過改進蟻群算法，在該路徑帶中進一步尋優(yōu)并得到最優(yōu)路徑；

Step 5 判斷連續(xù)5 次迭代計算得到的最優(yōu)路徑標準差變化是否大于5%，若是，則調整參數(shù)，并返回Step 4；若不是，則進入下一步；

Step 6 判斷算法是否滿足結束條件，計算結束。

3 算例驗證

假設無量綱化后的地圖面積為18×18，起點和終點坐標分別O（1，17）和O*（15，3），地圖上黑色區(qū)域為參考“1.1 威脅區(qū)域設置”相關描述設定的不可跨越區(qū)。算法中makline 線段等分數(shù)為12，螞蟻種群數(shù)為20，采用以上方法和思路計算，經(jīng)300 步得出的結果如圖2 和圖3 所示。從航線距離上看，對比Dijkstra 算法得到距離為27.885 0 的次優(yōu)航線，標準蟻群算法得到的航線距離為23.241 6，而本文算法得出的航線距離更短，為22.727 4。從效果上看，本文算法得到了航線平滑度高，途徑航跡點轉彎過渡平順，對飛機而言意味著可以用更少的機動動作、更低的油耗和更短的時間完成突防任務。從質量上看，相比標準蟻群算法，1）尋優(yōu)能力更強，在算法前期可很快收斂到全局最優(yōu)解附近；2）收斂速度更快，經(jīng)過118 步迭代，即得到全局最優(yōu)解；3）在前期陷入局部最優(yōu)解后，具有跳出能力，并可進一步尋優(yōu)；4）計算過程穩(wěn)定，數(shù)值波動范圍小、結果未見發(fā)散。

圖2 最優(yōu)突防路徑Fig.2 Optimal penetration route

圖3 標準蟻群算法與本文算法計算過程對比Fig.3 Calculation process comparison of standard ant colony algorithm and the proposed algorithm

4 結論

本文在對航空兵突擊作戰(zhàn)深入研究的基礎上，將飛機突防航線規(guī)劃問題抽象為在特定解空間中的最佳路徑尋優(yōu)。針對該問題特點，通過對標準蟻群算法的適應性改進和優(yōu)化，提高了算法效率，形成面向飛機突防問題的通用化解決方案，并可向類似專業(yè)領域推廣應用。經(jīng)驗證，該方法得到的突防航線對飛機而言，一是突防航程短，同等條件下用時少，減少了暴露風險；二是航線平滑度高，途徑航跡點轉彎角度平緩，降低了大角度機動轉彎帶來高油耗，間接增加了飛機任務時間。