吳亞楠 張 劍

（武漢數(shù)字工程研究所 武漢 430205）

1 引言

武器目標(biāo)分配（Weapon Target Assignment，WTA）問題，又稱導(dǎo)彈分配問題（Missile Assignment Prob?lem，MAP），起源于20 世紀(jì)50 年代［1］，是作戰(zhàn)指揮控制系統(tǒng)所要解決的重點(diǎn)問題。武器目標(biāo)分配方案是否實(shí)時(shí)、準(zhǔn)確、有效，將直接影響軍事對抗中能否取得更好的作戰(zhàn)效能并盡量減少作戰(zhàn)資源消耗［2］。

當(dāng)前，已有多種方法可用于求解WTA 問題。其中，以NSGA-II 算法等為代表的智能優(yōu)化算法［3～5］，以及由這些算法組合而成的混合優(yōu)化算法［6～8］，是目前WTA 問題的主流求解方法。受算法本身原理機(jī)制的影響，直接將NSGA-II 算法應(yīng)用于求解WTA 問題仍然存在無法規(guī)避的缺陷，如算法容易陷入局部最優(yōu)、多樣性不足。近年來，強(qiáng)化學(xué)習(xí)領(lǐng)域發(fā)展勢頭迅猛，有些學(xué)者開始思考將強(qiáng)化學(xué)習(xí)主動探索、不斷試錯的特性與傳統(tǒng)優(yōu)化算法結(jié)合的可能性［9～11］。封碩等［12］提出可采用雙種群“遷徙思想”對傳統(tǒng)單種群NSGA-II 算法進(jìn)行改進(jìn)，引入強(qiáng)化學(xué)習(xí)Q-learning 算法來對遷徙操作涉及到的相關(guān)參數(shù)m主動地進(jìn)行優(yōu)化，并通過實(shí)驗(yàn)驗(yàn)證了該做法可避免傳統(tǒng)單種群NSGA-II算法陷入局部最優(yōu)，解集具有更好的分布性，但其他兩項(xiàng)遷徙參數(shù)p、q的設(shè)置對算法的最終結(jié)果同樣起著重要的作用。

本文針對多類型反艦導(dǎo)彈攻擊艦艇編隊(duì)的WTA 問題進(jìn)行研究，首先對數(shù)學(xué)建模過程進(jìn)行簡要介紹，分析海戰(zhàn)場背景下可能影響分配方案結(jié)果的多項(xiàng)因素，建立多目標(biāo)優(yōu)化數(shù)學(xué)模型。為有效求解該模型，本文提出了基于深度強(qiáng)化學(xué)習(xí)的改進(jìn)NSGA-II算法，采用深度強(qiáng)化學(xué)習(xí)和雙種群“遷徙”思想對傳統(tǒng)單種群NSGA-II算法進(jìn)行改進(jìn)，通過深度強(qiáng)化學(xué)習(xí)DQN 算法對遷徙操作涉及到的多個(gè)參數(shù)進(jìn)行優(yōu)化。仿真實(shí)驗(yàn)表明，與傳統(tǒng)單種群NS?GA-II 算法、遷徙參數(shù)按照人類經(jīng)驗(yàn)設(shè)置的普通雙種群NSGA-II算法進(jìn)行對比，本文所提出的基于深度強(qiáng)化學(xué)習(xí)的改進(jìn)NSGA-II算法可提升算法性能，減少算法耗時(shí)，獲得更好的分配方案集結(jié)果。

2 問題描述與建模

在復(fù)雜的海戰(zhàn)場環(huán)境下，武器目標(biāo)分配方案的形成一方面要考慮最大化對敵毀傷效果，另一方面要盡量減少彈藥消耗。除此之外，還需考慮多個(gè)約束條件，如對單個(gè)目標(biāo)所分配彈藥上限、各類型反艦導(dǎo)彈總彈量、反艦導(dǎo)彈所搭載平臺上火力通道數(shù)限制、反艦導(dǎo)彈作用距離限制等。只有全面細(xì)致地考慮代價(jià)和收益兩方面因素，綜合各項(xiàng)約束條件，才能反映真實(shí)的戰(zhàn)場情況，得到更加科學(xué)、合理的武器—目標(biāo)分配方案。因此，本文所研究的WTA問題實(shí)質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問題，如圖1所示。

