基于KnCMPSO算法的異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配

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

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

為了高效地制定無(wú)人機(jī)的任務(wù)分配計(jì)劃、科學(xué)地控制無(wú)人機(jī),需要對(duì)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題建立合適模型.

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

在模型的優(yōu)化目標(biāo)研究方面,目前大部分研究工作建立的都是以最小化無(wú)人機(jī)飛行距離的單目標(biāo)模型[9],也有一些學(xué)者嘗試構(gòu)建無(wú)人機(jī)任務(wù)分配的多目標(biāo)優(yōu)化模型.如文獻(xiàn)[10]提出同時(shí)考慮無(wú)人機(jī)任務(wù)收益、任務(wù)執(zhí)行時(shí)間和任務(wù)執(zhí)行代價(jià)的多目標(biāo)模型,文獻(xiàn)[11]以無(wú)人機(jī)總飛行距離和任務(wù)完成時(shí)間為優(yōu)化目標(biāo)構(gòu)建了多目標(biāo)優(yōu)化模型.

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

異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配模型有多個(gè)復(fù)雜的約束條件,因此,如何處理不同類(lèi)型的約束條件,以提高算法的搜索效率,是求解異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配模型的重要問(wèn)題.近年來(lái),一些學(xué)者針對(duì)不同類(lèi)型的應(yīng)用問(wèn)題,研究采用不同約束處理方法進(jìn)行求解.求解方法大致可以分為基于罰函數(shù)(Prnalty function,PF)的約束處理方法[18-20]、基于可行性原則的約束處理方法(Stochastic ranking,SR)[21-22]、基于隨機(jī)排序的約束處理方法 (Feasibility rule,FR)[23]和基于多目標(biāo)的約束處理方法[24]4 類(lèi) .也有一些學(xué)者就約束處理技術(shù)理論方面提出了一些新的改進(jìn),如基于分級(jí)方式的約束處理準(zhǔn)則[25]、基于集成方式的約束處理準(zhǔn)則[26]或?qū)⒓s束轉(zhuǎn)化為新的優(yōu)化目標(biāo)[27].而在異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配模型中,存在無(wú)人機(jī)類(lèi)型約束、任務(wù)執(zhí)行時(shí)序約束及多機(jī)協(xié)同約束等多種復(fù)雜約束,上述方法無(wú)法直接用于求解.

為了使構(gòu)建的模型更加符合現(xiàn)實(shí)場(chǎng)景,現(xiàn)有對(duì)無(wú)人機(jī)任務(wù)分配問(wèn)題的研究工作均在約束條件或目標(biāo)函數(shù)上對(duì)模型做出了改進(jìn),但是大部分研究工作均假設(shè)無(wú)人機(jī)的觀測(cè)時(shí)間和一次彈藥消耗都是充足的,然而在實(shí)際作戰(zhàn)過(guò)程中,當(dāng)偵察機(jī)一次觀測(cè)時(shí)間過(guò)長(zhǎng)時(shí),存在被敵方發(fā)現(xiàn)乃至擊斃的風(fēng)險(xiǎn),戰(zhàn)斗機(jī)一次發(fā)射的彈藥數(shù)量也是有限的.因此本文在現(xiàn)有研究工作[11]的基礎(chǔ)上,進(jìn)一步考慮無(wú)人機(jī)單次任務(wù)最大觀測(cè)時(shí)間約束和無(wú)人機(jī)單次任務(wù)最大彈藥約束,建立基于多種約束條件的異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題模型.

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

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

2)采用協(xié)同進(jìn)化策略,將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)為多個(gè)單目標(biāo)優(yōu)化問(wèn)題,通過(guò)子種群間合作式協(xié)同降低求解復(fù)雜度,通過(guò)子種群內(nèi)競(jìng)爭(zhēng)式協(xié)同進(jìn)化加快算法收斂,進(jìn)一步提出基于學(xué)習(xí)的粒子更新策略來(lái)提升算法的收斂性,粒子不僅學(xué)習(xí)父代優(yōu)秀個(gè)體,也學(xué)習(xí)精英個(gè)體或全局最優(yōu)個(gè)體,可以實(shí)現(xiàn)更快收斂.

