基于改進(jìn)量子粒子群算法的多無(wú)人機(jī)任務(wù)分配*

鄧 可，連振江，周德云，李梟揚(yáng)

(1. 海軍大連艦艇學(xué)院，遼寧 大連 116018；2. 西北工業(yè)大學(xué)，陜西 西安 710072)

隨著計(jì)算機(jī)技術(shù)、人工智能的發(fā)展，無(wú)人機(jī)在軍事領(lǐng)域取得了眾多成功應(yīng)用，在可預(yù)見(jiàn)的未來(lái)，多無(wú)人機(jī)協(xié)同執(zhí)行作戰(zhàn)任務(wù)是無(wú)人機(jī)技術(shù)的一個(gè)重要發(fā)展方向[1]。美軍多所科研單位、軍事機(jī)構(gòu)都曾以全球鷹、捕食者、X-45、X-47為研究對(duì)象，進(jìn)行了多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題研究，探討了多無(wú)人機(jī)協(xié)同任務(wù)分配在真實(shí)戰(zhàn)場(chǎng)下的作戰(zhàn)效能[2]，并將多無(wú)人機(jī)協(xié)同作戰(zhàn)融入一體化作戰(zhàn)構(gòu)想中[3]。多無(wú)人機(jī)協(xié)同作戰(zhàn)是一個(gè)復(fù)雜化、多樣化、智能化的作戰(zhàn)過(guò)程，協(xié)同偵察攻擊任務(wù)作為協(xié)同作戰(zhàn)熱點(diǎn)研究問(wèn)題，指在作戰(zhàn)區(qū)域中對(duì)目標(biāo)實(shí)行協(xié)同偵察，對(duì)確定目標(biāo)進(jìn)行協(xié)同攻擊與毀傷評(píng)估任務(wù)[4]，多無(wú)人機(jī)任務(wù)分配是協(xié)同作戰(zhàn)的基礎(chǔ)與保障。

文獻(xiàn)[5]將QPSO算法應(yīng)用于復(fù)合結(jié)構(gòu)的無(wú)人機(jī)編隊(duì)分配問(wèn)題，文獻(xiàn)[6]提出了改進(jìn)的MRS與MAS系統(tǒng)框架針對(duì)無(wú)人機(jī)對(duì)地任務(wù)分配，但是這些框架模型存在控制參數(shù)多且難以確定的缺點(diǎn)；文獻(xiàn)[7]提出了一種基于MQABC算法求解無(wú)人機(jī)任務(wù)分配問(wèn)題的方法，文獻(xiàn)[8]利用Memetic算法求解協(xié)同分配模型，文獻(xiàn)[9]設(shè)計(jì)了一種蝗蟲(chóng)仿生算法針對(duì)多無(wú)人機(jī)搜救任務(wù)。但是這些算法存在收斂時(shí)間不穩(wěn)定的缺陷，在多無(wú)人機(jī)協(xié)同執(zhí)行單一類型任務(wù)性能優(yōu)異，面對(duì)多類型任務(wù)有所欠缺。

綜上所述，研究一種適用于多無(wú)人機(jī)的多目標(biāo)任務(wù)分配算法具有重要意義，為多無(wú)人機(jī)協(xié)同作戰(zhàn)奠定基礎(chǔ)并提供保障。本文綜合考慮多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題中的各類約束，結(jié)合多目標(biāo)優(yōu)化理論，構(gòu)建了多無(wú)人機(jī)協(xié)同任務(wù)分配模型，在QPSO(Quantum-behaved Particle Swarm Optimization)算法基礎(chǔ)上，借鑒變異的思想，設(shè)計(jì)了變異量子門(mén)克服了多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題中解空間狹長(zhǎng)導(dǎo)致求解算法陷入局部最優(yōu)的缺點(diǎn)，且改進(jìn)了QPSO算法下的慣性權(quán)重，自適應(yīng)慣性權(quán)重使得該算法具有收斂速度快，搜索能力強(qiáng)的優(yōu)點(diǎn)。

