基于D-NSGA-III算法的無人機(jī)群高維多目標(biāo)任務(wù)分配方法

周 晶, 趙曉哲, 許 震, 林 眾, 張曉盼,*

(1. 大連理工大學(xué)經(jīng)濟(jì)管理學(xué)院, 遼寧 大連 116024; 2. 海軍大連艦艇學(xué)院作戰(zhàn)軟件與仿真研究所,遼寧 大連 116018; 3. 武漢理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 湖北 武漢 430074)

0 引 言

隨著人工智能、衛(wèi)星導(dǎo)航、新材料、網(wǎng)絡(luò)通信等技術(shù)飛速發(fā)展,大量具有軍事用途的無人機(jī)應(yīng)運(yùn)而生。無人機(jī)具有速度快、全天候、非接觸、零傷亡等特點(diǎn)在實(shí)戰(zhàn)中得到了廣泛應(yīng)用[1-2]。特別是近十年來,世界范圍內(nèi)幾乎所有局部戰(zhàn)爭(zhēng)中都活躍著無人機(jī)的身影[3]。迄今為止,全球已有30余個(gè)國(guó)家和地區(qū)研制出了50多類300余種無人機(jī),有60多個(gè)國(guó)家的軍隊(duì)裝備了無人機(jī),且服役數(shù)量正在快速增加,精確打擊、編隊(duì)集群作戰(zhàn)成為無人機(jī)的主要發(fā)展方向。

盡管無人機(jī)技術(shù)發(fā)展迅猛,性能日益強(qiáng)大，但也難以獨(dú)立完成復(fù)雜作戰(zhàn)任務(wù),尤其是在解決空間上呈分布式狀態(tài)、時(shí)間上需并行處理的復(fù)雜任務(wù)時(shí),單系統(tǒng)難以發(fā)揮作用;同時(shí),受平臺(tái)載荷的制約,單個(gè)平臺(tái)能夠配備的資源受限,完成任務(wù)的能力也有限。針對(duì)上述問題,在實(shí)際應(yīng)用中往往需要多種類型無人機(jī)協(xié)同配合,才能完成繁重復(fù)雜的作戰(zhàn)任務(wù)。在協(xié)調(diào)多個(gè)無人機(jī)高效地執(zhí)行任務(wù)時(shí),任務(wù)分配是需要解決的重點(diǎn)和難點(diǎn)問題之一。任務(wù)分配的最優(yōu)方案求解問題已被證實(shí)是NP難問題,求解難度隨著任務(wù)規(guī)模的增大呈指數(shù)級(jí)增加,傳統(tǒng)的完全搜索算法無能為力[4-10],常規(guī)的局部搜索算法對(duì)于計(jì)算規(guī)模大、優(yōu)化目標(biāo)多、約束限制條件苛刻的復(fù)雜問題求解效果不佳[11-16]。近年來,分布式演化算法得到了廣泛的研究和應(yīng)用[17-18],非支配排序遺傳算法(non-dominated sorted genetic algorithm, NSGA) 是一種多目標(biāo)優(yōu)化算法,該方法通過Pareto最優(yōu)解集實(shí)現(xiàn)對(duì)多個(gè)目標(biāo)優(yōu)化[19],對(duì)多目標(biāo)優(yōu)化問題具有較好的效果,但在多無人機(jī)系統(tǒng)等分布式應(yīng)用場(chǎng)景的研究較少。本文結(jié)合多無人機(jī)實(shí)際組織架構(gòu),利用多無人機(jī)Island-Master-Slave分布式模型對(duì)NSGA-III算法[20]進(jìn)行改造,設(shè)計(jì)一種針對(duì)3個(gè)以上優(yōu)化目標(biāo)的分布式高維多目標(biāo)演化優(yōu)化算法(簡(jiǎn)稱為D-NSGA-III),該算法從最大化任務(wù)完成數(shù)、最小化能源消耗、最大化收益和最小化任務(wù)完成時(shí)間4個(gè)優(yōu)化目標(biāo)入手,得到最優(yōu)解或近似最優(yōu)Pareto解集,為進(jìn)一步提升算法全局最優(yōu)解集質(zhì)量和優(yōu)化效率,在算法執(zhí)行的評(píng)估階段引入遷移策略和貪心算法。仿真試驗(yàn)表明,該算法在求解此類問題上具有一定的效果。

