強化學習在多階段裝備組合規劃問題中的應用*

張驍雄，丁 松，李明浩，丁 鯤，王 龍，義余江

(1. 國防科技大學 第六十三研究所, 江蘇 南京 210007; 2. 浙江財經大學 經濟學院, 浙江 杭州 310018;3. 國防科技大學 系統工程學院, 湖南 長沙 410073; 4. 西南電子電信技術研究所, 四川 成都 610041)

裝備組合規劃選擇是武器裝備體系頂層發展規劃中的重要問題，旨在對一定規劃期內裝備的具體建設發展進行總體規劃安排[1]。當前戰爭形態的變化，要求決策者們更多關注裝備組合作為一個整體發揮的效能，而不再局限于單一裝備的性能。同時，在考慮涉及多個階段的裝備組合方面，任何單一階段的最優裝備組合無法保證整個規劃周期內的最優性。因此，需要合理權衡規劃不同階段、不同周期的裝備組合選擇，從而更好地滿足未來作戰能力需求和完成多元化的任務。

裝備組合選擇源于項目組合選擇問題，Markowitz[2]最早提出了組合的概念來處理投資組合問題，旨在最大化投資收益的同時降低投資的市場風險，奠定了金融領域的投資組合理論。后來該理論又逐漸被應用到項目管理中輔助組合方案的比較和選型。針對軍事領域的組合選擇問題，常見的研究方法有多準則決策分析、專家評審法、價值分析法、風險分析法和資源分配方法等。例如，Kangaspunta等[3]在考慮裝備之間相互關聯的條件下，提出了一種費用-效能分析方法，輔助裝備組合選型；Yang等[4]對復雜軍事大數據環境下的武器裝備組合選擇優化問題進行了建模，并設計了一種自適應的遺傳算法對模型進行求解；Li等[5]基于能力規劃的思想，提出了一種基于異質網絡模型的高端裝備組合選擇方法；Dou等[6]提出了一種基于偏好基線值的方法，對裝備組合中冗余裝備的取舍進行了研究；王等[7]運用epoch-era思想，構建了區間型需求下的裝備組合多階段隨機規劃模型；孫等[8]提出了面向作戰需求的衛星裝備組合優化算法，對不同裝備組合的作戰效能進行了評估。

此外，還有一些比較流行的概念和方法論，被用來指導武器裝備組合選擇與優化，包括美國國防部提出的基于能力的規劃(Capability Based Planning, CBP)[9]、麻省理工學院提出的多屬性權衡空間探索(Multi-Attribute Tradespace Exploration, MATE)方法[10]、美國軍方提出的將費用當作獨立變量的方法[11]等。同時，裝備組合選擇與評估優化問題也引起了國內如軍事科學院[12-13]、國防大學[14]、國防科技大學[15-16]等高校與研究機構的廣泛關注，并取得了一定的研究成果。

不同學者對軍事領域的組合選擇進行了不同的探索和嘗試，然而現實中這種建模對數據要求較高，目前仍然缺少較為定量的模型與算法，在支撐裝備體系頂層規劃和決策方面仍略有不足。同時，隨著考慮的場景、規劃的裝備數目以及規劃周期的增多，傳統的數學方法以及多目標優化算法在求解效率上往往捉襟見肘。例如，對于一個具備K個場景和T個優化周期的規劃問題來說，決策者需要至少同時考慮K·T個優化目標，大大增加了求解難度。近年來，深度學習在圖片識別等任務上取得了前所未有的效果，強化學習也在AlphaGo方面效果顯著，它通過學習和選擇動作改變外界環境，并使用一個累計回報來定義任意動作序列的質量，正適用于解決多階段下的裝備組合選擇問題。

因此，擬借鑒強化學習的思想，研究多階段情形下的裝備組合優化問題。以裝備組合的效能和成本為目標，建立武器裝備組合規劃問題的多目標優化模型，并基于智能算法生成各階段的最優裝備組合。相比傳統研究，本文采用強化學習對不同階段的裝備組合進行尋優，生成整個規劃周期內的最優裝備組合方案。目前，鮮有研究將強化學習應用于多階段的裝備規劃研究方面，且該方法可以大大提高求解效率。

