李文廣，李建增，胡永江，李永科，趙月飛

（陸軍工程大學(xué)石家莊校區(qū)，石家莊 050003）

0 引言

現(xiàn)階段，根據(jù)無(wú)人機(jī)偵察對(duì)象的不同，多無(wú)人機(jī)協(xié)同偵察問(wèn)題可分為“點(diǎn)對(duì)點(diǎn)”協(xié)同偵察［2］和“點(diǎn)對(duì)面”協(xié)同偵察兩個(gè)方面［3］。

“點(diǎn)對(duì)點(diǎn)”協(xié)同偵察即偵察對(duì)象為點(diǎn)目標(biāo)群，要求無(wú)人機(jī)以最小的時(shí)間代價(jià)完成偵察任務(wù)。如文獻(xiàn)［4］將多無(wú)人機(jī)偵察點(diǎn)目標(biāo)群的航跡規(guī)劃問(wèn)題先轉(zhuǎn)化為多旅行商問(wèn)題，然后利用遺傳算法求解得到各任務(wù)航跡。但該算法僅限于點(diǎn)目標(biāo)群規(guī)模較小的情況。為解決大規(guī)模點(diǎn)目標(biāo)群的偵察問(wèn)題，文獻(xiàn)［5］首先對(duì)點(diǎn)目標(biāo)群使用K-means 聚類(lèi)算法，將多旅行商問(wèn)題分解為單旅行商問(wèn)題，然后利用優(yōu)化后的遺傳算法對(duì)問(wèn)題進(jìn)行求解。

“點(diǎn)對(duì)面”協(xié)同偵察即偵察對(duì)象為廣域面目標(biāo)，需要無(wú)人機(jī)能夠?qū)υ撊蝿?wù)區(qū)域進(jìn)行全覆蓋偵察，常用的覆蓋方式有掃描線法［6-7］、柵格法［8］等。如文獻(xiàn)［9］在保證區(qū)域全覆蓋和滿足無(wú)人機(jī)動(dòng)力學(xué)約束的前提下，對(duì)無(wú)人機(jī)編隊(duì)的轉(zhuǎn)彎時(shí)機(jī)和轉(zhuǎn)彎位置進(jìn)行調(diào)整，完成了區(qū)域覆蓋搜索任務(wù)。文獻(xiàn)［10-11］根據(jù)無(wú)人機(jī)的性能，將任務(wù)區(qū)域分解為多個(gè)子任務(wù)區(qū)域，然后將子任務(wù)區(qū)域分配給各個(gè)無(wú)人機(jī)，由各個(gè)無(wú)人機(jī)使用掃描線法進(jìn)行區(qū)域覆蓋搜索，最終實(shí)現(xiàn)以最少的轉(zhuǎn)彎次數(shù)完成偵察任務(wù)。

對(duì)于上述兩種目標(biāo)類(lèi)型的航跡規(guī)劃問(wèn)題已有了較為成熟的研究成果，但是以鐵路、公路等線目標(biāo)為偵察對(duì)象的多無(wú)人機(jī)航跡規(guī)劃問(wèn)題，相關(guān)文獻(xiàn)較少。針對(duì)偵察線目標(biāo)的多無(wú)人機(jī)協(xié)同航跡規(guī)劃問(wèn)題，結(jié)合目標(biāo)屬性及最小時(shí)間代價(jià)要求，提出了一種基于集中一體化遺傳算法的協(xié)同航跡規(guī)劃方法。通過(guò)建立基于時(shí)間代價(jià)的航跡模型和采用集中一體化式遺傳算法對(duì)模型進(jìn)行求解，可得到具有最小時(shí)間代價(jià)的任務(wù)航跡。

1 基于時(shí)間代價(jià)的航跡模型

問(wèn)題描述：利用m 架無(wú)人機(jī)對(duì)任務(wù)區(qū)域內(nèi)的N條河流和道路進(jìn)行偵察，每個(gè)目標(biāo)均能被偵察到，且不能重復(fù)偵察并要求整體任務(wù)時(shí)間代價(jià)最小。

設(shè)L={L1，L2，…，LN}為待被偵察的線目標(biāo)集合，V={V1，V2，…，Vm}為各無(wú)人機(jī)對(duì)應(yīng)的巡航速度集合。第i 架無(wú)人機(jī)的位置為（xi，yi），其偵察的線目標(biāo)數(shù)量為ni，且第j 個(gè)線目標(biāo)的端點(diǎn)坐標(biāo)（xj1，yj1）、（xj2，yj2），滿足1≤i≤m，1≤j≤N。則第i 架無(wú)人機(jī)的航跡時(shí)間代價(jià)可表示為：

