基于D-NSGA-III算法的無人機群高維多目標任務分配方法

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

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

0 引 言

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

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

1 相關研究

本節主要介紹多無人機系統任務分配問題的形式化表述。以下為多無人機系統任務分配中各個元素定義[21-22]:

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

(4) 優化目標:為評價總體任務的完成情況,設定4個優化目標,分別為:① 最大化任務完成數量;② 最小化能源消耗;③ 最大化完成任務收益;④ 最小化時間消耗;

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

2 基于混合式架構的D-NSGA-III的任務分配方法

2.1 Island-Master-Slave架構

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

圖1 Island-Master-Slave模型

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

2.2 基本框架

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

圖2 程序流程圖

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

步驟 1各Master節點隨機初始化大小為N的種群P0作為父代;

步驟 2將種群Pi中的每個個體進行分段,并將每個分段發送給相關的Slave節點進行評估;

步驟 3Slave節點接收到Master節點發送的分段后進行評估,并將評估結果返回給對應的Master節點;

步驟 4Master節點收集本區域的Slave節點返回的分段評估結果,然后計算每個個體的整體評估值;

步驟 5Master節點通過復制、交叉、變異算子產生子代種群;

步驟 6Master和Slave再對子代個體進行分布式評估;

步驟 7Master節點對父代種群和子代種群進行非支配排序形成h個非支配層F1,F2,…,Fh;

步驟 8Master節點找出前h個非支配層的個體,使得|F1∪F2∪ … ∪Fh-1|

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

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

步驟 11以時間間隔dT1定期與其他Island交換自身環境變化信息,同時接收來自其他Island的環境變化信息,并根據變化信息調整自己的種群結構和評估函數;

步驟 12以時間間隔dT2將自己的當前Pareto解集發送給其他Island并接收其他Island發送過來的較優解;

步驟 13根據接收的較優解,采用貪心策略遍歷優化自己種群中的每個個體,進行策略性貪心算法優化較優解集。其中基于參考點方法的選擇算子見參考文獻[20];

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

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

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

圖3 染色體編碼示例

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

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

(1)

當2≤j≤|si|時:

task_time(si,j-1)+

(2)

(2) 資源約束:無人機ui(i=1,2,…,m)只有在ui有能力到達任務所在位置并有對應的資源執行該任務時才能成功執行任務si,如果發現無人機資源少于執行該任務的資源消耗,則放棄任務,反之直接執行。對于ui的執行序列si,有如下約束:

(3)

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

① 從無人機的角度看,對于i=1,2,…,m,有

(4)

該約束描述了根據無人機ui的功能,它能夠執行任務au1,au2…,aub。

② 從任務的角度看,對于j=1,2,…,n,有

(5)

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

該編碼方法的優點是所有個體編碼長度都是固定的,無需在評估個體時考慮無人機的功能約束,簡化了評估過程,而且易于對染色體進行初始化、交叉和變異等常規操作。

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

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

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

2.4 評估

在本節中首先給出無人機完成任務的4個評價指標,即優化目標,然后根據目標函數給出評估函數。

(1) 目標:針對不同的任務分配問題必將存在不同的優化目標,在本文中我們主要針對以下4個目標進行研究。

① 最大化任務完成數:

(6)

式中,當di≠NULL為真時返回結果1,否則返回0。

② 最小化資源消耗:

(7)

③ 最大化任務收益:

(8)

④ 最小化時間:

(9)

式中,time_cost(si,|si|)表示無人機ri執行si序列中的任務所需花費的時間。

當j=1時

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

(10)

當j=2，3，…，|si|時

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

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

(11)

(2) 評估函數:為了方便對個體進行以上4個目標的評估,將目標全部轉化為最小化的函數形式,具體步驟如下。

步驟 1執行任務完成數目標函數:

(12)

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

(13)

(14)

步驟 2執行任務能源消耗目標函數:

(15)

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

(16)

步驟 3執行任務收益目標函數:

(17)

式中,

(18)

步驟 4執行時間目標函數:

(19)

式中,max_time是任務完成的最長時間;g4(xi)表示為

(20)

通過對上面目標的描述然后將其轉換為評估函數進行個體評估,可以靈活地將約束條件糅合在染色體個體之間。時間約束和資源約束由函數h(iw)融合。通過目標值最小化轉換,可以簡單的得出個體的每個目標值的優化情況。

2.5 遷移策略和貪心算法

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

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

3 實驗結果與分析

本節將通過遷移策略實驗與多目標粒子群優化(multi-object particle swarm optimization, MOPSO)算法的對比實驗和結果論證的方法來展示本文所提方法的有效性。

本文實驗環境為:Window 7操作系統64位專業版,英特爾i7-7600U CPU,主頻2.80 GHz,內存8 G,編程環境為Visual Studio 2010。

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

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

表1 實驗參數設定

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

3.1 遷移策略實驗

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

其中,非遷移算法指不采用分布式架構,4個不同地理分布的無人機編隊各自獨立執行原NSGA-III分別優化4個目標。而遷移算法則指本文提出的算法,將每個無人機編隊形成一個Island,Island之間通過遷移學習來協作優化解的質量。當m=20,n=50時,采用遷移策略的算法共有11個解,非遷移算法共有7個解,采用遷移策略的算法多于非遷移算法4個解。當m=50,n=200時,遷移策略算法共有6個解,非遷移算法共有6個解,二者的解基本一致。由此可得,遷移算法的解較優于非遷移算法,更能突出其多樣性。

圖4 固定遷移值實驗結果對比

3.2 與MOPSO算法的對比實驗

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

圖5 不同r下的實驗結果

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

4 結 論

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