3)提出基于區(qū)間擾動(dòng)的局部搜索策略來(lái)提升算法的多樣性,進(jìn)一步提出基于拐點(diǎn)的學(xué)習(xí)策略來(lái)更新外部檔案集,加強(qiáng)了算法對(duì)帕累托前沿中心面的搜索,在保證收斂性的同時(shí)提升算法的多樣性,使得算法能搜索到更多的可行任務(wù)分配結(jié)果.

本文首先對(duì)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題建模,然后介紹基于拐點(diǎn)的協(xié)同多目標(biāo)粒子群優(yōu)化算法,接著設(shè)計(jì)仿真實(shí)例來(lái)驗(yàn)證算法的有效性,最后進(jìn)行總結(jié)和展望.

1 異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配模型

1.1 問(wèn)題描述

表1 展示了模型中涉及的各種符號(hào)以及相應(yīng)說(shuō)明.

表1 符號(hào)說(shuō)明Table 1 Symbol description

異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題描述如下: 假設(shè)在某二維已知區(qū)域內(nèi)發(fā)現(xiàn)了NT個(gè)敵方目標(biāo),則目標(biāo)集合T可表示為T(mén)={T1,T2,···,TNT}.無(wú)人機(jī)系統(tǒng)需要對(duì)每個(gè)目標(biāo)依次執(zhí)行三種不同類(lèi)型的任務(wù),分別為觀測(cè)、打擊、打擊結(jié)果評(píng)估,即三種任務(wù)之間存在時(shí)序關(guān)系.任務(wù)類(lèi)型集合M可以表示為M={Observe,Attack,Evaluate},因此模型中需要調(diào)度的總?cè)蝿?wù)數(shù)量NM的值為NM=3×NT.異構(gòu)無(wú)人機(jī)系統(tǒng)中的無(wú)人機(jī)可以被分為偵察機(jī)和戰(zhàn)斗機(jī)兩種類(lèi)型,其中用于執(zhí)行觀測(cè)和打擊結(jié)果評(píng)估任務(wù)的偵察無(wú)人機(jī)有S架,執(zhí)行打擊任務(wù)的戰(zhàn)斗無(wú)人機(jī)有A架,則無(wú)人機(jī)集合表示為U={U1,U2,···,US,US+1,···,US+A}.無(wú)人機(jī)執(zhí)行不同的任務(wù)需要消耗一定的資源量.同一個(gè)目標(biāo)上的相同任務(wù)可以由多臺(tái)無(wú)人機(jī)協(xié)同完成.當(dāng)所有目標(biāo)上的所有任務(wù)執(zhí)行完成,整個(gè)軍事作戰(zhàn)任務(wù)順利完成.

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

為了能夠更加合理地對(duì)無(wú)人機(jī)任務(wù)分配的結(jié)果進(jìn)行評(píng)估,本文的模型采用無(wú)人機(jī)總飛行距離和任務(wù)完成時(shí)間兩個(gè)目標(biāo)函數(shù).無(wú)人機(jī)的總飛行距離為無(wú)人機(jī)系統(tǒng)中所有參與任務(wù)的無(wú)人機(jī)飛行距離之和,任務(wù)完成時(shí)間為整個(gè)作戰(zhàn)任務(wù)中最后一個(gè)完成任務(wù)的無(wú)人機(jī)的總飛行時(shí)間.根據(jù)以上定義,本文模型的計(jì)算公式如下:

