基于改進(jìn)遺傳算法的UAV航跡規(guī)劃

魯 藝， 呂 躍， 羅 燕， 張 亮，， 趙志強， 唐 隆

(1.空軍工程大學(xué)工程學(xué)院，西安 710038; 2.中國人民解放軍95183部隊，湖南 邵陽 422000)

0 引言

無人飛行器(Unmaned Air Vehicle，UAV)作為一種新型作戰(zhàn)武器，必將會以其特有優(yōu)勢越來越多地應(yīng)用于未來戰(zhàn)爭中。作為UAV的關(guān)鍵技術(shù)之一，航跡規(guī)劃問題已受到國內(nèi)外學(xué)者的廣泛研究，但目前關(guān)于最優(yōu)航跡求解問題，大多是將某條整體代價最小航跡作為最優(yōu)航跡，而沒有求解出航跡上航跡點的殺傷概率［1－2］，這樣可能導(dǎo)致的問題是:即使某條航跡整體代價最小，但可能會出現(xiàn)局部航跡點的殺傷概率無法滿足UAV的安全性要求，因此所得到的最優(yōu)航跡并不是真正意義上的最優(yōu)航跡 。文獻(xiàn)［3－4］將火力殺傷區(qū)分為完全殺傷區(qū)和概率殺傷區(qū)，利用分水嶺算法求解出了最優(yōu)航跡，但仍然沒有求解出航跡點的具體殺傷概率，因此所求航跡在實際作戰(zhàn)環(huán)境中也不一定是可行航跡。

本文首先在利用骨架化算法得到規(guī)劃搜索空間的基礎(chǔ)上，建立了雷達(dá)探測威脅和地空導(dǎo)彈殺傷威脅共同作用下的殺傷概率模型，求解出了規(guī)劃搜索空間中航跡點的殺傷概率和航跡段的威脅代價。然后利用本文設(shè)計的遺傳算法找到代價最小、次小、第三小等航跡，并根據(jù)本文提出的航跡選取原則，選擇出真正意義上的最優(yōu)航跡。

1 骨架化算法的規(guī)劃空間建模

規(guī)劃空間建模作為航跡規(guī)劃的關(guān)鍵技術(shù)之一，是建立航跡代價函數(shù)和進(jìn)行航跡尋優(yōu)的基礎(chǔ)和依據(jù)。數(shù)字高程地圖作為記錄地形、地貌和地面威脅空間分布的工具，是航跡規(guī)劃的信息來源和計算依據(jù)。本文中采用某100 km×100 km的數(shù)據(jù)高程地圖，首先將其均勻離散化201×201的網(wǎng)格點，兩個相鄰網(wǎng)格點之間的垂直或水平距離為500 m。然后進(jìn)行數(shù)字高程地圖的二值化，規(guī)定圖像矩陣中“0”為背景，“1”為前景，該地圖在某高度的地形威脅二值圖像如圖1所示。

圖1 地形威脅圖像Fig.1 Image of terrain threats

在實際作戰(zhàn)環(huán)境中，除地形威脅外，還存在雷達(dá)探測威脅和火力殺傷威脅。本文假定地面火力威脅均為地空導(dǎo)彈殺傷威脅。地空導(dǎo)彈殺傷區(qū)可分為完全殺傷區(qū)和概率殺傷區(qū)。完全殺傷區(qū)可簡化為一系列在水平投影上不可穿越的黑色圓形區(qū)域，概率殺傷區(qū)的殺傷概率隨著UAV與地空導(dǎo)彈距離的增大逐漸變小。將地空導(dǎo)彈殺傷威脅與地形威脅圖像疊加可得到綜合威脅圖像，如圖2所示，圖中的黑色圓形區(qū)域表示地空導(dǎo)彈的完全殺傷區(qū)，完全殺傷區(qū)實際上等效于地形威脅。

圖2 綜合威脅圖像Fig.2 Image of compositive threats

對于如圖2所示綜合威脅圖像，采用骨架化算法［5－6］生成如圖3所示規(guī)劃搜索空間，將規(guī)劃搜索空間與綜合威脅圖像相疊加，可得到綜合威脅圖像與規(guī)劃搜索空間的疊加圖像，如圖4所示。

圖3 優(yōu)化后規(guī)劃搜索空間Fig.3 The planning space after optimuization

圖3 和圖4中，S為UAV的起始點;T為UAV的目標(biāo)點，分別用★和▲表示。

圖4 威脅與規(guī)劃搜索空間疊加Fig.4 Combination of threats and planning space

規(guī)劃搜索空間實際上是由一系列航跡段、航跡點和節(jié)點組成。提取規(guī)劃搜索空間中的信息，將航跡節(jié)點信息存儲于二維矩陣node(node_num，8)中，邊(航跡段)的信息存儲于二維矩陣way(way_num，10)中，航跡點的信息存儲于Route_point三維矩陣中［7］。

