余稼洋,郭建勝,張曉豐,解 濤,姚 賽

(空軍工程大學(xué) 裝備管理與無人機(jī)工程學(xué)院, 西安 710051)

0 引言

現(xiàn)代戰(zhàn)爭逐步呈現(xiàn)出“無人化”趨勢,無人機(jī)因其速度快、零傷亡、全天候等優(yōu)點(diǎn)廣泛應(yīng)用于軍事領(lǐng)域,對空戰(zhàn)模式產(chǎn)生革命性的影響[1]。如何在復(fù)雜戰(zhàn)場環(huán)境下,對無人機(jī)作戰(zhàn)任務(wù)進(jìn)行分配,使之在滿足限定條件下,得到?jīng)Q策者滿意的任務(wù)分配方案,成為當(dāng)前無人機(jī)應(yīng)用領(lǐng)域研究的一個熱點(diǎn)。

目前,絕大多數(shù)無人機(jī)任務(wù)分配問題的研究都基于參數(shù)確定這一假設(shè)。但是,受虛假情報(bào)、惡劣天氣等不確定因素影響,無人機(jī)任務(wù)分配過程中的油耗量、飛行時(shí)間、飛行威脅等不可測,造成確定條件下的任務(wù)分配方案失去最優(yōu)性。模糊集理論、魯棒優(yōu)化理論和概率論是解決不確定問題的常用方法,但是模糊集在數(shù)學(xué)上不具有自洽性[2],魯棒優(yōu)化求解的結(jié)果相對保守[3],應(yīng)用概率論的前提是不確定變量的概率分布可以獲取,但在實(shí)際作戰(zhàn)環(huán)境中缺乏采樣數(shù)據(jù),需要根據(jù)相關(guān)領(lǐng)域?qū)＜覍Σ淮_定變量進(jìn)行評估以獲取相關(guān)參數(shù)信息。為此,Liu[4-5]提出了不確定理論,并有相關(guān)學(xué)者開展了大量理論和應(yīng)用研究[6-8],無人機(jī)任務(wù)分配問題涉及較少。因此,本文中主要研究帶時(shí)間窗的不確定無人機(jī)多目標(biāo)任務(wù)分配問題。由于目標(biāo)函數(shù)和約束中均包含不確定變量,傳統(tǒng)的優(yōu)化方法無法解決此問題。本文中基于不確定理論,建立一種新的不確定無人機(jī)任務(wù)分配模型,分別引入期望值準(zhǔn)則和機(jī)會約束將帶有不確定變量的模型轉(zhuǎn)為確定型優(yōu)化模型。

當(dāng)前求解任務(wù)分配問題的方法主要有窮舉法、約束規(guī)劃法、圖論法、列表法及聚類法等,但這些方法在計(jì)算實(shí)時(shí)性、準(zhǔn)確性等方面仍有較大提升空間。煙花算法(fireworks algorithm,FWA)是譚營于2010年提出的一種智能算法,主要用于求解連續(xù)空間的單目標(biāo)優(yōu)化問題,其被證明具有良好的優(yōu)化性能[9]。文獻(xiàn)[10]中引入量子的思想,提出了一種自適應(yīng)旋轉(zhuǎn)角的量子煙花算法;文獻(xiàn)[11]中將遺傳算法和煙花算法結(jié)合,并增加模擬退火流程;文獻(xiàn)[12]中引入維度方差、禁忌搜索策略和輪盤賭策略改進(jìn)變異算子和選擇算子。文獻(xiàn)[10-12]中對算法的搜索速度和求解精度做出大量貢獻(xiàn),但只能解決單目標(biāo)優(yōu)化問題。為將煙花算法應(yīng)用到多目標(biāo)優(yōu)化問題上,文獻(xiàn)[13]中以各目標(biāo)適應(yīng)度值乘積大小判斷解的優(yōu)劣以確定火花爆炸半徑及數(shù)量,并引入Pareto優(yōu)越理論改進(jìn)選擇策略;文獻(xiàn)[14]中以規(guī)范后的各目標(biāo)適應(yīng)度值之和判斷解的優(yōu)劣以確定火花爆炸半徑及數(shù)量;文獻(xiàn)[15]中引入Pareto優(yōu)越理論和精英反向?qū)W習(xí)策略改進(jìn)算法的選擇策略,以上文獻(xiàn)雖成功的將煙花算法拓展到多目標(biāo)優(yōu)化問題求解中,但簡單地以各目標(biāo)適應(yīng)度值乘積或求和來確定爆炸算子中火花半徑和數(shù)量,可能造成煙花盲目搜索,降低搜索效率;此外,算法在求解精度上仍有較大提升空間。因此,本文中采用冪律分布函數(shù)改進(jìn)爆炸算子,以適應(yīng)度等級確定火花爆炸半徑和數(shù)量;此外,引入Levy變異算子并結(jié)合多目標(biāo)優(yōu)化理論和兩階段搜索策略提出了一種兩階段搜索的多目標(biāo)煙花算法(MLFWA),避免了算法的盲目搜索和早熟收斂,有效提高了算法搜索速度和全局搜索能力。最后通過實(shí)例仿真驗(yàn)證了算法和模型的有效性和可行性。

