基于KnCMPSO算法的異構無人機協同多任務分配

王 峰 黃子路 韓孟臣 邢立寧 王 凌

無人機(Unmanned aerial vehicle,UAV)以其體積輕巧、隱身性能好、續航時間長、可回收重復使用等優勢逐漸成為空中作戰的主角.相較于有人機,無人機能夠在偏遠、危險或者人員不可達的極端環境中,自主完成一些重要的諸如監測、搜救、偵察、打擊等任務[1].無人機協同作戰是指在實際的戰場中,多種類型的無人機充分發揮各自優勢,協同完成一項軍事任務.早期的無人機協同作戰由于作戰場景簡單、任務類型單一、任務難度較低,僅通過人工決策就能確定各無人機的作戰序列.然而隨著作戰場景逐漸復雜、任務類型逐漸多樣化、無人機智能化水平逐漸提高,僅靠人工決策很難充分挖掘各種無人機的特性并發揮無人機系統的協同作戰優勢.現實世界中的無人機往往是異構的,異構無人機指的是多種類型的無人機(偵察機、戰斗機等)[2],為了提高異構無人機執行任務的效率,提升異構無人機系統的自主性,開展異構無人機協同多任務分配問題研究具有十分重要的意義[3].

為了高效地制定無人機的任務分配計劃、科學地控制無人機,需要對無人機協同多任務分配問題建立合適模型.

在模型的約束條件研究方面,文獻[4]充分考慮了無人機執行任務之間的時序和多機協同等約束條件,將無人機分配問題構建成為協同多任務分配問題模型.文獻[5]提出以無人機自身性能約束、協同約束和實際三維復雜環境構建約束的無人機任務分配模型.然而上述模型中所考慮的各無人機都具有偵察、打擊、評估三種能力,不屬于異構無人機.在實際問題中,由于不同無人機的能力有差異,無法用一類無人機完成所有任務.因此通常選擇采用多架異構無人機組成集群來共同完成任務,解決不同無人機的能力限制.一些學者進一步對異構無人機協同任務分配模型提出了新的約束條件,如文獻[6]考慮無人機資源消耗、完成任務資源需求等約束,文獻[7]考慮任務優先級等約束,文獻[8]考慮無人機運動學等約束.

在模型的優化目標研究方面,目前大部分研究工作建立的都是以最小化無人機飛行距離的單目標模型[9],也有一些學者嘗試構建無人機任務分配的多目標優化模型.如文獻[10]提出同時考慮無人機任務收益、任務執行時間和任務執行代價的多目標模型,文獻[11]以無人機總飛行距離和任務完成時間為優化目標構建了多目標優化模型.

在無人機協同多任務分配模型的求解方面,近年來也有部分學者進行了深入研究[12],其中粒子群算法[13]作為群智能算法中的經典算法,具有操作簡單、收斂能力強等特點,可以很好地求解無人機協同任務分配問題.文獻[14]將多種目標函數進行加權,利用離散粒子群算法對構建的模型進行求解,但是采用的交叉變異操作方式較為簡單,求解效率有待進一步提升.文獻[10]利用多目標量子粒子群算法對無人機任務分配問題進行求解,但是算法編碼較為復雜,計算量比較大.文獻[15]提出采用改進的量子粒子群算法對無人機任務分配問題進行求解,但是算法需要額外計算平均歷史最優位置而且設定的參數較多.近年來,隨著異構無人機協同多任務分配模型研究的深入,一些學者針對異構無人機協同多任務分配問題的求解算法進行了探討.如文獻[11]提出一種基于協同進化的混合變量多目標粒子群優化算法,但其更新策略過于簡單且隨機性較大,隨著問題規模的增大,求解效率將逐漸下降.文獻[16]提出改進的多目標量子粒子群算法,但其重組方式較復雜,求解效率不高.文獻[17]提出改進的遺傳算法,但該算法主要針對單目標優化模型,無法很好地求解多目標異構無人機任務分配模型.