無(wú)人機(jī)航程和其消耗資源數(shù)緊密相關(guān),無(wú)人機(jī)飛行總航程越短,代表無(wú)人機(jī)執(zhí)行任務(wù)時(shí)消耗的資源越少.然而,飛行總航程最短并不一定能保證軍事任務(wù)的完成時(shí)間最短.例如,一些無(wú)人機(jī)可能在同一目標(biāo)上被分配較多的任務(wù)以滿(mǎn)足所有無(wú)人機(jī)飛行總航程最短,而這會(huì)導(dǎo)致該無(wú)人機(jī)完成所有任務(wù)的時(shí)間變長(zhǎng),從而使得整個(gè)軍事任務(wù)完成時(shí)間變長(zhǎng).因此,無(wú)人機(jī)飛行總航程和任務(wù)完成時(shí)間兩個(gè)指標(biāo)存在一定的沖突.

1.3 約束條件

為了能夠?qū)Χ嗯_(tái)無(wú)人機(jī)協(xié)同完成同一項(xiàng)軍事任務(wù)進(jìn)行更有效的刻畫(huà),本文在文獻(xiàn)[11]基礎(chǔ)上,進(jìn)一步考慮無(wú)人機(jī)單次任務(wù)最大觀測(cè)時(shí)間約束和無(wú)人機(jī)單次任務(wù)最大彈藥約束來(lái)建立異構(gòu)無(wú)人機(jī)多任務(wù)分配模型,其所包含的約束條件如下.

1)無(wú)人機(jī)類(lèi)型約束.由于無(wú)人機(jī)的異構(gòu)性,不同類(lèi)型的任務(wù)只能由特定類(lèi)型的無(wú)人機(jī)完成.

式中,i表示無(wú)人機(jī)編號(hào),j表示目標(biāo)編號(hào),k表示任務(wù)編號(hào).當(dāng)k∈{Observe,Evaluate}時(shí),i ∈{1,2,···,S}; 當(dāng)k ∈{Attack}時(shí),i∈{S+1,···,S+A}.

2)任務(wù)執(zhí)行時(shí)序約束.對(duì)于同一個(gè)目標(biāo),無(wú)人機(jī)系統(tǒng)要先對(duì)其執(zhí)行觀測(cè)任務(wù),然后對(duì)其執(zhí)行打擊任務(wù),最后才能夠執(zhí)行打擊結(jié)果評(píng)估任務(wù).因此對(duì)同一個(gè)目標(biāo)上的三種任務(wù)需滿(mǎn)足如下時(shí)序約束.

3)最大攜帶彈藥數(shù)目約束.戰(zhàn)斗無(wú)人機(jī)只能攜帶一定數(shù)目的彈藥.因此戰(zhàn)斗無(wú)人機(jī)執(zhí)行打擊任務(wù)消耗的彈藥數(shù)要小于其最大攜帶彈藥數(shù)目.

4)單次最大偵察時(shí)間.為了避免暴露時(shí)間過(guò)長(zhǎng)以至于被敵方發(fā)現(xiàn),偵察無(wú)人機(jī)在執(zhí)行觀測(cè)任務(wù)和打擊結(jié)果評(píng)估任務(wù)時(shí)存在最大偵察時(shí)間.

5)單次最大發(fā)射彈藥數(shù).戰(zhàn)斗無(wú)人機(jī)在執(zhí)行對(duì)某一個(gè)目標(biāo)上的打擊任務(wù)時(shí),由于自己性能的限制只能發(fā)射一定數(shù)量的彈藥.

6)多機(jī)協(xié)同約束.為了保證軍事任務(wù)順利完成,針對(duì)不同目標(biāo)的不同類(lèi)型的任務(wù)需要分配給不同數(shù)量的無(wú)人機(jī)協(xié)同執(zhí)行.其中對(duì)同一個(gè)目標(biāo)的觀測(cè)和打擊結(jié)果評(píng)估任務(wù)至少需被一架偵察無(wú)人機(jī)執(zhí)行,而打擊任務(wù)需要分配給至少一架戰(zhàn)斗無(wú)人機(jī)執(zhí)行.

7)完成任務(wù)資源需求約束.執(zhí)行相同任務(wù)的所有無(wú)人機(jī)資源消耗總量需要大于等于完成當(dāng)前任務(wù)所需要的資源總量.

