巡航導(dǎo)彈航路規(guī)劃算法研究＊

肖 劉，陳紅林，葉 健，李矛彤

（1西北工業(yè)大學(xué)電子信息學(xué)院，西安 710129；2海軍駐安順地區(qū)航空軍事代表室，貴州安順 561018；3總參陸航部駐西安地區(qū)軍事代表室，西安 710061）

0 引言

巡航導(dǎo)彈航路規(guī)劃是指在特定約束條件下，尋找導(dǎo)彈從初始點到目標點滿足某種性能指標最優(yōu)的運動軌跡，是提高巡航導(dǎo)彈低空突防能力的一個很重要的方法［1］。巡航導(dǎo)彈在進行低空突防飛行時，其很大程度上取決于其自身的突防能力，也就是最大限度的減小地空導(dǎo)彈、高炮、電磁脈沖等威脅單元和地形地物障礙對其自身造成傷害的能力，即威脅回避的能力（文中將對地形地物障礙的回避簡化為威脅回避）。因此，如果事先通過搜集任務(wù)區(qū)域的情報知道敵方威脅的分布和作用范圍，就可以采用有效的航路優(yōu)化技術(shù)對從起始點到目標點的飛行航路進行規(guī)劃，得到全局最優(yōu)或次優(yōu)的飛行航路。

在任務(wù)區(qū)域內(nèi)進行航路優(yōu)化是典型的大范圍優(yōu)化問題。動態(tài)規(guī)劃算法可以得到問題的最優(yōu)解，但具有維數(shù)爆炸特性。梯度法容易陷入局部最優(yōu)解中。另有一些優(yōu)化方法，如神經(jīng)網(wǎng)絡(luò)［2］等，存在收斂速度慢等問題。更為重要的是，這些算法得到的飛行航路，從起始點出發(fā)，不能保證有效收斂于目標點。而遺傳算法（genetic algorithm）的優(yōu)點是能夠在最短的時間里找到次優(yōu)解?；谶z傳算法的優(yōu)點，文中在大范圍、多威脅區(qū)的二維空間里用改進的遺傳算法解決受約束巡航導(dǎo)彈的航路規(guī)劃問題。

1 遺傳算法

在大范圍、多威脅區(qū)環(huán)境下應(yīng)用遺傳算法解決航路規(guī)劃問題，需要采用有效的編碼方式和準確而計算快速的適應(yīng)度函數(shù)，選擇合理的遺傳操作參數(shù)。

1.1 染色體編碼

一般而言，航路點編碼需要包含航路所有信息。假設(shè)巡航導(dǎo)彈是按直線從一個點到下一點飛行的，那么當巡航導(dǎo)彈在兩個點之間飛行時每個染色體可能包含一個高度變量。當然其它的航路細節(jié)如速度、加速度限制也可以包含在染色體里面。文中將在二維空間里并假設(shè)速度恒定的情況下研究遺傳算法，并采用直接對航路點位置（橫縱坐標）進行編碼。

個體編碼采用對航路點直接編碼的方法，x2I是航路點所在位置的橫縱坐標二進制合成編碼，（x1x2…xIxI＋1…x2I），其中I為航路點的數(shù)目，（x1，xI＋1）是第一個航路點，（x2，xI＋2）是第二個航路點，其它航路點以此類推。對于航路點橫縱坐標染色體編碼，若航路點個數(shù)較多，則二進制碼的位數(shù)非常長，降低算法的進化效率。為了減小染色體長度，需要初步確定航路點個數(shù)。過多的航路點數(shù)量必然影響遺傳進化的速度，合理的航路點個數(shù)應(yīng)該使得進化過程的計算可以實現(xiàn)，同時不失去優(yōu)良航路個體。文中依據(jù)威脅區(qū)數(shù)量確定節(jié)點個數(shù)，根據(jù)大量仿真實驗可知，航路點個數(shù)I應(yīng)該取N－2～N＋2之間［3］，其中N是威脅區(qū)個數(shù)。

1.2 初始種群

由于遺傳算法的群體型操作的需求，必須為遺傳操作準備一個由若干個初始個體組成的初始種群，種群中的個體都是通過隨機方法在遺傳空間內(nèi)產(chǎn)生的。假定初始種群規(guī)模為NIND，使用隨機數(shù)發(fā)生器產(chǎn)生［0 1］之間的均勻分布隨機數(shù)，乘以相應(yīng)基因幅值的限制值，形成初始種群。

1.3 適應(yīng)度函數(shù)的求取

必須首先考慮航路的避開威脅區(qū)能力，在此基礎(chǔ)上再做航路長度的比較，以確定航路個體的適應(yīng)度函數(shù)。

航路的適應(yīng)度函數(shù)按式（1）定義：