圖1 WTA方案優(yōu)化

3 改進(jìn)NSGA-II算法用于求解彈目分配問題

3.1 DQN算法優(yōu)化遷徙參數(shù)思想

文獻(xiàn)［12］提出可采用雙種群“遷徙思想”改善傳統(tǒng)單種群NSGA-II算法的缺陷，首先設(shè)置兩個(gè)獨(dú)立種群1和種群2，令兩種群分別進(jìn)行遺傳演化，在進(jìn)化初期的前p 代每隔q 代令種群1 的前m 個(gè)精英個(gè)體和種群2 的隨機(jī)m 個(gè)個(gè)體進(jìn)行交換，交換后形成新的種群1和種群2，隨后兩種群繼續(xù)尋優(yōu)進(jìn)化，直到達(dá)到終止條件。此時(shí)，共有p、q、m 三項(xiàng)遷徙參數(shù)需要確定，本文采用深度強(qiáng)化學(xué)習(xí)DQN 算法，通過智能體與環(huán)境的交互來同時(shí)對三項(xiàng)遷徙參數(shù)進(jìn)行動態(tài)調(diào)整，進(jìn)而提高算法性能，獲得更好的Pareto最優(yōu)方案集。

3.2 DQN算法要素設(shè)計(jì)

基于深度強(qiáng)化學(xué)習(xí)DQN 算法對傳統(tǒng)單種群NSGA-II算法進(jìn)行改進(jìn)，首先必須用馬爾可夫決策過程進(jìn)行建模，對狀態(tài)空間、動作空間、回報(bào)函數(shù)等進(jìn)行設(shè)計(jì)。本文以種群1和種群2的當(dāng)前收斂性與初始收斂性的比值、當(dāng)前多樣性與初始多樣性的比值作為狀態(tài)空間。選用七點(diǎn)平均距離SPAD［13］作為收斂性衡量指標(biāo)，選用指標(biāo)Δ*［14］作為多樣性衡量指標(biāo)。以三個(gè)遷徙參數(shù)p、q、m 的增大、減小、不變作為動作空間，根據(jù)狀態(tài)設(shè)計(jì)相應(yīng)的回報(bào)值，具體細(xì)節(jié)如下。

1）狀態(tài)空間S

狀態(tài)St表征當(dāng)前種群收斂性、多樣性與初始種群收斂性、多樣性的比值，即St=(SPAD1_m/SPAD10,SPAD2_m/SPAD20,VAR1_m/VAR10,VAR2_m/VAR20)。其中，SPAD10、SPAD20、VAR10、VAR20 分別表示初始種群1、初始種群2的收斂性值、多樣性值；SPAD1_m、SPAD2_m、VAR1_m、VAR2_m分別表示根據(jù)智能體動作獲取三個(gè)遷徙參數(shù)值，并按照參數(shù)值在環(huán)境中執(zhí)行完相應(yīng)的遷徙操作后當(dāng)前種群1、種群2的收斂性值、多樣性值。

根據(jù)比值大小，狀態(tài)的意義可分為與初始種群相比遷徙后數(shù)值增大、數(shù)值減小、數(shù)值保持不變，兩個(gè)種群共有4 個(gè)比值，總共3×3×3×3=81 種組合方式，即81 種狀態(tài)，目標(biāo)狀態(tài)為4 個(gè)比值均小于1（因收斂性衡量指標(biāo)SPAD和多樣性衡量指標(biāo)Δ*均為值越小越好型），表示按照遷徙參數(shù)值執(zhí)行相應(yīng)的遷徙操作后，當(dāng)前兩種群的收斂性和多樣性均優(yōu)于初始兩種群。

2）動作空間A

動作空間的動作設(shè)計(jì)為對p、q、m 三個(gè)遷徙參數(shù)大小的更改，如表1 所示。初始化種群的同時(shí)會隨機(jī)設(shè)定三個(gè)參數(shù)大小在一定范圍內(nèi)，用p_random、q_random、m_random分別代表三個(gè)遷徙參數(shù)的初始值。動作空間的每一個(gè)動作是在三個(gè)參數(shù)原基礎(chǔ)上進(jìn)行增加、減少或保持不變，每個(gè)參數(shù)的改變量由事先設(shè)定，如A×popsize=10、B×popsize=1、C×popsize=2，其中popsize=100代表種群大小，A、B、C分別代表參數(shù)p、參數(shù)q、參數(shù)m的調(diào)整比例。