無(wú)人機(jī)執(zhí)行觀測(cè)任務(wù)和打擊結(jié)果評(píng)估任務(wù)需要消耗一定的時(shí)間資源,所有執(zhí)行同一任務(wù)的偵察無(wú)人機(jī)偵察總時(shí)間需要滿(mǎn)足完成任務(wù)所需總時(shí)間.

無(wú)人機(jī)執(zhí)行打擊任務(wù)需要消耗一定的彈藥資源,所有執(zhí)行同一任務(wù)的戰(zhàn)斗無(wú)人機(jī)消耗彈藥數(shù)量需要滿(mǎn)足完成任務(wù)所需總彈藥數(shù)量.

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

上述異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配模型所包含的決策變量既有表示任務(wù)分配結(jié)果的離散變量,也有表示無(wú)人機(jī)資源消耗的離散和連續(xù)變量,這些混合變量導(dǎo)致問(wèn)題解空間變得更加復(fù)雜,難以進(jìn)行有效搜索.同時(shí)模型還包含多個(gè)復(fù)雜的約束條件,既有不等式約束,也有等式約束,這些約束條件進(jìn)一步使得問(wèn)題對(duì)應(yīng)的解空間變得不規(guī)則,增加了算法搜索到可行解的難度.

由于現(xiàn)有的算法無(wú)法對(duì)本文提出的多約束多目標(biāo)異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配模型進(jìn)行有效求解,本文提出一種基于拐點(diǎn)的協(xié)同多目標(biāo)粒子群優(yōu)化算法求解無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題.

2 基于拐點(diǎn)的協(xié)同多目標(biāo)粒子群算法

本文提出的基于拐點(diǎn)的協(xié)同多目標(biāo)粒子群優(yōu)化算法KnCMPSO,主要通過(guò)設(shè)計(jì)基于約束處理的初始化策略、協(xié)同進(jìn)化策略、基于學(xué)習(xí)的粒子更新策略、基于區(qū)間擾動(dòng)的局部搜索策略及基于拐點(diǎn)的外部檔案集更新策略提升算法的求解性能.

算法流程如圖1 所示.首先,采用子種群間合作、子種群內(nèi)競(jìng)爭(zhēng)的協(xié)同進(jìn)化策略,將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)為各個(gè)目標(biāo)維度上的單目標(biāo)優(yōu)化問(wèn)題,降低了問(wèn)題的求解復(fù)雜度;其次,在各個(gè)子種群內(nèi)部,針對(duì)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題包含混合變量以及多種約束的特點(diǎn),以二進(jìn)制交叉方法為基礎(chǔ),設(shè)計(jì)了基于學(xué)習(xí)的粒子更新策略和基于區(qū)間擾動(dòng)的局部搜索策略,提升了算法的求解性能;最后,引入基于拐點(diǎn)的學(xué)習(xí)策略來(lái)更新外部檔案集,增強(qiáng)了算法對(duì)帕累托前沿中心面的搜索,在保證收斂性的同時(shí)增強(qiáng)了算法的多樣性.

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

2.1 編碼以及初始化策略

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

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

基于三維矩陣的混合編碼方式不但能夠很好地描述目標(biāo)、任務(wù)、執(zhí)行任務(wù)的無(wú)人機(jī)以及無(wú)人機(jī)資源消耗的對(duì)應(yīng)關(guān)系,而且能夠直觀地表示出各臺(tái)無(wú)人機(jī)執(zhí)行任務(wù)的先后順序,方便后續(xù)初始化操作.雖然每個(gè)個(gè)體位置向量編碼長(zhǎng)度仍然可能不同,但是所有目標(biāo)在編碼中出現(xiàn)的次數(shù)是固定的,也就是說(shuō)所有粒子的編碼矩陣中第1 行目標(biāo)編號(hào)的長(zhǎng)度是固定的,這就大大降低了問(wèn)題的求解難度.

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

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

表3 目標(biāo)隊(duì)列集合Table 3 Target formation collection

表4 無(wú)人機(jī)集合Table 4 Drone collection

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

2.2 協(xié)同進(jìn)化策略

