改進蟻群算法在地形跟隨航線規劃問題中的應用 *

陶楊，周益，蔣黃滔

（1. 中國人民解放軍92728 部隊，上海 200436；2. 江西洪都航空工業集團有限責任公司，江西 南昌 330024）

0 引言

航線規劃是飛機任務規劃系統的重要組成部分，其要求是在給定環境和特定約束條件下，規避地圖障礙物，找尋起止點之間的最優飛行軌跡［1］。地形跟隨航線規劃作為航線規劃的一個重要分支，更被廣泛應用于飛機/直升機的低空突防作戰和無人機自主飛行任務系統中，為順利完成作戰任務提供了有效的手段。航線規劃實質是路徑規劃，近年來，對該問題的求解方法有很多種，既有解析法［2］、人工勢場法［3］、A*算法［4］等傳統方法，也有蟻群算法［5］、遺傳算法［6］、螢火蟲算法［7］等新興智能算法。大量研究發現，在解空間復雜程度較低的環境中，上述方法均可取得較好效果，適用度較高，但處理大規模的問題時卻表現一般，主要原因為傳統算法因需遍歷解空間內的所有節點，算法搜索開銷大、效率較低；而標準智能算法普遍易陷入局部最優的優化停滯狀態，因此，直接使用的效果均不盡理想。在算法選擇方面，相比而言，蟻群算法的螞蟻覓食行為與航線規劃有高度的相似性［5］，因此，采用蟻群算法求解航線規劃問題是相對最為合理的也是適應度最高的方法。同樣，標準蟻群算法也有一些缺點，例如性能優劣與關鍵參數強相關、關鍵參數設置經驗性和隨機性突出，收斂速度慢等，直接用于航線規劃效果不佳。鑒于此，本文提出了一種基于改進蟻群算法的快速生成地形跟隨航線的通用解決方案。

1 地形跟隨航線規劃的數學模型

1.1 建立解空間

在進行航線規劃前，首先要重構三維地圖建立解空間。這里以地圖數據的某一頂點為坐標原點，以經度、緯度和高度的增加方向為3 條坐標軸，以地圖數據的極值為各坐標軸終點，建立三維坐標系，所包圍的立方體區域即構成了航線規劃空間。采用空間等分的方法，離散規劃空間，抽取航線規劃所需的網格點，并由這些點的集合構造解空間。

1.2 約束條件

1.2.1 高度約束

為最大程度實現地形跟隨，對航路點高度應有嚴格要求：

（1） 保證航路點可達，即航路點高度應大于地圖地形海拔高度。

（2） 保證航線越障，即前后相鄰航路點連線應高于兩點間途徑地形的海拔高度，即

式中：Hn為前后航路點周圍的地形海拔高度；hi，j，k為前航路點海拔；hi+1，j+1，k+1為后航路點海拔；N為前后航路點周圍地形點個數。

（3） 保證航路點貼合地形，在同一鉛垂面上，應盡量選擇海拔高度最低的航路點為中轉節點，即

1.2.2 角度約束

在飛機實際航行中，航路點設置受其轉彎半徑的影響較大，轉彎半徑越小，對應的轉彎角度越小，則機動所需能量越高，耗油量越大，對航程航時影響越明顯，因此，在條件允許范圍內，航線規劃應盡可能搜尋相對平滑的飛行航線。受最小轉彎半徑約束，航路點轉彎角度θi，j，k≥θlim，θlim為最小轉彎半徑對應的最小轉彎角。

1.2.3 距離約束

受導航系統、飛機控制系統以及機動能力的多方面限制，需約束航線規劃中每兩個航路點之間的航跡距離，即

其中：dmin，dmax分別為最小和最大可用航跡長度；di，j，k為前航路航跡長度；di+1，j+1，k+1為后航路航跡長度。

1.3 目標函數

綜合上述約束條件，最優航線可設置為航路點距離與海拔高度之和最小，即可建立目標函數

2 地形跟隨航線規劃方法

2.1 算法要點分析

2.1.1 信息素更新

蟻群的信息素更新包括兩部分為

（1） 實時更新，表示當前螞蟻信息素對種群的影響，即當前螞蟻在選擇某個節點后對該節點信息素更新，以引導后續螞蟻的爬行路線

式中：ρ為信息素揮發因子。

（2） 路徑更新，表示最優個體信息素對種群的影響，全部螞蟻遍歷完所有路徑后，選擇最優螞蟻的爬行路徑，更新該條路徑上每個途經節點的信息素，保證次輪循環開始后該條路徑對螞蟻種群的引導為

