林君燦, 賈高偉, 侯中喜

(國(guó)防科技大學(xué)空天科學(xué)學(xué)院, 湖南 長(zhǎng)沙 410073)

0 引 言

防空雷達(dá)是空情預(yù)警的核心裝備,各類防空雷達(dá)裝備技術(shù)的快速發(fā)展,使得傳統(tǒng)電子戰(zhàn)飛機(jī)的作戰(zhàn)效能大大降低。同時(shí),傳統(tǒng)的電子戰(zhàn)飛機(jī)雷達(dá)反射截面積較大,導(dǎo)致隱身性能差,易被發(fā)現(xiàn)與攻擊。

小型無人飛行器系統(tǒng)具有尺寸小、成本低、突防能力強(qiáng)等特點(diǎn),且雷達(dá)散射回波通常較弱,能夠遂行復(fù)雜電磁環(huán)境下的電子干擾、誘騙及攻擊任務(wù)。同時(shí),隨著無人機(jī)自主控制能力的提高,無人機(jī)編隊(duì)?wèi)?zhàn)術(shù)引起了廣泛關(guān)注。將不同載荷不同平臺(tái)的無人機(jī)編隊(duì)(異構(gòu)無人機(jī)編隊(duì))用于對(duì)敵方雷達(dá)陣地實(shí)施偵察、定位、打擊、評(píng)估,是摧毀敵方防空預(yù)警系統(tǒng)的重要作戰(zhàn)樣式,受到國(guó)內(nèi)外的高度關(guān)注。

在異構(gòu)無人機(jī)編隊(duì)的應(yīng)用中,任務(wù)分配是頂層的規(guī)劃設(shè)計(jì),研究意義重要[1]。

國(guó)外的研究團(tuán)隊(duì)設(shè)計(jì)建立了多類任務(wù)分配模型,包括車輛路徑問題(vehicle routing problem,VRP)模型[2]、多旅行商問題(multiple traveling salesman problem,MTSP)模型[3]、混合整數(shù)線性規(guī)劃(mixed integer linear programming,MILP)模型[4]等。應(yīng)用MILP方法可以納入時(shí)間等連續(xù)約束條件,可以精確得到更加符合實(shí)際情況下的任務(wù)分配問題的最優(yōu)解。文獻(xiàn)[5]利用MILP模型分析解決了多個(gè)相同無人機(jī)(同構(gòu)無人機(jī))執(zhí)行廣域搜索地攻擊任務(wù)分配問題。此外,文獻(xiàn)[6]將遺傳算法應(yīng)用于多無人機(jī)任務(wù)分配問題上,凸顯了遺傳算法的計(jì)算時(shí)效性。

國(guó)內(nèi)方面,文獻(xiàn)[7]結(jié)合基于時(shí)間窗的MILP任務(wù)分配模型,給出多架同構(gòu)無人機(jī)協(xié)同對(duì)地攻擊優(yōu)化問題的任務(wù)分配方案。文獻(xiàn)[8]在MILP模型中加入目標(biāo)的威脅因素, 提高了完成任務(wù)的準(zhǔn)確性。文獻(xiàn)[9]通過對(duì)適應(yīng)度值做了標(biāo)定,改進(jìn)了遺傳算法,解決了多約束下多無人機(jī)協(xié)同任務(wù)分配問題。文獻(xiàn)[10]采用一種改進(jìn)的非支配排序遺傳算法,任務(wù)分配結(jié)果的Pareto最優(yōu)解集。