協(xié)同進(jìn)化是生物學(xué)中一種重要的進(jìn)化機(jī)制 , 可促進(jìn)物種之間的信息交流并提高物種進(jìn)化效率.協(xié)同進(jìn)化策略包括了合作式協(xié)同進(jìn)化策略和競(jìng)爭(zhēng)式協(xié)同進(jìn)化策略?xún)煞N類(lèi)型[29].已有研究表明,在優(yōu)化算法中采用協(xié)同進(jìn)化策略能夠降低問(wèn)題的求解難度,加快算法的搜索效率,提升算法的性能[30].

KnCMPSO 算法采用了子種群間合作式協(xié)同進(jìn)化、子種群內(nèi)競(jìng)爭(zhēng)式協(xié)同進(jìn)化的策略來(lái)生成新個(gè)體.子種群合作式協(xié)同進(jìn)化采用子問(wèn)題與子種群一一對(duì)應(yīng)的方式,將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)為每一個(gè)維度上的單目標(biāo)優(yōu)化問(wèn)題.子種群內(nèi)競(jìng)爭(zhēng)式協(xié)同進(jìn)化則采用子種群內(nèi)的全局最優(yōu)個(gè)體和外部檔案集中的精英個(gè)體相互競(jìng)爭(zhēng)的方式來(lái)選擇較優(yōu)的個(gè)體,并利用該個(gè)體對(duì)子種群生成過(guò)程進(jìn)行引導(dǎo),避免種群向極端點(diǎn)靠近.其整體流程如圖2 所示.針對(duì)一個(gè)M維的多目標(biāo)優(yōu)化問(wèn)題,算法生成M個(gè)子種群,每個(gè)子種群分別針對(duì)每一個(gè)維度上的目標(biāo)進(jìn)行優(yōu)化.同時(shí)利用外部檔案集Archive 的方式保存迭代過(guò)程中尋找到的所有種群的非支配解,從而實(shí)現(xiàn)種群之間搜索信息的共享.

圖2 種群間合作種群內(nèi)競(jìng)爭(zhēng)的協(xié)同進(jìn)化策略Fig.2 Coevolution strategy of inter-population cooperation and intra-population competition

子種群間合作式協(xié)同進(jìn)化是指將原始問(wèn)題分別看作某一個(gè)維度上的單目標(biāo)優(yōu)化問(wèn)題,同時(shí)利用外部檔案集保存迭代過(guò)程中的所有種群的非支配解.由于子問(wèn)題與子種群一一對(duì)應(yīng),子種群平行且單獨(dú)地進(jìn)化,降低了問(wèn)題的求解復(fù)雜度.在傳統(tǒng)的多目標(biāo)問(wèn)題中,當(dāng)兩個(gè)個(gè)體互不支配的時(shí)候,無(wú)法確定哪一個(gè)更優(yōu),導(dǎo)致算法無(wú)法選擇個(gè)體最優(yōu)粒子和全局最優(yōu)粒子對(duì)當(dāng)前個(gè)體進(jìn)行更新操作.采用子種群間合作式協(xié)同進(jìn)化可以有效避免上述問(wèn)題.每個(gè)子種群根據(jù)當(dāng)前維度目標(biāo)值的大小來(lái)進(jìn)行個(gè)體最優(yōu)和全局最優(yōu)的選擇,實(shí)現(xiàn)在該維度上的求解.子種群內(nèi)競(jìng)爭(zhēng)式協(xié)同進(jìn)化是指通過(guò)各個(gè)子種群中的全局最優(yōu)個(gè)體和外部檔案集中的精英個(gè)體之間競(jìng)爭(zhēng),獲取

對(duì)子種群中的其他個(gè)體的引導(dǎo)權(quán),具體過(guò)程如算法2 所示.

算法2.基于競(jìng)爭(zhēng)的個(gè)體更新策略

