改進(jìn)差分進(jìn)化算法求解武器目標(biāo)分配問題

吳文海, 郭曉峰, 周思羽, 高 麗

(海軍航空大學(xué)青島校區(qū)航空儀電控制工程與指揮系, 山東 青島 266041)

0 引 言

武器目標(biāo)分配(weapon-target assignment, WTA)是指依據(jù)戰(zhàn)術(shù)目標(biāo)、武器性能、目標(biāo)威脅等約束條件,結(jié)合實(shí)時戰(zhàn)場態(tài)勢信息,合理配置武器資源,確定最佳目標(biāo)分配方案,以獲得協(xié)同作戰(zhàn)的最佳攻擊效果,是典型的組合約束優(yōu)化問題[1]。WTA作為協(xié)同作戰(zhàn)中指揮決策的核心問題之一,吸引大量學(xué)者研究,具有重要的軍事意義[2]。

WTA通常分為靜態(tài)WTA(static WTA, SWTA)和動態(tài)WTA(dynamic WTA, DWTA)兩類。SWTA將所有武器在單一階段分配于目標(biāo);DWTA為多階段決策問題,在不同階段分配任務(wù)中,需考慮戰(zhàn)場態(tài)勢信息的變化,為后續(xù)決策提供依據(jù)[3]。WTA屬于NP完全問題(non-deterministic polynomial complete, NPC)[4],求解WTA的計(jì)算量隨維度增加呈指數(shù)增長,傳統(tǒng)方法如目標(biāo)規(guī)劃[5]、博弈論框架[6]、啟發(fā)式算法[7]、拉格朗日松弛法[8]等,能夠?qū)崿F(xiàn)對低維WTA問題求解,但難以對高維問題求解,全局尋優(yōu)能力差,無法滿足實(shí)際需求。智能算法以其尋優(yōu)精度高、收斂速度快的特點(diǎn)被廣泛應(yīng)用于求解WTA問題。Zhou[9]等人提出一種離散粒子群優(yōu)化算法,將遺傳算法中均勻變異和交叉概念引入粒子群優(yōu)化算法中求解SWTA問題;Sonuc[10]等人提出一種并行擬退火算法求解WTA問題;Chen[11]等人提出包括遺傳算法和模因算法在內(nèi)的進(jìn)化決策算法求解DWTA問題;Li[12]等人將針對具體問題的種群初始化方法引入進(jìn)化算法,改進(jìn)選擇操作機(jī)制,提高了求解SWTA問題的效率;Hu[13]等人提出基于精英策略的蟻群優(yōu)化算法,改進(jìn)路徑選擇、信息素更新等策略,對4種WTA模型進(jìn)行求解。盡管上述方法在尋優(yōu)精度方面有一定的改進(jìn),但收斂速度并不盡如人意,尤其面對高維問題,尋優(yōu)精度和收斂速度仍有很大改進(jìn)空間。

差分進(jìn)化(differential evolution, DE)算法基于“貪婪競爭”的尋優(yōu)策略,通過變異、交叉和選擇操作實(shí)現(xiàn)種群進(jìn)化,達(dá)到尋優(yōu)目的[14],其控制參數(shù)少、尋優(yōu)精度高、魯棒性強(qiáng)、易于工程實(shí)現(xiàn),被廣泛應(yīng)用于各領(lǐng)域優(yōu)化問題[15]。近年來不少學(xué)者通過DE算法求解WTA問題,Deng[16]等人提出一種基于雙種群的DE算法,分別采用浮點(diǎn)和序號對種群編碼,進(jìn)化過程中從浮點(diǎn)種群中生成相應(yīng)的序列種群,實(shí)現(xiàn)求解SWTA問題;王少蕾[17]等人提出一種自適應(yīng)DE算法求解WTA問題,利用混沌序列初始化種群,進(jìn)化過程中變異、交叉因子隨代數(shù)動態(tài)更新;Li[18]等人提出一種基于動態(tài)參數(shù)的變異策略,隨DE算法進(jìn)化過程推進(jìn),最優(yōu)個體所占信息量不斷增加。盡管上述方法對DE算法進(jìn)行了改進(jìn),但進(jìn)化過程中算法變異策略單一,個體鄰域固定不變,靜態(tài)鄰域拓?fù)湫畔⒔粨Q速率緩慢,無法平衡全局與局部搜索能力、減緩算法收斂速度,難以尋得全局最優(yōu);其次,進(jìn)化過程中算法未能充分利用“精英”個體信息,尋優(yōu)效率較低。

