帥偉偉，汪 君，任開君，楊 健，林 潔

（1.解放軍95795 部隊，廣西 桂林 541003；2.中國電子科技集團第十五研究所，北京 100080）

0 引言

無人機能夠自主飛行，具備獨立執(zhí)行任務(wù)能力，是現(xiàn)代信息化戰(zhàn)爭中的一種新型作戰(zhàn)平臺。利用多無人機進行協(xié)同偵察，需要考慮無人機航時、偵察時長、任務(wù)載荷、中途維護時常等，并綜合考慮基地數(shù)量、無人機數(shù)量、偵察間隔、目標偵察頻次等因素，在時空域上規(guī)劃出無人機航路和時間，并確定偵察每一任務(wù)點所使用的任務(wù)載荷。其復(fù)雜性主要體現(xiàn)在難以獲得滿足時間、空間、任務(wù)載荷等多重約束的多樣性有效解［1-3］，目前常用遺傳算法、蟻群算法等啟發(fā)式算法進行搜索［4-8］，能夠較為高效地尋找到可行解，但無法保證解的多樣性。本文借鑒多種群合作演化思路［9-10］，對傳統(tǒng)遺傳算法進行改進，用不同種群對解空間進行全局和局部兩個尺度的搜索，并通過并行成長和信息遷移，實現(xiàn)種群間的合作演化，以此在時空域上對無人機協(xié)同偵察任務(wù)進行高效規(guī)劃。如何合理描述多無人機協(xié)同偵察任務(wù)規(guī)劃問題，選取有效的搜索算法，以保證搜索的高效性和解的多樣性是本文的研究重點。

1 無人機協(xié)同偵察任務(wù)建模

1.1 問題描述

在無人機協(xié)同偵察常見任務(wù)中，多個基地需要派遣多架無人機對多個任務(wù)目標執(zhí)行偵察任務(wù)，無人機具有多種型號，搭載有一種或多種任務(wù)載荷，任務(wù)期間可以在具有保障能力的基地進行維護續(xù)航，不同目標點需要在一定時間間隔內(nèi)采用不同任務(wù)載荷進行偵察，且載荷偵察順序、頻次都有要求。為提高偵察效率，降低保障壓力，需對多無人機的航路以及對應(yīng)時間進行規(guī)劃。

針對多無人機協(xié)同偵察任務(wù)，可采用圖論描述方法對其進行描述，該方法將無人機可能的路徑以無向圖的方式表達出來，無向圖的節(jié)點和邊集如下：

式中，A 為目標集合；B 為基地集合；V 為無向圖的節(jié)點集合；E 為無向圖的邊集，表示V 中所有可能的路徑。

1.2 決策變量

1.3 狀態(tài)變量

1.4 約束條件

2）飛行時間約束：無人機單次最小飛行時間小于最大續(xù)航時間T0，當(dāng)天T1點前必須返回出發(fā)基地，可表示為：

3）任務(wù)載荷約束：無人機僅能攜帶起航基地所擁有的任務(wù)載荷，可表示為：

1.5 任務(wù)收益

1.5.1 任務(wù)處置收益

任務(wù)處置收益是對當(dāng)前任務(wù)完成情況的一個衡量，但無法對無人機偵察航路的優(yōu)化潛力進行評估，存在著不同軌跡但收益完全相同的情況。同時，任務(wù)處置收益還是一個整數(shù)型收益，在優(yōu)化求解過程中容易丟失梯度信息而陷入局部解中，因此，通過引入任務(wù)潛力收益和時間成本收益進行改善。

1.5.2 任務(wù)潛力收益

任務(wù)潛力主要為評估不同規(guī)劃航路中無人機的富余偵察能力，富余偵察能力越大，代表該條規(guī)劃航路魯棒性越強，其定義如下：

1.5.3 時間成本收益

時間成本收益實際上也體現(xiàn)了規(guī)劃航路的富余潛力，與任務(wù)潛力收益不同的是，其取值連續(xù)性強，航路點細微變化都必然帶來時間成本收益的改變，因此，能夠提供細微的梯度輔助信息，保證算法更快更好地收斂。其定義如下：

該值反映了剩余時間百分比，取值在0～1 之間，變化連續(xù)使其可作為任務(wù)處置收益的輔助收益指標。在實際求解過程中，任務(wù)潛力收益與時間成本收益之和優(yōu)化后期也小于1，不會偏離最終的任務(wù)處置數(shù)量。