1 相關(guān)研究

本節(jié)主要介紹多無人機(jī)系統(tǒng)任務(wù)分配問題的形式化表述。以下為多無人機(jī)系統(tǒng)任務(wù)分配中各個(gè)元素定義[21-22]:

(3) 執(zhí)行序列:表示為S={s1,s2,…,sm},其中si(i=1,2,…,m)表示為無人機(jī)ri的執(zhí)行序列,用|si|表示無人機(jī)執(zhí)行序列的長(zhǎng)度。舉例說明s1={a1,a3,a9,a4,a6}則表示為無人機(jī)r1執(zhí)行任務(wù)的順序是任務(wù)a1,任務(wù)a3,任務(wù)a9,任務(wù)a4,任務(wù)a6,其中本文用任務(wù)出現(xiàn)的次序描述序列中的某一任務(wù),上例中s11=a1,s12=a3,s13=a9,s14=a4,s15=a6,|s1|=5。需要注意的是任務(wù)編號(hào)與任務(wù)次序無關(guān),同時(shí)每個(gè)無人機(jī)在同一時(shí)刻只能執(zhí)行一個(gè)任務(wù)。同時(shí),凡是符號(hào)表示下標(biāo)為執(zhí)行序列sij(i=1,2,…,n,j=1,|s2|,…,|si|)的都可以替換為指定的任務(wù)ak(k=1,2,…,m);

(4) 優(yōu)化目標(biāo):為評(píng)價(jià)總體任務(wù)的完成情況,設(shè)定4個(gè)優(yōu)化目標(biāo),分別為:① 最大化任務(wù)完成數(shù)量;② 最小化能源消耗;③ 最大化完成任務(wù)收益;④ 最小化時(shí)間消耗;

(5) 約束條件:其中主要分為時(shí)間約束、資源約束和功能約束。在實(shí)際應(yīng)用中,無人機(jī)的功能難以滿足所有的執(zhí)行任務(wù),因此存在特定的任務(wù)只能由某些類型的無人機(jī)執(zhí)行。

2 基于混合式架構(gòu)的D-NSGA-III的任務(wù)分配方法

2.1 Island-Master-Slave架構(gòu)

實(shí)際應(yīng)用場(chǎng)景中,綜合考慮通信帶寬、通信數(shù)據(jù)量和無人機(jī)計(jì)算能力等制約,多無人機(jī)系統(tǒng)通常采用Island-Master-Slave模型作為系統(tǒng)的組織架構(gòu)[20]。該模型中,首先將多無人機(jī)系統(tǒng)劃分為多個(gè)局部作戰(zhàn)小組,將局部作戰(zhàn)定義為Island,并進(jìn)行編號(hào),在每一個(gè)Island里按照Master-Slave模型對(duì)所屬無人機(jī)進(jìn)行組織管理,方便局部范圍的通信和計(jì)算任務(wù)分配,同時(shí)還能對(duì)內(nèi)部的Slave進(jìn)行統(tǒng)一化狀態(tài)監(jiān)控。不同的Island之間也能通過內(nèi)部的Master進(jìn)行遷移較優(yōu)解、發(fā)送更新的環(huán)境信息。同時(shí)Master還要負(fù)責(zé)遺傳算法的常規(guī)操作,例如初始化、復(fù)制、交叉、變異、選擇、演化迭代等,因此Master的作用尤其重要,通常由計(jì)算能力和通信能力較強(qiáng)的無人機(jī)充當(dāng),該構(gòu)架示意圖如圖1所示。

圖1 Island-Master-Slave模型