針對上述問題,為提高求解DWTA問題效率,本文提出一種基于隨機(jī)鄰域的自適應(yīng)差分進(jìn)化算法(random neighborhood adaptive differential algorithm, RNADE)。首先,RNADE為每一個體生成隨機(jī)領(lǐng)域,領(lǐng)域中個體數(shù)量隨進(jìn)化過程動態(tài)更新,以平衡算法開發(fā)和探索能力。其次,引入基于歷史進(jìn)化信息的自適應(yīng)參數(shù)策略,根據(jù)“精英”信息動態(tài)更新每代個體的變異因子和交叉因子。最后,基于小、中、大3種武器目標(biāo)規(guī)模情境,與5種DE算法進(jìn)行了18組對比實(shí)驗(yàn)。

1 DWTA問題描述

DWTA屬于多階段決策問題,其突出特點(diǎn)是在各階段武器目標(biāo)分配過程中,需實(shí)時考慮戰(zhàn)場態(tài)勢變化,適應(yīng)動態(tài)求解環(huán)境,以獲得全局最優(yōu)攻擊方案?！肮?觀察-攻擊”是解決多階段DWTA問題的常用策略,如圖1所示。

圖1 “攻擊-觀察-攻擊”策略

“觀察”指對戰(zhàn)場態(tài)勢進(jìn)行分析,確定攻擊目標(biāo)及可用武器;“攻擊”指求解武器與目標(biāo)的分配結(jié)果,根據(jù)決策實(shí)施打擊,“觀察-攻擊”的過程類似于SWTA問題[19],則DWTA可表示為

DWTA={SWTA(1),SWTA(2),…,SWTA(T)}

(1)

本文選取目標(biāo)生存概率總期望值最小作為分配決策優(yōu)化目標(biāo),則優(yōu)化模型可表示為

minJ(X)=min{J(X(1)),J(X(2)),…,J(X(T))}

(2)

(3)

約束條件為

(4)

(5)

根據(jù)式(2)和式(3)可知,DWTA問題若想獲得全局最優(yōu)解,在每一階段必須獲得最優(yōu)解,因此精確、高效地獲得式(3)解是處理DWTA問題的關(guān)鍵。

2 改進(jìn)差分進(jìn)化算法

2.1 標(biāo)準(zhǔn)DE算法

DE算法是基于“貪婪競爭”的智能算法,通過變異、交叉、選擇操作實(shí)現(xiàn)群進(jìn)化。

(1)“DE/rand/1”

(6)

(2)“DE/best/1”

(7)

(8)

式中,Xmax和Xmin為搜索空間的上下界。

(9)

式中,jrand為控制參數(shù)；交叉因子CR∈(0,1)。

(10)

式中,f(·)為適應(yīng)值。

2.2 隨機(jī)鄰域變異策略

本文提出一種基于隨機(jī)鄰域的變異策略,進(jìn)化中為每代個體從當(dāng)前種群隨機(jī)挑選N個“鄰居”,其中最優(yōu)個體作為基向量,執(zhí)行“DE/neighbor/1”操作,可表示為

(11)

式中,Xnbest為鄰域中最優(yōu)個體;Xr1,Xr2為除Xnbest外,鄰域內(nèi)隨機(jī)挑選的個體。

鄰域內(nèi)個體數(shù)量N對DE搜索尋優(yōu)能力具有重要的影響。N取較大值時,DE將具有較好的開發(fā)能力;相反,N取較小值時,DE將具有較好的探索能力。因此,合理地選擇“鄰居”數(shù)量N對平衡DE探索和開發(fā)能力,提高DE尋優(yōu)性能起著重要的作用。本文提出一種自適應(yīng)N值更新策略,隨進(jìn)化過程動態(tài)計(jì)算N值:

(12)

傳統(tǒng)的DE僅采用固定的變異策略,減緩了算法收斂速度,甚至容易導(dǎo)致算法陷入局部最優(yōu)[20],“DE/neighbor/1”策略充分利用鄰域內(nèi)“最優(yōu)”和“隨機(jī)”信息,加速信息交換速度,平衡全局探索和局部開發(fā)能力,避免在算法陷入局部最優(yōu)的同時,提高種群多樣性和算法收斂速度。

2.3 自適應(yīng)參數(shù)策略

DE的控制參數(shù)對其尋優(yōu)性能具有重要的影響,傳統(tǒng)經(jīng)驗(yàn)方法所確定的控制參數(shù)無法始終保持最優(yōu)性[21]。因此,為了充分利用進(jìn)化過程中的“精英”信息,本文采用基于歷史進(jìn)化信息存檔的自適應(yīng)參數(shù)更新策略[22]。

(13)

(14)

(16)

式中,meanWL(·)為權(quán)重萊默均值,可表示為

(17)

(18)

本策略充分利用“精英”信息保證控制參數(shù)最優(yōu)性,同時采用柯西分布和正態(tài)分布提高隨機(jī)性,保證種群多樣性。

2.4 算法復(fù)雜度分析

3 基于RNADE的DWTA問題求解

3.1 DWTA問題決策流程

基于“攻擊-觀察-攻擊”的DWTA決策流程如圖2所示。

圖2 DWAT問題決策流程

由圖2可知,DWAT決策需根據(jù)戰(zhàn)場態(tài)勢分析結(jié)果確定當(dāng)前階段所需攻擊目標(biāo)及可用武器,將所確定的目標(biāo)及武器輸入RNADE執(zhí)行優(yōu)化迭代以獲得武器目標(biāo)分配決策,DWAT決策過程還需對分配結(jié)果及戰(zhàn)場態(tài)勢進(jìn)行評估與監(jiān)控,根據(jù)分配方案效果和戰(zhàn)場態(tài)勢信息,確定是否需要繼續(xù)迭代求解。DWTA決策過程需動態(tài)更新所需攻擊目標(biāo)及可用武器,因此對算法尋優(yōu)速度具有嚴(yán)苛要求,以滿足武器目標(biāo)分配決策的需求。

3.2 整數(shù)編碼操作

WTA屬于整數(shù)規(guī)劃問題,編碼方式需與其相適應(yīng),且滿足對約束條件的表示。在m個可用武器和n個所需攻擊目標(biāo)情況下,每個個體Xi都是m維的整數(shù),可表示為

Xi=(xi1,xi2,…,xim)

(19)

式中,xik∈[1,n],xik∈Z,xik為武器k所攻擊的目標(biāo)編號,具體編碼操作如圖3所示。

圖3 整數(shù)編碼

由圖3可知,分配決策為

{W1T4,W2T1,W3T5,W4T2,W5T3,W6T1,W7T6}

則根據(jù)整數(shù)編碼操作獲得的個體向量為

X=[4,1,5,2,3,1,6]

3.3 RNADE流程框架

RNADE的偽代碼如算法1所示。

算法1 RNADE的偽代碼初始化:隨機(jī)生成NP個體;設(shè)置k=1,MF和MCR中所有元素為0.5;while終止條件未達(dá)到do 重置SF=?,SCR=?; fori=1toNPdo根據(jù)式(13)和(14)生成FGi和CRGi;根據(jù)式(12)計(jì)算鄰域個體數(shù)量NGi;為第i個體隨機(jī)選擇NGi個領(lǐng)域個體,選擇最優(yōu)個體為Xnbest;根據(jù)式(11)執(zhí)行“DE/neighbor/1”生成變異個體VGi;根據(jù)式(9)執(zhí)行交叉操作生成實(shí)驗(yàn)個體UGi;iff(UGi)H; endifendwhile輸出:最優(yōu)解x