其中Pmissle＿arrival為巡航導(dǎo)彈最終到達目標的概率。式（1）用自然對數(shù)函數(shù)有利于增大具有較高到達目標概率航路之間適應(yīng)度的區(qū)分度。如果用到達目標概率本身作為適應(yīng)度，兩個航路被遺傳到下一代的概率將會幾乎相同。通過利用自然對數(shù)函數(shù)，較優(yōu)的航路被遺傳到下一代的概率將會更高。而當?shù)竭_目標概率降到10%以下時被遺傳到下一代的概率將會近似呈線性下降。

影響到達目標概率的因素有巡航導(dǎo)彈的偶然失敗、陷入已知威脅區(qū)的概率，以及巡航導(dǎo)彈由于違規(guī)不能按照航路飛行。把偶然失敗簡單描述為服從在10000km內(nèi)失敗的平均距離的泊松分布。

偶然失敗概率函數(shù)為：

式中：λ是在每公里內(nèi)偶然失敗的概率，x是飛行的距離，n是偶然失敗的次數(shù)。

此時如果巡航導(dǎo)彈到達目標，其偶然失敗概率為式（2）在到達目標之前偶然失敗次數(shù)n為0的概率。

其中失敗率λ是失敗的平均距離的倒數(shù)。文中λ設(shè)為10－4／km。

對于陷入已知威脅區(qū)的概率是這樣處理的：如果巡航導(dǎo)彈各航路點連線不穿過威脅圓，就認為陷入已知威脅區(qū)的概率為0；反之如果航路點連線穿過威脅圓就認為陷入已知威脅區(qū)的概率為1，即巡航導(dǎo)彈到達目標概率為0。

在航路規(guī)劃的過程中，如果對航路的長度不做約束，用遺傳算法將很容易得到從初始點到目標的并且繞過所有預(yù)先探測的威脅區(qū)的一條最優(yōu)航路。然而，實際中的巡航導(dǎo)彈只能攜帶有限的燃料，如果航路長度大于自身攜帶燃料所能到達的最大航程，那么巡航導(dǎo)彈到達目標概率可能將為0或者非常小。有必要對超過航路長度約束的航路進行處罰。式（4）為航路長度處罰概率函數(shù)：

ΔL＝Lroute－Lconstraint，以上航路長度單位都是km，Lroute為航路的總長度，Lconstraint為航路所允許的最大長度。

從式（4）可以看出：如果航路長度超過航路長度約束的幅度很小，航路長度處罰概率將幾乎為0.5，而隨著超過幅度的增大，航路長度處罰概率將趨于1，即如果規(guī)劃的航路超過航路長度約束，航路長度處罰概率至少為0.5。如果規(guī)劃的航路沒有超過航路長度約束，將不處罰航路長度，即Lpenalty＝0。

巡航導(dǎo)彈到達目標概率將通過乘以1－Lpenalty而減小。

與航路長度處罰類似，在航路規(guī)劃中也要對航路的轉(zhuǎn)彎進行考慮，以滿足巡航導(dǎo)彈的轉(zhuǎn)彎半徑性能指標要求。文中取了一個跟轉(zhuǎn)彎半徑相對應(yīng)的參數(shù)變量——轉(zhuǎn)彎弧度。如果航路在一航路點轉(zhuǎn)彎弧度超過巡航導(dǎo)彈最大轉(zhuǎn)彎弧度將要受到處罰。航路轉(zhuǎn)彎弧度處罰概率函數(shù)為：

上式角度的單位為rad，Tangle為航路在航路點轉(zhuǎn)彎的弧度，Tconstraint為航路轉(zhuǎn)彎所允許的最大弧度。如果在某航路點航路轉(zhuǎn)彎弧度在所允許范圍之內(nèi)，就不處罰，即Tpenalty＝0。巡航導(dǎo)彈到達目標的概率會通過乘以1－Tpenalty而減小。

為保證巡航導(dǎo)彈能夠在最大過載范圍內(nèi)沿著航路正常轉(zhuǎn)彎，要對航路點之間的最小距離即航路最小步長進行限制。如果航路在兩航路點之間距離長度小于航路最小步長將要受到處罰。航路最小步長處罰概率函數(shù)為：

Sconstraint為航路最小步長，Slength為兩航路點之間距離長度，R為巡航導(dǎo)彈的最小轉(zhuǎn)彎半徑。如果航路在兩航路點之間距離長度大于航路最小步長，將不會受到處罰，即Spenalty＝0。巡航導(dǎo)彈到達目標的概率會通過乘以1－Spenalty而減小。

綜上所述，巡航導(dǎo)彈到達目標概率為：

1.4 遺傳算法的改進

基本遺傳算法采用適應(yīng)度比例選擇、單點交叉和單點變異方法進行遺傳操作，其主要不足是收斂速度慢、早熟收斂。為了克服這些缺點，文中在實際仿真過程中對基本遺傳操作進行改進：

