基于集中一體化遺傳算法的協同航跡規劃方法*

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

（陸軍工程大學石家莊校區，石家莊 050003）

0 引言

現階段，根據無人機偵察對象的不同，多無人機協同偵察問題可分為“點對點”協同偵察［2］和“點對面”協同偵察兩個方面［3］。

“點對點”協同偵察即偵察對象為點目標群，要求無人機以最小的時間代價完成偵察任務。如文獻［4］將多無人機偵察點目標群的航跡規劃問題先轉化為多旅行商問題，然后利用遺傳算法求解得到各任務航跡。但該算法僅限于點目標群規模較小的情況。為解決大規模點目標群的偵察問題，文獻［5］首先對點目標群使用K-means 聚類算法，將多旅行商問題分解為單旅行商問題，然后利用優化后的遺傳算法對問題進行求解。

“點對面”協同偵察即偵察對象為廣域面目標，需要無人機能夠對該任務區域進行全覆蓋偵察，常用的覆蓋方式有掃描線法［6-7］、柵格法［8］等。如文獻［9］在保證區域全覆蓋和滿足無人機動力學約束的前提下，對無人機編隊的轉彎時機和轉彎位置進行調整，完成了區域覆蓋搜索任務。文獻［10-11］根據無人機的性能，將任務區域分解為多個子任務區域，然后將子任務區域分配給各個無人機，由各個無人機使用掃描線法進行區域覆蓋搜索，最終實現以最少的轉彎次數完成偵察任務。

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

1 基于時間代價的航跡模型

問題描述：利用m 架無人機對任務區域內的N條河流和道路進行偵察，每個目標均能被偵察到，且不能重復偵察并要求整體任務時間代價最小。

設L={L1，L2，…，LN}為待被偵察的線目標集合，V={V1，V2，…，Vm}為各無人機對應的巡航速度集合。第i 架無人機的位置為（xi，yi），其偵察的線目標數量為ni，且第j 個線目標的端點坐標（xj1，yj1）、（xj2，yj2），滿足1≤i≤m，1≤j≤N。則第i 架無人機的航跡時間代價可表示為：

其中，li1表示無人機從起飛點飛向所分配到的第一

個線目標進入點的路徑長度，li2表示各線目標之間

的路徑長度，即從上一線目標飛出點到下一線目標進入點的路徑長度，li3表示偵察各線目標時，在其上空飛過的路徑長度，一般與線目標長度近似相等，li4表示從最后一個線目標飛出點返回無人機起飛點的路徑長度。d（a，b）表示點a 和點b 之間的幾何距離，dj表示第j 個線目標的長度。

則各個無人機偵察航跡的時間代價可以用T=（t1，t2，…，tm）表示。

基于時間代價的航跡模型其目標函數即為：

表示此次偵察任務的整體時間代價由花費時間最長的無人機所決定。

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

其表示所有線目標均被偵察，且無重復偵察。

2 集中一體化遺傳算法

對于多無人機協同航跡規劃問題的求解方法主要有分層解耦法和集中一體化法。后者是將初始生成的航跡長度當作任務分配代價函數的一個自變量，在任務分配的同時得到偵察航跡，通過不斷迭代，來尋找最優解［12］。而分層解耦法則無法得到最優解或次優解。

針對偵察線目標的多無人機協同航跡規劃問題，引入集中一體化方法并結合改進的遺傳算法進行求解。但遺傳算法存在收斂性較差且易陷入局部最優的問題［13］。所以在標準遺傳算法的編碼、染色體交叉和變異環節進行了合理優化，來彌補標準遺傳算法的易早熟和收斂性差等缺點。

2.1 染色體編碼

采用集中一體化求解的思想，即可在染色體編碼階段，使得每條染色體上所有基因可對應表示線目標的分配結果，以及各無人機的偵察序列等信息。染色體編碼按以下步驟進行。

步驟1：產生一個行數為3，列數為N 的空矩陣E；

步驟2：第1 行的矩陣元素由區間［1，m］中的m個整數隨機填入；

步驟3：第2 行的矩陣元素由區間［1，N］中的N個整數隨機填入，要求整數無重復；

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

以上是多類型基因編碼方式，染色體的基因數由線目標數量所確定，每個染色體包含多個基因，每個基因由無人機編號、線目標編號和進入點編號構成。圖1 即染色體編碼的示意圖。

圖1 染色體編碼示意圖