RNADE的基本流程如圖4所示。

圖4 RNADE流程圖

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

為了驗(yàn)證RNADE求解WTA問題的尋優(yōu)性能,本文以空戰(zhàn)為背景設(shè)置小、中、大3種規(guī)模的武器目標(biāo)數(shù)量,其中武器數(shù)量可表示為戰(zhàn)機(jī)攜帶導(dǎo)彈數(shù)量,目標(biāo)可表示為敵機(jī)數(shù)量,則在小規(guī)模情況下可表示為單機(jī)或雙機(jī)協(xié)同空戰(zhàn)情境,中規(guī)模情況下可表示為具有4～6架戰(zhàn)機(jī)的中隊(duì)編隊(duì)空戰(zhàn)情境,大規(guī)模情況下可表示為“蜂群作戰(zhàn)”模式下我方防空火力分配任務(wù)情境。實(shí)驗(yàn)分為武器數(shù)量大于目標(biāo)數(shù)量(m>n)、武器數(shù)量等于目標(biāo)數(shù)量(m=n)和武器數(shù)量小于目標(biāo)數(shù)量(m

表1 測試分組設(shè)定

實(shí)驗(yàn)參數(shù)設(shè)置如下:武器i對目標(biāo)j的毀傷概率pi j=0.4+ρ(0.95-0.4),目標(biāo)j的威脅系數(shù)為vj=0.4+ρ(0.9-0.4);每組實(shí)驗(yàn)各算法獨(dú)立運(yùn)行30遍,最大函數(shù)評價(jià)次數(shù)max FES=2 000D,個體維度D=m。采用置信度為5%的威爾科克森秩和檢驗(yàn)評估RNADE與其他算法之間顯著性差異,“+/≈/-”分別表示RNADE優(yōu)于/近似/劣于所對比算法。

4.2 RNADE與先進(jìn)DE比較分析

為了驗(yàn)證RNADE處理DWAT問題的性能,將RNADE與標(biāo)準(zhǔn)DE[23]、JADE[24]、SaDE[25],MGBDE[26]以及DADDE[27]進(jìn)行對比,各算法參數(shù)設(shè)置與原文獻(xiàn)一致。

表2～表4分別為武器數(shù)量大于目標(biāo)數(shù)量m>n、武器數(shù)量等于目標(biāo)數(shù)量m=n及武器數(shù)量小于目標(biāo)數(shù)量m

表2 實(shí)驗(yàn)結(jié)果(m>n)

表3 實(shí)驗(yàn)結(jié)果(m=n)

表4 實(shí)驗(yàn)結(jié)果(m

由表2～表4實(shí)驗(yàn)結(jié)果可知,RNADE在測試中尋優(yōu)效果最好,18組測試中均獲得最優(yōu)值。根據(jù)威爾科克森秩和檢驗(yàn)評估結(jié)果表明,標(biāo)準(zhǔn)DE、JADE、SaDE、MGBDE、DADDE分別僅有2、2、5、2、4組測試獲得與RNADE近似的結(jié)果,其余測試結(jié)果均劣于RNADE。

分析表2～表4實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn),5種算法獲得與RNADE近似結(jié)果的測試均為小規(guī)模武器目標(biāo)數(shù)量情況,中規(guī)模和大規(guī)模武器目標(biāo)數(shù)量情況下5種算法尋優(yōu)性能均明顯劣于RNADE,尤其在大規(guī)模武器目標(biāo)數(shù)量情況下;其次,相較于武器數(shù)量大于目標(biāo)數(shù)量(m>n)和武器數(shù)量小于目標(biāo)數(shù)量(m

為直觀地評估RNADE尋優(yōu)性能,圖5給出了RNADE,標(biāo)準(zhǔn)DE、JADE、SaDE、MGBDE以及DADDE在18組測試中的收斂曲線。其中,橫坐標(biāo)FES表示為函數(shù)評價(jià)次數(shù),即實(shí)驗(yàn)過程中調(diào)用式(3)對個體進(jìn)行評價(jià)的次數(shù),縱坐標(biāo)為目標(biāo)函數(shù)的適應(yīng)值。

圖5 各算法收斂曲線圖

由圖5可看出,RNADE的收斂曲線均快于其余5種算法,具有更快的尋優(yōu)速度。盡管在小規(guī)模情況下其余5種算法的收斂速度并未明顯劣于RNADE,但中規(guī)模及大規(guī)模情況下差距明顯,如圖5(h)、圖5(l)、圖5(n)、圖5(q)。其次,從圖5中可以看出,RNADE在武器數(shù)量等于目標(biāo)數(shù)量m=n情況時,收斂速度遠(yuǎn)優(yōu)于其余5種算法,武器目標(biāo)規(guī)模越大,優(yōu)勢越明顯。最后,圖5還可以看出,除RNADE外其余5種算法均存在陷入局部最優(yōu),導(dǎo)致算法早熟現(xiàn)象,例如大規(guī)模武器數(shù)量等于目標(biāo)數(shù)量(m=n)情況下。綜合以上,說明RNADE出色的尋優(yōu)速度和尋優(yōu)精度。

采用取整操作會對算法處理小規(guī)模武器目標(biāo)數(shù)量的WTA問題產(chǎn)生一定的影響,因?yàn)樵谖淦髂繕?biāo)數(shù)量較小的情況下,采取取整操作會使得原本尋優(yōu)性能略差的算法在一定幾率下也同樣獲得最優(yōu)解。但是在中規(guī)模和大規(guī)模武器目標(biāo)數(shù)量的WTA問題上,由于取整操作所帶來的這種影響就變得非常小,根據(jù)表2～表4的結(jié)果和圖5的收斂曲線可以看出,RNADE的尋優(yōu)性能遠(yuǎn)優(yōu)于其余算法,尋優(yōu)精度和尋優(yōu)速度均表現(xiàn)最好。這是因?yàn)殡S著維數(shù)的增加,武器與目標(biāo)之間的分配方案急劇擴(kuò)大,武器與目標(biāo)之間的對應(yīng)關(guān)系變得復(fù)雜,因此取整操作帶來的影響將變的非常小,因取整操作而使得算法獲得最優(yōu)解的概率非常低。其次,在小規(guī)模武器目標(biāo)情況下,我們依然可以看出RNADE收斂速度要優(yōu)于其余算法,總體比較來看RNADE性能仍要勝于其余算法。