1 問題分析及建模

重點面向多個作戰場景，研究多階段情形下的裝備組合選擇問題。在橫向上突出面向不同場景的優化，縱向上突出時間維度，并非將單階段單場景下的裝備組合方案進行簡單疊加。任何針對單一場景或固定效能值的裝備組合選擇往往具有一定的片面性。圖1為多階段裝備組合發展示意圖，該問題研究的難點在于階段之間相互關聯，上一階段的決定直接影響后續階段的選擇，即每個階段裝備的解空間都發生變化，且裝備不能被重復選擇[17]。

圖1 多階段裝備組合發展示意圖Fig.1 An illustration of multi-period weapon portfolio selection

決策變量xi數學形式的定義為：

(1)

基于上述分析，針對單一階段的裝備組合優化問題，需要同時考慮K個可能場景，從當前可選裝備集合中選取合適的裝備組合，達到最大化裝備組合效能以及最小化裝備組合成本的目標。由此，可構建如式(2)所示目標函數。

(2)

其中，k∈[1,K]表示任意場景，K為場景總數，B表示總預算限制，δ為預算違背閾值。不等式約束限制了選中裝備組合的總成本。顯然，上述問題存在K+1個待優化目標。

武器裝備發展規劃需要對一個周期(通常為10 a)內的裝備進行統籌安排，并需要考慮裝備的更替。進一步，將上述優化問題擴展到多個階段，即決策者需要選擇能夠在整個規劃周期內最大化裝備組合效能并最小化裝備組合成本的方案。形式上，決策變量xit被定義為：

(3)

其中，Xt代表t階段可選裝備集合。

此時，目標函數在多階段多場景下變更為：

(4)

針對本節構建的多階段不確定性模型，可通過綜合使用多目標優化算法以及強化學習來處理。決策者可以有效應對未來階段的不確定性，并在每個階段產生的最優解中進行動態優化。

為使構造的模型更加合理，限定如下基本假設：

1)初始階段裝備項目已知，并在未來每一階段會有新裝備加入；

2)不同場景下各裝備的效能服從一定的分布，假定為正態分布；

3)裝備之間相互獨立，可并行發展；

4)各裝備發展成本已知且固定；

5)裝備一旦被選中發展則不可剔除。

2 模型構建求解

針對多階段裝備組合規劃問題，本節給出基于多目標優化算法以及強化學習的求解框架，并分小節闡述。

2.1 基于NSGA-Ⅲ的多目標優化算法

針對任一階段的裝備組合選型，需要在給定的決策空間中，最大化所選擇裝備組合的效能。由于考慮K個不同場景，且不同場景下裝備組合的效能無法進行簡單的疊加。故而，將其轉變為K+1個多目標優化問題，包括K個不同場景下裝備組合的效能以及裝備組合的成本。隨著場景數目以及裝備數目的增多，該多目標優化問題具備NP-hard性質。傳統的搜索方法效率低下，且使用范圍有限。

非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm-Ⅲ，NSGA-Ⅲ)[18]是一種新型智能優化算法，算法沿用了NSGA-Ⅱ的框架，但臨界層選擇方法采用參考點方法選擇個體，以使種群具有良好的分布性，保證更加準確的全局搜索能力。

針對上述待優化模型，首先初始化種群A，經過與NSGA-Ⅱ相同的選擇、交叉、變異后，選擇生成非支配個體A′。在對約束部分進行處理時，算法采用罰函數將個體違反約束的部分累加到目標函數中。之后，NSGA-Ⅲ將主要執行如下步驟。

(5)

式中，St為種群的個體集合。

之后尋找極值點，定義函數ASF。

(6)

遍歷每個函數，找到ASF數值最小的個體，即為極值點，再根據這些點計算出每個坐標點在對應坐標軸上的坐標值αi。之后，采用式(7)進行歸一化。

