基于改進遺傳算法的多無人機航路規劃方法*

劉 超

（中國飛行試驗研究院飛行仿真航空科技重點實驗室，西安 710089）

0 引言

單無人機在偵查目標數量較多情況下不能很好地完成偵察任務［1］，因此，實戰中常需采用多無人機協同行動對某個區域進行完整偵察［2］。

多無人偵察機協同的航路規劃問題與單架無人機規劃相比所要面臨的問題有很多不同之處，資源優化分配及協調是其中兩個需要解決的關鍵問題。偵察無人機可以看作是一種“資源”，需要讓多架無人機進行空間和時間上的合理分配來實現資源配置的最優化［3］。

為更好解決多無人機航路規劃問題，本文建立了多機協同偵察任務/航路規劃數學模型，并將其轉化為MTSP問題來求解偵察任務分配及排序問題，并提出改進的遺傳算法以獲得更好的規劃結果。

1 問題分析

1.1 多無人機偵察任務需求

應用場景為單基地情況下的多無人機協同偵察任務/航路規劃，該問題的詳細描述為：在滿足相關約束條件的前提下，采用多架無人機對于不同位置的多個目標進行偵察，相關約束有：

1）從基地出發并完成各自分配的偵察任務后，無人機都應返回基地；

2）須滿足關于傳感器類型和成像質量的要求［4］；

3）每個偵察目標不能重復進行偵察；

4）滿足無人機自身約束，諸如性能約束和時間約束條件等。

以上4項約束條件為前提，最后的優化結果要實現：

a.偵察目標數量最大化；b.執行任務的總代價最小。

1.2 偵察航路規劃問題分析

為了使模型能夠反映問題的特點，應對各具體要素進行分析。

1）偵察圖像的質量評價

2）在滿足任務要求同時，盡可能減少執行任務無人機的數量

對于任務規劃人員而言，總是期望高效地完成偵察任務，以此來達到資源和效益的最大化。目前已有的很多模型并沒有考慮到這一問題。

3）多目標優化問題分析

一般情況下，在進行協同偵察任務規劃時，期望的結果是“最優”的結果，即盡可能多的偵察目標、無人機飛行航跡總和盡可能短，安全程度盡可能大等等。

1.3 目標的分配和排序

多無人偵察機進行任務分配則可以看成是對多名旅行商進行規劃，等效于在滿足約束條件的情況下，讓多個旅行商遍歷所有的目的地。因此，可將多無人偵察機航路規劃問題轉化成MTSP問題求解。

2 多無人機航路規劃MTSP模型

作為較典型的組合優化問題［5-6］，MTSP是TSP問題的擴展。在該問題下，多偵察目標的任務分配和排序可以這樣描述：

給定數量為n的目標集合，有m架無人偵察機從目標n1出發分別訪問余下的n-1個目標。每一個目標只能有且僅有一架無人機執行偵察任務，并且所有無人機的總航程越小越好。

定義變量：

目標函數為：

其中：

式（2）中，cij為無人機從目標i到達目標j的直線距離。約束條件為：

式（1）表達使m架無人機的總航行距離最短；式（2）表達每一架無人機的航行距離大小；式（3）表達所有無人機從指定地點起飛，每個目標僅需訪問一次。

3 遺傳算法求解多無人機MTSP

3.1 編碼方式

采用符號編碼方式，利用1、2以及n分別代表目標1、目標2以及目標n，利用0來表示起點和終點。

對所有目標進行標記，其列表集合為W；給每個目標分配一個1…n之間的序號，該序號存在于集合W中。如兩架無人偵察機，有9個目標點，其編碼為：

圖1 符號編碼及解碼

解碼為第1架無人機飛行路線為從起點經過目標 1、2、3、4、5 后返回起點，第 2 架無人機飛行路線為從起點經過目標6、7、8、9后返回起點。

3.2 適應度函數

用L表示生成的各條航跡長度之和，用M表示航跡中最長的航跡與最短的航跡長度之差。種群進化既要使得飛行的總長度較小，又要使得各條航跡的長度相似，即L和M都要越小越好。所以適應度函數為：

式（4）中，L為全部航跡長度之和；M為最長的航跡與最短的航跡長度之差的絕對值；a為L的權值；b為M的權值。F的值越小，個體適應度就越好。

3.3 選擇操作

在對每個個體依照其適應度的大小進行評價的基礎上采用輪盤賭的方式進行選擇操作，其目的在于提高遺傳算法的收斂性和計算效率，表達式為：

3.4 交叉操作

采用置換交叉方式［7］，在兩個父體上隨機選取個數相同基因序列進行交換，其余位置與交換位置比較，如果有基因相同，則按照距離的大小依次替換為不同的基因，確保目標不被重復訪問或遺漏。如圖2所示，兩個父代個體基因為：

隨機選取交換位置為從位置5到位置8，經過交換后，兩個個體分別為：

圖3 交叉操作后基因位示意

其余位置上的基因依次與交換后的基因比較，S1n中基因5、7、9均重復，根據基因5的前一位基因1，計算基因2、6、3中與基因1距離最小的基因代替原有基因，如基因段16的長度比基因段12和13都小，則用6代替原來的5，以此類推，完成所有基因的替換。則交叉操作后的子代基因可能為：