1 不確定條件下無人機(jī)任務(wù)分配問題

無人機(jī)打擊任務(wù)分配問題是指無人機(jī)從基地出發(fā),在相關(guān)約束條件下以最小的代價(jià)實(shí)現(xiàn)對所有任務(wù)目標(biāo)的火力打擊,并回到基地的過程。該問題可表示為無向完全圖G={V+,E+}上的不確定整數(shù)規(guī)劃問題。

1.1 模型構(gòu)建

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

實(shí)際戰(zhàn)場環(huán)境中,無人機(jī)在路徑(i,j)上受電磁干擾、地形等帶來的威脅ηij和飛行時(shí)間tij無法準(zhǔn)確得知,兩者均為不確定變量。在任務(wù)分配問題中,決策者希望無人機(jī)以最小代價(jià)完成任務(wù)。一方面,需要降低無人機(jī)受到的威脅代價(jià)F1。假設(shè)ηij是滿足正態(tài)分布的一系列獨(dú)立不確定變量,即ηij～N(eij,σij)。故威脅代價(jià)F1可表示為

(1)

(2)

(3)

(4)

其中:λ為延遲懲罰系數(shù);i為無人機(jī)的前序任務(wù)。

1.1.2約束條件

無人機(jī)打擊任務(wù)分配約束主要包含以下3類。

1) 燃油約束

受限于無人機(jī)性能,單架無人機(jī)攜帶燃油數(shù)是一定的。受飛行高度、速度等因素影響,無人機(jī)在路徑(i,j)上的單位飛行距離油耗εij無法確定,為不確定變量。為確保無人機(jī)能夠安全返航,必須滿足

(5)

式中,Ak為單架無人機(jī)攜帶的燃油總量。

2) 任務(wù)協(xié)同約束

對于每個目標(biāo),其打擊任務(wù)只能被一架無人機(jī)執(zhí)行,即

(6)

3) 路徑起止約束

每架無人機(jī)都是從基地出發(fā)執(zhí)行任務(wù),最終返回基地,故路徑起止約束為

(7)

1.2 模型等價(jià)轉(zhuǎn)換

顯然,模型中求解空間的不等式約束及目標(biāo)函數(shù)中均包含不確定變量,無法確定可行解集和實(shí)現(xiàn)尋優(yōu),屬于不確定規(guī)劃問題。

期望值是不確定變量的重要統(tǒng)計(jì)特征,期望值模型是不確定規(guī)劃的常用處理方法。Liu[4]引入不確定機(jī)會約束,以最小化目標(biāo)函數(shù)的期望值為準(zhǔn)則,構(gòu)建了期望值模型以解決不確定規(guī)劃問題。式(8)是期望值模型的數(shù)學(xué)表達(dá)式。