(7)

步驟3：關鍵層解的選擇策略。通過定義參考線的方式，計算種群每個個體到參考線的垂直距離，并將種群中的個體分別關聯到相應的參考點。假設與參考點j關聯的解的數量為ρj。從關鍵層選取ρj最小的參考點j加入種群中。若ρj=0，則從關鍵層里選取一個距離該參考點j最小的解加入種群，否則將該參考點從當前代中去除；若ρj≥1，則從關鍵層里面隨機挑選一個關聯到該參考點的解加入種群。

2.2 Q-Learning強化學習方法

通過對單一階段的求解，可以獲取每個階段的Pareto解。然而任意單階段的最優解未必是整個規劃周期里的最優選擇。同時，當前階段的選擇又直接影響著下一個階段的決策空間和選擇。

強化學習[19]是一種重要的機器學習方法之一，它明確考慮了目標導向的智能體與不確定環境交互的整個問題，旨在最大化期望積累獎勵。強化學習的特點正適用于解決多階段的裝備組合選擇與規劃問題。圖2為強化學習示意圖。主要包括如下幾個關鍵要素：環境、回報、動作和狀態。

圖2 強化學習示意圖Fig.2 Illustration of reinforcement learning

1)狀態(state)。描述當前agent所處的狀態，所有可能的狀態稱為狀態空間。狀態s對應不同的決策階段。不同的決策階段對應不同的選型空間，即截至當前階段所有未被選中發展的裝備集合。

2)行動(action)。指agent根據每次所處的狀態以及上一狀態的回報確定當前要執行的動作。本研究中的動作即決策者在各個時刻選取裝備組合的行為。

3)回報(reward)。強化學習是agent可以學習行為以實現最大化其累計獎勵的方式，即在發生狀態轉移的同時，環境反饋給agent的獎賞，且回報是一個標量。

4)策略(policy)。策略用來描述agent在不同狀態下執行的動作。常見的策略分為確定性策略以及隨機性策略。確定性策略描述在狀態s下執行確定動作a，隨機策略描述狀態s下執行動作a的概率。本模型中，動作a代表在t時刻選取xit=1 (xit∈Xt)的裝備選擇行為。

5)價值函數(value function)。強化學習是一個連續決策的過程，當下的行為是否正確需要經過一定的時間才能得知，因此需要用未來一段時間的收益來作為當下行為的評判。如果僅僅關注當前階段收益的最大化，容易導致決策的片面性。因此建立當前狀態下的價值函數：

Vπ(S)=Eπ[Rt+1+γRt+2+γ2Rt+3+…|St=s]

(8)

式中：γ為獎勵衰減因子，且取值區間為[0，1]。γ越接近1，則考慮越長遠；若為0，則表示只考慮一步的獎勵。

6)狀態轉移模型。使用狀態轉移模型來預測接下來的動作行為，即在當前狀態下執行某一動作導致的狀態以及產生的回報。采用動作轉移概率與動作狀態回報來描述該模型。

(9)

2.3 基于Q-Learning的多階段組合優化模型求解

多階段裝備組合規劃選型旨在從每一階段的非支配解中選取合適的方案構成整個規劃周期內的裝備組合，并使裝備組合效能和成本總體達到最優。任何單一階段的最優解的集合未必在多個階段仍然最優，同時需要綜合考慮每一階段，決策對未來的影響。結合Q-Learning的算法，基于強化學習的多階段裝備組合規劃問題的求解步驟如下。

步驟1：在各階段，刪除之前階段已被選中發展的裝備組合，同時增加新型待發展的裝備集合(代指可供選擇發展的新增裝備)，更新并生成當前可供選擇發展的裝備集合，即當前階段的解空間。

步驟2：針對K個場景的選擇規劃問題，每個階段存在K+1個目標待優化，采用NSGA-Ⅲ算法對當前階段的目標進行求解，生成當前階段可供選擇的非支配Pareto解。