1 協(xié)同多任務(wù)分配模型

1.1 問(wèn)題描述

近年來(lái)，許多學(xué)者對(duì)無(wú)人機(jī)協(xié)同任務(wù)分配模型進(jìn)行了研究，但大多模型為單目標(biāo)優(yōu)化任務(wù)分配，面對(duì)多無(wú)人機(jī)多目標(biāo)優(yōu)化任務(wù)分配存在收斂慢、多目標(biāo)函數(shù)優(yōu)化性能差的不足，針對(duì)多無(wú)人機(jī)協(xié)同任務(wù)分配的特征，本文基于CMTAP[10]通用協(xié)同任務(wù)分配模型，結(jié)合多目標(biāo)優(yōu)化理論，融合多無(wú)人機(jī)協(xié)同作戰(zhàn)環(huán)境下的多種任務(wù)協(xié)同約束，構(gòu)建多無(wú)人機(jī)任務(wù)協(xié)同分配模型。

廣域搜索空對(duì)地戰(zhàn)場(chǎng)場(chǎng)景下，假定敵方目標(biāo)位置與戰(zhàn)場(chǎng)環(huán)境已經(jīng)預(yù)先獲得。U={U1,U2,…,Un}為執(zhí)行任務(wù)的UCAV集合，n為參與任務(wù)的UCAV架次，T={T1,T2,…,Tm}為敵方m個(gè)目標(biāo)；M={MT1,MT2,…,MTm}為待執(zhí)行的Mi×m個(gè)任務(wù)，對(duì)于每個(gè)目標(biāo)Ti需要完成三種作戰(zhàn)任務(wù)，分別為偵察(Classify)、攻擊(Attack)和毀傷評(píng)估(Verify)，因此任務(wù)集可寫(xiě)為

(1)

為適當(dāng)簡(jiǎn)化問(wèn)題，無(wú)人機(jī)UCAVi在t時(shí)刻的位置由(xUi(t),yUi(t))(i∈1,2,…,n)表示，目標(biāo)位置Ti由(xTi(t),yTi(t))(i∈1,2,…,m)表示。多無(wú)人機(jī)任務(wù)分配結(jié)果即為每一架無(wú)人機(jī)分配一條任務(wù)執(zhí)行序列，即

DUAVi={(xT0,yT0,MT0),(xT1,yT1,MT1),…,(xTk,yTk,MTk)}

(2)

其中，(xTi,yTi,MTij)為T(mén)i目標(biāo)下的任務(wù)合集中的第j類任務(wù)，每一架無(wú)人機(jī)須在執(zhí)行完任務(wù)序列后返回出發(fā)基地。

1.2 任務(wù)約束

多無(wú)人機(jī)協(xié)同執(zhí)行任務(wù)在實(shí)際戰(zhàn)場(chǎng)環(huán)境中，首先無(wú)人機(jī)受限于自身的航程以及負(fù)載，其次對(duì)目標(biāo)執(zhí)行偵察、攻擊、毀傷評(píng)估三類任務(wù)內(nèi)在包含時(shí)序要求，最后需要充分考慮協(xié)同作戰(zhàn)的效率性，因此多無(wú)人機(jī)協(xié)同任務(wù)分配問(wèn)題的多類復(fù)雜約束條件可主要?dú)w為三種，分別是任務(wù)時(shí)序約束、任務(wù)協(xié)同約束以及無(wú)人機(jī)能力約束。

2)任務(wù)時(shí)序約束是指執(zhí)行偵察、攻擊、毀傷評(píng)估任務(wù)具有內(nèi)在先后順序要求。假定對(duì)于敵方目標(biāo)i，執(zhí)行偵察任務(wù)時(shí)刻為t1，執(zhí)行攻擊任務(wù)時(shí)刻為t2，執(zhí)行毀傷評(píng)估任務(wù)時(shí)刻為t3，t1、t2、t3必須滿足：t1

