陶楊，周益，蔣黃滔

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

0 引言

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

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

1.1 建立解空間

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

1.2 約束條件

1.2.1 高度約束

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

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

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

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

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

1.2.2 角度約束

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

1.2.3 距離約束

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

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

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

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

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

2.1 算法要點(diǎn)分析

2.1.1 信息素更新

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

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

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

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

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

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

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

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

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

圖1 螞蟻樹狀移動(dòng)示意圖Fig. 1 Diagram of tree-like movement

2.1.2 節(jié)點(diǎn)選擇

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

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

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

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

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

每一點(diǎn)對(duì)應(yīng)的螞蟻移動(dòng)概率為

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

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

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

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

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

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

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

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

2.2 算法流程

算法主要通過(guò)以下步驟實(shí)現(xiàn)，流程見(jià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ò)空間等分法，離散規(guī)劃空間構(gòu)建解空間。

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

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

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

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

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

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

3 算例分析

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

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

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

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

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

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

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

4 結(jié)束語(yǔ)

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