對(duì)比發(fā)現(xiàn),在多無人機(jī)任務(wù)分配方法研究中,MILP和遺傳算法是兩類常用的方法[11-15]。現(xiàn)有的MILP類方法大多應(yīng)用在同構(gòu)無人機(jī)編隊(duì)間的任務(wù)分配,未考慮異構(gòu)無人機(jī)編隊(duì)在飛行平臺(tái)差異化、載荷功能差異化、時(shí)空協(xié)同復(fù)雜化方面的影響[16];而現(xiàn)有應(yīng)用于任務(wù)分配的遺傳算法及其改進(jìn)型,未考慮異構(gòu)無人機(jī)編隊(duì)的任務(wù)功能多樣化以及嚴(yán)格的時(shí)間窗約束。為了解決異構(gòu)無人機(jī)編隊(duì)復(fù)雜的任務(wù)分配問題,有必要對(duì)現(xiàn)有MILP方法和遺傳算法進(jìn)行改進(jìn)。本文提出了一種基于時(shí)間窗的異構(gòu)無人機(jī)編隊(duì)MILP模型,建立了無人機(jī)之間、執(zhí)行任務(wù)之間合理的協(xié)同約束關(guān)系。此外,提出了基于時(shí)間窗的多層編碼遺傳算法實(shí)現(xiàn)異構(gòu)無人機(jī)編隊(duì)任務(wù)分配,結(jié)合時(shí)空四維約束,清晰地表達(dá)出異構(gòu)無人機(jī)編隊(duì)執(zhí)行任務(wù)時(shí)的時(shí)序關(guān)系。

1 問題描述

異構(gòu)無人機(jī)編隊(duì)對(duì)敵方雷達(dá)陣地進(jìn)行攻擊作戰(zhàn)過程中,編隊(duì)內(nèi)的無人機(jī)能夠獨(dú)立進(jìn)行搜索、分類、攻擊、評(píng)估等任務(wù)。當(dāng)編隊(duì)中任何一架無人機(jī)進(jìn)行信息更新(例如發(fā)現(xiàn)一個(gè)新雷達(dá)目標(biāo)時(shí)),編隊(duì)內(nèi)的無人機(jī)均能共享該信息。當(dāng)發(fā)現(xiàn)潛在或可疑的目標(biāo)時(shí),啟動(dòng)分類任務(wù)。分類是從另一個(gè)觀察視角對(duì)目標(biāo)進(jìn)行第二次搜索探測(cè),從而提高目標(biāo)識(shí)別的置信水平。待可疑目標(biāo)被分類確認(rèn)后,對(duì)其執(zhí)行攻擊任務(wù)。在本想定中,執(zhí)行攻擊任務(wù)的無人機(jī)通過自身攜帶的彈藥部摧毀目標(biāo)。

一般地,對(duì)雷達(dá)站目標(biāo)的打擊需要在特定的時(shí)間窗口內(nèi)進(jìn)行(例如雷達(dá)的開機(jī)時(shí)間內(nèi))。隨后還需由另一架飛機(jī)進(jìn)行探測(cè)核實(shí)以確認(rèn)目標(biāo)是否已被摧毀。

任務(wù)描述如下:在某作戰(zhàn)區(qū)域內(nèi),我方區(qū)域內(nèi)分布有V架無人機(jī),敵方區(qū)域上分布N個(gè)地面雷達(dá)站,我方無人機(jī)對(duì)敵方區(qū)域進(jìn)行搜索,在被探測(cè)到的敵方雷達(dá)站上依次執(zhí)行分類,攻擊和毀傷評(píng)估任務(wù),在滿足無人機(jī)分配邏輯和任務(wù)到達(dá)先后次序的前提下,總的任務(wù)執(zhí)行時(shí)間最小,沒有分配到任務(wù)或完成任務(wù)的無人機(jī)繼續(xù)對(duì)目標(biāo)進(jìn)行搜索。