異構無人機協同多任務分配模型有多個復雜的約束條件,因此,如何處理不同類型的約束條件,以提高算法的搜索效率,是求解異構無人機協同多任務分配模型的重要問題.近年來,一些學者針對不同類型的應用問題,研究采用不同約束處理方法進行求解.求解方法大致可以分為基于罰函數(Prnalty function,PF)的約束處理方法[18-20]、基于可行性原則的約束處理方法(Stochastic ranking,SR)[21-22]、基于隨機排序的約束處理方法 (Feasibility rule,FR)[23]和基于多目標的約束處理方法[24]4 類 .也有一些學者就約束處理技術理論方面提出了一些新的改進,如基于分級方式的約束處理準則[25]、基于集成方式的約束處理準則[26]或將約束轉化為新的優化目標[27].而在異構無人機協同多任務分配模型中,存在無人機類型約束、任務執行時序約束及多機協同約束等多種復雜約束,上述方法無法直接用于求解.

為了使構建的模型更加符合現實場景,現有對無人機任務分配問題的研究工作均在約束條件或目標函數上對模型做出了改進,但是大部分研究工作均假設無人機的觀測時間和一次彈藥消耗都是充足的,然而在實際作戰過程中,當偵察機一次觀測時間過長時,存在被敵方發現乃至擊斃的風險,戰斗機一次發射的彈藥數量也是有限的.因此本文在現有研究工作[11]的基礎上,進一步考慮無人機單次任務最大觀測時間約束和無人機單次任務最大彈藥約束,建立基于多種約束條件的異構無人機協同多任務分配問題模型.

上述模型不僅包含混合變量,同時還存在多個復雜的約束條件,問題的求解難度較大,傳統的多目標優化算法并不能有效地求解上述模型.同其他智能優化算法相比,粒子群算法具有計算簡單、魯棒性好、搜索能力強且收斂速度快的特點,在求解多約束多目標異構無人機協同任務分配問題時,具有較大優勢.為了高效求解該模型,本文提出了一種基于拐點的協同多目標粒子群優化算法(Knee point based coevolution multi-objective particle swarm optimization,KnCMPSO).本文的主要貢獻如下:

1)針對模型包含混合變量以及多種約束的特點,采用基于三維矩陣的混合編碼方式以及基于約束處理的初始化方法,有效避免不可行解的生成,提高算法的搜索效率.

2)采用協同進化策略,將多目標優化問題轉為多個單目標優化問題,通過子種群間合作式協同降低求解復雜度,通過子種群內競爭式協同進化加快算法收斂,進一步提出基于學習的粒子更新策略來提升算法的收斂性,粒子不僅學習父代優秀個體,也學習精英個體或全局最優個體,可以實現更快收斂.

3)提出基于區間擾動的局部搜索策略來提升算法的多樣性,進一步提出基于拐點的學習策略來更新外部檔案集,加強了算法對帕累托前沿中心面的搜索,在保證收斂性的同時提升算法的多樣性,使得算法能搜索到更多的可行任務分配結果.

本文首先對無人機協同多任務分配問題建模,然后介紹基于拐點的協同多目標粒子群優化算法,接著設計仿真實例來驗證算法的有效性,最后進行總結和展望.

1 異構無人機協同多任務分配模型

1.1 問題描述

表1 展示了模型中涉及的各種符號以及相應說明.

表1 符號說明Table 1 Symbol description

異構無人機協同多任務分配問題描述如下: 假設在某二維已知區域內發現了NT個敵方目標,則目標集合T可表示為T={T1,T2,···,TNT}.無人機系統需要對每個目標依次執行三種不同類型的任務,分別為觀測、打擊、打擊結果評估,即三種任務之間存在時序關系.任務類型集合M可以表示為M={Observe,Attack,Evaluate},因此模型中需要調度的總任務數量NM的值為NM=3×NT.異構無人機系統中的無人機可以被分為偵察機和戰斗機兩種類型,其中用于執行觀測和打擊結果評估任務的偵察無人機有S架,執行打擊任務的戰斗無人機有A架,則無人機集合表示為U={U1,U2,···,US,US+1,···,US+A}.無人機執行不同的任務需要消耗一定的資源量.同一個目標上的相同任務可以由多臺無人機協同完成.當所有目標上的所有任務執行完成,整個軍事作戰任務順利完成.

1.2 目標函數

為了能夠更加合理地對無人機任務分配的結果進行評估,本文的模型采用無人機總飛行距離和任務完成時間兩個目標函數.無人機的總飛行距離為無人機系統中所有參與任務的無人機飛行距離之和,任務完成時間為整個作戰任務中最后一個完成任務的無人機的總飛行時間.根據以上定義,本文模型的計算公式如下:

無人機航程和其消耗資源數緊密相關,無人機飛行總航程越短,代表無人機執行任務時消耗的資源越少.然而,飛行總航程最短并不一定能保證軍事任務的完成時間最短.例如,一些無人機可能在同一目標上被分配較多的任務以滿足所有無人機飛行總航程最短,而這會導致該無人機完成所有任務的時間變長,從而使得整個軍事任務完成時間變長.因此,無人機飛行總航程和任務完成時間兩個指標存在一定的沖突.

1.3 約束條件

為了能夠對多臺無人機協同完成同一項軍事任務進行更有效的刻畫,本文在文獻[11]基礎上,進一步考慮無人機單次任務最大觀測時間約束和無人機單次任務最大彈藥約束來建立異構無人機多任務分配模型,其所包含的約束條件如下.

1)無人機類型約束.由于無人機的異構性,不同類型的任務只能由特定類型的無人機完成.

式中,i表示無人機編號,j表示目標編號,k表示任務編號.當k∈{Observe,Evaluate}時,i ∈{1,2,···,S}; 當k ∈{Attack}時,i∈{S+1,···,S+A}.

2)任務執行時序約束.對于同一個目標,無人機系統要先對其執行觀測任務,然后對其執行打擊任務,最后才能夠執行打擊結果評估任務.因此對同一個目標上的三種任務需滿足如下時序約束.

3)最大攜帶彈藥數目約束.戰斗無人機只能攜帶一定數目的彈藥.因此戰斗無人機執行打擊任務消耗的彈藥數要小于其最大攜帶彈藥數目.

4)單次最大偵察時間.為了避免暴露時間過長以至于被敵方發現,偵察無人機在執行觀測任務和打擊結果評估任務時存在最大偵察時間.

5)單次最大發射彈藥數.戰斗無人機在執行對某一個目標上的打擊任務時,由于自己性能的限制只能發射一定數量的彈藥.

6)多機協同約束.為了保證軍事任務順利完成,針對不同目標的不同類型的任務需要分配給不同數量的無人機協同執行.其中對同一個目標的觀測和打擊結果評估任務至少需被一架偵察無人機執行,而打擊任務需要分配給至少一架戰斗無人機執行.

7)完成任務資源需求約束.執行相同任務的所有無人機資源消耗總量需要大于等于完成當前任務所需要的資源總量.

無人機執行觀測任務和打擊結果評估任務需要消耗一定的時間資源,所有執行同一任務的偵察無人機偵察總時間需要滿足完成任務所需總時間.

無人機執行打擊任務需要消耗一定的彈藥資源,所有執行同一任務的戰斗無人機消耗彈藥數量需要滿足完成任務所需總彈藥數量.

8)最大航程約束.假設無人機i執行的任務序列為Mi=(M1,M2,···,Mm),Dis(Mk,Mk+1) 表示無人機執行第k個任務到第k+1 個任務的飛行距離,M axDisi表示無人機最大飛行距離,則有:

上述異構無人機協同多任務分配模型所包含的決策變量既有表示任務分配結果的離散變量,也有表示無人機資源消耗的離散和連續變量,這些混合變量導致問題解空間變得更加復雜,難以進行有效搜索.同時模型還包含多個復雜的約束條件,既有不等式約束,也有等式約束,這些約束條件進一步使得問題對應的解空間變得不規則,增加了算法搜索到可行解的難度.

由于現有的算法無法對本文提出的多約束多目標異構無人機協同多任務分配模型進行有效求解,本文提出一種基于拐點的協同多目標粒子群優化算法求解無人機協同多任務分配問題.

2 基于拐點的協同多目標粒子群算法

本文提出的基于拐點的協同多目標粒子群優化算法KnCMPSO,主要通過設計基于約束處理的初始化策略、協同進化策略、基于學習的粒子更新策略、基于區間擾動的局部搜索策略及基于拐點的外部檔案集更新策略提升算法的求解性能.

算法流程如圖1 所示.首先,采用子種群間合作、子種群內競爭的協同進化策略,將多目標優化問題轉為各個目標維度上的單目標優化問題,降低了問題的求解復雜度;其次,在各個子種群內部,針對無人機協同多任務分配問題包含混合變量以及多種約束的特點,以二進制交叉方法為基礎,設計了基于學習的粒子更新策略和基于區間擾動的局部搜索策略,提升了算法的求解性能;最后,引入基于拐點的學習策略來更新外部檔案集,增強了算法對帕累托前沿中心面的搜索,在保證收斂性的同時增強了算法的多樣性.

