基于集中一體化遺傳算法的協(xié)同航跡規(guī)劃方法*

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

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

0 引言

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

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

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

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

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

問題描述：利用m 架無人機(jī)對任務(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}為各無人機(jī)對應(yīng)的巡航速度集合。第i 架無人機(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 架無人機(jī)的航跡時(shí)間代價(jià)可表示為：

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

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

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

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

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

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

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

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

2 集中一體化遺傳算法

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

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

2.1 染色體編碼

采用集中一體化求解的思想，即可在染色體編碼階段，使得每條染色體上所有基因可對應(yīng)表示線目標(biāo)的分配結(jié)果，以及各無人機(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ù)無重復(fù)；

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

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

圖1 染色體編碼示意圖

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

相關(guān)說明：定義無人機(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)典的輪盤賭法來對種群中的染色體進(jìn)行優(yōu)選，形成父代染色體種群，且染色體適應(yīng)度越小，被優(yōu)選的概率越大。

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

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

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

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

2.3 染色體交叉

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

首先，對父代染色體種群進(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)編號沖突檢測。完成沖突檢測后，再分別將染色體A'和B'中第p-q 之間的基因片段反轉(zhuǎn)，即得到交叉操作后的子染色體C 和D。

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

2.4 染色體變異

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

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

1）無人機(jī)編號變異

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

圖3 無人機(jī)編號變異示意圖

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

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

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

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

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

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

2.5 算法收斂性

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

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

3 仿真驗(yàn)證

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

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

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

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

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

圖7 最佳染色體

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

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

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

2）該方法可有效求解得到各無人機(jī)的任務(wù)航跡，各偵察航跡的時(shí)間代價(jià)分別為3.295 min、2.747 min和2.945 min，且航跡之間無交叉、無沖突，如圖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é)論

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

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

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

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

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