2 航跡代價函數(shù)建立

航跡代價函數(shù)建立是航跡規(guī)劃中一個基本而又重要的組成部分。建立航跡代價函數(shù)時，需綜合考慮影響航跡代價的各項因素，進(jìn)而確定影響航跡代價的指標(biāo)和權(quán)重。

1)通過骨架化算法得到了規(guī)劃搜索空間，對于規(guī)劃搜索空間中的任意航跡段，其燃油代價記為 Jfuel，i［2］。文獻(xiàn)［8－9］分別建立了雷達(dá)探測概率模型和地空導(dǎo)彈殺傷概率模型，但實際上雷達(dá)和地空導(dǎo)彈是相互聯(lián)系的，地空導(dǎo)彈打擊目標(biāo)在雷達(dá)發(fā)現(xiàn)目標(biāo)的前提下進(jìn)行，因此應(yīng)該建立雷達(dá)探測威脅和地空導(dǎo)彈殺傷威脅共同作用下的殺傷概率模型。

本文假設(shè)地空導(dǎo)彈和雷達(dá)為一體。結(jié)合系統(tǒng)，N部雷達(dá)發(fā)現(xiàn)目標(biāo)相互獨立，發(fā)現(xiàn)目標(biāo)的概率分別為P(R1)，P(R2)，…，P(RN)(N ＞0)，則 N 部雷達(dá)共同作用下對目標(biāo)的探測概率為

設(shè)Q部地空導(dǎo)彈在N部雷達(dá)作用下對目標(biāo)的殺傷概率分別為 P(M1|R)，P(M2|R)，…，P(MQ|R)(Q ＞0)，則N部雷達(dá)共同作用下，單部地空導(dǎo)彈對目標(biāo)的殺傷概率分別為P(M1R)，P(M2R)，…，P(MQR)，則應(yīng)用全概率公式［10］可求得Q部地空導(dǎo)彈和N部雷達(dá)共同作用下對UAV的殺傷概率為

對于規(guī)劃搜索空間中任意航跡點和航跡段，都可利用式(1)和式(2)求解出其在多部地空導(dǎo)彈和多部雷達(dá)共同作用下航跡點的殺傷概率和航跡段的威脅代價，航跡點的殺傷概率記為p，航跡段的威脅代價記為fthreat，i。

2) 求出燃油代價 Jfuel，i和威脅代價 fthreat，i后，可將航跡代價函數(shù)簡化為

式中:J表示航跡的總代價;ω1，ω2分別表示燃油代價和威脅代價的權(quán)值，取值范圍為［0，1］，且 ω1+ω2=1。

3 遺傳算法航跡尋優(yōu)

遺傳算法(Genetic Algorithm，GA)屬于仿生算法，是一種基于生物自然選擇與基因遺傳學(xué)機理的隨機搜索算法，具有并形搜索、全局最優(yōu)等優(yōu)點［11］。

3.1 基因編碼方式

由于所求航跡的航跡段個數(shù)不確定，因此本文采用變長度的基因編碼方式，如圖5所示。

圖5 染色體結(jié)構(gòu)Fig.5 The configuration of chromosone

圖中:mi為當(dāng)前節(jié)點的序列碼;(xi，yi，zi)為當(dāng)前節(jié)點的空間坐標(biāo)信息;fi為當(dāng)前節(jié)點的適應(yīng)值(即當(dāng)前節(jié)點到下一個節(jié)點的代價值);n為染色體的最大長度;N為染色體的實際基因的長度;F為該條染色體的航跡代價信息。

已知規(guī)劃搜索空間中節(jié)點和邊的信息，因此在進(jìn)行基因編碼時采取特殊的編碼方式，具體步驟如下:

1)首先隨機產(chǎn)生從1到node_num之間的隨機數(shù)N，將其作為染色體結(jié)構(gòu)的終點，連同與之相關(guān)的坐標(biāo)信息填入相應(yīng)的基因位，規(guī)定終點的適應(yīng)值fN為0;

2)根據(jù)選定的起點信息和node(node_num，8)矩陣中node_num值的大小，連同與之相關(guān)的空間坐標(biāo)信息、適應(yīng)值信息填入染色體基因位的第1位;

3)根據(jù)way(way_num，10)矩陣中的信息，從前往后依次對每一條染色體的第2位至第(N－1)位進(jìn)行填寫，每個基因位對應(yīng)1個節(jié)點，每個節(jié)點周圍可能存在有1個節(jié)點、3個節(jié)點和4個節(jié)點3種情況，對于當(dāng)前節(jié)點，其下一位節(jié)點信息分別按照這3種情況取均等概率填寫;