圖1 KnCMPSO 算法流程圖Fig.1 Flowchart of KnCMPSO algorithm

2.1 編碼以及初始化策略

在使用粒子群算法求解無人機協同多任務分配問題時,首先需要解決的問題就是如何對粒子中個體進行編碼操作.為了處理模型中的混合變量以及各種約束條件,本文將采用基于三維矩陣的混合編碼方式對決策變量進行編碼.如表2 所示,編碼矩陣中的第1 行是目標編號,每一個目標編號在粒子的第1 行都會出現3 次,按照出現先后順序分別代表了在此目標上執行的觀測任務、打擊任務、打擊結果評估任務.第2 行是無人機編號,代表了執行此任務的無人機.由于目標編號在矩陣出現的先后順序代表了不同的任務類型,因此無人機編號(無人機類型) 需要根據目標編號所代表的任務類型來設置.第3 行是無人機執行對應任務的資源消耗,其中偵察機消耗的資源為時間,是連續變量,戰斗機消耗的資源為彈藥,是離散變量.

表2 粒子編碼方式Table 2 Particle encoding scheme

基于三維矩陣的混合編碼方式不但能夠很好地描述目標、任務、執行任務的無人機以及無人機資源消耗的對應關系,而且能夠直觀地表示出各臺無人機執行任務的先后順序,方便后續初始化操作.雖然每個個體位置向量編碼長度仍然可能不同,但是所有目標在編碼中出現的次數是固定的,也就是說所有粒子的編碼矩陣中第1 行目標編號的長度是固定的,這就大大降低了問題的求解難度.

在上述編碼方式的基礎上,本文提出基于約束處理的初始化策略,具體過程如算法1 所示.

表3 和表4 為初始化策略示例說明,表3 為目標隊列集合,表4 為無人機集合.首先,建立一個4×N的目標矩陣,將所有的目標依次放入矩陣中的第1 行,每個目標上的任務按照觀測任務、打擊任務和打擊結果評估任務的順序依次排列到矩陣的第2、3、4 行.無人機按照偵察機和戰斗機類別不同分別放入兩個隊列當中;然后,粒子將按照從左往右的順序依次初始化位置向量.每次均從目標矩陣中隨機選擇一個目標,并將目標中尚未完成的任務取出進行分配.根據任務類型選擇相應的無人機類型,并設置無人機對應的資源消耗.如果此任務上的所有無人機的資源消耗量與完成此任務的資源需求量相等則代表當前任務執行完畢.當某個目標對應的三種任務全部執行完畢代表此目標的分配全部完成;最后,當所有的目標都分配完成之后,得到的粒子就是一個滿足所有約束條件的可行解,且可以有效避免出現由于某個任務的前置任務未完成而導致的死鎖狀態[28].

表3 目標隊列集合Table 3 Target formation collection

表4 無人機集合Table 4 Drone collection

算法1.基于約束處理的初始化策略

2.2 協同進化策略

協同進化是生物學中一種重要的進化機制 , 可促進物種之間的信息交流并提高物種進化效率.協同進化策略包括了合作式協同進化策略和競爭式協同進化策略兩種類型[29].已有研究表明,在優化算法中采用協同進化策略能夠降低問題的求解難度,加快算法的搜索效率,提升算法的性能[30].

KnCMPSO 算法采用了子種群間合作式協同進化、子種群內競爭式協同進化的策略來生成新個體.子種群合作式協同進化采用子問題與子種群一一對應的方式,將多目標優化問題轉為每一個維度上的單目標優化問題.子種群內競爭式協同進化則采用子種群內的全局最優個體和外部檔案集中的精英個體相互競爭的方式來選擇較優的個體,并利用該個體對子種群生成過程進行引導,避免種群向極端點靠近.其整體流程如圖2 所示.針對一個M維的多目標優化問題,算法生成M個子種群,每個子種群分別針對每一個維度上的目標進行優化.同時利用外部檔案集Archive 的方式保存迭代過程中尋找到的所有種群的非支配解,從而實現種群之間搜索信息的共享.

圖2 種群間合作種群內競爭的協同進化策略Fig.2 Coevolution strategy of inter-population cooperation and intra-population competition