結(jié)合實(shí)際作戰(zhàn)情況,想定如下:①地面雷達(dá)站為固定目標(biāo),位置坐標(biāo)均已知,無人機(jī)當(dāng)前位置坐標(biāo)也已知;②同一個(gè)目標(biāo)上的任務(wù)執(zhí)行順序?yàn)?先分類后攻擊再評(píng)估;③同一架無人機(jī)在同一個(gè)目標(biāo)上最多執(zhí)行兩次任務(wù),即允許執(zhí)行分類任務(wù)后立刻執(zhí)行攻擊任務(wù);④無人機(jī)攻擊目標(biāo)后自爆自毀,將不再接受任務(wù)分配;⑤由于飛行時(shí)間遠(yuǎn)大于執(zhí)行任務(wù)的時(shí)間,故忽略任務(wù)執(zhí)行時(shí)間。

2 基于MILP模型的任務(wù)分配

基于MILP模型的任務(wù)分配描述如下,假設(shè)有N+V+1個(gè)節(jié)點(diǎn):N個(gè)目標(biāo)節(jié)點(diǎn)、V個(gè)無人機(jī)源節(jié)點(diǎn)和一個(gè)搜索節(jié)點(diǎn)。節(jié)點(diǎn)1,2,…,N對(duì)應(yīng)N個(gè)目標(biāo)位置,節(jié)點(diǎn)N+1,N+2,…,N+V對(duì)應(yīng)V個(gè)無人機(jī)源節(jié)點(diǎn),節(jié)點(diǎn)N+V+1是搜索節(jié)點(diǎn)。當(dāng)下一步?jīng)]有別的任務(wù)指派給無人機(jī)時(shí),將使用搜索節(jié)點(diǎn),當(dāng)所有任務(wù)都被執(zhí)行或者沒有指派其他的任務(wù)時(shí),將到達(dá)搜索節(jié)點(diǎn)。實(shí)際上,當(dāng)一個(gè)無人機(jī)到達(dá)搜索節(jié)點(diǎn)時(shí),它將執(zhí)行對(duì)作戰(zhàn)區(qū)域的搜索任務(wù)。

2.1 決策變量

表1 MILP決策變量

2.2 目標(biāo)函數(shù)

≤tf,j=1,2,…,N

(1)

代價(jià)函數(shù)是對(duì)所有目標(biāo)執(zhí)行完任務(wù)的總時(shí)間最小化,然而,只要對(duì)最后一個(gè)目標(biāo)執(zhí)行任務(wù)時(shí)沒有延遲,該代價(jià)函數(shù)就不會(huì)對(duì)單個(gè)目標(biāo)執(zhí)行任務(wù)時(shí)產(chǎn)生的延遲進(jìn)行補(bǔ)償。因此,為提高性能,可以增加一個(gè)小的權(quán)重,以激勵(lì)對(duì)每個(gè)單獨(dú)目標(biāo)也盡快執(zhí)行完任務(wù)。這樣,代價(jià)函數(shù)變?yōu)?/p>

(2)

2.3 約束條件

將MILP模型應(yīng)用于異構(gòu)無人機(jī)任務(wù)分配問題的最大難點(diǎn)是把約束條件轉(zhuǎn)化為合理的數(shù)學(xué)表達(dá)式。實(shí)現(xiàn)所期望的飛行器行為需要囊括必要的約束條件。完整的約束條件集合包括非時(shí)間約束和時(shí)間約束兩種:

(1) 對(duì)于每個(gè)目標(biāo),3個(gè)任務(wù)都只能完成一次:

(3)

和

(4)

(2) 每個(gè)目標(biāo)j的任務(wù)k最多只能由一架UAV執(zhí)行:

≤1,k=1,3

(5)

和

≤1

(6)

(3) 每個(gè)UAVv從外部最多訪問一次目標(biāo)節(jié)點(diǎn)j:

≤1

(7)

(4) 每個(gè)UAVv只能進(jìn)入搜索節(jié)點(diǎn)一次:

≤1

(8)

(5) 每個(gè)UAVv最多離開節(jié)點(diǎn)j最多一次:

≤1

(9)

(6) 由于UAVv執(zhí)行一次攻擊任務(wù)之后,就不能再使用了,這樣,每個(gè)UAVv最多只能攻擊一個(gè)目標(biāo)。UAV最多進(jìn)入目標(biāo)j一次,因此它不能攻擊目標(biāo)節(jié)點(diǎn)j再離開該節(jié)點(diǎn):

