劉 超

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

0 引言

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

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

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

1 問題分析

1.1 多無人機偵察任務需求

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 目標的分配和排序

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

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

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

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

定義變量：

目標函數(shù)為：

其中：

式（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架無人機飛行路線為從起點經(jīng)過目標 1、2、3、4、5 后返回起點，第 2 架無人機飛行路線為從起點經(jīng)過目標6、7、8、9后返回起點。

3.2 適應度函數(shù)

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

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

3.3 選擇操作

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

3.4 交叉操作

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

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

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

其余位置上的基因依次與交換后的基因比較，S1n中基因5、7、9均重復，根據(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基因位置意圖

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

3.5 變異操作

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

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

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

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

4 遺傳算法的改進

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

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

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

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

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

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

SUM1，SUM2，SUM3分別為這 3 種方案需要飛行的距離，隨機選出初始目標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遠遠小于 SUM1，SUM2和 SUM3。

表1 8個目標間的距離

4.2 交叉概率變參方法

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

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

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

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

4.3 變異概率的變參方法

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

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

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

5 仿真驗證

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

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

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

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

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

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

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

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

表3 目標偵察情況表

5.2 仿真分析

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

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

6 結(jié)論

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