為了更直觀地比較6種算法30次運(yùn)行最優(yōu)解的分布情況,分析各算法穩(wěn)定性,圖6給出了6種算法18組測試的盒圖,算法1～算法6分別代表RNADE、標(biāo)準(zhǔn)DE、JADE、SaDE、MGBDE以及DADDE。

由圖6可看出,在小規(guī)模武器目標(biāo)數(shù)量情況下6種算法最優(yōu)解分布情況集中,僅少數(shù)幾組測試存在極端異常值情況,各算法穩(wěn)定性相對較高;在中規(guī)模及大規(guī)模武器目標(biāo)數(shù)量情況下,RNADE穩(wěn)定性最好,尤其是在武器數(shù)量大于目標(biāo)數(shù)量(m>n)和武器數(shù)量小于目標(biāo)數(shù)量(m

圖6 各算法盒圖

仿真結(jié)果顯示RNADE在30次實(shí)驗(yàn)中均收斂到相同的武器目標(biāo)分配方案。由于中規(guī)模和大規(guī)模武器目標(biāo)數(shù)量較大,在此僅列出小規(guī)模情況下尋優(yōu)分配方案。

X5-3=(2,3,3,1,1)與之對應(yīng)的分配決策為{W1T2,W2T3,W3T3,W4T1,W5T1};

X5-5=(2,1,3,4,5)與之對應(yīng)的分配決策為{W1T2,W2T1,W3T3,W4T4,W5T5};

X3-5=(3,1,2)與之對應(yīng)的分配決策為{W1T3,W2T1,W3T2};

X8-5=(2,3,2,4,1,4,3,5)與之對應(yīng)的分配決策為{W1T2,W2T3,W3T2,W4T4,W5T1,W6T4,W7T3,W8T5};

X8-8=(5,8,4,2,3,6,1,7)與之對應(yīng)的分配決策為{W1T5,W2T8,W3T4,W4T2,W3T1,W6T6,W7T1,W8T7};

X5-8=(4,8,1,3,5)與之對應(yīng)的分配決策為{W1T4,W2T8,W3T1,W4T3,W5T5}。

采用弗里德曼測試進(jìn)一步比較RNADE與其余5種算法處理WTA問題的性能。

基于弗里德曼測試的算法平均排序值結(jié)果如表5所示,黑體為最優(yōu)值,由表5可知RNADE取得最優(yōu)排序值,6種算法基于弗里德曼測試的排序?yàn)?/p>