≤1

(10)

和

(11)

(7) 如果UAVv對(duì)目標(biāo)節(jié)點(diǎn)j執(zhí)行分類任務(wù),則該無人機(jī)必須離開目標(biāo)節(jié)點(diǎn)或者對(duì)目標(biāo)節(jié)點(diǎn)j執(zhí)行攻擊任務(wù):

(12)

(8) 所有的UAV必須離開它們的源節(jié)點(diǎn),即使是被指派直接飛往搜索節(jié)點(diǎn):

(13)

(9) UAVv不能離開尚未指派進(jìn)入的節(jié)點(diǎn)j:

(14)

(10) 一個(gè)UAV不能從節(jié)點(diǎn)j出來再攻擊目標(biāo)j,除非它進(jìn)入節(jié)點(diǎn)j的目的是執(zhí)行分類任務(wù):

(15)

對(duì)于式(1)～式(11),其中i=1,2,…,N+V;j=1,2,…,N;v=1,2,…,V;k=1,2,…,K。

(11) 對(duì)于時(shí)間約束的線性關(guān)系表示可以采用一系列的線性不等式約束。令

(16)

為所有飛行器中最長(zhǎng)的剩余飛行時(shí)間。這樣線性時(shí)間約束可以表示為

(17)

(18)

(19)

(20)

式中,i=1,2,…,N;j=1,2,…,N;i≠j;v=1,2,…,V;k=1,3。

(12)另外對(duì)于飛行器v對(duì)目標(biāo)j既執(zhí)行分類任務(wù)又執(zhí)行攻擊任務(wù)的情況,還需要另外的線性時(shí)間約束:

(21)

(22)

(23)

(24)

式中,i=1,2,…,N;j=1,2,…,N;i≠j;v=1,2,…,V。

(13) 每個(gè)UAV執(zhí)行的第一個(gè)任務(wù),其約束如下:

(25)

(26)

式中,i=1,2,…,N;v=1,2,…,V;k=1,2,3。

(14)任務(wù)優(yōu)先級(jí)次序必須滿足:

(27)

(28)

(15)在同一個(gè)目標(biāo)上的兩個(gè)相鄰任務(wù)(如分類和攻擊任務(wù),攻擊和毀傷評(píng)估任務(wù))間由于信號(hào)延遲或者煙霧干擾等原因,中間需要加入時(shí)間延遲間隔α[α1,α2],可有如下約束:

(29)

(30)

建立了MILP模型后,通過求解約束優(yōu)化方程,能夠得到任務(wù)分配結(jié)果。

2.4 仿真分析

表2 目標(biāo)任務(wù)信息

表3 目標(biāo)任務(wù)執(zhí)行時(shí)間窗

表4 無人機(jī)性能參數(shù)

對(duì)上述MILP問題利用LINGO軟件求解,用時(shí)為30 min,求解結(jié)果如下:

(1) 決策變量

其余為0;

(2) 搜索任務(wù)決策變量

其余為0。

(3) 連續(xù)時(shí)間變量:任務(wù)出發(fā)時(shí)刻(min)

t1=44.7,t2=38.7,t3=33.4,

t7=19.1,t8=22.4,t9=31.8,t10=29.2

其余UAV出發(fā)時(shí)間為任務(wù)開始時(shí)刻。

(4) 目標(biāo)任務(wù)結(jié)束時(shí)刻(min)

上述任務(wù)分配結(jié)果如圖1所示。

圖1 MILP最優(yōu)任務(wù)分配結(jié)果Fig.1 Optimal task assignment of MILP