2 基于多種群合作演化的任務(wù)規(guī)劃算法設(shè)計

多種群合作演化過程中，不同種群在不同尺度上并行搜索，這里主要采用兩個種群分別在全局和局部兩個尺度搜索，全局搜索主要保證解的多樣性；局部搜索則是在當(dāng)前解鄰域范圍進行搜索，優(yōu)化解的質(zhì)量，兩者并行進行，共同保證解的多樣性和有效性。合作演化則是保證不同種群的遷移演化，實現(xiàn)全局搜索與局部搜索的信息共享與統(tǒng)一，而不僅僅將其當(dāng)作物理隔絕的兩個獨立種群，有利于提高搜索效率。

2.1 基本流程

圖1 為多種群合作演化遺傳算法的基本流程。

圖1 多種群合作演化示意圖Fig.1 Schematic diagram of multi-group cooperative evolution

2.1.1 全局搜索

全局搜索主要是對染色體中的每個基因以相同概率進行交叉變異，以保證搜索解盡可能分布在整個解空間，保證解的多樣性。

2.1.2 局部搜索

局部搜索主要是在全局優(yōu)解基礎(chǔ)上，對時間、中轉(zhuǎn)基地基因以較高概率交叉變異，對路徑點以較低概率交叉變異，實現(xiàn)在全局優(yōu)解鄰域空間搜尋更優(yōu)解。

2.1.3 合作演化

并行搜索后都將個體最優(yōu)解放入優(yōu)解池，分別按照獨立的概率遷移到各自種群內(nèi)，通過若干代迭代，將實現(xiàn)全局搜索與局部搜索的信息共享與統(tǒng)一，而不僅僅將其當(dāng)作物理隔絕的兩個獨立種群。

2.2 交叉變異

染色體編碼采用的是混合編碼，其中，時間基因為連續(xù)量，其他基因為離散量。對于離散的任務(wù)點序列，采取兩點交叉和多點變異，兩點交叉即在兩個個體編碼串中隨機設(shè)置兩個交叉點，并交換交叉點之間的部分染色體；多點變異則是隨機選擇染色體中多個變異點，變異點個數(shù)和變異后數(shù)值都由隨機數(shù)生成。

2.3 合作演化

合作演化的重點是將全局搜索得到的優(yōu)解逐步傳遞用于局部搜索，局部搜索得到的更優(yōu)解進一步傳遞優(yōu)化全局搜索的解集合，在此過程中，既要保證解的質(zhì)量，也要保證解的多樣性，以免提前收斂，無法發(fā)揮并行搜索的優(yōu)勢。

對于全局搜索的每個解，依次根據(jù)收益指標和多樣性指標采取輪盤賭方法隨機選擇解，并以概率p 加入到優(yōu)解池中，局部搜索則以概率p 隨機從優(yōu)解池中選擇解進行局部優(yōu)化，并將優(yōu)化后的解加入到優(yōu)解池，并傳遞給全局搜索。為了保證全局搜索和局部搜索保持染色體個數(shù)不變，每次從優(yōu)解池選擇優(yōu)解都需從原解集淘汰相同數(shù)量。

3 多無人機協(xié)同偵察任務(wù)規(guī)劃模型求解

3.1 查找單架無人機有效路徑

由于時間、空間等多重約束，每條染色體對應(yīng)的無人機路徑難以保證是一條有效路徑，因此，根據(jù)算法1 約束查找染色體對應(yīng)的無人機有效路徑。

算法1 單架無人機有效路徑查找算法已知：遺傳算法搜索得到的初始序列images/BZ_178_795_1899_1072_1947.png；偵察時間代價矩陣T（n×n）；最大偵察時間images/BZ_178_535_2032_566_2065.png。求：滿足航程約束的有效路徑序列Pv。1：初始化①初始化合理路徑列表images/BZ_178_693_2264_829_2315.png；②初始化無人機總飛行時間t=0。2：重復(fù)執(zhí)行算法流程3-5 共n-1 次，循環(huán)序號為i。3：對任一返航基地j，如果images/BZ_178_669_2455_982_2509.png，代表無人機飛往下一目標后能夠返回出發(fā)基地或者飛往任一基地進行維護，則跳轉(zhuǎn)到步驟4，否則跳轉(zhuǎn)到步驟5；4：將pi+1 加入Pvimages/BZ_178_503_2653_643_2693.png，images/BZ_178_661_2649_847_2694.png；5：尋找最近的無人機基地j，判斷能否當(dāng)天飛往j 后返航到出發(fā)基地，能夠則將基地j 加入Pv，images/BZ_178_750_2775_936_2820.png，否則，跳轉(zhuǎn)到步驟2。