表1 遷徙參數(shù)調(diào)整

如表1 所示，動作空間共有1×3×3=9 個(gè)動作可供選擇，其中參數(shù)p 的數(shù)值不可減小或保持不變，因參數(shù)p代表在前p代執(zhí)行遷徙，而遺傳操作一經(jīng)執(zhí)行不可逆轉(zhuǎn)，故參數(shù)p只可增大。

3）回報(bào)函數(shù)R

本文優(yōu)化的目的在于尋找p，q，m 三個(gè)參數(shù)的最佳值，以使得與之前種群相比，種群1和種群2的收斂性、多樣性指標(biāo)均有所改善。因此，對回報(bào)函數(shù)設(shè)計(jì)如下式所示。

當(dāng)回報(bào)值Ri(i=1,2,3,4) 的值為0.5 時(shí)，代表執(zhí)行遷徙動作后當(dāng)前種群收斂性或多樣性優(yōu)于初始種群。

3.3 改進(jìn)NSGA-II算法實(shí)現(xiàn)

將雙種群NSGA-II算法主體部分作為環(huán)境，它將根據(jù)智能體選定的動作獲取三項(xiàng)遷徙參數(shù)的值，在相應(yīng)遺傳代數(shù)執(zhí)行遷徙操作，并根據(jù)當(dāng)前遷徙操作的結(jié)果，將相應(yīng)回報(bào)值返回至智能體。

主程序DQN算法實(shí)現(xiàn)步驟如表2所示，主要描述了算法如何進(jìn)行動作選擇、如何訓(xùn)練Q網(wǎng)絡(luò)等細(xì)節(jié)。

表2 DQN算法實(shí)現(xiàn)步驟

環(huán)境更新部分的算法步驟如表3 所示，主要描述了環(huán)境如何根據(jù)智能體的動作獲取相應(yīng)的遷徙參數(shù)，對狀態(tài)進(jìn)行更新等。

表3 環(huán)境更新算法步驟

當(dāng)網(wǎng)絡(luò)訓(xùn)練完成后，即可利用訓(xùn)練好的Q網(wǎng)絡(luò)對遷徙參數(shù)進(jìn)行調(diào)整優(yōu)化，并在優(yōu)化完成后繼續(xù)執(zhí)行遺傳迭代，直到獲得最終的Pareto 最優(yōu)解集結(jié)果。該部分的算法步驟如表4所示。

表4 驗(yàn)證測試算法步驟

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

4.1 想定設(shè)計(jì)

假設(shè)某一時(shí)刻，我方?jīng)Q定對敵方艦艇編隊(duì)發(fā)起攻擊。初始狀態(tài)下，我方共有4 種不同類型的反艦導(dǎo)彈，敵艦編隊(duì)共有5 艘艦船目標(biāo)，一些參數(shù)信息詳見表5～表8，數(shù)據(jù)來源參考文獻(xiàn)［15］。規(guī)定整個(gè)過程中分給各目標(biāo)的彈量總上限均為12 枚，避免造成彈藥浪費(fèi)。算法遺傳迭代終止后輸出武器目標(biāo)分配方案，作為一個(gè)打擊波次。每波次打擊結(jié)束后評估各目標(biāo)的毀傷程度，確定剩余彈量，根據(jù)戰(zhàn)場信息并結(jié)合表8 確定是否繼續(xù)解算下一波次方案，規(guī)定對所有目標(biāo)的毀傷程度應(yīng)為重傷或擊沉。

表5 目標(biāo)威脅程度

表6 反艦導(dǎo)彈基本信息

表7 導(dǎo)彈對目標(biāo)毀傷概率

表8 毀傷程度區(qū)間

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