混合式構(gòu)架通過結(jié)合傳統(tǒng)的Master-Slave模型和Island模型進(jìn)行優(yōu)化,利用多個(gè)不同的主無人機(jī)進(jìn)行溝通,從而避免了單點(diǎn)失效的問題;同時(shí)通過對(duì)無人機(jī)進(jìn)行編隊(duì)來定向執(zhí)行任務(wù),在現(xiàn)實(shí)情況中考慮操作和管理。每個(gè)Island中運(yùn)行基于Master-Slave模型的D-NSGA-III算法,其中Island中的主無人機(jī)作為Master節(jié)點(diǎn),其他無人機(jī)都作為Slave節(jié)點(diǎn)。Master節(jié)點(diǎn)需要具有良好的計(jì)算能力和通信能力,具有對(duì)內(nèi)和對(duì)外兩個(gè)方面的職能,對(duì)內(nèi)能負(fù)責(zé)統(tǒng)籌規(guī)劃、種群初始化、迭代、交叉、變異、個(gè)體選擇等操作;對(duì)外能定期傳送給其他Island自身的環(huán)境變化信息、種群變化以及最優(yōu)解集。Slave節(jié)點(diǎn)負(fù)責(zé)收集任務(wù)環(huán)境的動(dòng)態(tài)信息,負(fù)責(zé)個(gè)體評(píng)估、信息采集、變化監(jiān)控,并將個(gè)體評(píng)估結(jié)果以及所采集、監(jiān)控的最新信息發(fā)送給Master節(jié)點(diǎn)。然后通過Master節(jié)點(diǎn)將這些信息共享到其他Island區(qū)域,使信息能夠共享,從而可以借鑒其他Island的遷移個(gè)體來優(yōu)化種群,確保每個(gè)Island優(yōu)化的問題一致。

2.2 基本框架

本節(jié)我們首先給出本文算法的流程圖,如圖2所示。

圖2 程序流程圖

其中,k為當(dāng)前迭代次數(shù);t的整數(shù)倍進(jìn)行遷移操作,maxIterN為最大迭代次數(shù)。然后描述出算法的具體流程。在這種模式下,算法步驟如下：

步驟 1各Master節(jié)點(diǎn)隨機(jī)初始化大小為N的種群P0作為父代;

步驟 2將種群Pi中的每個(gè)個(gè)體進(jìn)行分段,并將每個(gè)分段發(fā)送給相關(guān)的Slave節(jié)點(diǎn)進(jìn)行評(píng)估;

步驟 3Slave節(jié)點(diǎn)接收到Master節(jié)點(diǎn)發(fā)送的分段后進(jìn)行評(píng)估,并將評(píng)估結(jié)果返回給對(duì)應(yīng)的Master節(jié)點(diǎn);

步驟 4Master節(jié)點(diǎn)收集本區(qū)域的Slave節(jié)點(diǎn)返回的分段評(píng)估結(jié)果,然后計(jì)算每個(gè)個(gè)體的整體評(píng)估值;

步驟 5Master節(jié)點(diǎn)通過復(fù)制、交叉、變異算子產(chǎn)生子代種群;

步驟 6Master和Slave再對(duì)子代個(gè)體進(jìn)行分布式評(píng)估;

步驟 7Master節(jié)點(diǎn)對(duì)父代種群和子代種群進(jìn)行非支配排序形成h個(gè)非支配層F1,F2,…,Fh;

步驟 8Master節(jié)點(diǎn)找出前h個(gè)非支配層的個(gè)體,使得|F1∪F2∪ … ∪Fh-1|

步驟 9Master節(jié)點(diǎn)通過選擇操作決定下一代種群,若|F1∪F2∪…∪Fh|=N,則直接選擇前h層的個(gè)體作為下一代種群,否則通過參考點(diǎn)方法從臨界層Fh中選擇出N-|F1∪F2∪ … ∪Fh-1|個(gè)個(gè)體與F1，F(xiàn)2，…，F(xiàn)h-1層的個(gè)體一起作為下一代種群;

步驟 10直到超過最大迭代次數(shù)或者直至種群收斂,從而得到該種群的Pareto解集;