如圖3 所示,假設(shè)子種群1 的優(yōu)化目標(biāo)為f1,Gbest為子種群1 在迭代次數(shù)為t時(shí)候全局最優(yōu)個(gè)體,待更新的個(gè)體為S.首先,在外部檔案集中隨機(jī)選擇一個(gè)精英個(gè)體A.計(jì)算個(gè)體A和S之間的余弦相似度;然后,與Gbest和S之間的余弦相似度進(jìn)行比較.當(dāng)A與S之間的余弦相似度更小時(shí),說(shuō)明個(gè)體A對(duì)個(gè)體S的引導(dǎo)能力更強(qiáng),更有利于算法的收斂,因此選擇A作為S的全局學(xué)習(xí)對(duì)象;反之,選擇Gbest作為S的全局學(xué)習(xí)對(duì)象.

圖3 競(jìng)爭(zhēng)式協(xié)同進(jìn)化策略Fig.3 Competitive coevolution strategy

上述兩種協(xié)同進(jìn)化策略不僅能降低問(wèn)題的求解復(fù)雜度,而且能有效提高算法的收斂速度.

2.3 基于學(xué)習(xí)的粒子更新策略

在標(biāo)準(zhǔn)粒子群算法中,種群中的個(gè)體通過(guò)對(duì)個(gè)體最優(yōu)粒子和全局最優(yōu)個(gè)體進(jìn)行學(xué)習(xí)來(lái)更新速度,再通過(guò)粒子的當(dāng)前位置和速度來(lái)更新粒子的狀態(tài).本文模型中包含了混合變量,并且約束條件較多,按照標(biāo)準(zhǔn)粒子群的更新方式將很難生成滿(mǎn)足約束的粒子,所以本文將對(duì)粒子的更新方式進(jìn)行改進(jìn),不再使用粒子速度這一個(gè)概念,粒子在更新的時(shí)候只通過(guò)向優(yōu)秀個(gè)體學(xué)習(xí)的方式來(lái)更新粒子的狀態(tài).基于此,在KnCMPSO 中提出了一種基于學(xué)習(xí)的粒子更新策略,具體過(guò)程如算法3 所示.

算法3.基于學(xué)習(xí)的粒子更新策略

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

圖4 粒子向較優(yōu)個(gè)體的學(xué)習(xí)過(guò)程Fig.4 The learning process of particles from better individuals

通過(guò)向優(yōu)秀個(gè)體進(jìn)行學(xué)習(xí),粒子位置向量將按照式(11)進(jìn)行更新.其中Xi(t) 代表粒子i在第t次迭代中的位置,Pbesti為粒子在第t次迭代中的個(gè)體最優(yōu)值,A為外部檔案集中的個(gè)體,Gbest為第t次迭代中的全局最優(yōu),w為權(quán)重系數(shù),competition代表了粒子A和Gbest相互競(jìng)爭(zhēng),F代表了粒子向較優(yōu)個(gè)體的學(xué)習(xí)過(guò)程.

2.4 基于區(qū)間擾動(dòng)的局部搜索

如前所述,采用上述基于學(xué)習(xí)的粒子更新策略對(duì)種群中的個(gè)體進(jìn)行更新能夠有效地對(duì)問(wèn)題空間進(jìn)行搜索,但如果粒子在更新的時(shí)候只采用該策略對(duì)群體中較優(yōu)的個(gè)體進(jìn)行學(xué)習(xí),會(huì)導(dǎo)致算法在迭代后期陷入局部最優(yōu).為了進(jìn)一步提升種群的多樣性以及算法的搜索能力,本文進(jìn)一步提出了一種基于擾動(dòng)的局部搜索策略,具體過(guò)程如算法4 所示.

算法4.基于區(qū)間擾動(dòng)的局部搜索策略

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

圖5 基于區(qū)間擾動(dòng)的局部搜索策略Fig.5 Local search strategy based on interval disturbance

2.5 基于拐點(diǎn)的外部檔案集更新策略