(8)

其中,M{Gi(x,ξ)≤0}≥αi是置信度水平為α的不確定機(jī)會約束,確保了模型有確定的可行解集。由此,無人機(jī)打擊任務(wù)分配期望值模型為

(9)

2 兩階段搜索的多目標(biāo)煙花算法

2.1 多目標(biāo)煙花算法

2.1.1編碼方式及初始化

在無人機(jī)打擊任務(wù)分配問題中,每個煙花均代表一種可行的任務(wù)分配方案。煙花xi的長度為n,即需打擊目標(biāo)數(shù),以確保每個任務(wù)均能分配到無人機(jī)且不會重復(fù)分配。本文中采取半連續(xù)編碼,整數(shù)部分表示執(zhí)行任務(wù)的無人機(jī)編號,根據(jù)小數(shù)部分值大小確定無人機(jī)執(zhí)行任務(wù)的順序。以2架無人機(jī)打擊5個目標(biāo)為例,煙花(1.7,2.5,1.3,2.1,2.7)表示無人機(jī)1依次打擊目標(biāo)3、1,無人機(jī)2依次打擊目標(biāo)5、2、4。

然后,根據(jù)煙花數(shù)量N初始化解空間,并計(jì)算初始解的適應(yīng)度值。煙花的初始解產(chǎn)生方式為

xi=xmin+(xmax-xmin)rand(0,1)

(10)

其中:xi=(xi1,xi2,…,xin)為第i個煙花的位置;xij為第i個煙花在第j維度上的值;xmax和xmin表示火花的上下界。

2.1.2爆炸算子

傳統(tǒng)FWA中,煙花產(chǎn)生的火花數(shù)和振幅依賴于煙花種群的適應(yīng)度值,且煙花間差異不可控。雖然其限制了極端煙花產(chǎn)生的火花數(shù),但未考慮其對種群中其他煙花的火花數(shù)的影響。此外,在多目標(biāo)問題中,帕累托解不分優(yōu)劣,無法得到最大和最小適應(yīng)度值,故無法簡單地根據(jù)適應(yīng)度值大小計(jì)算煙花產(chǎn)生的火花數(shù)及振幅。故考慮使用冪律分布函數(shù),按照煙花適應(yīng)度值高低將搜索種群劃分為若干等級,以此計(jì)算煙花產(chǎn)生的火花數(shù)

(11)

式中:k為煙花的適應(yīng)度等級;a為分布形狀系數(shù),其值越大,高適應(yīng)度值的煙花產(chǎn)生的火花數(shù)越多。

2.1.3變異算子

煙花算法采用高斯變異以增加種群多樣性。但高斯變異擾動范圍較小,且其變異范圍為整個實(shí)數(shù)區(qū)間,對于搜索范圍為正實(shí)數(shù)區(qū)間的任務(wù)分配問題會造成重復(fù)搜索,大大降低了變異效率。

圖1和圖2給出了Levy分布、柯西分布和高斯分布的概率密度函數(shù)和分布函數(shù),可以看出Levy分布的波峰更高,尾翼更寬,且其變異范圍為正實(shí)數(shù)區(qū)間,增大了算法的搜索范圍及搜索效率。Levy分布的概率密度函數(shù)及分布函數(shù)分別為

圖1 3種分布的概率密度函數(shù)曲線Fig.1 Probability density function curves for each distribution

圖2 3種分布的分布函數(shù)曲線Fig.2 Distribution function curves for each distribution

(12)

F(X;u;c)=P{X≤x}=

(13)

其中:u為位置參數(shù),影響分布曲線的左右平移,函數(shù)定義域?yàn)閇u,+∞];c為標(biāo)度參數(shù),其數(shù)值越小,Levy分布的波峰越高,尾翼越寬。

引入Levy變異算子的火花變異公式為

x′ik=round(β×xik)

(14)