步驟 11以時(shí)間間隔dT1定期與其他Island交換自身環(huán)境變化信息,同時(shí)接收來自其他Island的環(huán)境變化信息,并根據(jù)變化信息調(diào)整自己的種群結(jié)構(gòu)和評(píng)估函數(shù);

步驟 12以時(shí)間間隔dT2將自己的當(dāng)前Pareto解集發(fā)送給其他Island并接收其他Island發(fā)送過來的較優(yōu)解;

步驟 13根據(jù)接收的較優(yōu)解,采用貪心策略遍歷優(yōu)化自己種群中的每個(gè)個(gè)體,進(jìn)行策略性貪心算法優(yōu)化較優(yōu)解集。其中基于參考點(diǎn)方法的選擇算子見參考文獻(xiàn)[20];

步驟 14迭代執(zhí)行步驟5～步驟13,直至滿足終止條件。

2.3 染色體編碼,交叉和變異

在遺傳算法中,本文需要將解決的實(shí)際問題進(jìn)行編碼化,常規(guī)操作就是將問題的可行解編碼為“染色體”,而這些組成可行解的元素本文稱之為“基因”,其實(shí)質(zhì)而言基因就是解集的部分。算法的最優(yōu)解取決于最后一次迭代中種群的非支配解集,算法會(huì)將種群中的染色體進(jìn)行非支配排序,從而得到Pareto解集。在具體應(yīng)用場(chǎng)景中,使用者可以根據(jù)自身的偏好和需求,在Pareto解集中選取他所側(cè)重的目標(biāo)上解質(zhì)量較好的個(gè)體作為最終合適的解,再基于該解來執(zhí)行任務(wù)。對(duì)于遺傳算法來說,染色體的概念至關(guān)重要,也是算法操作的主體。因此，染色體的編碼也影響著算法的效率優(yōu)化[22-24]。在此處本文的染色體編碼是由無人機(jī)的任務(wù)序列組成的,在保證實(shí)際任務(wù)的資源約束和時(shí)間約束的前提下,將每個(gè)無人機(jī)執(zhí)行任務(wù)序列看作一個(gè)基因元素,同時(shí)本文假設(shè)每個(gè)無人機(jī)執(zhí)行的任務(wù)數(shù)是一致的,這樣就能夠很便捷地結(jié)合約束來編碼了。比如由n個(gè)無人機(jī)組成的染色體,可采用如圖3的染色體示例。

圖3 染色體編碼示例

在任務(wù)分配問題中往往需要考慮很多約束條件,其中主要是時(shí)間約束、資源約束和功能約束。

(1) 時(shí)間約束:無人機(jī)u(i=1,2,…,m)只有在ui到達(dá)任務(wù)所在位置并在執(zhí)行時(shí)間區(qū)間[startj,endj]開始執(zhí)行時(shí)才能成功執(zhí)行任務(wù)sj,如果到來時(shí)間小于開始時(shí)間startj,則需要等待;如果在執(zhí)行時(shí)間區(qū)間內(nèi),則直接開始執(zhí)行任務(wù)。對(duì)于ui的執(zhí)行序列si,有如下約束:

(1)

當(dāng)2≤j≤|si|時(shí):

task_time(si,j-1)+

(2)

(2) 資源約束:無人機(jī)ui(i=1,2,…,m)只有在ui有能力到達(dá)任務(wù)所在位置并有對(duì)應(yīng)的資源執(zhí)行該任務(wù)時(shí)才能成功執(zhí)行任務(wù)si,如果發(fā)現(xiàn)無人機(jī)資源少于執(zhí)行該任務(wù)的資源消耗,則放棄任務(wù),反之直接執(zhí)行。對(duì)于ui的執(zhí)行序列si,有如下約束:

(3)