1.3 問(wèn)題描述

多UCAV總飛行航程指標(biāo)能有效反映分配方案的作戰(zhàn)耗損，即實(shí)際戰(zhàn)場(chǎng)下多UCAV的耗油量、飛行時(shí)長(zhǎng)等無(wú)人機(jī)自身屬性約束，多UCAV的總飛行時(shí)間能直接反映分配方案的作戰(zhàn)效率，即實(shí)際戰(zhàn)場(chǎng)中多UCAV快速完成任務(wù)的能力，本文多無(wú)人機(jī)任務(wù)分配問(wèn)題主要通過(guò)UCAV總飛行航程與UCAV總飛行時(shí)間這兩項(xiàng)評(píng)價(jià)指標(biāo)來(lái)評(píng)價(jià)不同任務(wù)分配方案的優(yōu)劣。

假定每架無(wú)人機(jī)飛行速度恒定為V。本文的多無(wú)人機(jī)任務(wù)協(xié)同分配模型目標(biāo)函數(shù)定義為：

minJ=[J1,J2]

(3)

式中J1為UCAV總飛行航程指標(biāo)，其中Li為每一架UCAV的飛行航程，DUAVij為第i架UCAV任務(wù)序列中相鄰目標(biāo)間距離；J2為UCAV總飛行時(shí)間指標(biāo)。

2 改進(jìn)的量子粒子群算法

2.1 QPSO算法描述

粒子群算法是由Kennedy和Eberhart在1995年提出的，該算法本質(zhì)粒子在解空間追隨最優(yōu)的粒子進(jìn)行搜索最優(yōu)解，但是粒子群優(yōu)化算法不是一個(gè)全局收斂算法，且全局搜索能力對(duì)速度上限過(guò)度依靠導(dǎo)致算法的魯棒性較差。由于粒子群算法的劣勢(shì)，Sun等根據(jù)量子力學(xué)中的粒子行為，假設(shè)粒子具有量子效應(yīng)，提出了量子粒子群算法。在量子空間中，粒子狀態(tài)X=[x1,x2,…,xn]由波函數(shù)ψ(x,t)來(lái)描述，波函數(shù)為粒子在量子空間的統(tǒng)計(jì)概率表述，實(shí)質(zhì)上波函數(shù)模的平方即為粒子的概率密度函數(shù)，因此通過(guò)求解波函數(shù)可得到粒子在量子空間下出現(xiàn)位置的統(tǒng)計(jì)概率，以隨機(jī)數(shù)模擬的方式類比波函數(shù)的觀測(cè)坍縮即可得到粒子位置[11]。

QPSO算法的粒子進(jìn)化方程為：

(4)

其中：

P=αPi+(1-α)Pg

(5)

(6)

式中，α、μ為[0,1]上服從均勻分布的隨機(jī)數(shù)；Pi為第t次迭代時(shí)粒子個(gè)體的最優(yōu)位置，Pg為第t次迭代時(shí)粒子群體最優(yōu)位置；P為第t次迭代時(shí)粒子個(gè)體最優(yōu)位置與粒子群體最優(yōu)位置之間一個(gè)隨機(jī)位置；Pmbest為粒子群平均最好位置；M為粒子群中粒子的數(shù)目。

其中β為慣性權(quán)重，是影響QPSO算法收斂速度的一個(gè)重要參數(shù)，它可取為固定值，也可隨著算法迭代動(dòng)態(tài)變化，慣性權(quán)重一般采用線性遞減策略。

(7)

通過(guò)設(shè)置慣性權(quán)重的上下邊界βmax與βmin，根據(jù)式(7)按當(dāng)前迭代次數(shù)t與設(shè)定迭代次數(shù)tmax的線性關(guān)系進(jìn)行線性遞減。通常情況下，β從1線性遞減至0.5時(shí)能取得較好的結(jié)果。