子種群間合作式協同進化是指將原始問題分別看作某一個維度上的單目標優化問題,同時利用外部檔案集保存迭代過程中的所有種群的非支配解.由于子問題與子種群一一對應,子種群平行且單獨地進化,降低了問題的求解復雜度.在傳統的多目標問題中,當兩個個體互不支配的時候,無法確定哪一個更優,導致算法無法選擇個體最優粒子和全局最優粒子對當前個體進行更新操作.采用子種群間合作式協同進化可以有效避免上述問題.每個子種群根據當前維度目標值的大小來進行個體最優和全局最優的選擇,實現在該維度上的求解.子種群內競爭式協同進化是指通過各個子種群中的全局最優個體和外部檔案集中的精英個體之間競爭,獲取

對子種群中的其他個體的引導權,具體過程如算法2 所示.

算法2.基于競爭的個體更新策略

如圖3 所示,假設子種群1 的優化目標為f1,Gbest為子種群1 在迭代次數為t時候全局最優個體,待更新的個體為S.首先,在外部檔案集中隨機選擇一個精英個體A.計算個體A和S之間的余弦相似度;然后,與Gbest和S之間的余弦相似度進行比較.當A與S之間的余弦相似度更小時,說明個體A對個體S的引導能力更強,更有利于算法的收斂,因此選擇A作為S的全局學習對象;反之,選擇Gbest作為S的全局學習對象.

圖3 競爭式協同進化策略Fig.3 Competitive coevolution strategy

上述兩種協同進化策略不僅能降低問題的求解復雜度,而且能有效提高算法的收斂速度.

2.3 基于學習的粒子更新策略

在標準粒子群算法中,種群中的個體通過對個體最優粒子和全局最優個體進行學習來更新速度,再通過粒子的當前位置和速度來更新粒子的狀態.本文模型中包含了混合變量,并且約束條件較多,按照標準粒子群的更新方式將很難生成滿足約束的粒子,所以本文將對粒子的更新方式進行改進,不再使用粒子速度這一個概念,粒子在更新的時候只通過向優秀個體學習的方式來更新粒子的狀態.基于此,在KnCMPSO 中提出了一種基于學習的粒子更新策略,具體過程如算法3 所示.

算法3.基于學習的粒子更新策略

圖4 中的lS表示待學習的個體,cS表示當前個體,nS代表經過學習方式之后生成的新個體.整個學習過程如下: 首先,初始化一個空的個體nS.依次選擇模型中的目標編號,以一定的概率選擇當前目標編號進行學習操作.假設當前選中的目標編號為2,則將待學習個體位置向量第1 行與2 相等的三個位置上的值,按照其在lS位置向量中出現的先后次序依次插入到新個體nS位置向量的對應位置,同時將各個任務對應的無人機以及無人機資源消耗量插入到位置向量的對應位置.對目標編號進行一次遍歷之后,新個體nS中非空位置保存的就是待學習個體lS的信息.然后,將原始個體cS中的目標、目標對應的無人機以及無人機資源使用量從左到右依次填入到新個體位置向量中的空位置,跳過新個體nS中已存在的目標.

圖4 粒子向較優個體的學習過程Fig.4 The learning process of particles from better individuals

通過向優秀個體進行學習,粒子位置向量將按照式(11)進行更新.其中Xi(t) 代表粒子i在第t次迭代中的位置,Pbesti為粒子在第t次迭代中的個體最優值,A為外部檔案集中的個體,Gbest為第t次迭代中的全局最優,w為權重系數,competition代表了粒子A和Gbest相互競爭,F代表了粒子向較優個體的學習過程.

2.4 基于區間擾動的局部搜索

如前所述,采用上述基于學習的粒子更新策略對種群中的個體進行更新能夠有效地對問題空間進行搜索,但如果粒子在更新的時候只采用該策略對群體中較優的個體進行學習,會導致算法在迭代后期陷入局部最優.為了進一步提升種群的多樣性以及算法的搜索能力,本文進一步提出了一種基于擾動的局部搜索策略,具體過程如算法4 所示.

算法4.基于區間擾動的局部搜索策略

具體實現方式見圖5.圖5 中cS代表當前個體,nS代表執行完局部搜索策略之后生成的新個體.按照一定的概率在個體cS上隨機選擇某一個目標上的某一個任務k.按照任務執行的時序約束找到任務k可插入的位置范圍 [startPos,endPos].圖5 中加下劃線的方框表示隨機選擇的任務k,兩個灰色背景方框的位置從左往右分別為startPos和endPos.在此范圍內隨機選擇任務插入的位置insertPos. 將任務k插入位置向量中的insertPos.其余位置的任務依次插入到nS的[startPos,endPos]之中,并重新設置完成任務k的無人機以及相應的資源消耗.需要指出的是,任務類型應滿足無人機作戰類型約束,即該任務如果是觀測和打擊結果的評估任務,則只能選擇偵察無人機集合中的無人機,否則選擇戰斗無人機集合中的無人機.此外,所選擇的無人機仍需滿足資源約束和最大航程約束.