(3) 功能約束:在現(xiàn)實(shí)生活中,無人機(jī)的功能性結(jié)構(gòu)比較單一,難以滿足所有的執(zhí)行任務(wù),因此存在特定的任務(wù)只能由某些類型的無人機(jī)執(zhí)行。其中定義分配關(guān)系:D={d1,d2,…,dn},其中di(i=1,2,…,n)表示任務(wù)di的分配,如上圖2染色體實(shí)例,無人機(jī)ui以編碼順序依次執(zhí)行任務(wù)序列,在考慮時(shí)間和資源約束的前提下,若滿足執(zhí)行該任務(wù)的條件,才會(huì)執(zhí)行任務(wù),否則跳過該任務(wù)執(zhí)行下一個(gè)任務(wù);功能約束可在基因中得到體現(xiàn),若無人機(jī)能夠執(zhí)行該任務(wù),則該任務(wù)可以分配在該無人機(jī)的任務(wù)序列中,因此在染色體中的任務(wù)序列可能重復(fù),若當(dāng)前任務(wù)在之前已執(zhí)行則跳過,否則嘗試分配操作。例如無人機(jī)1,首先我們執(zhí)行任務(wù)5,然后執(zhí)行任務(wù)3,再執(zhí)行任務(wù)30,接著執(zhí)行任務(wù)27,若執(zhí)行某一任務(wù)時(shí)時(shí)間約束和資源約束不滿足時(shí),直接跳過當(dāng)前執(zhí)行任務(wù)執(zhí)行下一個(gè),然后到了任務(wù)9;若任務(wù)9也在無人機(jī)2的執(zhí)行序列中,則表明無人機(jī)1和無人機(jī)2同時(shí)滿足任務(wù)9的功能約束,若當(dāng)前無人機(jī)1在執(zhí)行任務(wù)9時(shí)不滿足約束條件,則由無人機(jī)2執(zhí)行任務(wù)9,反之則由無人機(jī)1執(zhí)行。在此案例中我們假設(shè)一個(gè)任務(wù)只能由某一無人機(jī)執(zhí)行。在染色體中,將任務(wù)分配給相應(yīng)可執(zhí)行它的無人機(jī),對(duì)比,從不同的角度存在如下約束:

① 從無人機(jī)的角度看,對(duì)于i=1,2,…,m,有

(4)

該約束描述了根據(jù)無人機(jī)ui的功能,它能夠執(zhí)行任務(wù)au1,au2…,aub。

② 從任務(wù)的角度看,對(duì)于j=1,2,…,n,有

(5)

該約束描述了根據(jù)任務(wù)ai對(duì)無人機(jī)功能的要求,可以將其分配給任何{sj1,sj2,…,sjc}中的智能體執(zhí)行。

該編碼方法的優(yōu)點(diǎn)是所有個(gè)體編碼長(zhǎng)度都是固定的,無需在評(píng)估個(gè)體時(shí)考慮無人機(jī)的功能約束,簡(jiǎn)化了評(píng)估過程,而且易于對(duì)染色體進(jìn)行初始化、交叉和變異等常規(guī)操作。

在本文中通過隨機(jī)初始化種群,基于上面的編碼,Master節(jié)點(diǎn)根據(jù)相應(yīng)的無人機(jī)ui的功能約束來生成可執(zhí)行任務(wù)集合{si1,si2,…,sjc},然后生成隨機(jī)序列,作為染色體的第i部分。

種群的交叉使用單點(diǎn)雜交算子,隨機(jī)選擇兩個(gè)個(gè)體分別為x=x1x2…xm作為父親,y=y1y2…ym作為母親,然后生成一個(gè)1到m的隨機(jī)數(shù)k,進(jìn)行交換得到兩個(gè)子代個(gè)體x′=x1x2…xkyk+1yk+2…ym和y′=y1y2…ykxk+1xk+2…xm。

種群的變異是為了保證解的多樣性以及避免局部最優(yōu),在進(jìn)化算法中變異一般較少,采用一個(gè)參數(shù)來控制個(gè)體的變異,一般操作就是Master節(jié)點(diǎn)再生成一個(gè){si1,si2,…,sjc}的隨機(jī)排列替換原有染色體的第i部分。

