基于改進(jìn)遺傳算法的多無人機航路規(guī)劃方法*

劉 超

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

0 引言

單無人機在偵查目標(biāo)數(shù)量較多情況下不能很好地完成偵察任務(wù)［1］，因此，實戰(zhàn)中常需采用多無人機協(xié)同行動對某個區(qū)域進(jìn)行完整偵察［2］。

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

為更好解決多無人機航路規(guī)劃問題，本文建立了多機協(xié)同偵察任務(wù)/航路規(guī)劃數(shù)學(xué)模型，并將其轉(zhuǎn)化為MTSP問題來求解偵察任務(wù)分配及排序問題，并提出改進(jìn)的遺傳算法以獲得更好的規(guī)劃結(jié)果。

1 問題分析

1.1 多無人機偵察任務(wù)需求

應(yīng)用場景為單基地情況下的多無人機協(xié)同偵察任務(wù)/航路規(guī)劃，該問題的詳細(xì)描述為：在滿足相關(guān)約束條件的前提下，采用多架無人機對于不同位置的多個目標(biāo)進(jìn)行偵察，相關(guān)約束有：

1）從基地出發(fā)并完成各自分配的偵察任務(wù)后，無人機都應(yīng)返回基地；

2）須滿足關(guān)于傳感器類型和成像質(zhì)量的要求［4］；

3）每個偵察目標(biāo)不能重復(fù)進(jìn)行偵察；

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

以上4項約束條件為前提，最后的優(yōu)化結(jié)果要實現(xiàn)：

a.偵察目標(biāo)數(shù)量最大化；b.執(zhí)行任務(wù)的總代價最小。

1.2 偵察航路規(guī)劃問題分析

為了使模型能夠反映問題的特點，應(yīng)對各具體要素進(jìn)行分析。

1）偵察圖像的質(zhì)量評價

2）在滿足任務(wù)要求同時，盡可能減少執(zhí)行任務(wù)無人機的數(shù)量

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

3）多目標(biāo)優(yōu)化問題分析

一般情況下，在進(jìn)行協(xié)同偵察任務(wù)規(guī)劃時，期望的結(jié)果是“最優(yōu)”的結(jié)果，即盡可能多的偵察目標(biāo)、無人機飛行航跡總和盡可能短，安全程度盡可能大等等。

1.3 目標(biāo)的分配和排序

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

2 多無人機航路規(guī)劃MTSP模型

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

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

定義變量：

目標(biāo)函數(shù)為：

其中：

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

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

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

3.1 編碼方式

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

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

圖1 符號編碼及解碼

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

3.2 適應(yīng)度函數(shù)

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

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

3.3 選擇操作

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

3.4 交叉操作

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

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

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

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

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

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

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

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

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

交叉操作是一種保持進(jìn)化種群保留優(yōu)良遺傳基因的有效方法。

3.5 變異操作

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

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

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

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

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

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

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

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

4.1 三交換啟發(fā)交叉方法的基本思想

通過3條染色體進(jìn)行交叉操作來產(chǎn)生后代，以圖9列出的8個目標(biāo)為例來說明這一過程，其中cij由表1給出，設(shè)3條父代染色體為：

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

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

圖10 父代的第1位置示意

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

圖11 父代位置重排示意

由此規(guī)則計算可得：SUM0=24

圖12 三染色體交叉優(yōu)化示意

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

表1 8個目標(biāo)間的距離

4.2 交叉概率變參方法

設(shè)K=1，則Pc的表達(dá)式為：

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

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

若當(dāng)前一代的最優(yōu)值和其3個父代的平均值之差較大時，說明父代可通過交叉來產(chǎn)生更好的個體。

4.3 變異概率的變參方法

變異概率Pm的變參形式表達(dá)如下：

fbest為當(dāng)前代中最佳值；f為當(dāng)前代的平均值；f′當(dāng)要進(jìn)行變異的父代。

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

5 仿真驗證

5.1 多偵察目標(biāo)分配和排序仿真驗證

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

表2 待偵察目標(biāo)參數(shù)表坐標(biāo)單位：km

所有目標(biāo)分配及偵察順序結(jié)果如下頁圖13所示。

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

圖13 仿真結(jié)果示意圖

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

目標(biāo)偵察完成情況及拍攝圖像質(zhì)量如表3所示。

表3 目標(biāo)偵察情況表

5.2 仿真分析

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

根據(jù)圖和表的內(nèi)容可以看出，在多任務(wù)復(fù)雜環(huán)境下，所提方法可以保證多無人機能夠按照規(guī)劃的航跡從起點出發(fā)，在偵察了多個目標(biāo)后返回終點，取得很好的偵察效果。

6 結(jié)論

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