圖1表示的任務(wù)分配為10架異構(gòu)無人機(jī)編隊(duì)4個(gè)目標(biāo)時(shí)的最優(yōu)任務(wù)分配: UAV-01和UAV-02分別在任務(wù)開始44.7 min和38.7 min后出發(fā),分別經(jīng)過45.3 min和31.3 min到達(dá)目標(biāo)3和目標(biāo)1,并對(duì)他們執(zhí)行毀傷評(píng)估任務(wù);UAV-03在任務(wù)開始33.4 min后出發(fā),經(jīng)過36.6 min到達(dá)目標(biāo)2執(zhí)行毀傷評(píng)估任務(wù),又經(jīng)過21.2 min達(dá)到目標(biāo)4執(zhí)行毀傷評(píng)估任務(wù);UAV-04、UAV-05、 UAV-06未分配到任務(wù),故一直呈編隊(duì)狀態(tài)執(zhí)行搜索任務(wù);UAV-07在任務(wù)開始19.1 min后出發(fā),經(jīng)過32.6 min到達(dá)目標(biāo)2執(zhí)行分類任務(wù),隨后對(duì)目標(biāo)2執(zhí)行攻擊任務(wù),自爆;UAV-08在任務(wù)開始19.1 min后出發(fā),經(jīng)過35.9 min到達(dá)目標(biāo)1執(zhí)行分類任務(wù),隨后對(duì)目標(biāo)1執(zhí)行攻擊任務(wù),自爆;UAV-09在任務(wù)開始31.8 min后出發(fā),經(jīng)過43.2 min到達(dá)目標(biāo)3執(zhí)行分類任務(wù),隨后對(duì)目標(biāo)3執(zhí)行攻擊任務(wù),自爆;UAV-10在任務(wù)開始29.2 min后出發(fā),經(jīng)過45.8 min到達(dá)目標(biāo)4執(zhí)行分類任務(wù),隨后對(duì)目標(biāo)3執(zhí)行攻擊任務(wù),自爆。

3 基于時(shí)間窗的多層編碼遺傳算法

3.1 算法描述

為避免前述MILP模型優(yōu)化方法的復(fù)雜性,并加快一個(gè)良好可行方案的收斂速度,可以采用遺傳算法。該類方法不需要計(jì)算問題的梯度,可以并行運(yùn)算,且不會(huì)陷入局部極小點(diǎn),但也可能得不到最優(yōu)方案。

基于時(shí)間窗的多層編碼遺傳算法中染色體的編碼是求解過程中的一個(gè)主要工作,染色體可以充分表達(dá)簡(jiǎn)單問題的潛在解;然而,對(duì)于較復(fù)雜的多目標(biāo)、多約束優(yōu)化求解問題,染色體則難以充分表達(dá)問題的解。為了解決這個(gè)問題,我們改進(jìn)了編碼方式,提出了多層編碼遺傳算法,把染色體編碼從一層拓展為多層,每層編碼表達(dá)一個(gè)或多個(gè)約束關(guān)系,多層編碼共同表達(dá)了問題的完整解。

本文染色體編碼方式為整數(shù)編碼,每個(gè)染色體個(gè)體映射為目標(biāo)的執(zhí)行順序和無人機(jī)編號(hào)。針對(duì)本文的問題,我們?nèi)∪旧w為二層編碼,當(dāng)目標(biāo)總數(shù)為n,每個(gè)目標(biāo)需要執(zhí)行k項(xiàng)任務(wù),則染色體的長(zhǎng)度為2×n×k。其中,第一層染色體編碼表示所有目標(biāo)的執(zhí)行順序,第二層編碼表示執(zhí)行上層對(duì)應(yīng)位置對(duì)應(yīng)的任務(wù)的無人機(jī)編號(hào)。以如下個(gè)體為例:

解碼后任務(wù)順序表示為:301 302 101 201 303 401 102 402 202 103 203 403。以301為例,其中3表示目標(biāo)編號(hào),01表示任務(wù)編號(hào)。從中可以看出,染色體的長(zhǎng)度為12×2,任務(wù)分配結(jié)果如下:UAV-01首先攻擊目標(biāo)3,然后對(duì)目標(biāo)2進(jìn)行毀傷評(píng)估;UAV-02對(duì)目標(biāo)4執(zhí)行分類任務(wù),然后再以自爆自毀的方式攻擊目標(biāo)1;UAV-03和UAV-04分別對(duì)目標(biāo)3和目標(biāo)1執(zhí)行分類任務(wù),然后再執(zhí)行毀傷評(píng)估任務(wù);UAV-05和UAV-06都以自爆自毀的方式對(duì)分別目標(biāo)2和目標(biāo)4執(zhí)行打擊任務(wù);UAV-07對(duì)目標(biāo)2執(zhí)行分類任務(wù)后,對(duì)目標(biāo)3執(zhí)行毀傷評(píng)估任務(wù)。

在無人機(jī)任務(wù)規(guī)劃過程中,通常有某個(gè)任務(wù)要求必須在某個(gè)指定的時(shí)間范圍內(nèi)完成,則該時(shí)間范圍就稱為時(shí)間窗約束。異構(gòu)無人機(jī)編隊(duì)在反雷達(dá)作戰(zhàn)中,對(duì)敵方雷達(dá)站執(zhí)行打擊任務(wù)時(shí),打擊時(shí)間設(shè)定在雷達(dá)的開機(jī)時(shí)間[t,t+Δt1]窗口內(nèi),對(duì)于打擊效果的毀傷評(píng)估任務(wù)為了避免煙塵等影響,需要在打擊任務(wù)結(jié)束后的Δt2時(shí)間內(nèi)進(jìn)行,超過這兩個(gè)時(shí)間窗口限制,目標(biāo)狀態(tài)將發(fā)送改變,導(dǎo)致任務(wù)效能降低。

3.2 算法流程

基于時(shí)間窗的多層編碼遺傳算法流程描述如下。

步驟1初始化參數(shù)

種群初始化,確定初始種群規(guī)模、選擇概率、交叉概率、變異概率、最大進(jìn)化代數(shù)。

步驟2個(gè)體編碼

根據(jù)打擊任務(wù)的時(shí)間窗口推算分類任務(wù)和毀傷評(píng)估任務(wù)的執(zhí)行時(shí)間,對(duì)不符合任務(wù)時(shí)間窗要求的染色體進(jìn)行修復(fù),生成合適的染色體進(jìn)行后續(xù)步驟,可以提高算法的計(jì)算速度,染色體適應(yīng)度值的計(jì)算根據(jù)式(2)給出。

步驟3選擇操作

采用輪盤賭法,根據(jù)選擇概率,在原始種群中選擇適應(yīng)度較好的染色體個(gè)體保留到下一代種群中,個(gè)體選擇概率為

(31)

Fitness(i)=1/Fitness(i)

步驟4交叉操作

根據(jù)交叉概率,從種群中選取兩個(gè)染色體,隨機(jī)確定染色體上的交叉位置,將兩個(gè)染色體上層對(duì)應(yīng)交叉位置的基因編碼進(jìn)行交叉操作。操作方法如圖2所示。

圖2 交叉操作Fig.2 Crossover operation

由于將合理染色體的編碼順序交叉后容易出現(xiàn)某些目標(biāo)的任務(wù)多余而某些目標(biāo)任務(wù)缺失,因此需要進(jìn)行編碼的調(diào)整和修復(fù):把任務(wù)多余的基因位調(diào)整為任務(wù)缺失的基因,并且按交叉操作之前編碼第二層所對(duì)應(yīng)的無人機(jī)編號(hào)來調(diào)整編碼,調(diào)整操作方法如圖3所示。

圖3 調(diào)整編碼Fig.3 Code adjustment

步驟5變異操作

