基于改進蟻群算法的無人機三維航跡規劃研究*

趙冬梅 周 波 宋 陽 周國軍

（海軍大連艦艇學院基礎部 大連 116018）

1 引言

無人機（UAV）結構簡單，價格低廉，安全性好，適用于執行偵察、攻擊和評估等軍事任務。2020年1 月3 日，美國出動無人機在巴格達機場附近暗殺前伊斯蘭革命衛隊圣城軍指揮官蘇萊曼尼［1］。隨著無人機技術的發展，在未來戰場上，無人機將大顯身手，成為陸、海、空戰的主力。航跡規劃是無人機完成任務的前提，是無人機技術研究的關鍵環節。航跡規劃的目的是在復雜的戰場環境中，在滿足一定的約束條件下，尋找一條從出發點到目標點的最優路徑［2］。目前，國內外學者圍繞無人機的航跡規劃算法開展了大量研究［3］，主要分為Dijkstra算法［4］、模擬退火算法［5］和人工勢場法［6～7］等傳統經典算法和遺傳算法［8］、粒子群優化算法［9］和蟻群優化算法［10～11］等現代智能算法。

相比于經典算法，智能優化算法以其概念簡明、實現方便、參數設置少、魯棒性強［12］等優點越來越受到研究學者的青睞。文獻［13］采用基于時間和空間的信息素揮發因子自適應更新策略改進蟻群算法，保證搜索范圍的同時加快了收斂速度；文獻［14］提出改進變步長蟻群算法，兼顧較大的搜索區域和較少的迭代次數，提高算法的全局尋優能力；文獻［15］將起始點和目的點的直線連線作為對角線劃定矩形區域，區別初始化區域內和區域外的信息素濃度，利于減小搜索初期的盲目性，但沒有進一步細化信息素差異；文獻［16］提出一種新的信息素更新機制，在迭代后期將每代最優路徑長度引入信息素增量公式中，區分不同搜索時期的信息素更新，但以固定的迭代次數作為劃分依據，降低算法的靈活性；文獻［17］根據最優解增加最優路徑上的信息素，根據最差解減弱最差路徑上的信息素，提高了蟻群算法的收斂速度，但沒有解決易陷入局部最優問題。

綜合上述文獻對蟻群算法改進的優缺點，提出一種新的改進思路：初始化信息素時增大出發點和目標點連線附近的濃度，同時根據距離遠近設置濃度差異，使螞蟻在搜索初期就能沿著目標點方向選擇路徑，提高搜索的指向性；為提高搜索效率，改進啟發函數，增加待選點和目標點的距離信息以及相鄰航跡的轉角信息；隨著算法的進程，優質路徑的優勢逐漸顯現，故在搜索后期進行狀態轉移時，采用概率選擇和確定性選擇相融合的策略，進一步提高算法的收斂速度；完善信息素更新機制，根據迭代次數動態調整信息素總量，自適應地進行信息素更新，以平衡算法收斂速度和陷入局部最優之間的矛盾。最后通過仿真實驗驗證算法的優越性。

2 航跡規劃問題建模

2.1 問題描述

無人機在100km×100km×8km的空間區域內從基地出發，到達目標點執行攻擊任務，這就需要規劃出一條避開障礙物、路徑較短、高度起伏和轉彎較小的最優航跡。

2.2 三維環境地形建模

采取隨機地形和典型地形相結合的方式建立環境地形模型。通過式（1）設置隨機地形的高度，模擬較平坦的地形。

式（2）用于模擬典型地形山峰或山谷，n 為山峰或山谷的個數，（xi0，yi0）為山峰或山谷的中心坐標，hi為高度值，通過xis和yis設置峰谷的陡峭程度。

取隨機地形和典型地形的較大值為坐標點（x，y）對應的實際高度值z，如式（3）所示。

2.3 三維空間抽象建模