1）設(shè)置代溝GGAP，剔除一部分不合理的個體，加快收斂速度。

2）采用兩點交叉的方式，增強算法的全局搜索能能力，防止陷入局部最優(yōu)解之中。兩點交叉是設(shè)置了兩個交叉點，將兩個交叉點之間的同組基因進行基因的交換。當染色體長n時，則可能有（n－2）＊（n－3）種交叉點的設(shè)置。

3）采用高斯算子的變異方式，讓變異與適應(yīng)度緊密相連，防止隨機變異對適應(yīng)度較優(yōu)的個體造成損傷，按變異率選擇某個個體并按下式變異（以k染色體為例）：

式中：gen′（i），gen（i）分別為子代和父代個體的第i位基因；Fmax、Fk分別為本代個體的最優(yōu)適應(yīng)度和第k代個體適應(yīng)度。γi為均值為0、方差為1的高斯隨機變量。

2 算法流程

1）根據(jù)編碼，應(yīng)用隨機數(shù)函數(shù)隨機產(chǎn)生初始種群的個體；

2）針對每個個體，形成相應(yīng)的航路，并計算相應(yīng)的個體適應(yīng)度；

3）個體按照性能指標排序，并通過設(shè)置代溝剔除不良個體，復(fù)制優(yōu)良個體；

4）種群內(nèi)個體隨機兩兩配對，按照交叉概率PC進行交叉操作，文中采用兩點交叉操作；

5）計算個體的變異概率PM，進行變異操作，文中采用高斯算子變異方式操作；

6）終止條件判斷，若不滿足中終條件，則繼續(xù)重復(fù)2）～5）的步驟；若滿足終止條件，則輸出最優(yōu)或次優(yōu)結(jié)果，作出航路規(guī)劃圖，算法結(jié)束。

3 仿真結(jié)果

航路的初始點和目標點坐標分別為（0，0），（30，30），單位都是km。航路點坐標為（Xi，Yi）（其中i＝1，2，…，I），I為所取航路點的數(shù)目。

使用參數(shù)：

巡航導(dǎo)彈最小轉(zhuǎn)彎半徑R＝0.6km；

群體規(guī)模NIND＝500；

最大遺傳代數(shù)MAXGEN＝300；

代溝GGAP＝0.9；

交叉概率PC＝0.7；

變異概率PM＝0.7／Lind，其中Lind為染色體長度；

航路長度約束（最大航路長度）

Lconstraint＝50km；

航路轉(zhuǎn)彎約束（最大轉(zhuǎn)彎弧度）

Tconstraint＝π／3rad；

航路點個數(shù)I＝4。

文中取了4個威脅圓（x，y，r），x、y分別為其中心坐標，r為其作用半徑。

威脅圓1：（3，5，1）為地形地物障礙威脅；

威脅圓2：（5，3，1）為高炮陣地威脅；

威脅圓3：（15，15，5）為電磁脈沖威脅；

威脅圓4：（25，25，3）為防空導(dǎo)彈陣地威脅。

文中在聯(lián)想奔4臺式機Windows XP sp3環(huán)境下利用Matlab R2008a實現(xiàn)上述算法，共花費時間為2min35s。

仿真結(jié)果如圖1、圖2所示。

圖1 巡航導(dǎo)彈的航路圖

圖2 到達目標概率變化和到達目標概率均值的變化圖

4 結(jié)論

文中將遺傳算法理論應(yīng)用到巡航導(dǎo)彈低空突防航路規(guī)劃中，并在航路規(guī)劃中對具有典型意義的巡航導(dǎo)彈在現(xiàn)在戰(zhàn)爭中可能遇到的四種威脅區(qū)進行了考慮。同時用改進后的遺傳算法對其進行模擬仿真，從仿真結(jié)果圖1來看文中的遺傳算法還是有效可行的，從圖2來看該算法是收斂的，同時也表明該算法可以解決大范圍、多威脅區(qū)的巡航導(dǎo)彈低空突防航路規(guī)劃問題。

［1］范洪達，馬向玲，葉文.飛機低空突防航路規(guī)劃技術(shù)［M］.北京：國防工業(yè)出版社，2007.

［2］閻平凡.人工神經(jīng)網(wǎng)絡(luò)與模擬進化計算［M］.北京：清華大學(xué)出版社，2000.

［3］馮琦，周德云.極坐標系下基于遺傳算法的路徑規(guī)劃方法［J］.機械科學(xué)與技術(shù)，2004，23（5）：625－626.

［4］Matthew A Russell，Gary B Lamont.A genetic algorithm for unmanned aerial vehicle routing［C］／／Proceedings of the 2005Conference on Genetic and Evolutionary Computation，2005：1523－1530.

［5］J Latiurell，B Wallet，B Copeland.Genetic algorithm to solve constrained routing problem with applications for cruise missile routing［C］／／Proc SPIE 1998，vol.3390：490－500.