基于多種群合作演化的無(wú)人機(jī)協(xié)同偵察任務(wù)規(guī)劃研究

帥偉偉，汪 君，任開(kāi)君，楊 健，林 潔

（1.解放軍95795 部隊(duì)，廣西 桂林 541003；2.中國(guó)電子科技集團(tuán)第十五研究所，北京 100080）

0 引言

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

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

1.1 問(wèn)題描述

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

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

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

1.2 決策變量

1.3 狀態(tài)變量

1.4 約束條件

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

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

1.5 任務(wù)收益

1.5.1 任務(wù)處置收益

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

1.5.2 任務(wù)潛力收益

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

1.5.3 時(shí)間成本收益

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

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

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

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

2.1 基本流程

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

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

2.1.1 全局搜索

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

2.1.2 局部搜索

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

2.1.3 合作演化

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

2.2 交叉變異

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

2.3 合作演化

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

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

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

3.1 查找單架無(wú)人機(jī)有效路徑

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

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

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

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

算法2 有效偵察次數(shù)遞歸查找算法已知：被偵察時(shí)間序列images/BZ_178_1618_613_2004_673.png；被偵察載荷序列images/BZ_178_1618_695_2041_753.png。求：當(dāng)前有效偵察時(shí)間序列Tl；有效偵察載荷序列Dl。1：初始化Tl、Dl 為空；2：重復(fù)執(zhí)行算法流程L 次，循環(huán)序號(hào)為i；3：重復(fù)執(zhí)行算法流程L-i 次，循環(huán)序號(hào)為j；4：對(duì)于每一個(gè)元素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 元素個(gè)數(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 算法性能評(píng)估

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

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

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

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

表2 收益對(duì)比表Table 2 Comparison on efficiency

圖3 綜合收益對(duì)比曲線(xiàn)Fig.3 The comparison curve of the comprehensive benefits

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

4 結(jié)論

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

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