參考文獻［18］，在三維坐標系下，沿x 軸取經度方向，沿y 軸取緯度方向，沿z 軸取海拔高度方向。當無人機執行任務的搜索空間確定后，其在三維坐標系下的路徑空間也隨之建立。以xGrid、yGrid、zGrid為步長分別對x、y、z 三個方向進行等分，從而確定航跡規劃空間內離散化的三維點集合。無人機航跡規劃可以抽象為在這些三維點中進行航跡點選擇，確定從出發點S（xs，ys，zs）到目標點T（xt，yt，zt）的最優航跡。

2.4 搜索區域規則

為降低航跡規劃的復雜度，規定經度方向為螞蟻移動的主方向，即無人機沿x 軸方向以xGrid的固定步長移動，同時設置螞蟻沿緯度和高度方向均有最大允許移動距離，分別為Dymax和Dzmax，這就為螞蟻選擇下一航跡點提供了一個較小的可搜索空間，進一步提高算法的運行效率。

3 改進蟻群算法

3.1 蟻群算法原理

螞蟻從出發點開始，根據信息素τij(t)和啟發函數ηij(t)按照式（4）的概率選擇下一個節點，直至到達目標點并計算航跡距離。

式（4）中，allowm為螞蟻m 待訪問節點的集合，α和β分別為信息素和啟發函數重要程度參數，體現蟻群先驗知識和未探知航跡的權重大小。

隨著時間的推移，信息素濃度會逐漸揮發，ρ為揮發因子，當所有螞蟻尋找到一條從出發點到目標點的航跡后，信息素按式（5）進行更新。

重復上述計算轉移概率、確定下一節點、計算各個螞蟻路徑長度、更新信息素濃度的步驟，直至迭代結束，得到最優航跡BestPath。

3.2 非均勻初始化信息素

信息素是吸引螞蟻移動的主要因素之一，合理設置信息素的初始值和更新方法是蟻群算法有效實現的重要保證。傳統蟻群算法設置濃度相同的信息素初始值，信息素的均勻分布增加了螞蟻搜索初期的難度，使算法不易收斂。為引導螞蟻從出發點朝著目標點方向移動，設置非均勻分布的信息素初始值。

以無人機出發點和目標點的連線ST 為中心，向四周空間輻射的信息素濃度逐漸減小。設計方法為計算空間中任一航跡點到直線ST 的垂直距離d，該航跡點信息素的初始值τ與距離d 服從指數分布，二者關系為

其中，τ0為ST上航跡點的信息素初始值，也是信息素初始值的最大值。

根據上述設計，信息素初始值呈現以出發點和目標點連線為中心的指數遞減分布，突出了搜索初期從出發點到目標點的引導性，極大提高了算法的效率和準確性。

3.3 基于距離和轉角的啟發信息

啟發信息是吸引螞蟻移動的另一重要因素，文獻［20］將目標節點信息加入啟發因子中，利于算法收斂，但忽略了局部最短路徑，易出現折線路徑。為此，本文將待選航跡點與目標點距離和相鄰航跡間的轉角兩項因素融入啟發函數中，降低螞蟻轉彎的概率，進一步縮短航跡，減小無人機能耗。

其中，γ1、γ2、γ3為上述三個因素的權重因素，代表它們各自的重要程度。

1）相鄰航跡點距離

Dij的計算公式如下：

式中，（xi，yi，zi）為當前航跡點的坐標值，（xj，yj，zj）為待選航跡點的坐標值，該啟發信息的設置有利于螞蟻選取距離較短的航跡點。

2）待選航跡點與目標點距離

Qij的計算公式如下：

式中，（xj，yj，zj）為待選航跡點的坐標值，（xt，yt，zt）為目標點的坐標值，該啟發信息的設置有利于螞蟻選取距離目標較近的航跡點。

3）相鄰航跡線的轉角信息

式中，ε是值大于0 的轉角調整系數，目的是防止Φij的分母為0，該啟發信息的設置有助于螞蟻選取轉角較小的航跡點。

3.4 融入確定性選擇的狀態轉移策略

選擇下一節點j的方法為

其中，q 為0～1 之間的隨機數，q0為0～1 之間的可調參數，表示使用確定性節點轉移策略的概率。