2.4 評(píng)估

在本節(jié)中首先給出無人機(jī)完成任務(wù)的4個(gè)評(píng)價(jià)指標(biāo),即優(yōu)化目標(biāo),然后根據(jù)目標(biāo)函數(shù)給出評(píng)估函數(shù)。

(1) 目標(biāo):針對(duì)不同的任務(wù)分配問題必將存在不同的優(yōu)化目標(biāo),在本文中我們主要針對(duì)以下4個(gè)目標(biāo)進(jìn)行研究。

① 最大化任務(wù)完成數(shù):

(6)

式中,當(dāng)di≠NULL為真時(shí)返回結(jié)果1,否則返回0。

② 最小化資源消耗:

(7)

③ 最大化任務(wù)收益:

(8)

④ 最小化時(shí)間:

(9)

式中,time_cost(si,|si|)表示無人機(jī)ri執(zhí)行si序列中的任務(wù)所需花費(fèi)的時(shí)間。

當(dāng)j=1時(shí)

time_cost(si,1)=move_time(pri,psi1)+tsi1

(10)

當(dāng)j=2，3，…，|si|時(shí)

time_cost(si, j)=max{task_time(si,j-1)+

move_time(psi(j-1),psij),startsij}+tsij

(11)

(2) 評(píng)估函數(shù):為了方便對(duì)個(gè)體進(jìn)行以上4個(gè)目標(biāo)的評(píng)估,將目標(biāo)全部轉(zhuǎn)化為最小化的函數(shù)形式,具體步驟如下。

步驟 1執(zhí)行任務(wù)完成數(shù)目標(biāo)函數(shù):

(12)

式中,xi=i1，i2,…,ib；g1(xi)計(jì)算方法為

(13)

(14)

步驟 2執(zhí)行任務(wù)能源消耗目標(biāo)函數(shù):

(15)

式中,max_resource表示為無人機(jī)配備的最大資源量;g3(xi)表示為

(16)

步驟 3執(zhí)行任務(wù)收益目標(biāo)函數(shù):

(17)

式中,

(18)

步驟 4執(zhí)行時(shí)間目標(biāo)函數(shù):

(19)

式中,max_time是任務(wù)完成的最長(zhǎng)時(shí)間;g4(xi)表示為

(20)

通過對(duì)上面目標(biāo)的描述然后將其轉(zhuǎn)換為評(píng)估函數(shù)進(jìn)行個(gè)體評(píng)估,可以靈活地將約束條件糅合在染色體個(gè)體之間。時(shí)間約束和資源約束由函數(shù)h(iw)融合。通過目標(biāo)值最小化轉(zhuǎn)換,可以簡(jiǎn)單的得出個(gè)體的每個(gè)目標(biāo)值的優(yōu)化情況。

2.5 遷移策略和貪心算法

為了提升種群的多樣性以及加快搜索速度,本文通過交換不同Island的較優(yōu)個(gè)體遷移到其他的Island,通過遷移策略來增加每個(gè)Island的優(yōu)化能力。若遷移個(gè)體支配種群中某個(gè)個(gè)體,會(huì)執(zhí)行替換;若遷移個(gè)體未支配種群中某個(gè)個(gè)體,會(huì)根據(jù)遷移個(gè)體的每段染色體片段對(duì)種群個(gè)體進(jìn)行貪心替換,即遷移個(gè)體中某段染色體中優(yōu)于原先染色體的相應(yīng)片段,則進(jìn)行替換操作。

遷移策略偽代碼輸入:個(gè)體x輸出:優(yōu)化后的個(gè)體xMaster節(jié)點(diǎn)執(zhí)行:1for 每個(gè)個(gè)體j ∈Pareto解集x do2 if dominate(x, j)3 Pi+1F1∪F2∪…∪Fh∪x4 else5 Greedy(x,j);6 end if7end for8return x

3 實(shí)驗(yàn)結(jié)果與分析