步驟3：采用隨機探索或者利用最優Q值的方式，從上階段的Pareto解中選取一個裝備組合，并采用式(10)中的Q-Learning公式更新當前階段下選擇該裝備組合的Q值。

(10)

式中，Q(St,at)表示在狀態St下采取動作at產生的Q值，α∈[0,1]表示學習率，描述控制新信息被采用的程度。該公式評估了在某個特定狀態采取某個特定行動的價值。

步驟4：重復迭代，直至達到停止標準。

如步驟2所述，需要針對每一階段求解生成該階段的非劣解，并從中選取一個裝備組合作為該階段的動作行為。步驟3中基于探索或利用的策略，從當前階段的Pareto解中隨機選擇或者選擇Q值最高的裝備組合。常見的Q-Learning引入一個參數τ來控制在兩種選擇策略之間的權衡關系。一般來說，將τ設置為0.5，即允許算法在兩種策略之間隨機選擇。

步驟5：回報函數的構建是衡量和計算非劣解中方案Q值的重要依據。采用式(11)來衡量當前階段St選擇方案at的回報值。

Rt=w1RE+w2RC

(11)

式中：RE和RC分別代表裝備組合在效能以及成本方面的回報，默認為二者都已經過歸一化處理；w1和w2是針對效能和成本的權重，且滿足兩者之和為1，此處將二者都設置為0.5。

具體來說，RE與當前所選裝備組合以及下一階段可能選擇的裝備組合的效能息息相關，采用式(12)進行度量。

(12)

其中，K代表場景的個數，等式右邊括號中前半部分代表當前所選擇裝備組合a在K個場景中效能的算術平均，后半部分代表下一階段所有可能裝備組合a′在K個場景中效能的算術平均，Pt+1為下一階段的最優Pareto解，NPt+1代表該Pareto解的個數。

對于RC，決策者希望在每個階段t所選擇的裝備組合at的成本能盡可能貼近當前階段給定的總成本約束Bt，同時下一階段的裝備組合非劣解中每個方案的成本也盡可能與下階段的成本約束相近，由此，采用式(13)來衡量與成本相關的回報。

(13)

其中，Ca表示當前階段裝備組合的成本。等式右邊括號中前半部分對當前階段的選擇進行了衡量，后半部分則對未來階段的可能性進行了衡量，以此來凸顯當前選擇可能對未來的影響。由于決策者希望任一階段的裝備組合成本更加貼近給定的預算，即與給定預算之間的差值越小越好，因此對兩邊的加和進行取反操作，以保證RC越大越好。獲得方案的當前回報值Rt后，采用式(10)中的Q-Learning公式對Q值進行更新。

3 實驗與結果分析

3.1 數據說明

本節開展示例研究，將Q-Learning思想應用于多階段裝備組合規劃中。采用隨機生成的方法產生裝備的效能以及成本數據。具體參數設置如下：

1)裝備項目：假定存在50個初始裝備，之后每年增加5個。

2)場景(K)：假定存在3個不同場景。

3)規劃階段(T)：假定整個規劃周期為10 a，該數值可根據需要進行調整。

4)效能與成本：通過正態分布模擬裝備在不同場景下發揮的效能以及發展成本，如圖3所示。表1給出了初始階段的裝備效能以及成本數值，且假設裝備效能和成本取值均已經過歸一化處理。

圖3 效能成本分布Fig.3 Distribution for weapon effectiveness and cost

其他方面，設置總經費S=25億元，一般情形下保證年度經費分配相對平均，并允許在一定范圍δ=0.1(10%)內波動，即每年的年度經費波動范圍為[(1-δ)S/T,(1+δ)S/T][20]；回報函數中，學習率α=0.1，折算率γ=0.9。

表1 不同場景下裝備效能與成本

續表

本次實驗仿真采用MATLAB 2017軟件，運行于Windows 7 64位系統中，軟件環境見表2。

表2 實驗硬件環境