3.2 統(tǒng)計任務(wù)目標有效偵察次數(shù)

對于每個待偵察的任務(wù)目標，要求利用一種或多種偵察載荷，在約定的偵察間隔內(nèi)進行一次或多次偵察，為了計算任務(wù)收益值，需要根據(jù)算法2 遞歸查找有效偵察次數(shù)，以判斷任務(wù)目標是否成功偵察。

算法2 有效偵察次數(shù)遞歸查找算法已知：被偵察時間序列images/BZ_178_1618_613_2004_673.png；被偵察載荷序列images/BZ_178_1618_695_2041_753.png。求：當(dāng)前有效偵察時間序列Tl；有效偵察載荷序列Dl。1：初始化Tl、Dl 為空；2：重復(fù)執(zhí)行算法流程L 次，循環(huán)序號為i；3：重復(fù)執(zhí)行算法流程L-i 次，循環(huán)序號為j；4：對于每一個元素images/BZ_178_1581_1129_1694_1178.pngimages/BZ_178_1712_1130_1844_1177.png，如果，則執(zhí)行步驟5，否則繼續(xù)執(zhí)行步驟4；5：且images/BZ_178_1320_1200_1415_1242.pngimages/BZ_178_1321_1274_1418_1313.pngimages/BZ_178_1438_1276_1555_1313.png表示Tl 元素個數(shù)如果，，images/BZ_178_1575_1264_1757_1316.png，其中，images/BZ_178_1873_1266_1950_1316.pngimages/BZ_178_1357_1338_1531_1390.png，則結(jié)束，否則跳轉(zhuǎn)到步驟2。

3.3 算法性能評估

使用5 架無人機從3 個基地出發(fā)協(xié)同偵察15個任務(wù)目標，并按照表1 設(shè)置算法參數(shù)進行仿真求解，其中一次結(jié)果如下頁圖2 所示，能夠看出5 架無人機很好地完成了對任務(wù)目標點的全覆蓋。

表1 算法參數(shù)表Table 1 Algorithm parameter

圖2 多無人協(xié)同偵察結(jié)果圖Fig.2 The result of multi-UAV cooperative reconnaissance

為了比較本文算法與常規(guī)的單種群遺傳算法的優(yōu)劣，對任務(wù)處置收益、任務(wù)潛力收益、時間成本收益進行比較如表2 所示，并給出圖3 所示的綜合收益對比曲線。為了保證公平性，單種群遺傳算法的染色體個數(shù)為多種群的2 倍。

表2 收益對比表Table 2 Comparison on efficiency

圖3 綜合收益對比曲線Fig.3 The comparison curve of the comprehensive benefits

表2 為10 次仿真結(jié)果的平均結(jié)果，其中，多種群合作演化遺傳算法中任務(wù)處置收益33 為當(dāng)前仿真條件下任務(wù)處置收益的飽和值，表示此時能夠?qū)崿F(xiàn)有效偵察次數(shù)33 次，完成了當(dāng)前要求的偵察任務(wù)。而單種群遺傳算法由于缺乏并行的局部搜索環(huán)節(jié)，僅靠收斂階段對鄰域小范圍的細致搜索，解的質(zhì)量較之多種群更差，同時算法收斂也更慢，如圖3所示。

4 結(jié)論

本文研究在多種約束條件下的多無人機規(guī)劃問題，提出基于多種群合作演化的無人機協(xié)同偵察算法，該算法對規(guī)劃問題進行分層描述，確定單架無人機有效路徑查找算法，采用多種群合作演化在全局和局部兩個尺度進行搜索，在確保搜索效率的同時，通過并行成長和信息遷移，實現(xiàn)種群間的合作演化，實現(xiàn)了在時空域上對無人機協(xié)同偵察任務(wù)的高效規(guī)劃。

仿真結(jié)果表明，該算法與單種群搜索算法相比，在任務(wù)處置效益、任務(wù)潛力效益、時間成本效益等方面均有提升，但由于多種群信息遷移過程中加入了新的參數(shù)，提高了參數(shù)選擇的難度。下一步工作將考慮種群多樣性和收斂性設(shè)計參數(shù)自動選擇算法，提高算法靈活性。