其中，li1表示無(wú)人機(jī)從起飛點(diǎn)飛向所分配到的第一

個(gè)線目標(biāo)進(jìn)入點(diǎn)的路徑長(zhǎng)度，li2表示各線目標(biāo)之間

的路徑長(zhǎng)度，即從上一線目標(biāo)飛出點(diǎn)到下一線目標(biāo)進(jìn)入點(diǎn)的路徑長(zhǎng)度，li3表示偵察各線目標(biāo)時(shí)，在其上空飛過(guò)的路徑長(zhǎng)度，一般與線目標(biāo)長(zhǎng)度近似相等，li4表示從最后一個(gè)線目標(biāo)飛出點(diǎn)返回?zé)o人機(jī)起飛點(diǎn)的路徑長(zhǎng)度。d（a，b）表示點(diǎn)a 和點(diǎn)b 之間的幾何距離，dj表示第j 個(gè)線目標(biāo)的長(zhǎng)度。

則各個(gè)無(wú)人機(jī)偵察航跡的時(shí)間代價(jià)可以用T=（t1，t2，…，tm）表示。

基于時(shí)間代價(jià)的航跡模型其目標(biāo)函數(shù)即為：

表示此次偵察任務(wù)的整體時(shí)間代價(jià)由花費(fèi)時(shí)間最長(zhǎng)的無(wú)人機(jī)所決定。

航跡模型的約束條件則為：

其表示所有線目標(biāo)均被偵察，且無(wú)重復(fù)偵察。

2 集中一體化遺傳算法

對(duì)于多無(wú)人機(jī)協(xié)同航跡規(guī)劃問(wèn)題的求解方法主要有分層解耦法和集中一體化法。后者是將初始生成的航跡長(zhǎng)度當(dāng)作任務(wù)分配代價(jià)函數(shù)的一個(gè)自變量，在任務(wù)分配的同時(shí)得到偵察航跡，通過(guò)不斷迭代，來(lái)尋找最優(yōu)解［12］。而分層解耦法則無(wú)法得到最優(yōu)解或次優(yōu)解。

針對(duì)偵察線目標(biāo)的多無(wú)人機(jī)協(xié)同航跡規(guī)劃問(wèn)題，引入集中一體化方法并結(jié)合改進(jìn)的遺傳算法進(jìn)行求解。但遺傳算法存在收斂性較差且易陷入局部最優(yōu)的問(wèn)題［13］。所以在標(biāo)準(zhǔn)遺傳算法的編碼、染色體交叉和變異環(huán)節(jié)進(jìn)行了合理優(yōu)化，來(lái)彌補(bǔ)標(biāo)準(zhǔn)遺傳算法的易早熟和收斂性差等缺點(diǎn)。

2.1 染色體編碼

采用集中一體化求解的思想，即可在染色體編碼階段，使得每條染色體上所有基因可對(duì)應(yīng)表示線目標(biāo)的分配結(jié)果，以及各無(wú)人機(jī)的偵察序列等信息。染色體編碼按以下步驟進(jìn)行。

步驟1：產(chǎn)生一個(gè)行數(shù)為3，列數(shù)為N 的空矩陣E；

步驟2：第1 行的矩陣元素由區(qū)間［1，m］中的m個(gè)整數(shù)隨機(jī)填入；

步驟3：第2 行的矩陣元素由區(qū)間［1，N］中的N個(gè)整數(shù)隨機(jī)填入，要求整數(shù)無(wú)重復(fù)；

步驟4：第3 行的矩陣元素由整數(shù)1 或2 隨機(jī)填入，最終形成矩陣E'。

以上是多類(lèi)型基因編碼方式，染色體的基因數(shù)由線目標(biāo)數(shù)量所確定，每個(gè)染色體包含多個(gè)基因，每個(gè)基因由無(wú)人機(jī)編號(hào)、線目標(biāo)編號(hào)和進(jìn)入點(diǎn)編號(hào)構(gòu)成。圖1 即染色體編碼的示意圖。

圖1 染色體編碼示意圖

其表示4 架無(wú)人機(jī)偵察6 個(gè)線目標(biāo)，其中無(wú)人機(jī)1 的偵察序列為從起飛點(diǎn)起飛，然后從線目標(biāo)3的右側(cè)端點(diǎn)進(jìn)入，再?gòu)木€目標(biāo)5 的左側(cè)端點(diǎn)進(jìn)入，最后返回起飛點(diǎn)，以此類(lèi)推。

相關(guān)說(shuō)明：定義無(wú)人機(jī)偵察線目標(biāo)時(shí)，均從線目標(biāo)的1 個(gè)端點(diǎn)進(jìn)入，另1 個(gè)端點(diǎn)飛出；1 表示從線目標(biāo)左側(cè)端點(diǎn)進(jìn)入，2 則表示從右側(cè)端點(diǎn)進(jìn)入。