圖5 基于區間擾動的局部搜索策略Fig.5 Local search strategy based on interval disturbance

2.5 基于拐點的外部檔案集更新策略

將原始問題看作各個目標維度上的單目標優化問題,雖然降低了問題的求解難度,但是由于各個子種群分別優化某一個目標,種群將會向每個目標維度上的極端點靠近.最后得到的非支配解集也將更多地分布在各個目標維度的附近,導致算法搜索不到帕累托面的中心部分,降低算法的多樣性.如圖6 所示,以兩目標問題為例,其中矩形點為極端點,圓形點代表非支配解,三角形點為支配解,虛線框所在的區域為中心解集區域.可以明顯看出,中心區域解集分布較少.這是由于每一個子種群的全局最優為對應目標維度的極端點,使得種群在不斷迭代過程中大部分的解將向極端點靠近,導致最后生成的非支配解集多樣性不足.

圖6 解集分布不均勻圖Fig.6 Uneven solution set distribution graph

為了使得外部檔案集中的解集分布更加均勻,同時提升算法的收斂性,本文利用拐點來引導檔案集中的其他精英個體的更新.如圖7 所示,點B和點C為某個種群內部的邊界點,兩者之間的連線為L,通過計算種群中其他點到直線L的距離,選擇距離最大的那個點作為拐點,即點A.對于三目標或者是超多目標問題,邊界點所構成的是一個平面或是超平面,則拐點也被定義為距離這個平面或者是超平面最遠的點.本文所提的利用拐點更新外部檔案集的方式如式(12)所示,外部檔案集中的個體向拐點學習更新位置向量.

圖7 拐點圖示Fig.7 Illustration of knee point

式(12)中Ai代表外部檔案集Archive中任意的一個精英個體,kneePt代表拐點,F為粒子向優秀個體的學習過程,具體實現方式見第2.3 節.

3 實驗與結果分析

本文基于不同的任務數量和無人機類型設計了4 種不同規模的實例并進行了仿真實驗.實驗中的算法均采用Java 編程,運行環境為JDK1.8,編譯器為Eclipse,處理器為主頻3.6 GHz 的Intel Core i7-4790.

3.1 仿真實例設計

本文設計了4 種不同規模的實例,其中實例1包含14 臺無人機和6 個軍事任務目標,實例2 包含16 臺無人機和12 個軍事任務目標,實例3 包含18 臺無人機和18 個軍事任務目標,實例4 包含20臺無人機和24 個軍事任務目標.各個實例中的任務目標被隨機地設置在一個固定的位置,每一個任務目標上包含了三種屬性,分別代表了完成此目標上的某一個軍事任務所需要的資源量.各個實例中的無人機同樣的被隨機地設置在一個固定的位置,每一個無人機包括了飛行速度、最大攜帶彈藥數目和最遠飛行距離.實例4 中各個目標和無人機的屬性設置情況如表5 和表6 所示,其他3 個實例見附錄A.上述實例包含不同規模、不同分布的無人機任務分配場景,4 個實例的示意圖如圖8 所示.其中,實例1 和實例2 中的目標和無人機在軍事區域內分布的相對集中且規模較小,這意味著在任務分配時可選擇的合適的無人機較多,因此在實例1 和實例2 的目標空間中存在較多的局部最優解,算法在實例1 和實例2 上的實驗結果能反映算法求解多峰優化問題時的性能.而實例3 和實例4 中目標和無人機的分布相對分散且規模更大,算法在實例3和實例4 上的實驗結果能較好地反映算法求解模型的收斂性能.通過在4 個實例上做實驗,可以對算法的探索能力和勘探能力進行較全面的評估.

圖8 4 個實例的示意圖Fig.8 Schematic diagram of four examples

表5 實例4 中目標屬性值Table 5 The target attribute value in example 4

表6 實例4 中無人機屬性值Table 6 Attribute value of drone in example 4