式中：，Q為信息素強度因子；Δτi，j，k為本次循環途經節點。

在路徑信息素更新中，相比傳統蟻群算法，這里引入了2 種改進方案。

（1）再勵學習策略，根據優劣螞蟻爬行路徑情況調整信息素濃度，以達到保障種群的總體優秀程度、提升算法尋優能力的效果。主要操作為增加最優螞蟻途徑節點的信息素濃度，強化最優螞蟻對蟻群的引導作用；減少最劣螞蟻途徑節點的信息素濃度，降低最劣螞蟻爬行路線對蟻群的偏離影響。基于該思想，信息素的增量可表示為

式中：q1，q2分別為最優、最劣螞蟻的信息素強度因子；Lmax為最劣路徑；Lmin為最優路徑；Mmax為選擇最劣路徑的螞蟻數量；M為種群中全體螞蟻數量；Mmin為選擇最優路徑的螞蟻數量。

（2） 自適應信息素揮發因子調整策略。信息素揮發因子ρ反映了蟻群個體之間的相互影響程度，ρ過大時，再次選擇被搜索過的路徑概率增大，算法隨機性減弱，易陷入局部最優；ρ過小時，路徑殘留信息素濃度較高，算法隨機性增強，收斂速度減慢。因此，最佳方案為根據循環迭代結果對ρ值動態調整。根據文獻［8］的研究結論表明，ρ的取值范圍一般在[0.3，1)。這里，考慮采取自適應的信息素揮發因子，通過判斷一定迭代運算下最優路徑的偏離程度，動態調整ρ值。具體為首先設置β值初始值為0.3，在計算過程中，若出現累積10 次計算結果的標準差變化范圍都在至當前迭代循環次數計算結果的中位數10%以內，表示則令ρ值在其定義域內增加5%，螞蟻樹狀移動圖如圖1 所示。

圖1 螞蟻樹狀移動示意圖Fig. 1 Diagram of tree-like movement

2.1.2 節點選擇

綜合考慮信息素濃度和啟發值，構建適應度函數：

式中：κ為角度補償系數，表示轉彎角對選擇航路點的影響，當小于θlim時，飛機在該航路點的轉彎半徑超出其固有最小轉彎半徑要求，該航路點被舍棄，反之，角度越大則為算法帶來的正反饋越強；α為信息啟發因子，反映了螞蟻在移動過程中累積信息量對蟻群搜索的指導程度，其值越大，表示在螞蟻移動中起到的作用越大，螞蟻越可能選擇之前的路徑，α值越小，表示螞蟻對之前爬行路徑的記憶力越淡，α= 0 時，為傳統的隨機貪心算法，路徑最短點被選中的概率最大；β為期望啟發因子，反映了先驗知識對蟻群搜索的指導程度，其值越大，螞蟻越傾向選擇局部最短路徑，β值越小，表示螞蟻對先驗知識的關心程度越低，β= 0 時，螞蟻會完全按照信息素濃度確定移動路徑。

啟發值由行進距離和節點高度共同表征為

式中：S為判斷算子，用于判斷下一點是否可達；di，j，k為螞蟻當前所在點與下一點之間的距離和螞蟻后續待移動節點與終點距離；為螞蟻當前所在點高度；σ1，σ2分別為距離和高度的權重系數，且σ2≥σ1，目的在于行動距離相等的情況下盡量選擇飛行高度更低的點，以優先滿足地形跟隨的要求。

假設螞蟻只能沿縱軸增加方向移動，且移動范圍有限，移動步長為εi，j，k，采用文獻［9］的樹狀移動法，在鉛垂投影面形成下一航路點搜索空間，即點集。

每一點對應的螞蟻移動概率為

通過輪盤賭的方法，根據移動概率，確定下一點，并進一步判斷該航路點的可達性，即檢查是否滿足航路避障要求。

2.1.3 參數優化

從上述分析可知，α和β與算法收斂速度與成正比、與搜索隨機性成反比，為了保證算法質量，需要選取合適的α和β值。根據文獻［10-11］的研究結論，考慮算法收斂速度和全局搜索效率，取α∈[1，3]，β∈[1，5]。由于目前尚無完整的理論體系支撐確定兩者最優組合方案，所以，常規做法是根據特定研究問題，以窮舉法通過大量重復性試驗，不斷試湊得到滿意的組合［11-12］。由于該方法強依賴于主觀經驗，且耗時較長，效率較低，嚴重制約了算法最優性能的發揮。為了解決該問題，本文利用粒子群算法對(α，β) 進行優化求解。