根據(jù)變異概率,在種群中隨機(jī)選擇變異個(gè)體,隨機(jī)選擇染色體的兩個(gè)變異位置,把染色體中兩個(gè)變異位置對(duì)應(yīng)的基因以及下層編碼對(duì)應(yīng)的無人機(jī)編號(hào)進(jìn)行交換。操作方法如圖4所示。

圖4 變異操作Fig.4 Mutation operation

步驟6合并父代和經(jīng)過選擇、交叉、變異操作后產(chǎn)生的子代種群,生成混合種群。

步驟7計(jì)算混合種群適應(yīng)度值。

步驟8判斷是否滿足循環(huán)終止條件,若不滿足,跳轉(zhuǎn)到步驟2,循環(huán)直至滿足終止條件,最終輸出最優(yōu)任務(wù)分配方案。

3.3 仿真分析

算法的基本參數(shù)為:種群數(shù)目為50,最大迭代次數(shù)為100,選擇概率為0.94,交叉概率為0.8,變異概率為0.1。仿真平臺(tái)與上述相同,求解用時(shí)為4.5 s,算法的搜索過程如圖5所示,表示隨著遺傳代數(shù)的進(jìn)化,種群最優(yōu)解與均值的變化關(guān)系。算法在第80代時(shí)得到最優(yōu)解,最優(yōu)解為92.8 min。

圖5 算法搜索過程Fig.5 Algorithm search process

最優(yōu)個(gè)體對(duì)應(yīng)的任務(wù)執(zhí)行順序甘特圖如圖6所示。

結(jié)果說明: UAV-01在任務(wù)時(shí)刻出發(fā),經(jīng)過36.6 min到達(dá)目標(biāo)2執(zhí)行分類任務(wù),在43.5 min時(shí)刻開始經(jīng)過30 min至目標(biāo)1執(zhí)行毀傷評(píng)估任務(wù);UAV-02在任務(wù)開始51.6 min后出發(fā),經(jīng)過36.6 min到達(dá)目標(biāo)2執(zhí)行毀傷評(píng)估任務(wù);UAV-03未分配到任務(wù),故一直呈編隊(duì)狀態(tài)執(zhí)行搜索任務(wù);UAV-04在任務(wù)開始40.9 min后出發(fā),經(jīng)過39.5 min到達(dá)目標(biāo)4執(zhí)行攻擊任務(wù),自爆;UAV-05未分配到任務(wù),故一直呈編隊(duì)狀態(tài)執(zhí)行搜索任務(wù);UAV-06在任務(wù)開始19.9 min后出發(fā),經(jīng)過42.8 min到達(dá)目標(biāo)1執(zhí)行攻擊任務(wù),自爆;UAV-07在任務(wù)開始49.6 min后出發(fā),經(jīng)過43.2 min到達(dá)目標(biāo)3執(zhí)行毀傷評(píng)估任務(wù);UAV-08在任務(wù)時(shí)刻出發(fā),經(jīng)過45.8 min到達(dá)目標(biāo)4執(zhí)行分類任務(wù),在53 min時(shí)刻開始經(jīng)過21.2 min至目標(biāo)2執(zhí)行攻擊任務(wù),自爆;UAV-09在任務(wù)開始38.3 min后出發(fā),經(jīng)過43.2 min到達(dá)目標(biāo)3執(zhí)行攻擊任務(wù),自爆;UAV-10在任務(wù)開始時(shí)刻出發(fā),經(jīng)過35.9 min到達(dá)目標(biāo)1執(zhí)行分類任務(wù),而后經(jīng)過21.2 min到達(dá)目標(biāo)3執(zhí)行分類任務(wù),在60.9 min時(shí)刻開始經(jīng)過30 min對(duì)目標(biāo)4執(zhí)行毀傷評(píng)估任務(wù)。

圖6 任務(wù)執(zhí)行甘特圖Fig.6 Task execution Gantt chart

4 對(duì)比與分析