將原始問(wèn)題看作各個(gè)目標(biāo)維度上的單目標(biāo)優(yōu)化問(wèn)題,雖然降低了問(wèn)題的求解難度,但是由于各個(gè)子種群分別優(yōu)化某一個(gè)目標(biāo),種群將會(huì)向每個(gè)目標(biāo)維度上的極端點(diǎn)靠近.最后得到的非支配解集也將更多地分布在各個(gè)目標(biāo)維度的附近,導(dǎo)致算法搜索不到帕累托面的中心部分,降低算法的多樣性.如圖6 所示,以?xún)赡繕?biāo)問(wèn)題為例,其中矩形點(diǎn)為極端點(diǎn),圓形點(diǎn)代表非支配解,三角形點(diǎn)為支配解,虛線框所在的區(qū)域?yàn)橹行慕饧瘏^(qū)域.可以明顯看出,中心區(qū)域解集分布較少.這是由于每一個(gè)子種群的全局最優(yōu)為對(duì)應(yīng)目標(biāo)維度的極端點(diǎn),使得種群在不斷迭代過(guò)程中大部分的解將向極端點(diǎn)靠近,導(dǎo)致最后生成的非支配解集多樣性不足.

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

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

圖7 拐點(diǎn)圖示Fig.7 Illustration of knee point

式(12)中Ai代表外部檔案集Archive中任意的一個(gè)精英個(gè)體,kneePt代表拐點(diǎn),F為粒子向優(yōu)秀個(gè)體的學(xué)習(xí)過(guò)程,具體實(shí)現(xiàn)方式見(jiàn)第2.3 節(jié).

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

本文基于不同的任務(wù)數(shù)量和無(wú)人機(jī)類(lèi)型設(shè)計(jì)了4 種不同規(guī)模的實(shí)例并進(jìn)行了仿真實(shí)驗(yàn).實(shí)驗(yàn)中的算法均采用Java 編程,運(yùn)行環(huán)境為JDK1.8,編譯器為Eclipse,處理器為主頻3.6 GHz 的Intel Core i7-4790.

3.1 仿真實(shí)例設(shè)計(jì)

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

圖8 4 個(gè)實(shí)例的示意圖Fig.8 Schematic diagram of four examples

表5 實(shí)例4 中目標(biāo)屬性值Table 5 The target attribute value in example 4

表6 實(shí)例4 中無(wú)人機(jī)屬性值Table 6 Attribute value of drone in example 4

其中軍事任務(wù)目標(biāo)和無(wú)人機(jī)的坐標(biāo)單位為千米,無(wú)人機(jī)飛行速度單位為千米/秒,無(wú)人機(jī)最大飛機(jī)距離為2 000 千米.無(wú)人機(jī)完成觀測(cè)任務(wù)和打擊結(jié)果評(píng)估任務(wù)的最大觀測(cè)時(shí)間為60 秒.無(wú)人機(jī)完成一次打擊任務(wù)最大消耗彈藥數(shù)量為4 枚.

3.2 對(duì)比算法和評(píng)價(jià)指標(biāo)

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

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

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

在實(shí)驗(yàn)過(guò)程中,每個(gè)算法均將在上述無(wú)人機(jī)任務(wù)分配實(shí)例上執(zhí)行30 次獨(dú)立實(shí)驗(yàn).各算法在所有實(shí)例上的HV 指標(biāo)數(shù)據(jù)如表7 所示,其中Mean 表示各個(gè)算法30 次實(shí)驗(yàn)計(jì)算得到的HV 指標(biāo)的平均值,其大小反映算法求得的非支配解集的收斂性和多樣性.Std 表示各個(gè)算法30 次實(shí)驗(yàn)計(jì)算得到的HV 指標(biāo)的方差,其大小反映算法的穩(wěn)定性.Best表示算法運(yùn)行30 次后得到的最優(yōu)的HV 值.Worst表示算法得到的最差HV 值.表7 中各個(gè)測(cè)試函數(shù)上的最優(yōu)結(jié)果加粗標(biāo)注,次優(yōu)結(jié)果用下劃線標(biāo)注.

表7 算法在各個(gè)實(shí)例上的HV 值Table 7 The HV value of the algorithm on each example

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

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

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