另外，由于每年會增加一些新的待選裝備，而之前已經被選中發展的裝備在未來規劃階段內不能作為待選裝備出現，因此需要對每個階段的可選裝備組合進行更新。具體裝備信息生成、更新方法如圖4所示。

圖4 裝備更新策略Fig.4 Weapon update strategy

3.2 結果分析

基于所述算法，采用探索和利用相結合的方式，設置τ=0.5，對示例進行20次運行。每次運行需要考慮整個規劃周期內每個年度的優化目標。將所采用的多目標優化算法(NSGA-Ⅲ)的種群規模設為100，迭代次數設為50，交叉概率設為0.8，變異概率設為0.02。

經過100次學習，可以獲得100組Q值矩陣，對應不同的裝備組合方案。選取總體效能最大的方案，各個年度對應裝備組合的Q值如圖5所示。

圖5 最優規劃方案對應的Q值Fig.5 Corresponding Q value of the best portfolio solution

Q矩陣中每一行代表一種裝備組合規劃方案，而每一元素代表該方案在當前階段下裝備組合產生的Q值。圖5中，第1、4、7以及第10階段，采用隨機探索的方式選取裝備組合方案，其他年度按Q值最大值選取裝備組合方案。

圖6 最優裝備發展方案Fig.6 Optimal weapon development solution

總的規劃周期內，各個規劃階段的裝備組合選擇方案如圖6所示。圖6中，黃色部分代表整個規劃周期內被選中發展的裝備。由圖6可知，得益于每年新裝備的加入，此次規劃方案一共選擇發展58個裝備，每一年被選中發展的裝備數目相對平均，除了第3年、第6年和第8年，選擇發展了6個裝備，其他階段都選擇發展了5個裝備，且每年裝備投入的成本也相對均衡，滿足現實約束的需要。

為突出NSGA-Ⅲ參數對算法結果的影響，對算法中主要參數進行敏感性分析。分別獨立運行各種情形20次，并對各情形下的裝備組合方案效能值以及成本取平均值進行分析，結果見表3。

表3 NSGA-Ⅲ參數敏感性分析

由表3 可知，不同情形下最終方案效能以及成本各異。總體來說，隨著種群規模和迭代次數的增大，最后生成的方案在效能上更優，但方案成本以及算法運行時間也隨之增大。隨著交叉概率的增大，各最終生成方案總體更優，主要表現為方案的效能總和不斷增加，因為較大的交叉概率可以較好地保證進化時種群的豐富性。隨著變異概率的增大，各情形下生成的方案結果差異性不大，主要因為總體變異幅度相對較小。

3.3 對比分析

為驗證本文方法的有效性，分別設置兩個傳統解決多階段問題的基準方法進行對比分析。其中，基準方法1在滿足經費約束條件下隨機生成各階段的裝備組合方案，并實時更新下一階段的可選裝備集合空間。基準法2與基準方法1相似，但在各階段選取裝備時按照當前可選裝備在各場景中發揮效能均值的大小從高到低依次進行選擇，生成當前選擇裝備組合，并更新下一階段的可選裝備組合空間。重復上述步驟直至生成整個規劃周期內的裝備組合方案。兩種方法都更加注重短期內各階段的選擇，沒有考慮多個階段之間的權衡選擇問題，且這兩種方法都沒有選擇智能優化算法對多目標優化問題進行求解[19]。分別運行上述算法以及本文方法20次，圖7給出了不同方法策略下的最優裝備組合方案在各階段的效能均值以及成本均值。

由于基準方法2是在各階段選擇效能最大的裝備構成當前裝備組合，因此總體效能略優于其他兩種方法。但由圖7(a)可知，本文方法在后續各階段的生成裝備組合效能與基準方法2基本持平，并在第7年后略優于基準方法2。基準方法1生成的裝備組合方案效能在各階段均相對較低。由圖7(b)可知，基準方法2的成本總體較高。而本文方法除了在初始階段成本略高于另兩種方法，在后續各階段的成本均明顯低于兩種基準方法，且成本總和最低。從占優的角度，本文方法優于另兩種方法對應的裝備組合方案。換而言之，本文方法可以在更低成本下生成總體效能更優的裝備組合方案。