本文利用MILP和基于時(shí)間窗的多層編碼遺傳算法解決異構(gòu)無人機(jī)編隊(duì)在反雷達(dá)作戰(zhàn)中的協(xié)同任務(wù)分配問題,仿真結(jié)果表明二者都能得出可行最優(yōu)分配方案及任務(wù)執(zhí)行時(shí)序圖。對(duì)比發(fā)現(xiàn):①在相同的平臺(tái)下,基于時(shí)間窗的多層編碼遺傳算法的求解時(shí)間遠(yuǎn)快于MILP方法;②MILP方法得到任務(wù)執(zhí)行最短時(shí)間為91.2 min,而基于時(shí)間窗的多層編碼遺傳算法得到的最短執(zhí)行時(shí)間為92.8 min。經(jīng)過分析,由于MILP方法通過搜索得到的是目標(biāo)函數(shù)的全局最優(yōu)解,故其精度更高。

仿真分析表明,MILP模型通過數(shù)學(xué)表達(dá)式可以方便地將時(shí)間、空間、物理、邏輯約束聯(lián)系起來,將一個(gè)實(shí)際的作戰(zhàn)任務(wù)轉(zhuǎn)化成數(shù)學(xué)問題,能夠求解有時(shí)間窗要求的任務(wù)分配問題。但用數(shù)學(xué)表達(dá)式將所有的約束問題融入到一個(gè)MILP模型中,將導(dǎo)致NP-Hard優(yōu)化問題,且計(jì)算量隨著求解規(guī)模呈指數(shù)遞增。以本次仿真采用的計(jì)算平臺(tái)為例,一般地,對(duì)于規(guī)模大于2個(gè)目標(biāo),且每個(gè)目標(biāo)有3個(gè)任務(wù)的問題,難以實(shí)現(xiàn)實(shí)時(shí)求解。鑒于MILP在分配最優(yōu)性方面的優(yōu)勢(shì),對(duì)于中等規(guī)模的問題,可以采用MILP離線方式尋找到最優(yōu)分配方案。

基于時(shí)間窗的多層編碼遺傳算法亦可以得到異構(gòu)無人機(jī)編隊(duì)任務(wù)分配方案,便于利用甘特圖直觀表示任務(wù)執(zhí)行時(shí)序,其顯著特點(diǎn)是算法執(zhí)行時(shí)間大大小于MILP方法。在算法中,編碼是迭代處理的前提,染色體編碼難以精確體現(xiàn)所有約束,因此求解方案的最優(yōu)性將會(huì)受到一些影響,但仍可以得到可行的任務(wù)分配結(jié)果。

概括來講,基于MILP的任務(wù)分配能夠得到全局最優(yōu)解,但當(dāng)問題規(guī)模較大時(shí)難以滿足實(shí)時(shí)性,適用于小規(guī)模任務(wù)分配實(shí)時(shí)解算;基于時(shí)間窗的多層編碼遺傳算法具有明確的計(jì)算優(yōu)勢(shì),但可能得到局部最優(yōu)解,適用于為較大規(guī)模任務(wù)分解實(shí)時(shí)提供初始任務(wù)分配方案。

5 結(jié) 論

本文利用MILP和基于時(shí)間窗的多層編碼遺傳算法解決異構(gòu)無人機(jī)編隊(duì)在反雷達(dá)作戰(zhàn)中的協(xié)同任務(wù)分配的問題。MILP模型將實(shí)際作戰(zhàn)任務(wù)轉(zhuǎn)化成數(shù)學(xué)規(guī)劃問題,簡(jiǎn)明易懂,對(duì)于小規(guī)模的問題可以在線運(yùn)行得出最優(yōu)的分配方案。相對(duì)于MILP模型,基于時(shí)間窗的多層編碼遺傳算法計(jì)算效率高,通過能夠?qū)崟r(shí)給出良好的分配方案,在異構(gòu)無人機(jī)編隊(duì)任務(wù)分配中,可根據(jù)任務(wù)分配規(guī)模、用戶需求選擇使用兩類算法。