其中, β為服從Levy分布的隨機(jī)數(shù)。

2.1.4映射

考慮到部分煙花爆炸和變異產(chǎn)生的火花值可能會超出可行域,考慮使用模運(yùn)算將超出可行域的火花映射到可行域內(nèi)

(15)

式中:| |表示絕對值運(yùn)算;mod表示模運(yùn)算。

2.1.5選擇

對于多目標(biāo)優(yōu)化問題,解集質(zhì)量和解集的覆蓋范圍是判斷帕累托解優(yōu)劣的標(biāo)準(zhǔn)[16]。算法迭代過程中選取適應(yīng)度值好、分布分散的煙花更有利于尋優(yōu)。首先建立容量為W的外部檔案室,用以存儲迭代過程中產(chǎn)生的煙花;其次,根據(jù)Pareto優(yōu)越理論用非支配排序法將煙花劃分為不同的非支配等級[17],針對同一等級煙花,根據(jù)式(16)計(jì)算煙花的擁擠度距離,非支配等級越小,距離越大,煙花越好,即任務(wù)分配方案越好,選取最優(yōu)的N個煙花作為下次迭代的初始煙花種群。若檔案室中煙花的數(shù)量超出上限W時(shí),按照非支配排序和擁擠度距離選擇最優(yōu)的W個煙花留在檔案室,刪除多余煙花

(16)

式中:u為當(dāng)前煙花鄰域內(nèi)煙花數(shù);dmin和dmax為煙花種群最近和最遠(yuǎn)距離。相較于傳統(tǒng)擁擠度計(jì)算方法,式(16)能夠反映出當(dāng)前煙花在種群中的整體分布,能夠更好地度量煙花的領(lǐng)域分布,有利于在整體和局部上保證煙花的多樣性。

2.2 兩階段搜索策略

為更好更快得到帕累托解,提出一種兩階段搜索方式,如圖3所示。第一階段為快速搜索階段,其目的為加速搜索;第二階段是尋優(yōu)搜索階段,其目的為提高解的多樣性。

圖3 兩階段搜索示意圖Fig.3 Two-stage search diagram

2.2.1快速搜索階段

第一階段主要目的是加快算法搜索速度,使種群迅速接近帕累托前沿,故用當(dāng)前種群到實(shí)際帕累托前沿的距離指導(dǎo)算法搜索。但在實(shí)際中,絕大多數(shù)多目標(biāo)優(yōu)化問題的帕累托解不易獲取,無法準(zhǔn)確計(jì)算種群到帕累托前沿的距離。故考慮引入一個參考點(diǎn),用當(dāng)前種群到參考點(diǎn)的距離代替其到真實(shí)帕累托解的實(shí)際距離,以指導(dǎo)算法搜索。

參考點(diǎn)一般選取搜索域的邊界或搜索域外的點(diǎn),否則會造成搜索種群無法接近帕累托前沿。如圖4所示,x1,x2,x3,x4,x5為搜索種群,A、B、C、D表示不同的參考點(diǎn)。其中A和B位于搜索域內(nèi),C位于搜索域邊界,D位于搜索域外。當(dāng)選取B、C、D作為參考點(diǎn)時(shí),種群會朝著帕累托前沿搜索;當(dāng)選取A作為參考點(diǎn)時(shí),粒子x1,x2朝著帕累托前沿搜索,但粒子x3,x4,x5逐漸遠(yuǎn)離帕累托前沿,造成搜索效率降低。

圖4 不同位置參考點(diǎn)搜索過程示意圖Fig.4 Schematic diagram of reference point search process at different locations

2.2.2尋優(yōu)搜索階段

第一階段雖然加速了種群對帕累托解的逼近,但也導(dǎo)致種群過度集中(見圖3)。為使算法能夠快速找到具有多樣性的解,需要增強(qiáng)算法在單次搜索過程中的搜索范圍,故將傳統(tǒng)FWA中的高斯變異算子換為變異范圍更廣的Levy變異算子。

