改進差分進化算法求解武器目標分配問題

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

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

0 引 言

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

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

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

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

1 DWTA問題描述

DWTA屬于多階段決策問題,其突出特點是在各階段武器目標分配過程中,需實時考慮戰場態勢變化,適應動態求解環境,以獲得全局最優攻擊方案。“攻擊-觀察-攻擊”是解決多階段DWTA問題的常用策略,如圖1所示。

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

“觀察”指對戰場態勢進行分析,確定攻擊目標及可用武器;“攻擊”指求解武器與目標的分配結果,根據決策實施打擊,“觀察-攻擊”的過程類似于SWTA問題[19],則DWTA可表示為

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

(1)

本文選取目標生存概率總期望值最小作為分配決策優化目標,則優化模型可表示為

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

(2)

(3)

約束條件為

(4)

(5)

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

2 改進差分進化算法

2.1 標準DE算法

DE算法是基于“貪婪競爭”的智能算法,通過變異、交叉、選擇操作實現群進化。

(1)“DE/rand/1”

(6)

(2)“DE/best/1”

(7)

(8)

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

(9)

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

(10)

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

2.2 隨機鄰域變異策略

本文提出一種基于隨機鄰域的變異策略,進化中為每代個體從當前種群隨機挑選N個“鄰居”,其中最優個體作為基向量,執行“DE/neighbor/1”操作,可表示為

(11)

式中,Xnbest為鄰域中最優個體;Xr1,Xr2為除Xnbest外,鄰域內隨機挑選的個體。

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

(12)

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

2.3 自適應參數策略

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

(13)

(14)

(16)

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

(17)

(18)

本策略充分利用“精英”信息保證控制參數最優性,同時采用柯西分布和正態分布提高隨機性,保證種群多樣性。

2.4 算法復雜度分析

3 基于RNADE的DWTA問題求解

3.1 DWTA問題決策流程

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

圖2 DWAT問題決策流程

由圖2可知,DWAT決策需根據戰場態勢分析結果確定當前階段所需攻擊目標及可用武器,將所確定的目標及武器輸入RNADE執行優化迭代以獲得武器目標分配決策,DWAT決策過程還需對分配結果及戰場態勢進行評估與監控,根據分配方案效果和戰場態勢信息,確定是否需要繼續迭代求解。DWTA決策過程需動態更新所需攻擊目標及可用武器,因此對算法尋優速度具有嚴苛要求,以滿足武器目標分配決策的需求。

3.2 整數編碼操作

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

Xi=(xi1,xi2,…,xim)

(19)

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

圖3 整數編碼

由圖3可知,分配決策為

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

則根據整數編碼操作獲得的個體向量為

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

3.3 RNADE流程框架

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

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

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

圖4 RNADE流程圖

4 實驗分析

4.1 實驗參數設置

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

表1 測試分組設定

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

4.2 RNADE與先進DE比較分析

為了驗證RNADE處理DWAT問題的性能,將RNADE與標準DE[23]、JADE[24]、SaDE[25],MGBDE[26]以及DADDE[27]進行對比,各算法參數設置與原文獻一致。

表2～表4分別為武器數量大于目標數量m>n、武器數量等于目標數量m=n及武器數量小于目標數量m

表2 實驗結果(m>n)

表3 實驗結果(m=n)

表4 實驗結果(m

由表2～表4實驗結果可知,RNADE在測試中尋優效果最好,18組測試中均獲得最優值。根據威爾科克森秩和檢驗評估結果表明,標準DE、JADE、SaDE、MGBDE、DADDE分別僅有2、2、5、2、4組測試獲得與RNADE近似的結果,其余測試結果均劣于RNADE。

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

為直觀地評估RNADE尋優性能,圖5給出了RNADE,標準DE、JADE、SaDE、MGBDE以及DADDE在18組測試中的收斂曲線。其中,橫坐標FES表示為函數評價次數,即實驗過程中調用式(3)對個體進行評價的次數,縱坐標為目標函數的適應值。

圖5 各算法收斂曲線圖

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

采用取整操作會對算法處理小規模武器目標數量的WTA問題產生一定的影響,因為在武器目標數量較小的情況下,采取取整操作會使得原本尋優性能略差的算法在一定幾率下也同樣獲得最優解。但是在中規模和大規模武器目標數量的WTA問題上,由于取整操作所帶來的這種影響就變得非常小,根據表2～表4的結果和圖5的收斂曲線可以看出,RNADE的尋優性能遠優于其余算法,尋優精度和尋優速度均表現最好。這是因為隨著維數的增加,武器與目標之間的分配方案急劇擴大,武器與目標之間的對應關系變得復雜,因此取整操作帶來的影響將變的非常小,因取整操作而使得算法獲得最優解的概率非常低。其次,在小規模武器目標情況下,我們依然可以看出RNADE收斂速度要優于其余算法,總體比較來看RNADE性能仍要勝于其余算法。

為了更直觀地比較6種算法30次運行最優解的分布情況,分析各算法穩定性,圖6給出了6種算法18組測試的盒圖,算法1～算法6分別代表RNADE、標準DE、JADE、SaDE、MGBDE以及DADDE。

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

圖6 各算法盒圖

仿真結果顯示RNADE在30次實驗中均收斂到相同的武器目標分配方案。由于中規模和大規模武器目標數量較大,在此僅列出小規模情況下尋優分配方案。

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

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

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

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

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

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

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

基于弗里德曼測試的算法平均排序值結果如表5所示,黑體為最優值,由表5可知RNADE取得最優排序值,6種算法基于弗里德曼測試的排序為

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

RNADEfJADEfSaDEfMGBDEfDADDEfDE

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

表6 多重檢驗結果

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

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

5 結 論

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