圖4 距離最小的基因位代替示意

如果在交叉操作中，出現兩個個體的位置段內，一個含有起點0而另一個不含有，則不含0的基因段少交換一位，含有0的基因段0的位置不變，比如原有基因為：

圖5 交叉操作前0基因位置意圖

交換位置為3到6。由于S1中基因段不含0，則少交換一位，只交換5、8、2三個位置的基因，S2中0的位置不變，則交叉操作后的子代基因可能為：

圖6 交叉操作后0基因位置意圖

交叉操作是一種保持進化種群保留優良遺傳基因的有效方法。

3.5 變異操作

變異操作指的是一條染色體上的兩個基因以一定的概率進行交換并產生新的個體。圖7是變異操作前染色個體基因示意圖。

圖7 變異操作前基因位置示意

圖8 變異操作后基因位置示意

圖8是位置5的基因位與位置10的基因位隨機交換后的新染色個體。變異操作保持種群多樣性的有效方法。

4 遺傳算法的改進

采用一種改進的稱為三交換［7］啟發交叉方法，其改進主要有兩點：

1）將傳統兩條染色體參與交叉操作改為3條；

2）交叉和變異概率不再固定，以降低染色體近親繁殖的概率，以控制進化過程［8-9］。

4.1 三交換啟發交叉方法的基本思想

通過3條染色體進行交叉操作來產生后代，以圖9列出的8個目標為例來說明這一過程，其中cij由表1給出，設3條父代染色體為：

圖9 三染色體交叉操作示意SUM1=42，SUM2=40，SUM3=46

SUM1，SUM2，SUM3分別為這 3 種方案需要飛行的距離，隨機選出初始目標j=1，Sj=3右轉動，使3成為3父代的第1位置。

圖10 父代的第1位置示意

由于 c（3，2）＞c（3，5），所以有：

圖11 父代位置重排示意

由此規則計算可得：SUM0=24

圖12 三染色體交叉優化示意

SUM0為3個父代所產生子代的距離或懲罰費用總和，顯然 SUM0遠遠小于 SUM1，SUM2和 SUM3。

表1 8個目標間的距離

4.2 交叉概率變參方法

設K=1，則Pc的表達式為：

式中，f′=（SUM1+SUM2+SUM3）/3為當前交叉的 3條父代染色體的平均值；ffit為當前代中最短的路程值；f為當前代的平均值；SUM1，SUM2，SUM3分別為未交叉的3個父代的總航程或懲罰費用。

若某子代當中的所有個體的適應度值很接近，說明結果可能陷入了局部最優，這時須增大Pc來擺脫這種情況。

若當前一代的最優值和其3個父代的平均值之差較大時，說明父代可通過交叉來產生更好的個體。

4.3 變異概率的變參方法

變異概率Pm的變參形式表達如下：

fbest為當前代中最佳值；f為當前代的平均值；f′當要進行變異的父代。

隨著f′的變化而設置不同的變異概率是為了防止算法陷入局部最優。當fbest與f很接近時，某代中所有的值可能陷入了局部最優解，所以通過讓Pm較大的方法來擺脫可能產生的局部最優解。當fbest與f′相差很遠時，說明f′離最優值還相差很大，所以要增大變異概率。

5 仿真驗證

5.1 多偵察目標分配和排序仿真驗證

兩架無人偵察機的起點和終點均相同，飛行高度為12 km，飛行速度保持不變，速度為250 m/s，飛行最大距離為70 km，傳感器的成像時間為6 s，最大焦距f=1.75 m。任務規劃的環境區域是一個25 km×25 km的正方形區域，地形平坦。區域中共有20個待偵察目標，目標均視為點目標。目標參數如表2所示。

表2 待偵察目標參數表坐標單位：km

所有目標分配及偵察順序結果如下頁圖13所示。

第1架無人機的飛行順序為：起點－目標20－目標6－目標17－目標4－目標13－目標7－目標11－目標1－終點。

圖13 仿真結果示意圖

第2架無人機的飛行順序為：起點－目標2－目標16－目標9－目標19－目標14－目標8－目標15－終點。

目標偵察完成情況及拍攝圖像質量如表3所示。

表3 目標偵察情況表

5.2 仿真分析

從表3可看到，偵察環境中一共存在20個待偵察目標，按照預先任務分配和規劃的航路，兩架無人機共偵察到15個目標，這15個目標點的偵察質量均達到要求。數量偵察效率為75%，飛行總距離為105 969.9 m。雖然飛行總距離偏大，但每一架無人機的飛行距離減小了，其中，第2架無人機的飛行距離為55 845.3 m，遠遠小于低于飛行最大距離限制。

根據圖和表的內容可以看出，在多任務復雜環境下，所提方法可以保證多無人機能夠按照規劃的航跡從起點出發，在偵察了多個目標后返回終點，取得很好的偵察效果。

6 結論

在分析了多無人機執行偵察任務時的要求、限制等要素基礎上，建立了多無人機航路規劃優化模型，并采用求解MTSP問題的方法求解該優化問題，同時通過改進遺傳算法的交叉及變異操作算子更進一步完善最終航路的尋優過程，仿真結果表明，該算法在目標分布復雜多變的環境下，可以得到實際偵察需求的分配方案和航路。