2.2 適應(yīng)度求解與優(yōu)選

染色體的選擇采用經(jīng)典的輪盤(pán)賭法來(lái)對(duì)種群中的染色體進(jìn)行優(yōu)選，形成父代染色體種群，且染色體適應(yīng)度越小，被優(yōu)選的概率越大。

第s 條染色體對(duì)應(yīng)的適應(yīng)度為：

式中，Ts表示第s 條染色體其對(duì)應(yīng)偵察序列下的各無(wú)人機(jī)時(shí)間代價(jià)的集合。

則整個(gè)種群最佳的適應(yīng)度為：

式中，k 為遺傳代數(shù)，k=1，2，…，r，fks表示第k 代中第s 條染色體對(duì)應(yīng)的適應(yīng)度。

2.3 染色體交叉

通過(guò)對(duì)兩個(gè)染色體進(jìn)行交叉操作，使得被選擇的兩個(gè)染色體之間交叉互換若干部分基因，達(dá)到遺傳繁衍產(chǎn)生子代的作用。集中一體化式遺傳算法對(duì)染色體進(jìn)行交叉操作后，能夠進(jìn)一步使得種群向適應(yīng)度值更優(yōu)的方向進(jìn)行迭代，也可以提高算法收斂速度。

首先，對(duì)父代染色體種群進(jìn)行適應(yīng)度求解及優(yōu)選，選取父染色體A 和B。然后，隨機(jī)產(chǎn)生兩個(gè)不相等整數(shù)p 和q（p、q∈［1，N］），將父染色體A 中的第p 和q 個(gè)基因與B 中的第p 和q 個(gè)基因?qū)?yīng)相互交換。為了保證每個(gè)目標(biāo)都被偵察到且最多被偵察到一次，還需進(jìn)行目標(biāo)編號(hào)沖突檢測(cè)。完成沖突檢測(cè)后，再分別將染色體A'和B'中第p-q 之間的基因片段反轉(zhuǎn)，即得到交叉操作后的子染色體C 和D。

相關(guān)說(shuō)明：由于每個(gè)線目標(biāo)要求至多被偵察一次，所以要對(duì)線目標(biāo)的編號(hào)進(jìn)行沖突檢測(cè)。

2.4 染色體變異

為了防止種群陷入局部最優(yōu)，還需對(duì)子染色體進(jìn)行變異操作。針對(duì)染色體編碼的特點(diǎn)，設(shè)計(jì)了3種變異方式：即無(wú)人機(jī)編號(hào)變異、目標(biāo)編號(hào)變異、進(jìn)入點(diǎn)編號(hào)變異。

圖2 染色體交叉操作示意圖

1）無(wú)人機(jī)編號(hào)變異

隨機(jī)產(chǎn)生變異基因，將其對(duì)應(yīng)的無(wú)人機(jī)編號(hào)隨機(jī)突變?yōu)槠渌麩o(wú)人機(jī)編號(hào)。如圖3 所示，無(wú)人機(jī)變異基因?yàn)?，對(duì)應(yīng)的無(wú)人機(jī)編號(hào)為3，將其突變?yōu)榫幪?hào)為1 的無(wú)人機(jī)。

圖3 無(wú)人機(jī)編號(hào)變異示意圖

2）目標(biāo)編號(hào)變異

隨機(jī)產(chǎn)生變異基因，將其對(duì)應(yīng)的目標(biāo)編號(hào)隨機(jī)突變?yōu)槠渌哪繕?biāo)編號(hào)，同時(shí)檢測(cè)目標(biāo)編號(hào)沖突。如圖4 所示，無(wú)人機(jī)變異基因?yàn)?，對(duì)應(yīng)的目標(biāo)編號(hào)為5，將其突變?yōu)榫幪?hào)為4 的目標(biāo)，此時(shí)，該基因的目標(biāo)編號(hào)與基因6 的目標(biāo)編號(hào)沖突，將基因6 的目標(biāo)編號(hào)4 修改為基因4 變異前的目標(biāo)編號(hào)5。

圖4 目標(biāo)編號(hào)變異示意圖

3）進(jìn)入點(diǎn)編號(hào)變異

隨機(jī)產(chǎn)生變異基因位，將其對(duì)應(yīng)的進(jìn)入點(diǎn)編號(hào)隨機(jī)突變?yōu)榱硪粋€(gè)進(jìn)入點(diǎn)編號(hào)。如圖5 所示，進(jìn)入點(diǎn)變異基因?yàn)?，對(duì)應(yīng)的進(jìn)入點(diǎn)編號(hào)為1，將其突變?yōu)榱硪粋€(gè)進(jìn)入點(diǎn)2。