4)填寫完所有基因位后，由前至后將每一基因位的適應(yīng)值相加填入染色體的最后一位，作為總的適應(yīng)值F。

與文獻(xiàn)［11］中的基因編碼方式相比，采用這種染色體結(jié)構(gòu)編碼方式在賦值階段的時間消耗會比隨機賦值時間消耗稍多，但在進(jìn)化時卻能夠節(jié)省很多時間，從而提高了航跡尋優(yōu)的效率。

3.2 航跡評價

采用這種特殊的基因編碼方式后，航跡評價就不用設(shè)置復(fù)雜的罰函數(shù)，只需遵循一條準(zhǔn)則:適應(yīng)值小的航跡優(yōu)于適應(yīng)值大的航跡。

3.3 進(jìn)化算子的設(shè)計

由于采用了基于ERP算法［11］的特殊基因編碼方式，因此本文設(shè)計了1個交叉算子和5個變異算子。包括交叉算子、擾動算子、插入算子、刪除算子、交換算子和平滑算子［7］。

3.4 算法描述

采用遺傳算法進(jìn)行航跡規(guī)劃時，系統(tǒng)首先為無人機生成大小為P的種群，完成初始化。然后按照圖6所示進(jìn)行航跡尋優(yōu)。

圖6 遺傳算法流程圖Fig.6 The flow chart of genetic algorithm

3.5 航跡選取原則

在實際作戰(zhàn)環(huán)境中，UAV總會受到地空導(dǎo)彈的攻擊，如果長期暴露在殺傷威脅區(qū)，必然會增大UAV被地空導(dǎo)彈擊毀的概率，為此提出實際作戰(zhàn)環(huán)境中的航跡評價原則:UAV在不同殺傷概率下沿某航跡飛行時所允許連續(xù)穿越的航跡點個數(shù)，不能超過保證其安全的最大航跡點個數(shù)，如表1所示。

表1 無人機在不同殺傷概率下的連續(xù)最大航跡點數(shù)目Table 1 The maximum number of route points for different kill probability

本文在采用遺傳算法尋找到整體航跡代價最小、次小、第三小等航跡的同時，描繪出對應(yīng)航跡上航跡點的殺傷概率分布圖，因而對于所求航跡，均可通過表1和航跡所對應(yīng)的殺傷概率分布圖對其進(jìn)行選取，判別其在實際作戰(zhàn)環(huán)境中是否為可行航跡。

3.6 航跡平滑

航跡平滑是在航跡尋優(yōu)的基礎(chǔ)上，對尋優(yōu)結(jié)果進(jìn)行平滑處理［3］。航跡平滑前后航跡上航跡點位置的變化必然引起殺傷概率的變化，為確保無人機安全性，得到最優(yōu)可飛航跡，本文提出航跡平滑的3個原則:

1)平滑后的航跡要滿足無人機機動性能要求;

2)平滑后的航跡要滿足無人機的安全性要求;

3)步長選取應(yīng)以平滑后的航跡代價最小為原則。

4 仿真分析

4.1 仿真情況1

仿真情形1為利用遺傳算法求解最優(yōu)航跡。

采用圖2中所示的綜合威脅圖像，根據(jù)式(3)中的航跡代價函數(shù)，在Matlab 2009環(huán)境下進(jìn)行仿真分析。

參數(shù)設(shè)置:

1)雷達(dá)的最大探測距離Rmax=20 km，地空導(dǎo)彈完全殺傷區(qū)半徑L0=6km，最大殺傷區(qū)半徑Lmax=20 km;

2)P=100，S=60，即種群的大小為 100，每次迭代取60條航跡進(jìn)行進(jìn)化操作;

3)無人機起點坐標(biāo)為(18 km，5 km)，終點坐標(biāo)為(100 km，80 km)，在圖中分別用★和▲表示;

4)所有的進(jìn)化算子以1/6的概率選取;

5)最大進(jìn)化代數(shù)為100代;

6) 燃油代價權(quán)值 ω1=0.7，威脅代價 ω2=0.3。

遺傳算法的進(jìn)化曲線如圖7所示。

圖7 遺傳算法時的進(jìn)化曲線Fig.7 The evolutionary curve of GA algorithm

圖8 ～圖10所示分別為整體代價最小、次小和代價第3小航跡，具體航跡代價值和不同殺傷概率下的不可行航跡點數(shù)目見表2。

表2 各航跡的代價值和不滿足殺傷概率點的個數(shù)Table 2 The cost of route and the number of unfeasilble points

由圖7可知，采用本文設(shè)計的遺傳算法，在初始化完成后，就形成可行航跡。進(jìn)化到20代左右時，形成接近全局最優(yōu)航跡;進(jìn)化到60代左右時，形成代價最小航跡。

圖8 代價最小航跡及航跡點殺傷概率分布Fig.8 Route of the minimum cost and the kill prdoability of route points