2.2.3搜索轉(zhuǎn)換策略

當(dāng)快速搜索的種群收斂時(shí),需要自動進(jìn)入尋優(yōu)搜索階段,如何設(shè)計(jì)合適的搜索階段轉(zhuǎn)換指標(biāo)是該算法的關(guān)鍵問題之一?？紤]以子代個體支配父代個體數(shù)的均值作為階段轉(zhuǎn)換指標(biāo)。當(dāng)子代個體能夠支配較多父代個體,認(rèn)為當(dāng)前種群在快速接近帕累托解;否則,認(rèn)為當(dāng)前種群的搜索正在收斂。當(dāng)滿足式(17)時(shí),可以認(rèn)定種群搜索已經(jīng)收斂。

ui<α

(17)

式中:ui為子代個體能夠支配父代個體數(shù)的均值;α為指標(biāo)轉(zhuǎn)換閾值。不同閾值對算法的影響將在第4節(jié)詳細(xì)說明。

3 實(shí)例仿真

3.1 評價(jià)指標(biāo)

多目標(biāo)算法的性能比較往往比較困難,需要考慮解集質(zhì)量、算法求解效率、魯棒性等諸多方面。本文中選取超體積指標(biāo)(Hypervolume,HV)評價(jià)算法優(yōu)劣。HV度量了解集的空間覆蓋情況,能同時(shí)衡量算法的多樣性和收斂性。HV值越大,表明帕累托前沿分布越均勻,收斂性越好[16]。HV的計(jì)算公式為

HV(A)=[1-f1(xi)][1-f2(xi)]+

(18)

其中,fm(xi)表示解xi的第m個目標(biāo)函數(shù)值。將目標(biāo)函數(shù)值范圍進(jìn)行歸一化,則有HV(A)∈[0,1]且越接近1表示解集質(zhì)量越高。

3.2 算法測試

為驗(yàn)證MLFWA的有效性,在ZDT和DTLZ系列[18]多目標(biāo)測試函數(shù)上驗(yàn)證算法性能,選取多目標(biāo)遺傳算法(NSGA-Ⅱ)、基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)和多目標(biāo)粒子群算法(MOPSO)作為對比。其中,DLZT系列測試函數(shù)的優(yōu)化目標(biāo)數(shù)和搜索變量數(shù)均可拓展,考慮到本文中研究的是雙目標(biāo)優(yōu)化問題,故優(yōu)化目標(biāo)數(shù)取2。各測試函數(shù)特性和問題維度如表1所示。各算法初始種群規(guī)模設(shè)為100,最大迭代次數(shù)為1 000次,外部檔案室的大小為50。

表1 各測試函數(shù)的相關(guān)參數(shù)及特性Table 1 Parameters and characteristics for each test function

為減少隨機(jī)因素對算法性能影響,各算法獨(dú)立運(yùn)行50次,得到各算法HV的均值及方差,見表2。算法在測試函數(shù)上的帕累托前沿如圖5所示。結(jié)果表明,MLFWA算法求解的解集質(zhì)量及算法穩(wěn)定性要優(yōu)于對比算法。

圖5 各算法在測試函數(shù)中的帕累托前沿Fig.5 The Pareto front for each algorithm in the test function

表2 各算法HV的均值和方差Table 2 The mean value and variance of HV for each algorithm

表3給出了不同α值下ZDT系列測試函數(shù)在階段轉(zhuǎn)換時(shí)的HV指標(biāo)。結(jié)果表明,α值越小,進(jìn)入尋優(yōu)搜索階段的搜索種群質(zhì)量更高。圖6給出不同α值下的MLFWA算法在ZDT1測試函數(shù)中第二階段初始解分布。

表3 不同α值ZDT系列測試函數(shù)的HV值Table 3 HV value of ZDT test functions with different α

圖6 ZDT1測試函數(shù)中不同α值第二階段初始解分布Fig.6 The initial solution distribution of different E values in the second stage in ZDT1 test function