通過(guò)上述實(shí)驗(yàn)結(jié)果中本文算法和其他算法HV指標(biāo)性能表現(xiàn),以及5 個(gè)算法在各個(gè)實(shí)例中的解集分布情況可以發(fā)現(xiàn),相比較于其他4 個(gè)算法,本文算法無(wú)論在收斂性方面還是多樣性方面均明顯占優(yōu),充分證明了本文算法求解無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題的有效性.

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

表8 算法在各個(gè)實(shí)例上的HV 值Table 8 The HV value of the algorithm on each example

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

表9 算法在各個(gè)實(shí)例上的HV 值Table 9 The HV value of the algorithm on each example

4 結(jié)束語(yǔ)

本文以異構(gòu)無(wú)人機(jī)協(xié)同作戰(zhàn)為背景,針對(duì)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題建立了包含多種約束條件的異構(gòu)無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題模型.為了求解此模型,本文提出了基于拐點(diǎn)的協(xié)同多目標(biāo)粒子群優(yōu)化算法KnCMPSO,并設(shè)計(jì)了4 種不同規(guī)模的實(shí)例進(jìn)行仿真實(shí)驗(yàn).實(shí)驗(yàn)結(jié)果顯示本文所提的算法在多樣性和收斂性上均優(yōu)于其他的對(duì)比算法,表明本文所提算法能夠有效求解無(wú)人機(jī)協(xié)同多任務(wù)分配問(wèn)題.

KnCMPSO 算法采用混合編碼方式以及基于約束處理的初始化方法,能有效避免不可行解的生成,采用協(xié)同進(jìn)化策略將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)為各目標(biāo)維度上的單目標(biāo)優(yōu)化問(wèn)題,同時(shí)設(shè)計(jì)相應(yīng)的搜索策略提升算法的收斂性和多樣性,因此可以很好地適用于多目標(biāo)多約束的無(wú)人機(jī)任務(wù)分配問(wèn)題.但由于KnCMPSO 算法的編碼和搜索策略是根據(jù)異構(gòu)無(wú)人機(jī)任務(wù)分配問(wèn)題的特性進(jìn)行設(shè)計(jì),對(duì)于其他的多目標(biāo)多約束混合變量?jī)?yōu)化問(wèn)題,還需研究特定的編碼方式和搜索策略來(lái)進(jìn)行求解.

本文提出的模型雖然考慮了更加符合實(shí)際情況的約束條件和目標(biāo)函數(shù),但是相比于現(xiàn)實(shí)作戰(zhàn)環(huán)境的復(fù)雜性還存在一定的差距,為了更進(jìn)一步提高任務(wù)分配模型的有效性,未來(lái)在構(gòu)建無(wú)人機(jī)任務(wù)分配模型時(shí)將考慮更多符合實(shí)際的約束條件和目標(biāo)函數(shù).

附錄A

表A1 和表A2 分別展示了實(shí)例3 的目標(biāo)和無(wú)人機(jī)的各種屬性.表A3 和表A4 分別展示了實(shí)例2 的目標(biāo)和無(wú)人機(jī)的各種屬性.表A5 和表A6 分別展示了實(shí)例1 的目標(biāo)和無(wú)人機(jī)的各種屬性.

表A1 實(shí)例3 中目標(biāo)屬性值Table A1 The target attribute value in example 3

表A1 實(shí)例3 中目標(biāo)屬性值 (續(xù)表)Table A1 The target attribute value in example 3(continued table)

表A2 實(shí)例3 中無(wú)人機(jī)屬性值Table A2 Attribute value of drone in example 3

表A3 實(shí)例2 中目標(biāo)屬性值Table A3 The target attribute value in example 2

表A4 實(shí)例2 中無(wú)人機(jī)屬性值Table A4 Attribute value of drone in example 2

表A5 實(shí)例1 中目標(biāo)屬性值Table A5 The target attribute value in example 1

表A6 實(shí)例1 中無(wú)人機(jī)屬性值Table A6 Attribute value of drone in example 1