設(shè)置對比實(shí)驗(yàn)來驗(yàn)證本文基于深度強(qiáng)化學(xué)習(xí)的改進(jìn)NSGA-II 算法在求解WTA 問題上的有效性，選擇傳統(tǒng)單種群NSGA-II 算法、普通雙種群NSGA-II算法（遷徙參數(shù)按照人類經(jīng)驗(yàn)設(shè)置）、與本文方法進(jìn)行對比，比較最終生成的Pareto 解集的收斂性、多樣性、算法耗時(shí)長短等。

1）收斂性、多樣性對比

將上述三種算法的程序各自獨(dú)立運(yùn)行20 次，記錄每一次運(yùn)行后最終種群的收斂性值、多樣性值，對20 次的結(jié)果取平均，結(jié)果如表9 所示。由表可知，對比傳統(tǒng)單種群NSGA-II 算法，本文的改進(jìn)算法結(jié)果在收斂性和多樣性上均有一定程度的提升。進(jìn)一步對比普通雙種群NSGA-II 算法和本文方法，可以看出本文所提出的基于DQN 的改進(jìn)NS?GA-II 算法在收斂性和多樣性上與對比算法表現(xiàn)基本一致。

表9 算法收斂性與多樣性對比

2）算法運(yùn)行耗時(shí)對比

記錄三種算法生成最終Pareto 前沿的運(yùn)行時(shí)間，將20 次運(yùn)行耗時(shí)取平均值，結(jié)果如表10 所示。由表10 可知，與其他兩種算法進(jìn)行對比，盡管本文基于深度強(qiáng)化學(xué)習(xí)的改進(jìn)NSGA-II 算法前期需要較久的時(shí)間用于模型的訓(xùn)練，但在最后的優(yōu)化階段耗時(shí)較少，表現(xiàn)更佳。

表10 算法運(yùn)行耗時(shí)

3）優(yōu)化目標(biāo)函數(shù)值對比

將三種算法的程序各自獨(dú)立運(yùn)行20 次，記錄每次最終Pareto前沿結(jié)果中目標(biāo)函數(shù)f1的最大值、f2的最小值，繪制兩個(gè)目標(biāo)函數(shù)的20 次結(jié)果的統(tǒng)計(jì)箱線圖如圖2、圖3 所示，從圖可以看出，傳統(tǒng)單種群NSGA-II 算法在兩個(gè)目標(biāo)函數(shù)上的數(shù)據(jù)均存在較大的波動，表明該方法的解集結(jié)果隨機(jī)性較大，不夠穩(wěn)定；雙種群NSGA-II 算法和本文方法均引入了遷徙思想，可在傳統(tǒng)單種群NSGA-II算法基礎(chǔ)上改善不穩(wěn)定的問題；對雙種群NSGA-II算法和本文方法做進(jìn)一步對比可知，本文方法將深度強(qiáng)化學(xué)習(xí)DQN 用于遷徙參數(shù)的優(yōu)化，盡管可以在算法性能和算法耗時(shí)上獲得一定的改善，但算法在魯棒性上略顯不足。

圖2 不同算法對敵毀傷箱型圖

圖3 不同算法資源消耗箱型圖

5 結(jié)語

本文針對傳統(tǒng)單種群NSGA-II 算法在求解WTA 數(shù)學(xué)模型時(shí)，容易陷入局部最優(yōu)、多樣性不足等缺陷，提出可引入深度強(qiáng)化學(xué)習(xí)和雙種群“遷徙”思想對其進(jìn)行改進(jìn)，利用深度強(qiáng)化學(xué)習(xí)DQN 算法來對“遷徙”操作涉及到的三項(xiàng)參數(shù)進(jìn)行優(yōu)化。面向具體的海戰(zhàn)場武器目標(biāo)分配場景進(jìn)行仿真實(shí)驗(yàn)，結(jié)果顯示：與傳統(tǒng)單種群NSGA-II 算法、遷徙參數(shù)依靠人類經(jīng)驗(yàn)進(jìn)行設(shè)置的普通雙種群NSGA-II 算法相比，本文所提出的基于深度強(qiáng)化學(xué)習(xí)的改進(jìn)NSGA-II 算法可以獲得更好的收斂性、多樣性結(jié)果，且算法耗時(shí)更少，驗(yàn)證了本文改進(jìn)方法的有效性。