其表示4 架無人機偵察6 個線目標，其中無人機1 的偵察序列為從起飛點起飛，然后從線目標3的右側端點進入，再從線目標5 的左側端點進入，最后返回起飛點，以此類推。

相關說明：定義無人機偵察線目標時，均從線目標的1 個端點進入，另1 個端點飛出；1 表示從線目標左側端點進入，2 則表示從右側端點進入。

2.2 適應度求解與優選

染色體的選擇采用經典的輪盤賭法來對種群中的染色體進行優選，形成父代染色體種群，且染色體適應度越小，被優選的概率越大。

第s 條染色體對應的適應度為：

式中，Ts表示第s 條染色體其對應偵察序列下的各無人機時間代價的集合。

則整個種群最佳的適應度為：

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

2.3 染色體交叉

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

首先，對父代染色體種群進行適應度求解及優選，選取父染色體A 和B。然后，隨機產生兩個不相等整數p 和q（p、q∈［1，N］），將父染色體A 中的第p 和q 個基因與B 中的第p 和q 個基因對應相互交換。為了保證每個目標都被偵察到且最多被偵察到一次，還需進行目標編號沖突檢測。完成沖突檢測后，再分別將染色體A'和B'中第p-q 之間的基因片段反轉，即得到交叉操作后的子染色體C 和D。

相關說明：由于每個線目標要求至多被偵察一次，所以要對線目標的編號進行沖突檢測。

2.4 染色體變異

為了防止種群陷入局部最優，還需對子染色體進行變異操作。針對染色體編碼的特點，設計了3種變異方式：即無人機編號變異、目標編號變異、進入點編號變異。

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

1）無人機編號變異

隨機產生變異基因，將其對應的無人機編號隨機突變為其他無人機編號。如圖3 所示，無人機變異基因為3，對應的無人機編號為3，將其突變為編號為1 的無人機。

圖3 無人機編號變異示意圖

2）目標編號變異

隨機產生變異基因，將其對應的目標編號隨機突變為其他的目標編號，同時檢測目標編號沖突。如圖4 所示，無人機變異基因為4，對應的目標編號為5，將其突變為編號為4 的目標，此時，該基因的目標編號與基因6 的目標編號沖突，將基因6 的目標編號4 修改為基因4 變異前的目標編號5。

圖4 目標編號變異示意圖

3）進入點編號變異

隨機產生變異基因位，將其對應的進入點編號隨機突變為另一個進入點編號。如圖5 所示，進入點變異基因為5，對應的進入點編號為1，將其突變為另一個進入點2。

圖5 進入點編號變異示意圖

2.5 算法收斂性

標準遺傳算法是在經過交叉、變異兩個環節之后才會進行適應度的求解和優選，但染色體在經過交叉操作后有可能已經是最優解了，這將導致算法收斂速度變慢，也可能陷入局部最優解。

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

3 仿真驗證

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

為了驗證本文方法的有效性，采用以下驗證方案：現有3 架無人機，無人機的巡航速度均為10 m/s，各無人機起飛點坐標分別為（0，0）、（100，0）和（80，80），任務要求對8 個線目標進行快速協同偵察。線目標端點坐標參數如表1 所示，各無人機和線目標的位置關系如圖6 所示。

表1 待偵察的線目標坐標

圖6 無人機和目標位置示意圖

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

圖7 最佳染色體

現將實驗結果分析如下：

1）根據最終迭代輸出的染色體，對應編碼規則可解譯得到各無人機的偵察序列及各個線目標的進入點編號，如表2 所示。

表2 各無人機偵察序列及時間代價（min）

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

圖8 航跡規劃結果

3）集中一體化式遺傳算法在第101 代已達到收斂，而標準遺傳算法在第613 代才收斂，且前者達到收斂的時間優于標準遺傳算法達到收斂的時間。即集中一體化式遺傳算法與標準遺傳算法相比，不僅收斂速度快，算法求解效率也更高。

圖9 收斂性分析

4 結論

本文針對偵察線目標的多無人機協同航跡規劃問題進行了研究，并提出了相應的航跡規劃方法。

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

2）對染色體交叉、變異操作的改進，有效彌補了標準遺傳算法的易早熟和收斂性差等缺點，為其他啟發性算法的優化提供了思路。

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

4）下一步可在多無人機協同偵察航跡規劃問題中引入更加復雜的任務背景和任務要求，來提高算法的實用性。