本節(jié)將通過遷移策略實(shí)驗(yàn)與多目標(biāo)粒子群優(yōu)化(multi-object particle swarm optimization, MOPSO)算法的對(duì)比實(shí)驗(yàn)和結(jié)果論證的方法來展示本文所提方法的有效性。

本文實(shí)驗(yàn)環(huán)境為:Window 7操作系統(tǒng)64位專業(yè)版,英特爾i7-7600U CPU,主頻2.80 GHz,內(nèi)存8 G,編程環(huán)境為Visual Studio 2010。

首先,隨機(jī)生成相關(guān)的智能體和任務(wù)數(shù)據(jù),為了方便進(jìn)行對(duì)比實(shí)驗(yàn),在準(zhǔn)備階段隨機(jī)生成測(cè)試數(shù)據(jù)。為了模擬實(shí)驗(yàn),假設(shè)每個(gè)無人機(jī)的初試位置為pri=(x,y)(i=1，2,…，m),x和y為[0,100)之間的隨機(jī)整數(shù);最早可以執(zhí)行時(shí)間startai為[0,100]之間的隨機(jī)數(shù),最晚可開始執(zhí)行時(shí)間endai為[startai,150)之間的隨機(jī)數(shù);執(zhí)行任務(wù)需消耗的時(shí)間tai為[1,10)之間的隨機(jī)數(shù);執(zhí)行任務(wù)需消耗的資源reai為[0,100)之間的隨機(jī)數(shù);執(zhí)行任務(wù)的收益eai為[0,1)之間的隨機(jī)數(shù)。對(duì)于功能約束,本文假設(shè)每個(gè)任務(wù)一定有一個(gè)或多個(gè)無人機(jī)可以執(zhí)行它。在進(jìn)行一定次數(shù)的迭代后,全局的無人機(jī)和任務(wù)發(fā)生變化。通過變化信息我們對(duì)染色體進(jìn)行相應(yīng)的變更。為便于實(shí)驗(yàn)開展,假設(shè)傳輸?shù)臅r(shí)間成本和資源成本與距離成線性關(guān)系。

本文中實(shí)驗(yàn)源碼主要基于Chian的NSGA-III的實(shí)現(xiàn)版本進(jìn)行二次開發(fā),詳見參考文獻(xiàn)[25]。在本文的驗(yàn)證試驗(yàn)中,設(shè)置Island數(shù)量為4(可根據(jù)需要設(shè)定),設(shè)置每個(gè)島嶼的演變迭代次數(shù)設(shè)為100次,雜交概率為1.0,突變率設(shè)為0.2,貪婪策略中的精度參數(shù)ε為0.001,詳細(xì)參數(shù)設(shè)定詳見表1。

表1 實(shí)驗(yàn)參數(shù)設(shè)定

其中,對(duì)于求解問題的參數(shù)(如無人機(jī)數(shù)目、任務(wù)數(shù)目等),主要是參考真實(shí)應(yīng)用情況,選取具有代表性的設(shè)置;對(duì)于演化算法的參數(shù)(如交叉概率、變異概率、迭代次數(shù)等),主要是根據(jù)實(shí)驗(yàn)測(cè)試情況選取優(yōu)化能力較好的設(shè)置。此外,這些參數(shù)的設(shè)置也參考了同領(lǐng)域的其他研究工作,如文獻(xiàn)[21-22]。在實(shí)際情況中,也可根據(jù)具體要求更改本文算法參數(shù)的設(shè)置。

3.1 遷移策略實(shí)驗(yàn)

為驗(yàn)證遷移策略的算法性能,本文在設(shè)置相同的初試數(shù)據(jù)和環(huán)境變更信息的條件下,對(duì)是否使用遷移策略的兩種情況進(jìn)行對(duì)比,設(shè)定遷移數(shù)量為固定值10,改變無人機(jī)和任務(wù)規(guī)模進(jìn)行對(duì)比實(shí)驗(yàn)。由于篇幅有限無法呈現(xiàn)所有解的情況,對(duì)于相近的數(shù)據(jù)(即兩條數(shù)據(jù)若在f1～f4上相差均在0.05內(nèi))僅取其一呈現(xiàn)在表格中。圖4分別給出采用遷移策略和非遷移條件下,設(shè)置(m=20,n=50)和(m=50，n=200)的對(duì)比結(jié)果。