其中軍事任務目標和無人機的坐標單位為千米,無人機飛行速度單位為千米/秒,無人機最大飛機距離為2 000 千米.無人機完成觀測任務和打擊結果評估任務的最大觀測時間為60 秒.無人機完成一次打擊任務最大消耗彈藥數量為4 枚.

3.2 對比算法和評價指標

為了驗證KnCMPSO 算法性能,本文選取求解無人機協同任務分配問題的基于協同進化的混合變量多目標粒子群優化算法(Coevolution based mixed-variable multi-objective particle swarm optimization algorithm,C-MOPSO)[11]與3 個具有代表性的基于協同進化的多種群粒子群優化算法(Coevolutionary multiswarm particle swarm optimization,CMPSO)[30]、基于協同進化的粒子群優化算法(Coevolutionary particle swarm optimization,CPSO)[31]和基于分解的協同進化多目標局部搜索算法(Coevolutionary multiobjective local search based on decomposition,CoMOLS/D)[32]進行對比實驗.所有算法的種群大小N設置為300,最大迭代次數為500 次,外部檔案集大小均為種群大小的二分之一.同時采用超體積Hypervolum(HV) 指標評價各個算法獲得非支配解集的優劣.HV 指標是一個綜合性評價指標,能夠同時評估算法在收斂性和多樣性上的表現.HV 指標的數值越大,表示算法在收斂性和多樣性上的表現越好.本文HV 指標參考點設置為(15 000,15 000).

3.3 實驗結果與分析

為了使選取的各對比算法能夠求解本文的模型,上述對比算法均采用了與KnCMPSO 相同的編碼策略以及初始化方式.需要指出的是,為了保證實驗結果的公平性,除C-MOPSO 算法之外,其他的算法均采用本文所提出的粒子更新方式和局部搜索策略.

在實驗過程中,每個算法均將在上述無人機任務分配實例上執行30 次獨立實驗.各算法在所有實例上的HV 指標數據如表7 所示,其中Mean 表示各個算法30 次實驗計算得到的HV 指標的平均值,其大小反映算法求得的非支配解集的收斂性和多樣性.Std 表示各個算法30 次實驗計算得到的HV 指標的方差,其大小反映算法的穩定性.Best表示算法運行30 次后得到的最優的HV 值.Worst表示算法得到的最差HV 值.表7 中各個測試函數上的最優結果加粗標注,次優結果用下劃線標注.

表7 算法在各個實例上的HV 值Table 7 The HV value of the algorithm on each example

由表7 可以看出,相較于其他對比算法,Kn-CMPSO 在4 個實例上的HV 指標的平均值上都能取得最優結果,表明了算法在多樣性和收斂性上均優于其他對比算法.另外KnCMPSO 算法求得HV 指標中Std、Best 和Worst 值相比較于其他對比算法同樣是占優的,表明了KnCMPSO 算法在穩定性上同樣優于其他對比算法.原因如下: 1) KnCMPSO 利用協同進化的策略降低了問題的求解難度;2) 通過引入基于拐點的外部檔案集更新策略增加了算法對帕累托前沿中心區域的搜索能力.CMPSO 算法和CPSO 算法雖然同樣采用了協同進化策略,但是在CMPSO 和CPSO 算法中極端點對個體的引導能力過于強烈,導致最后生成的解集更多分布在各個目標維度極端解的附近,算法的多樣性受損.CoMOLS/D 算法采用的權重和法和反轉邊界交叉懲罰均是基于權重向量的策略.由于解集的好壞與權重向量的設置關系十分密切,在求解帕累托前沿分布不均勻的實際問題上優勢不明顯.C-MOPSO 算法針對無人機任務分配問題設計了基于結構學習的重組方法進行求解,但是這種重組方法不確定性較大,尤其是隨著問題規模的不斷變大,算法的求解性能逐漸降低,與C-MOPSO 算法的對比證明了本文所提粒子更新方式和局部搜索策略的有效性.

為了更加直觀展示算法在各個實例上的結果分布情況,算法在每個實例上所得解集的分布情況如圖9 所示.由圖中各實例解集分布情況可以看出,相比較于其他對比算法,本文算法求解得到的解集不論是在多樣性還是收斂性上都明顯占優,這與上述HV 指標的評估結果一致.

圖9 算法在各實例上的解集的分布圖Fig.9 Distribution diagram of the solution set of the algorithm on each example

通過上述實驗結果中本文算法和其他算法HV指標性能表現,以及5 個算法在各個實例中的解集分布情況可以發現,相比較于其他4 個算法,本文算法無論在收斂性方面還是多樣性方面均明顯占優,充分證明了本文算法求解無人機協同多任務分配問題的有效性.