表5 弗里德曼測試平均排序值

RNADEfJADEfSaDEfMGBDEfDADDEfDE

RNADE與5種算法的多重檢驗(yàn)結(jié)果如表6所示,由表6可知,RNADE與DE、MGBDE、DADDE存在顯著性差異。通過以上分析可知RNADE處理WTA問題的性能明顯優(yōu)于其余算法。

表6 多重檢驗(yàn)結(jié)果

綜合以上結(jié)果可知RNADE處理WTA問題具有良好的效果,尋優(yōu)性能越明顯優(yōu)于其余算法。相較于RNADE,尋優(yōu)性能存在顯著性差異的3種算法:標(biāo)準(zhǔn)DE采用單一變異策略及固定控制參數(shù),無法隨進(jìn)化過程進(jìn)行動態(tài)調(diào)整,導(dǎo)致算法多樣性不足,容易陷入局部最優(yōu),尋優(yōu)性能差;DADDE雖采用2種變異策略,但策略本身缺乏動態(tài)更新能力,其次參數(shù)的整定采用確定性機(jī)制的自適應(yīng)策略,進(jìn)化過程中也未能充分利用“精英”信息,導(dǎo)致尋優(yōu)效果較差;MGBDE改進(jìn)變異策略,利用最優(yōu)個體信息的同時采用高斯分布提高隨機(jī)性,但MGBDE采用固定的控制參數(shù),無法隨進(jìn)化過程調(diào)整種群的變異和交叉,導(dǎo)致尋優(yōu)性能差。

RNADE能夠充分利用進(jìn)化過程中的“精英”信息提高算法的尋優(yōu)精度,變異操作中以最優(yōu)個體作為基向量,控制參數(shù)根據(jù)“精英”存檔動態(tài)更新;同時能夠保證算法隨機(jī)性提高算法的動態(tài)性能,變異操作中為每一個體產(chǎn)生隨機(jī)鄰域,控制參數(shù)根據(jù)高斯分布和柯西分布動態(tài)更新。RNADE充分結(jié)合“最優(yōu)性”和“隨機(jī)性”,提高處理WTA問題的尋優(yōu)精度和尋優(yōu)速度。

5 結(jié) 論

為提高求解WTA問題的精度和速度,本文提出一種基于RNADE。采用“DE/neighbor/1”策略執(zhí)行變異操作,為每一個體生成隨機(jī)領(lǐng)域,領(lǐng)域中個體數(shù)量隨進(jìn)化動態(tài)更新,以平衡算法開發(fā)和探索能力;引入基于歷史進(jìn)化信息的自適應(yīng)參數(shù)策略,根據(jù)“精英”信存檔動態(tài)更新每代個體的變異因子和交叉因子。為驗(yàn)證RNADE求解DWTA問題的高效性,設(shè)置小、中、大3種武器目標(biāo)規(guī)模,共18組測試,分別與標(biāo)準(zhǔn)DE、JADE、SaDE、MGBDE、DADDE進(jìn)行比較。實(shí)驗(yàn)結(jié)果驗(yàn)證了RNADE求解DWTA問題的有效性,相較于對比算法,RNADE具有尋優(yōu)精度高、收斂速度快、魯棒性強(qiáng)的優(yōu)點(diǎn)。