其中,非遷移算法指不采用分布式架構(gòu),4個(gè)不同地理分布的無人機(jī)編隊(duì)各自獨(dú)立執(zhí)行原NSGA-III分別優(yōu)化4個(gè)目標(biāo)。而遷移算法則指本文提出的算法,將每個(gè)無人機(jī)編隊(duì)形成一個(gè)Island,Island之間通過遷移學(xué)習(xí)來協(xié)作優(yōu)化解的質(zhì)量。當(dāng)m=20,n=50時(shí),采用遷移策略的算法共有11個(gè)解,非遷移算法共有7個(gè)解,采用遷移策略的算法多于非遷移算法4個(gè)解。當(dāng)m=50,n=200時(shí),遷移策略算法共有6個(gè)解,非遷移算法共有6個(gè)解,二者的解基本一致。由此可得,遷移算法的解較優(yōu)于非遷移算法,更能突出其多樣性。

圖4 固定遷移值實(shí)驗(yàn)結(jié)果對(duì)比

3.2 與MOPSO算法的對(duì)比實(shí)驗(yàn)

粒子群優(yōu)化(particle swarm optimization,PSO)算法具有搜索速度快、效率高、編碼簡(jiǎn)單等優(yōu)點(diǎn),常用于求解優(yōu)化問題。MOPSO算法[26]將只能用于求解單目標(biāo)優(yōu)化問題的PSO的優(yōu)點(diǎn)擴(kuò)展到多目標(biāo)優(yōu)化問題上,它繼承了單目標(biāo)PSO的諸多優(yōu)點(diǎn),在多目標(biāo)優(yōu)化問題上具有較好的效果,因此本文將與MOPSO進(jìn)行實(shí)驗(yàn)對(duì)比。本文結(jié)合具體案例,將無人機(jī)任務(wù)分配轉(zhuǎn)化為半連續(xù)編碼。其中位置信息的整數(shù)部分為無人機(jī)的ID,粒子維數(shù)對(duì)應(yīng)于任務(wù)ID,詳細(xì)編碼信息可參考論文[27]。本文算法與MOPSO算法的對(duì)比實(shí)驗(yàn)結(jié)果如圖5所示。

圖5 不同r下的實(shí)驗(yàn)結(jié)果

問題規(guī)模設(shè)定為(m=20,n=50)、(m=50,n=200),遷移數(shù)量設(shè)定為5。當(dāng)m=20,n=50時(shí),采用本文的算法共有7個(gè)解,MOPSO算法共有5個(gè)解,解的質(zhì)量相當(dāng)(相互之間沒有支配關(guān)系)。當(dāng)m=50,n=200時(shí),采用本文的算法共有5個(gè)解,MOPSO算法共有3個(gè)解,解的質(zhì)量相當(dāng)?？梢钥闯?本文的算法在解的多樣性方面優(yōu)于MOPSO算法。

4 結(jié) 論

為解決大規(guī)模多無人機(jī)在混合分布式構(gòu)架下的任務(wù)分配問題,本文提出了一種基于分布式高維多目標(biāo)演化算法和遷移策略的方法,主要針對(duì)完成任務(wù)過程中,最大化任務(wù)完成數(shù)、最小化能源消耗、最大化任務(wù)收益和最小化時(shí)間4個(gè)優(yōu)化目標(biāo)進(jìn)行優(yōu)化。該算法利用演化算法的種群多樣性提高全局的搜索能力,通過遷移策略和貪心算法來改善染色體的多樣化信息和收斂速度,提高局部的搜索能力。通過與非遷移策略的實(shí)驗(yàn)對(duì)比,可以得出采用遷移策略后解的多樣性更加豐富,從而使任務(wù)分配的解集質(zhì)量更高。