2.2 變異量子門(mén)算子

QPSO算法在狹長(zhǎng)且離散的解空間下進(jìn)行全局搜索，在算法后期容易陷入局部最優(yōu)解。為改進(jìn)QPSO算法這一缺陷，提高對(duì)多無(wú)人機(jī)任務(wù)分配問(wèn)題的適用性，本文借鑒遺傳算法中的變異算子思想，設(shè)計(jì)了變異量子門(mén)算子。每次迭代后，根據(jù)粒子狀態(tài)計(jì)算每個(gè)粒子的目標(biāo)函數(shù)值，判斷每個(gè)粒子是否處于支配狀態(tài)，并將非支配解置入Pareto解集，維護(hù)并更新Pareto解集，使得Pareto解集中始終保持非支配Pareto最優(yōu)解；若連續(xù)多次迭代過(guò)程中，Pareto解集未發(fā)生更新，則將粒子群按一定概率對(duì)密集程度高的部分粒子進(jìn)行變異。

針對(duì)多無(wú)人機(jī)任務(wù)分配問(wèn)題中解空間狹長(zhǎng)的特點(diǎn)，采用通用量子門(mén)形式進(jìn)行變異操作，以保證尋優(yōu)過(guò)程中解的多樣性。通用量子門(mén)包括量子旋轉(zhuǎn)門(mén)與量子非門(mén)，其中量子旋轉(zhuǎn)門(mén)使得粒子的原有量子編碼進(jìn)行旋轉(zhuǎn)，獲得新的角動(dòng)量方向，量子非門(mén)則使得粒子編碼位進(jìn)行變異，若進(jìn)行隨機(jī)變異，粒子易出現(xiàn)飛離解空間邊界的情況，將減弱算法尋優(yōu)能力減緩收斂速度，因此本文根據(jù)解空間狹長(zhǎng)的特點(diǎn)，以全局最優(yōu)粒子位置與當(dāng)前粒子最優(yōu)位置取代量子非門(mén)下的隨機(jī)變異操作，該種變異形式能提高算法的局部搜索能力，并且避免在狹長(zhǎng)解空間下隨機(jī)變異帶來(lái)的退化現(xiàn)象，變異量子門(mén)算子如下所示：

(8)

式中，γ1、γ2為[0,1]上服務(wù)均勻分布的隨機(jī)數(shù)。通過(guò)把變異量子門(mén)算子的引入，實(shí)現(xiàn)了粒子群在局部最優(yōu)解中的跳變，使得QPSO算法在多無(wú)人機(jī)任務(wù)分配問(wèn)題下能保證廣域的搜索空間，并保證后期的局部搜索能力。實(shí)驗(yàn)表明，變異概率隨迭代次數(shù)線性遞增，上界取0.2-0.3之間的值，可獲得較好的效果。

2.3 自適應(yīng)慣性權(quán)重

在QPSO算法中慣性權(quán)重的大小影響全局搜索能力與局部搜索能力。實(shí)驗(yàn)表明，慣性權(quán)重增大可加強(qiáng)全局搜索減弱局部搜索，慣性權(quán)重減小時(shí)反之。對(duì)于QPSO算法中粒子群而言，粒子群當(dāng)前粒子位置與全局最優(yōu)粒子位置間的距離表明了算法在解空間內(nèi)搜索范圍的覆蓋尺度。為使得QPSO算法在搜索最優(yōu)解過(guò)程中的自適應(yīng)機(jī)制，對(duì)于離全局最佳位置點(diǎn)近的粒子，應(yīng)適當(dāng)增大β，以保證粒子群更大的覆蓋范圍；而對(duì)離全局最佳位置點(diǎn)遠(yuǎn)的粒子，應(yīng)適當(dāng)縮小β，防止粒子過(guò)度分散，減弱算法的局部搜索能力。此外，在算法早期，粒子搜索域需要保持較大的覆蓋范圍，若粒子群過(guò)度分散，則會(huì)導(dǎo)致算法收斂慢的問(wèn)題，此時(shí)需要控制粒子群的分散程度，防止粒子群搜索發(fā)散；隨著算法迭代的進(jìn)行，算法后期需要更為精確的搜索，若粒子群過(guò)于集中時(shí)，容易陷入局部最優(yōu)點(diǎn)，使得算法陷入局部最優(yōu)解，因此需要根據(jù)迭代次數(shù)與粒子群集中程度調(diào)整慣性權(quán)重，適當(dāng)放大粒子群的搜索范圍。