粒子群算法源自對鳥類覓食行為的研究，按照“個體認知”和“群體協作”的規則，搜尋離食物最近個體的周圍區域，并以此更新自體移動速度和所在位置，并最終聚集到食物周圍［13-14］。本文充分利用粒子群算法在參數尋優方面的優越性和算法實現的便利性，尋求(α，β)的最佳組合。

首先，以(α，β)定義域形成二維搜索空間Dim，規模為n的種群中每個粒子在搜索空間中的位置為、速度為。將蟻群算法中的適應度函數作為解函數，在第r步迭代過程中，通過計算解函數在每個粒子上的映射，更新粒子位置和速度，即

式中：c1，c2為加速度因子；RND1，RND2為[0，1]區間隨機數；ωr為慣性權重，表示粒子對前序速度的繼承能力，根據文獻［15-16］的研究結論為

式中：ωstart為初始慣性權重；ωend為迭代結束時的慣性權重；R為總迭代次數。

記錄每次循環迭代尋優得到的解函數f(gen)，建立誤差函數若在有限次內誤差不變，則認為算法已收斂，對應的(α，β)即為所求。

2.2 算法流程

算法主要通過以下步驟實現，流程見圖2。

圖2 算法流程圖Fig. 2 Algorithm flow

圖3 粒子群優化(α，β)參數組合誤差變化Fig. 3 Parameter combination error variation of particle swarm optimization

step 1： 設置包含山谷區域的規劃空間，通過空間等分法，離散規劃空間構建解空間。

step 2： 建立小規模種群個體，執行改進蟻群算法進行路徑尋優。

step 3： 以step 2 的蟻群移動路徑為評價目標，利用粒子群算法，優化求解蟻群算法中(α，β)最優參數組合。

step 4： 以最優路徑的標準差變化為粒子群算法結束判斷依據，若30 次結果的標準差無變化，則認為粒子群算法已收斂，此時的(α，β)即為所求。

step 5： 建立較大規模的種群個體，代入step 3的優化參數，執行改進蟻群算法進行路徑尋優。

step 6： 判斷累積10 次計算結果的標準差變化范圍是否至當前迭代循環次數計算結果的中位數10%以內，若是，則令ρ值在其定義域內增加5%；若不是，則進入下一步。

step 7： 判斷算法是否達到最大迭代運算次數，計算結束。

3 算例分析

本文以某一三維地形為例，驗證以上提出的地形跟隨航線規劃方法。假設該地形經無量綱化處理后的體積為21×21×10，起點和終點坐標分別為（1，18，5）和（21，8，6），飛機需要在與起伏地形無接觸的情況下尋找一條與其盡量貼合的最短飛行航線。

3.1 求解最優參數組合

初始化一群只有5 個個體的小型蟻群，設定迭代次數為10 步，以蟻群移動最優路徑為目標函數，通過粒子群算法對蟻群算法中的(α，β)參數組合進行優化計算，其中，粒子群算法的種群規模為15，加速度因子均為1.5。結果見圖 3。在經過41 步迭代計算，結果已收斂，此時，(α，β)組合對應為（1.966 7，3.927 2）。

3.2 求解最優航線

重新生成個體數為20 的大型蟻群，按照上文方法和思路，將第1 步求得的(α，β)組合參數代入后，對地形跟隨航線進行優化求解，結果見圖4。從航線質量來看，本文算法在諸多約束條件下，仍能很好地搜尋到可行航線。與傳統蟻群算法得到的個體適應度變化見圖5，本文算法通過105 步迭代，可得到最優航線路徑為117.3，而標準蟻群算法則多次陷入局部最優解，至300 步最大迭代次數結束，仍未完全收斂，此時對應的局部最優航線路徑為126.2。時效性上，本文算法完成最大迭代次數耗時1.36 s，而標準蟻群算法為2.52 s，運算速度提高近一倍。

圖4 地形跟隨航線示意圖Fig. 4 Map of dimensionless grain terrain following course

圖5 本文算法與標準蟻群算法計算過程比較Fig. 5 Calculation process of this algorithm compared with standard ant colony algorithm

4 結束語

本文針對地形跟隨航線規劃的特點，將該問題抽象為在特定三維解空間中的最佳路徑尋優。進一步，通過對標準蟻群算法的適應性改進和優化，提高了算法適應性，形成了面向地形跟隨航線規劃問題的通用化解決方案。經算例驗證表明，該方法用時短，生成的航線與地貌貼合度高、與地形匹配度好，進一步說明了該方法的有效性，并可在相似領域推廣應用。