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

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

0 引言

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

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

1 遺傳算法

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

1.1 染色體編碼

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

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

1.2 初始種群

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.4 遺傳算法的改進(jìn)

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

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

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

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

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

2 算法流程

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

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

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

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

5）計(jì)算個(gè)體的變異概率PM，進(jìn)行變異操作，文中采用高斯算子變異方式操作；

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

3 仿真結(jié)果

航路的初始點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)分別為（0，0），（30，30），單位都是km。航路點(diǎn)坐標(biāo)為（Xi，Yi）（其中i＝1，2，…，I），I為所取航路點(diǎn)的數(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；

航路點(diǎn)個(gè)數(shù)I＝4。

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

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

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

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

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

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

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

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

圖2 到達(dá)目標(biāo)概率變化和到達(dá)目標(biāo)概率均值的變化圖

4 結(jié)論

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

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

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

［3］馮琦，周德云.極坐標(biāo)系下基于遺傳算法的路徑規(guī)劃方法［J］.機(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.