(a) 效能分析(a) Effectiveness analysis

3.4 參數敏感性

為突出選取策略參數對模型結果的影響，在同樣的參數設置下，改變每個階段選取裝備的策略：將探索和利用兩種策略的控制參數τ從0.1增加到0.9。其中，τ=0.5對應3.1節中的基本設置。由于效能與成本均是歸一化后的值，因此可對不同方案的結果在同一維度下進行加和比較。通過計算，五種策略對應的組合方案的三種效能值以及成本如圖8所示。

圖8 不同策略對應方案結果對比Fig.8 Comparison of different solutions under different strategies

圖8中的效能1、效能2和效能3分別指裝備組合方案在三種不同場景下的效能之和。對比發現，不同策略下方案的效能值以及成本各異。從占優的角度，四種方案都是非劣解，即不存在一個方案在每一項指標上都優于其他方案。但從總體效能的角度來看，方案3(τ=0.5)混合策略下產生方案的效能在三種場景下皆優于其他幾種方案。在效能1方面，方案5(τ=0.9)優于方案1(τ=0.1)、方案4(τ=0.7)和方案2(τ=0.3)。在效能2方面，方案1次優，后面依次為方案5、方案2和方案4。在效能3方面，方案1次優，后面依次為方案5、方案4和方案2。從成本角度來看，方案3所產生裝備組合成本相對較高，方案4對應裝備組合方案成本最低。對比實驗表明，在進行算法設計時，采取探索與利用相結合的方式選取裝備，可以生成更加魯棒的總體裝備組合方案。

3.5 Q-Learning效果分析

為驗證模型中是否采用Q-Learning策略對最終選型方案的影響，繼續開展對比實驗。采用強化學習的策略依據Q函數選取各階段的裝備，而不采取強化學習的策略則在各階段從候選Pareto中隨機選取裝備，類似于傳統的優化算法。分別運行算法各20次，圖9給出了是否采取強化學習策略下的最優裝備組合方案運算結果分布情況。

(a) 效能分析(a) Effectiveness analysis

由圖9的盒須圖可知，利用Q-Learning策略下生成的裝備組合在大多數階段的性能表現在最優值、均值等方面均優于未利用Q-Learning策略生成的方案。尤其是在第3至6階段，利用Q-Learning的方案最優值顯著優于未利用Q-Learning的方案，且方案在整個規劃周期的總效能更優。在成本方面，未利用Q-Learning策略生成的方案在最優值方面略優于采用Q-Learning策略生成的方案。但在成本均值方面，兩者基本相當，且在第2、第3、第4、第6和第10階段以及各階段的總和，利用Q-Learning策略生成的方案在各階段的成本之和更優。換而言之，利用Q-Learning策略方案可以在相對更低成本下生成總體效能更高的裝備組合方案，這驗證了本文模型采取Q-Learning策略的優勢。

4 結論

武器裝備組合規劃是我軍武器裝備體系建設發展中亟須解決的現實問題，具有十分重要的戰略意義。結合多目標優化算法與強化學習技術，重點回答了多個階段多個場景下的武器裝備組合選擇問題，而目前仍鮮有研究將強化學習應用于多階段的裝備規劃研究方面，其中，多目標優化算法用來在每個規劃時間決策點內，以最大化多個場景裝備組合的總效能與最小化總成本為目標，搜索非支配的裝備組合方案；強化學習算法可以有效對多階段問題進行水平搜索，形成任意階段的策略規則，從而有效保證決策結果在整個階段的最優性。通過具體示例驗證了本文模型的可行性與求解的高效性。對比實驗表明，本文方法生成的裝備組合方案優于其他傳統多目標決策方法，探索和利用策略的控制參數對模型結果具有一定影響，且采取強化學習生成的方案優于不采取強化學習方法生成的方案。提出的模型與算法可以支撐武器裝備中長期規劃決策和論證。