基于以上討論，本文采用當(dāng)前粒子狀態(tài)與全局最優(yōu)粒子狀態(tài)差值來(lái)衡量粒子群的集中程度，結(jié)合算法的迭代時(shí)期來(lái)動(dòng)態(tài)調(diào)節(jié)慣性權(quán)重，即

(9)

其中，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，P為當(dāng)前粒子狀態(tài)，Pg為全局最優(yōu)粒子狀態(tài)。

2.4 改進(jìn)QPSO算法流程

本文提出的改進(jìn)QPSO算法流程如下：

步驟1沒(méi)置迭代次數(shù)t=0，設(shè)置基本參數(shù)，如總迭代次數(shù)、粒子數(shù)量等。初始化每一個(gè)粒子的波函數(shù)，計(jì)算粒子的位置概率密度函數(shù)獲得粒子位置，Xi中儲(chǔ)存最優(yōu)的粒子，Pi(0)=Xi(0)。

步驟2根據(jù)式(6)計(jì)算粒子群的平均最好位置。

步驟3循環(huán)執(zhí)行步驟4-9，直到粒子群所有粒子均完成更新。

步驟4對(duì)粒子i的每一維，根據(jù)式(5)計(jì)算得到一個(gè)當(dāng)前位置與全局最優(yōu)位置間的一個(gè)隨機(jī)點(diǎn)位置。

步驟5計(jì)算粒子的新位置。

步驟6根據(jù)多無(wú)人機(jī)任務(wù)分配模型指標(biāo)，計(jì)算粒子i當(dāng)前位置X(t)的適應(yīng)度f(wàn)(X(t))，并根據(jù)步驟5獲得的粒子新位置X(t+1)計(jì)算適應(yīng)度f(wàn)(X(t+1))，根據(jù)兩適應(yīng)度的支配關(guān)系更新最優(yōu)個(gè)體值，若無(wú)支配關(guān)系則按設(shè)定概率判定是否更新。

步驟7對(duì)于粒子i，將該粒子適應(yīng)值與全局最好位置的適應(yīng)值比較，若支配則更新。

步驟8根據(jù)Pareto占優(yōu)理論評(píng)價(jià)更新后的粒子群并維護(hù)Pareto最優(yōu)解集。

步驟9根據(jù)Pareto解集更新情況與變異概率，對(duì)粒子群進(jìn)行量子門(mén)變異操作，產(chǎn)生新個(gè)體計(jì)算適應(yīng)度后重組種群。

步驟10直至滿足循環(huán)條件，輸出Pareto解集，否則返回步驟4。

3 仿真實(shí)驗(yàn)

為驗(yàn)證本文所提出的改進(jìn)QPSO算法相比標(biāo)準(zhǔn)QPSO算法針對(duì)多無(wú)人機(jī)任務(wù)分配問(wèn)題更具有有效性，本文在表1下的假定環(huán)境中，將QPSO算法與改進(jìn)QPSO算法進(jìn)行仿真實(shí)驗(yàn)對(duì)比，分析改進(jìn)粒子群算法在求解多無(wú)人機(jī)任務(wù)分配問(wèn)題上的可靠性與優(yōu)越性。