3.3 實(shí)例仿真

為驗(yàn)證本文中提出的任務(wù)分配模型及MLFWA算法,設(shè)計(jì)場景為4架無人機(jī)執(zhí)行14個任務(wù)目標(biāo)。采用NSGA-Ⅱ算法、MOEA/D算法、MOPSO算法和前文提到的MLFWA算法分別進(jìn)行求解,各算法參數(shù)設(shè)置與4.2相同。為便于分析,將無人機(jī)和任務(wù)目標(biāo)看作質(zhì)點(diǎn),在任務(wù)分配過程中不考慮無人機(jī)之間的通信約束。仿真區(qū)域設(shè)置為90 km×150 km的平面,各目標(biāo)坐標(biāo)及任務(wù)時(shí)間窗見表4所示。

表4 任務(wù)目標(biāo)點(diǎn)參數(shù)Table 4 The parameters of targets

續(xù)表(表4)

為確保實(shí)驗(yàn)結(jié)果的準(zhǔn)確性,各算法重復(fù)運(yùn)行50次,最大迭代次數(shù)為200。MLFWA和其他對比算法在任務(wù)分配實(shí)例上求解的解集分布如圖7所示。從圖7可以看出,本文中所提MLFWA在求解無人機(jī)多目標(biāo)任務(wù)分配問題中解的質(zhì)量要明顯優(yōu)于NSGA-Ⅱ、MOEA/D、MOPSO算法。

圖7 各算法求解結(jié)果示意圖Fig.7 Schematic diagram of solution results for each algorithm

對各算法求解得到的目標(biāo)函數(shù)值進(jìn)行歸一化,計(jì)算得到各算法運(yùn)行30次的HV均值和方差,如表5所示。從表5可以看出,MLFWA在實(shí)例中求解得到的解集HV均值要大于3種對比算法,說明了MLFWA求解得到的解集具有較好的多樣性和收斂性。但MLFWA的求解得到解集的HV值的方差要略大于MOEA/D、NSGA-Ⅱ算法,說明算法的穩(wěn)定性略差于MOEA/D、NSGA-Ⅱ算法。由于多目標(biāo)優(yōu)化問題主要關(guān)注解集質(zhì)量,故在提升算法求解質(zhì)量的前提下,適當(dāng)降低算法穩(wěn)定是可取的。

表5 各算法的HV均值和方差Table 5 The mean and variance of HV for each algorithm

4 結(jié)論

針對不確定條件下無人機(jī)多目標(biāo)任務(wù)分配問題,運(yùn)用不確定理論將任務(wù)執(zhí)行過程中的威脅、油耗、飛行時(shí)間等不確定變量進(jìn)行量化處理,將其建模為確定型多目標(biāo)優(yōu)化問題。引入冪律分布函數(shù)和Levy變異算子,結(jié)合多目標(biāo)優(yōu)化理論和兩階段搜索策略提出了一種兩階段搜索的多目標(biāo)煙花算法,克服了傳統(tǒng)煙花算法不能解決多目標(biāo)問題的缺陷,并有效提高了算法的求解精度和效率。實(shí)驗(yàn)結(jié)果表明,MLFWA能夠在滿足油耗等約束的前提下,有效找出最佳任務(wù)分配方案。

下一步工作主要包括以下幾個方面。從理論層面,考慮利用不確定性理論中的樂觀值、悲觀值準(zhǔn)則直接求解多目標(biāo)問題;從模型層面,考慮任務(wù)目標(biāo)價(jià)值時(shí)變、戰(zhàn)場威脅改變、無人機(jī)戰(zhàn)損等因素細(xì)化模型,使之更貼近戰(zhàn)場實(shí)際;從算法層面,考慮多目標(biāo)優(yōu)化理論和智能算法如何更好的結(jié)合,以降低算法復(fù)雜度及增強(qiáng)算法尋優(yōu)效率。