3.5 動態調整的信息素更新機制

改變傳統蟻群算法信息素總量Q 固定不變的機制，以算法迭代次數為變量控制Q的取值。在搜索初期，由于螞蟻主要根據非均勻初始化的信息素濃度尋找航跡，可設置較大的Q 值，有助于提高搜索效率；隨著算法的推進，經過一定次數的迭代，各航跡上的信息素數值較大，為避免阻塞和停滯，應適當降低Q 值，利于螞蟻進行全局搜索；在算法后期，螞蟻已基本找到最優航跡，為加快算法收斂，可再適當增加Q 值。因此，設計信息素總量Q 隨迭代次數服從倒置的高斯分布，表達式為

其中，l為迭代次數，c取值為最大迭代次數的1/2，σ取值為最大迭代次數的1/4，設置信息素總量Q 的取值范圍在［Qmin，Qmax］區間內。

對于信息素更新公式（5），為平衡算法的全局搜索能力和收斂速度，采取參考文獻［21］提出的自適應信息素更新策略，公式為

其中，φm=a·l，和迭代次數l成正比，a為常數。

3.6 航跡評價函數

航跡評價函數體現無人機航跡規劃的優劣程度。本文設計基于航程距離代價、海拔高度代價和相鄰航線轉角代價的航跡評價函數，表達式如下：

其中，ωD、ωH和ωθ分別為航程、海拔和轉角代價的權重因子。

上述評價指標兼顧了飛行距離、高度和轉角，能夠引導螞蟻選擇出長度較短、高度起伏較緩和轉動角度較小的最優航跡。

4 算法流程

應用改進蟻群算法進行無人機三維航跡規劃的流程如圖1所示。

圖1 改進蟻群算法流程圖

5 仿真實驗與結果分析

為檢驗本文提出的改進蟻群算法的有效性，進行如下仿真實驗。設置螞蟻數量為20，出發點和目標點坐標分別為（1，20，4）和（100，80，5），最大迭代次數NC=400。環境建模參數如表1所示。

表1 三維環境建模參數

傳統蟻群算法和改進蟻群算法規劃的航跡如圖2所示。

圖2 傳統蟻群算法和改進蟻群算法規劃航跡對比圖

由圖2 可見，傳統蟻群算法規劃的航跡轉彎點較多，增加了無人機的飛行距離；而改進算法規劃的轉彎點較少，航跡較平滑，提高了無人機的飛行性能。

傳統算法和改進算法的航跡評價函數值隨迭代次數變化的曲線如圖3所示。

圖3 傳統蟻群算法和改進蟻群算法航跡評價函數值對比圖

隨機選取3 次實驗，記錄兩種算法在航跡長度、轉角和、迭代次數和運行時間等方面的結果如表2所示。

表2 傳統蟻群算法和改進蟻群算法的性能對比

綜上所述，與傳統蟻群算法相比，改進后的算法在搜索初期具有較強的收斂性，整體迭代次數更少，規劃的航跡長度更短，航跡轉角和更小，這充分說明改進蟻群算法的優越性。

6 結語

本文采用改進的蟻群算法進行無人機航跡規劃。為克服初始階段螞蟻搜索的盲目性，加強起點和終點連線附近的信息素濃度，并由近及遠形成遵循指數衰減分布的濃度梯度，極大提高了第一代蟻群的搜索效率。設計基于相鄰航跡點長度、待選航跡點與目標點長度和相鄰航線轉動角度三個要素的啟發函數，進一步平滑航跡，縮短航程，減小無人機油耗。在搜索后期進行航跡點選擇時，采用概率選擇和確定性選擇相融合的策略，進一步提高算法的收斂速度。改進信息素更新機制，根據迭代次數自適應調整信息素總量和更新信息素，以兼顧算法收斂速度快和全局搜索能力。仿真實驗表明：改進后的算法具有較強的全局搜索能力，有效減小了迭代次數，較大程度提高了航跡規劃的質量。