圖5 進(jìn)入點(diǎn)編號(hào)變異示意圖

2.5 算法收斂性

標(biāo)準(zhǔn)遺傳算法是在經(jīng)過(guò)交叉、變異兩個(gè)環(huán)節(jié)之后才會(huì)進(jìn)行適應(yīng)度的求解和優(yōu)選，但染色體在經(jīng)過(guò)交叉操作后有可能已經(jīng)是最優(yōu)解了，這將導(dǎo)致算法收斂速度變慢，也可能陷入局部最優(yōu)解。

集中一體化遺傳算法對(duì)染色體交叉、變異操作進(jìn)行了優(yōu)化，同時(shí)要求經(jīng)過(guò)每次染色體交叉或變異操作后，都要對(duì)前后每個(gè)染色體的適應(yīng)度進(jìn)行計(jì)算并優(yōu)選，以有效保證每次迭代后，算法可有效收斂并得到最優(yōu)解。

3 仿真驗(yàn)證

仿真平臺(tái)為Inter（R）Core（TM）i5-5200UCPU，4 GB 內(nèi)存，64 位Win7 操作系統(tǒng)的戴爾筆記本。編程工具為Matlab-R2016a（64 位）。

為了驗(yàn)證本文方法的有效性，采用以下驗(yàn)證方案：現(xiàn)有3 架無(wú)人機(jī)，無(wú)人機(jī)的巡航速度均為10 m/s，各無(wú)人機(jī)起飛點(diǎn)坐標(biāo)分別為（0，0）、（100，0）和（80，80），任務(wù)要求對(duì)8 個(gè)線目標(biāo)進(jìn)行快速協(xié)同偵察。線目標(biāo)端點(diǎn)坐標(biāo)參數(shù)如表1 所示，各無(wú)人機(jī)和線目標(biāo)的位置關(guān)系如圖6 所示。

表1 待偵察的線目標(biāo)坐標(biāo)

圖6 無(wú)人機(jī)和目標(biāo)位置示意圖

經(jīng)過(guò)對(duì)3 架無(wú)人機(jī)偵察航跡的求解，算法最終迭代的輸出結(jié)果如圖7 所示。

圖7 最佳染色體

現(xiàn)將實(shí)驗(yàn)結(jié)果分析如下：

1）根據(jù)最終迭代輸出的染色體，對(duì)應(yīng)編碼規(guī)則可解譯得到各無(wú)人機(jī)的偵察序列及各個(gè)線目標(biāo)的進(jìn)入點(diǎn)編號(hào)，如表2 所示。

表2 各無(wú)人機(jī)偵察序列及時(shí)間代價(jià)（min）

2）該方法可有效求解得到各無(wú)人機(jī)的任務(wù)航跡，各偵察航跡的時(shí)間代價(jià)分別為3.295 min、2.747 min和2.945 min，且航跡之間無(wú)交叉、無(wú)沖突，如圖8所示。

圖8 航跡規(guī)劃結(jié)果

3）集中一體化式遺傳算法在第101 代已達(dá)到收斂，而標(biāo)準(zhǔn)遺傳算法在第613 代才收斂，且前者達(dá)到收斂的時(shí)間優(yōu)于標(biāo)準(zhǔn)遺傳算法達(dá)到收斂的時(shí)間。即集中一體化式遺傳算法與標(biāo)準(zhǔn)遺傳算法相比，不僅收斂速度快，算法求解效率也更高。

圖9 收斂性分析

4 結(jié)論

本文針對(duì)偵察線目標(biāo)的多無(wú)人機(jī)協(xié)同航跡規(guī)劃問(wèn)題進(jìn)行了研究，并提出了相應(yīng)的航跡規(guī)劃方法。

1）該方法適用于多無(wú)人機(jī)協(xié)同偵察鐵路、河流等線目標(biāo)，可求解得到各無(wú)人機(jī)的偵察序列及航跡。

2）對(duì)染色體交叉、變異操作的改進(jìn)，有效彌補(bǔ)了標(biāo)準(zhǔn)遺傳算法的易早熟和收斂性差等缺點(diǎn)，為其他啟發(fā)性算法的優(yōu)化提供了思路。

3）集中一體化式遺傳算法在求解效率及算法收斂性上，均具有一定的優(yōu)越性。

4）下一步可在多無(wú)人機(jī)協(xié)同偵察航跡規(guī)劃問(wèn)題中引入更加復(fù)雜的任務(wù)背景和任務(wù)要求，來(lái)提高算法的實(shí)用性。