為了驗證KnCMPSO 算法所提基于學習的粒子更新策略的有效性,本文將文獻[11]的基于結構學習的生成算子(Structure learning reproduction,SLR)嵌入到KnCMPSO 算法框架中,記該算法為KnCMPSO-SLR,與現有結果進行了對比,對比結果見表8.由表8 可以看出,KnCMPSO 在實例2上與KnCMPSO-SLR 的結果相近,但在實例1、實例3 和實例4 上都能取得最優結果,表明該算法可以保持較好的多樣性和收斂性,其原因在于Kn-CMPSO-SLR 采用基于結構學習的粒子更新策略只學習了父代個體的部分基因,而KnCMPSO 采用基于學習的粒子更新策略不僅學習父代個體,還向精英個體或全局最優個體學習,因此具有更好的收斂性能.

表8 算法在各個實例上的HV 值Table 8 The HV value of the algorithm on each example

同時,考慮到本文求解實際問題的特殊性,Kn-CMPSO 在解的初始化過程中提出了一種基于約束處理的初始化方法,為了驗證該方法的優越性,本文選擇采用其他3 種經典約束處理方法與本文KnCMPSO 算法框架結合構成新的算法,包括與基于罰函數[18]的約束處理方法結合KnCMPSO-PF,與基于可行性原則的約束處理方法[21]結合Kn-CMPSO-SR 和與基于隨機排序的約束處理方法結合KnCMPSO-FR[22],并將這3 種算法與本文算法進行實驗對比,實驗結果見表9.由表9 可以看出,KnCMPSO 在所有實例上均取得了最優結果,這主要歸因于KnCMPSO 將約束處理融入到粒子初始化以及更新的過程中,能有效地解決多種復雜約束,保證算法迭代過程中生成的解都為可行解,且在迭代過程中采用基于區間擾動的變異策略來提升種群的多樣性,提高了算法的搜索效率.而其他算法在迭代過程中生成了部分不可行解,導致算法搜索效率下降.

表9 算法在各個實例上的HV 值Table 9 The HV value of the algorithm on each example

4 結束語

本文以異構無人機協同作戰為背景,針對無人機協同多任務分配問題建立了包含多種約束條件的異構無人機協同多任務分配問題模型.為了求解此模型,本文提出了基于拐點的協同多目標粒子群優化算法KnCMPSO,并設計了4 種不同規模的實例進行仿真實驗.實驗結果顯示本文所提的算法在多樣性和收斂性上均優于其他的對比算法,表明本文所提算法能夠有效求解無人機協同多任務分配問題.

KnCMPSO 算法采用混合編碼方式以及基于約束處理的初始化方法,能有效避免不可行解的生成,采用協同進化策略將多目標優化問題轉為各目標維度上的單目標優化問題,同時設計相應的搜索策略提升算法的收斂性和多樣性,因此可以很好地適用于多目標多約束的無人機任務分配問題.但由于KnCMPSO 算法的編碼和搜索策略是根據異構無人機任務分配問題的特性進行設計,對于其他的多目標多約束混合變量優化問題,還需研究特定的編碼方式和搜索策略來進行求解.

本文提出的模型雖然考慮了更加符合實際情況的約束條件和目標函數,但是相比于現實作戰環境的復雜性還存在一定的差距,為了更進一步提高任務分配模型的有效性,未來在構建無人機任務分配模型時將考慮更多符合實際的約束條件和目標函數.

附錄A

表A1 和表A2 分別展示了實例3 的目標和無人機的各種屬性.表A3 和表A4 分別展示了實例2 的目標和無人機的各種屬性.表A5 和表A6 分別展示了實例1 的目標和無人機的各種屬性.

表A1 實例3 中目標屬性值Table A1 The target attribute value in example 3

表A1 實例3 中目標屬性值 (續表)Table A1 The target attribute value in example 3(continued table)

表A2 實例3 中無人機屬性值Table A2 Attribute value of drone in example 3

表A3 實例2 中目標屬性值Table A3 The target attribute value in example 2

表A4 實例2 中無人機屬性值Table A4 Attribute value of drone in example 2

表A5 實例1 中目標屬性值Table A5 The target attribute value in example 1

表A6 實例1 中無人機屬性值Table A6 Attribute value of drone in example 1