假定作戰(zhàn)環(huán)境為我方須對(duì)敵方5個(gè)目標(biāo)區(qū)域執(zhí)行作戰(zhàn)任務(wù)，共出動(dòng)5架無(wú)人機(jī)。5個(gè)目標(biāo)區(qū)域所執(zhí)行的任務(wù)集均為Classify、Attack、Verify三類任務(wù)，即總?cè)蝿?wù)數(shù)M=15；我方無(wú)人機(jī)均具有偵察、打擊、毀傷評(píng)估能力，且各個(gè)無(wú)人機(jī)出發(fā)基地位置不同，須在執(zhí)行任務(wù)后返回出發(fā)基地，基地位置與目標(biāo)位置見(jiàn)表1。

表1 UCAV與目標(biāo)屬性

QPSO算法和改進(jìn)QPSO算法均設(shè)置粒子數(shù)量為50，最大迭代次數(shù)為2000；改進(jìn)QPSO算法主要參數(shù)設(shè)置如下：Pareto解集更新不變次數(shù)為30次，變異量子門(mén)概率設(shè)為0.25。兩算法分別獨(dú)立運(yùn)行30次，各算法的分配方案如表2所示。

圖1與圖2分別給出了改進(jìn)QPSO算法迭代過(guò)程中，總飛行航程指標(biāo)與任務(wù)完成時(shí)間指標(biāo)每一代更新中最優(yōu)值迭代圖。由圖可以看出，隨著算法的迭代次數(shù)遞增，目標(biāo)函數(shù)均得到了優(yōu)化，最后收斂至穩(wěn)定值。并且從收斂曲線可以看出，改進(jìn)后的慣性權(quán)重能根據(jù)算法的收斂程度，在粒子群聚集搜索空間小時(shí)，增大粒子的搜索范圍，使得算法避免過(guò)早收斂，而在粒子群過(guò)于分散時(shí)，慣性權(quán)重自適應(yīng)減小，防止算法收斂緩慢。

圖1 航程代價(jià)變化曲線

圖2 任務(wù)執(zhí)行時(shí)間變化曲線

由表2可以看出，改進(jìn)QPSO算法在Pareto解的前沿上搜索能力總體優(yōu)于基本QPSO算法。其中改進(jìn)QPSO算法下的方案1、2、3均支配QPSO算法下的方案1、2、3解集；此外，改進(jìn)QPSO算法的方案1對(duì)QPSO算法下的方案1與3是支配的，并且改進(jìn)QPSO算法下方案2解也對(duì)QPSO下方案2、3、4支配。由此可以看出，在兩種算法獲得的Pareto解集上，改進(jìn)的QPSO算法能更有效地進(jìn)行局部搜索，使得算法跳出局部最優(yōu)解，且能保證解集的多樣性。因此改進(jìn)QPSO算法相比基本QPSO算法在多無(wú)人機(jī)任務(wù)分配問(wèn)題上更有效。將改進(jìn)QPSO算法任務(wù)分配方案2轉(zhuǎn)換為UCAV任務(wù)對(duì)應(yīng)表與任務(wù)執(zhí)行序列，如表3與表4所示。

表2 分配方案

表3 UCAV對(duì)應(yīng)任務(wù)

表4 任務(wù)執(zhí)行序列

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

本文通過(guò)綜合考慮多無(wú)人機(jī)任務(wù)分配約束條件，以多UCAV總飛行航程和多UCAV總飛行時(shí)間兩個(gè)關(guān)鍵指標(biāo)作為任務(wù)分配方案的評(píng)價(jià)標(biāo)準(zhǔn)，構(gòu)建多無(wú)人機(jī)任務(wù)分配模型，采用改進(jìn)的QPSO算法進(jìn)行優(yōu)化求解多無(wú)人機(jī)任務(wù)分配問(wèn)題。通過(guò)仿真得到的多無(wú)人機(jī)協(xié)同任務(wù)分配方案顯示，改進(jìn)的QPSO算法能更好地搜索Pareto前沿，更為有效地解決多無(wú)人機(jī)任務(wù)分配問(wèn)題。