基于改進遺傳算法的UAV航跡規劃

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

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

0 引言

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

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

1 骨架化算法的規劃空間建模

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

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

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

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

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

圖3 優化后規劃搜索空間Fig.3 The planning space after optimuization

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

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

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

2 航跡代價函數建立

航跡代價函數建立是航跡規劃中一個基本而又重要的組成部分。建立航跡代價函數時，需綜合考慮影響航跡代價的各項因素，進而確定影響航跡代價的指標和權重。

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

本文假設地空導彈和雷達為一體。結合系統，N部雷達發現目標相互獨立，發現目標的概率分別為P(R1)，P(R2)，…，P(RN)(N ＞0)，則 N 部雷達共同作用下對目標的探測概率為

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

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

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

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

3 遺傳算法航跡尋優

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

3.1 基因編碼方式

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

圖5 染色體結構Fig.5 The configuration of chromosone

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

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

1)首先隨機產生從1到node_num之間的隨機數N，將其作為染色體結構的終點，連同與之相關的坐標信息填入相應的基因位，規定終點的適應值fN為0;

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

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

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

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

3.2 航跡評價

采用這種特殊的基因編碼方式后，航跡評價就不用設置復雜的罰函數，只需遵循一條準則:適應值小的航跡優于適應值大的航跡。

3.3 進化算子的設計

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

3.4 算法描述

采用遺傳算法進行航跡規劃時，系統首先為無人機生成大小為P的種群，完成初始化。然后按照圖6所示進行航跡尋優。

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

3.5 航跡選取原則

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

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

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

3.6 航跡平滑

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

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

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

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

4 仿真分析

4.1 仿真情況1

仿真情形1為利用遺傳算法求解最優航跡。

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

參數設置:

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

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

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

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

5)最大進化代數為100代;

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

遺傳算法的進化曲線如圖7所示。

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

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

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

由圖7可知，采用本文設計的遺傳算法，在初始化完成后，就形成可行航跡。進化到20代左右時，形成接近全局最優航跡;進化到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可知，利用遺傳算法進行航跡尋優，不僅可以找到代價最小航跡，而且還可以找到代價次小和第三小等航跡。

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

4.2 仿真情形2

仿真情形2為航跡平滑。

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

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

圖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 平滑后的航跡代價及不同殺傷概率下連續不可行航跡點個數Table 3 The cost of smoothed route and the number of unfeasible points on different kill probability

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

5 小結

為實現實際作戰環境中的UAV航跡規劃，本文設計了一種基于特殊編碼方式的改進遺傳算法，不僅得到了最優可飛航跡，而且提高了航跡規劃效率，具有實際作戰意義。

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

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

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

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

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

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

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

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

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

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

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

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