圖9 代價次小航跡及航跡點殺傷概率分布Fig.9 Route of the seconed minimum cost and the kill probability of route points

由圖8～圖10和表2可知，利用遺傳算法進(jìn)行航跡尋優(yōu)，不僅可以找到代價最小航跡，而且還可以找到代價次小和第三小等航跡。

但代價最小和次小航跡不滿足表1中UAV的安全性要求，故此時將代價第三小航跡作為真正意義上的最優(yōu)航跡。

4.2 仿真情形2

仿真情形2為航跡平滑。

針對仿真情形1所得到的最優(yōu)航跡，選擇步長L=3為單位進(jìn)行平滑處理。

圖11所示為步長L=12時平滑后的航跡和其上航跡點的殺傷概率分布。表3所示為不同步長L平滑后的歸一化航跡代價及不同殺傷概率下的最大連續(xù)不可行航跡點個數(shù)。

圖10 代價第三小航跡及航跡點殺傷概率分布Fig.10 Route of the third minimum cost and the kill probability of route points

圖11 L=12時平滑后的航跡及航跡點的殺傷概率分布Fig.11 The smoothed route when L=12 and the kill probability of route points

表3 平滑后的航跡代價及不同殺傷概率下連續(xù)不可行航跡點個數(shù)Table 3 The cost of smoothed route and the number of unfeasible points on different kill probability

仿真結(jié)果表明:各種步長條件下平滑后的航跡均滿足無人機的安全性要求。當(dāng)步長從L=3增大時，燃油代價和威脅代價均逐漸減小，整體代價也逐漸減小;當(dāng)步長L=12時，整體代價最小。但隨著步長進(jìn)一步增大，燃油代價仍逐漸減小，威脅代價逐漸增大，整體代價卻逐漸增大，所以將步長L=12時平滑的航跡作為最優(yōu)航跡。因此，圖11a中所示航跡為平滑后的最優(yōu)可飛航跡。

5 小結(jié)

為實現(xiàn)實際作戰(zhàn)環(huán)境中的UAV航跡規(guī)劃，本文設(shè)計了一種基于特殊編碼方式的改進(jìn)遺傳算法，不僅得到了最優(yōu)可飛航跡，而且提高了航跡規(guī)劃效率，具有實際作戰(zhàn)意義。

本文首先采用骨架化算法生成規(guī)劃搜索空間，在簡化作戰(zhàn)環(huán)境同時得到了貼近實際的規(guī)劃搜索空間，并詳細(xì)獲知了規(guī)劃搜索空間中的信息。其次，建立了雷達(dá)和地空導(dǎo)彈共同作用下的殺傷概率模型，求解出了規(guī)劃搜索空間中航跡點的殺傷概率和航跡段的威脅代價。第三，采用本文設(shè)計的遺傳算法進(jìn)行航跡尋優(yōu)，并根據(jù)航跡選取原則和平滑原則得到了實際作戰(zhàn)環(huán)境中的可飛航跡。

［1］ 李季，孫秀霞.基于改進(jìn)A_star算法的無人機航跡規(guī)劃方法研究［J］.兵工學(xué)報，2008，29(7):788－792.

［2］ 趙文婷，彭俊毅.基于VORONOI圖的無人機航跡規(guī)劃［J］.系統(tǒng)仿真學(xué)報，2008，18(S2):159－165.

［3］ 楊新勇.基于分水嶺算法的無人機航跡規(guī)劃研究［D］.西安:空軍工程大學(xué)，2009.

［4］ 穆中林，周麗麗.分水嶺分割算法的飛行器低空突防航路規(guī)劃［J］.電光與控制，2009，16(12):43－45.

［5］ 田巖，彭復(fù)員.數(shù)字圖像處理與分析［M］.武漢:華中科技大學(xué)出版社，2009.

［6］ 穆中林，魯藝.基于改進(jìn)A*算法的無人機航跡規(guī)劃方法研究［J］.彈箭與制導(dǎo)學(xué)報，2007，27(1):297－300.

［7］ 張亮.基于生存原則的無人機航跡規(guī)劃方法研究［D］.西安:空軍工程大學(xué)，2010.

［8］ 徐正軍，唐碩.基于改進(jìn)遺傳算法的飛行航跡規(guī)劃［J］.宇航學(xué)報，2008，29(5):1540－1544.

［9］ 郭錫福，趙子華.火控彈道模型理論及應(yīng)用［M］.北京:國防工業(yè)出版社，1997.

［10］ 盛驟，謝式千.概率論與數(shù)理統(tǒng)計［M］.北京:高等教育出版社，2003.

［11］ 丁明躍，鄭昌文，周成平，等.無人飛行器航跡規(guī)劃［M］.北京:電子工業(yè)出版社，2009.