陶楊，周益，蔣黃滔

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

0 引言

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

1 地形跟隨航線規(guī)劃的數(shù)學(xué)模型

1.1 建立解空間

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

1.2 約束條件

1.2.1 高度約束

為最大程度實現(xiàn)地形跟隨，對航路點高度應(yīng)有嚴(yán)格要求：

（1） 保證航路點可達(dá)，即航路點高度應(yīng)大于地圖地形海拔高度。

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

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

（3） 保證航路點貼合地形，在同一鉛垂面上，應(yīng)盡量選擇海拔高度最低的航路點為中轉(zhuǎn)節(jié)點，即

1.2.2 角度約束

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

1.2.3 距離約束

受導(dǎo)航系統(tǒng)、飛機控制系統(tǒng)以及機動能力的多方面限制，需約束航線規(guī)劃中每兩個航路點之間的航跡距離，即

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

1.3 目標(biāo)函數(shù)

綜合上述約束條件，最優(yōu)航線可設(shè)置為航路點距離與海拔高度之和最小，即可建立目標(biāo)函數(shù)

2 地形跟隨航線規(guī)劃方法

2.1 算法要點分析

2.1.1 信息素更新

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

（1） 實時更新，表示當(dāng)前螞蟻信息素對種群的影響，即當(dāng)前螞蟻在選擇某個節(jié)點后對該節(jié)點信息素更新，以引導(dǎo)后續(xù)螞蟻的爬行路線

式中：ρ為信息素?fù)]發(fā)因子。

（2） 路徑更新，表示最優(yōu)個體信息素對種群的影響，全部螞蟻遍歷完所有路徑后，選擇最優(yōu)螞蟻的爬行路徑，更新該條路徑上每個途經(jīng)節(jié)點的信息素，保證次輪循環(huán)開始后該條路徑對螞蟻種群的引導(dǎo)為

式中：，Q為信息素強度因子；Δτi，j，k為本次循環(huán)途經(jīng)節(jié)點。

在路徑信息素更新中，相比傳統(tǒng)蟻群算法，這里引入了2 種改進(jìn)方案。

（1）再勵學(xué)習(xí)策略，根據(jù)優(yōu)劣螞蟻爬行路徑情況調(diào)整信息素濃度，以達(dá)到保障種群的總體優(yōu)秀程度、提升算法尋優(yōu)能力的效果。主要操作為增加最優(yōu)螞蟻途徑節(jié)點的信息素濃度，強化最優(yōu)螞蟻對蟻群的引導(dǎo)作用；減少最劣螞蟻途徑節(jié)點的信息素濃度，降低最劣螞蟻爬行路線對蟻群的偏離影響?；谠撍枷?，信息素的增量可表示為

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

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

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

2.1.2 節(jié)點選擇

綜合考慮信息素濃度和啟發(fā)值，構(gòu)建適應(yīng)度函數(shù)：

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

啟發(fā)值由行進(jìn)距離和節(jié)點高度共同表征為

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

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

每一點對應(yīng)的螞蟻移動概率為

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

2.1.3 參數(shù)優(yōu)化

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

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

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

式中：c1，c2為加速度因子；RND1，RND2為[0，1]區(qū)間隨機數(shù)；ωr為慣性權(quán)重，表示粒子對前序速度的繼承能力，根據(jù)文獻(xiàn)［15-16］的研究結(jié)論為

式中：ωstart為初始慣性權(quán)重；ωend為迭代結(jié)束時的慣性權(quán)重；R為總迭代次數(shù)。

記錄每次循環(huán)迭代尋優(yōu)得到的解函數(shù)f(gen)，建立誤差函數(shù)若在有限次內(nèi)誤差不變，則認(rèn)為算法已收斂，對應(yīng)的(α，β)即為所求。

2.2 算法流程

算法主要通過以下步驟實現(xiàn)，流程見圖2。

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

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

step 1： 設(shè)置包含山谷區(qū)域的規(guī)劃空間，通過空間等分法，離散規(guī)劃空間構(gòu)建解空間。

step 2： 建立小規(guī)模種群個體，執(zhí)行改進(jìn)蟻群算法進(jìn)行路徑尋優(yōu)。

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

step 4： 以最優(yōu)路徑的標(biāo)準(zhǔn)差變化為粒子群算法結(jié)束判斷依據(jù)，若30 次結(jié)果的標(biāo)準(zhǔn)差無變化，則認(rèn)為粒子群算法已收斂，此時的(α，β)即為所求。

step 5： 建立較大規(guī)模的種群個體，代入step 3的優(yōu)化參數(shù)，執(zhí)行改進(jìn)蟻群算法進(jìn)行路徑尋優(yōu)。

step 6： 判斷累積10 次計算結(jié)果的標(biāo)準(zhǔn)差變化范圍是否至當(dāng)前迭代循環(huán)次數(shù)計算結(jié)果的中位數(shù)10%以內(nèi)，若是，則令ρ值在其定義域內(nèi)增加5%；若不是，則進(jìn)入下一步。

step 7： 判斷算法是否達(dá)到最大迭代運算次數(shù)，計算結(jié)束。

3 算例分析

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

3.1 求解最優(yōu)參數(shù)組合

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

3.2 求解最優(yōu)航線

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

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

圖5 本文算法與標(biāo)準(zhǔn)蟻群算法計算過程比較Fig. 5 Calculation process of this algorithm compared with standard ant colony algorithm

4 結(jié)束語

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