一種基于DQN的改進NSGA-II算法?

吳亞楠 張 劍

（武漢數字工程研究所 武漢 430205）

1 引言

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

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

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

2 問題描述與建模

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

圖1 WTA方案優化

3 改進NSGA-II算法用于求解彈目分配問題

3.1 DQN算法優化遷徙參數思想

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

3.2 DQN算法要素設計

基于深度強化學習DQN 算法對傳統單種群NSGA-II算法進行改進，首先必須用馬爾可夫決策過程進行建模，對狀態空間、動作空間、回報函數等進行設計。本文以種群1和種群2的當前收斂性與初始收斂性的比值、當前多樣性與初始多樣性的比值作為狀態空間。選用七點平均距離SPAD［13］作為收斂性衡量指標，選用指標Δ*［14］作為多樣性衡量指標。以三個遷徙參數p、q、m 的增大、減小、不變作為動作空間，根據狀態設計相應的回報值，具體細節如下。

1）狀態空間S

狀態St表征當前種群收斂性、多樣性與初始種群收斂性、多樣性的比值，即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分別表示根據智能體動作獲取三個遷徙參數值，并按照參數值在環境中執行完相應的遷徙操作后當前種群1、種群2的收斂性值、多樣性值。

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

2）動作空間A

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

表1 遷徙參數調整

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

3）回報函數R

本文優化的目的在于尋找p，q，m 三個參數的最佳值，以使得與之前種群相比，種群1和種群2的收斂性、多樣性指標均有所改善。因此，對回報函數設計如下式所示。

當回報值Ri(i=1,2,3,4) 的值為0.5 時，代表執行遷徙動作后當前種群收斂性或多樣性優于初始種群。

3.3 改進NSGA-II算法實現

將雙種群NSGA-II算法主體部分作為環境，它將根據智能體選定的動作獲取三項遷徙參數的值，在相應遺傳代數執行遷徙操作，并根據當前遷徙操作的結果，將相應回報值返回至智能體。

主程序DQN算法實現步驟如表2所示，主要描述了算法如何進行動作選擇、如何訓練Q網絡等細節。

表2 DQN算法實現步驟

環境更新部分的算法步驟如表3 所示，主要描述了環境如何根據智能體的動作獲取相應的遷徙參數，對狀態進行更新等。

表3 環境更新算法步驟

當網絡訓練完成后，即可利用訓練好的Q網絡對遷徙參數進行調整優化，并在優化完成后繼續執行遺傳迭代，直到獲得最終的Pareto 最優解集結果。該部分的算法步驟如表4所示。

表4 驗證測試算法步驟

4 仿真實驗

4.1 想定設計

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

表5 目標威脅程度

表6 反艦導彈基本信息

表7 導彈對目標毀傷概率

表8 毀傷程度區間

4.2 實驗結果與分析

設置對比實驗來驗證本文基于深度強化學習的改進NSGA-II 算法在求解WTA 問題上的有效性，選擇傳統單種群NSGA-II 算法、普通雙種群NSGA-II算法（遷徙參數按照人類經驗設置）、與本文方法進行對比，比較最終生成的Pareto 解集的收斂性、多樣性、算法耗時長短等。

1）收斂性、多樣性對比

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

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

2）算法運行耗時對比

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

表10 算法運行耗時

3）優化目標函數值對比

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

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

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

5 結語

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