多約束集群目標下武器-目標分配問題

張 凱，周德云，楊 振，潘 潛

（西北工業大學電子信息學院，西安710072）

（*通信作者電子郵箱zhangkainwpu@mail.nwpu.edu.cn）

0 引言

隨著軍事技術和作戰概念的發展，集群智能體成為未來戰場的作戰主體已是必然趨勢。在近年美國國防高級研究局（Defense Advanced Research Projects Agency，DARPA）推出的小精靈項目、海軍/空軍低成本無人機集群技術中，其作戰單位均具有低探測性、低成本、可回收、零人員傷亡等優點，并可協同完成多方位、多批次、高密度的飽和攻擊。2016 年美軍發布的《小型無人機系統路線圖2016—2036》指出小型無人機系統及其集群對情報、偵察與監視領域具有“填補戰術與戰略之間空白”的重要意義，并預計在2025 年以后，無人機將具有集群戰場認知能力，實現完全自組織作戰［1］。

當目標毀傷概率向量滿足目標毀傷門限向量ρ時，g2(x)為0；反之，g1(x)與毀傷門限的偏離程度成正比。

武器-目標偏好指派約束的約束違反值設計為:

當目標處于偏好武器的殺傷范圍內時，g3(x)為0；反之g3(x)與目標-偏好武器的距離成正比。

2.4 性能度量

在對多目標優化算法的性能度量中，一般評估所得Pareto 前沿面的收斂性和分布性。前者評價解得Pareto 解集與真實Pareto 集合的趨緊程度，如Convergence 指標［22］；分布性評價Pareto集合在目標空間中的均勻性、多樣性，如Spacing指標［23］。在CMWTA 問題中，由于解集在目標空間中呈現分層遞減的特定非均勻分布，因此無需分布性反映Pareto 前沿面的優劣。而一般收斂性指標需要理論最優解，而通常無法得到CMWTA 問題的理論最優解，因此本文在比較不同算法收斂性的優劣時，設計針對CMWTA模型的Convergence變式:令P={p1，p2，…，p||P}為不同算法對同一CMWTA問題求解的歷史解集形成的近似Pareto 最優解集合，A={a1，a2，…，a||A}為單次求解得到的近似Pareto 最優解集合，通過下式計算該解集距離P的近似歸一化距離:

除了設計Convergence變式給出CMWTA算法收斂性的定量評價外，另采用Coverage指標［24］進行各算法的定性評價:

其中:解集A、B分別為同一算例用不同算法解得的Pareto 集合，通常IC(A，B)≠IC(B，A)，且IC(A，B)＞IC(B，A)時，表明解集A優于解集B。

3 仿真與分析

算例1 為便于研究，引入以下作戰想定:假設在二維場景中并略去相應單位，戰場環境大小為20×20，其中集群威脅目標個體數量為20，存在2 個友方/中立目標，阿拉伯數字1～20 代表威脅目標，圓點代表友方/中立目標，目標6 和目標13后的不等式表示其生存概率門限值分別為0.2和0.1，目標14后的羅馬數字Ⅲ表示優先將武器3 分配給該目標，如圖2 所示。己方可使用的武器數量為30，武器有效殺傷半徑為［2.1:0.1:5］。相關參數見表1。

圖2 算例1作戰場景態勢圖Fig. 2 Situation diagram of fighting scenario of example one

表1 算例1裝訂數據Tab. 1 Numerical values of example one

分別采用多目標進化算法中具有代表性的NSGA-Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ）［25］、SPEA2（Strength Pareto Evolutionary Algorithm Ⅱ）［26］和MOEA/D（Multi-Objective Evolutionary Algorithm based on Decomposition）［27］框架對上述模型進行求解。為了不影響以上三種算法求解CMWTA 問題的對比分析，此算例中的三種算法均采用了修復策略。關于修復算法對算法的影響在算例2中進行仿真分析。本算例中相關算法參數如下:

NSGA-Ⅱ:種群規模N=1 200，交配池規模MP=600，終止代數tmax= 100，交叉概率Pc= 0.8，變異概率Pm= 0.2，交叉分布指數ηc= 1，變異分布指數ηm= 1。

SPEA2:種群數量N= 1000，存檔集規模M= 200，交配池規模MP= 100，終止種群代數tmax= 100，鄰近值k= 35，交叉概率Pc= 0.8，變異概率Pm= 0.2，交叉分布指數ηc= 1，變異分布指數ηm= 1。

MOEA/D:權值向量數量N= 1000，鄰居向量數量B= 20，終止種群代數tmax= 100，交叉分布指數ηc= 1，變異分布指數ηm= 1。

在本算例中，獨立運行NSGA-Ⅱ、SPEA2和MOEA/D 各30次。所求得Pareto 集合的相關統計數據如表2，其中第2 欄為三種算法所求得的Pareto 集合的Convergence 均值，第3～7 欄為獲得的在不同武器消耗區間的非支配解的次數。

表2 NSGA-Ⅱ、SPEA2和MOEA/D在30次獨立運行下Pareto集合統計數據Tab. 2 Statistics of Pareto sets obtained by NSGA-Ⅱ，SPEA2 and MOEA/D in 30 independent runs

在表2中，首先由Convergence指標一欄可知，三種算法對于歷史最優解的逼近能力為:SPEA2＞NSGA-Ⅱ＞MOEA/D，其中SPEA2 略優于NSGA-Ⅱ，MOEA/D 與另兩種算法差距較大。其次由先驗信息和仿真結果可得知，本算例理論Pareto 集合的容量為29，即滿足約束的武器消耗的下限為2，上限為30。在30 次運行中獲得的Pareto 集合完整性指標中，NSGA-Ⅱ有19例位于［16，20］區間；SPEA2有17例位于［21，25］區間，2例位于［11，15］區間；而MOEA/D 下大部分集合容量都小于10。且NSGA-Ⅱ和SPEA2 可以確保所求得的非支配解均為可行解，在MOEA/D 下得到了6個非可行解。綜合以上Pareto集合的收斂性、完整性和可行性，SPEA2略優于NSGA-Ⅱ。

為了直觀地給出三種算法在不同的武器消耗區間的搜索能力，圖3 給出了三種算法在30 次獨立運行中非支配可行解的不同武器消耗下的分布。

圖3 NSGA-Ⅱ、SPEA2和MOEA/D在30次獨立運行中非支配可行解在各武器消耗下的分布Fig. 3 Distribution of feasible non-dominated solutions of different weapon consumption obtained by NSGA-Ⅱ，SPEA2 and MOEA/D in 30 independent runs

除表2 和圖3 給出各算法下Pareto 解集分布性的定性比較外，圖4 定量比較了NSGA-Ⅱ、SPEA2 和MOEA/D 的各項性能指標。在各算法獨立運行30次的前提下:圖4（a）為各算法Convergence 均值隨進化代數的變化曲線；圖4（b）為各算法下Convergence 值的盒圖分布；圖4（c）表示各算法在不同武器消耗下的目標期望生存價值均值，即CMWTA模型中目標函數f1均值；圖4（d）～（f）分別為三種算法兩兩比較的Coverage 指標的盒圖分布。

如圖4（a）所示，MOEA/D 在CMWTA 模型中的搜索能力明顯弱于NSGA-Ⅱ和SPEA2。雖然NSGA-Ⅱ和SPEA2 在50代后的表現較為接近，但SPEA2 擁有更高的收斂速度和更優的Convergence 值。在圖4（b）中，SPEA2 下Convergence 值的整體分布優于NSGA-Ⅱ，但NSGA-Ⅱ較SPEA2 擁有更小的離散度。在圖4（c）中，SPEA2 在武器消耗為［6，15］區間內略優于NSGA-Ⅱ，而MOEA/D 曲線出現的震蕩和間斷表明MOEA/D 在保證在Pareto 前沿面的完整性方面表現較差。在圖4（d）～（f）中，除了MOEA/D 在Coverage 方面明顯落后于其他算法外，NSGA-Ⅱ和SPEA2表現相當。

圖4 NSGA-Ⅱ、SPEA2和MOEA/D算法下相關性能指標對比Fig. 4 Related performance metrics comparison of NSGA-Ⅱ，SPEA2 and MOEA/D algorithms

綜合分析圖4中的各項結果，從CMWTA模型的數值求解出發，各算法的尋優能力為:SPEA2＞NSGA-Ⅱ＞MOEA/D。雖然MOEA/D 在求解無約束點對點MWTA 問題時表現較好，但由于CMWTA 中的點對面攻擊和多約束的特點，缺乏對改進目標函數、分解策略和約束處理方法三者系統性的研究，因此直接應用MOEA/D求解CMWTA問題效果較差。

而在比較NSGA-Ⅱ和SPEA2 算法求解CMWTA 模型時，需要注意的是，由圖4（c）可知，當武器使用數量達到15后，繼續增加武器消耗的邊際收益極小。結合圖4 中NSGA-Ⅱ在武器消耗小于20時的明顯優勢，可得出結論:在CMWTA 模型中，雖然SPEA2 在Convergence 的數值和離散度上優于NSGA-Ⅱ，但主要優勢在于保證武器消耗大于20 的非支配解的完備性。但從實際作戰的效費比考慮，高武器消耗下的非支配解并非CMWTA 模型中的求解重點，而由圖5（b）和5（d）可知，NSGA-Ⅱ在求解低武器消耗下的CMWTA 問題時具有更好的魯棒性。因此從指揮控制系統的輔助決策考慮，NSGA-Ⅱ可能更具有實際應用價值。

為了更直觀地說明以上結論，選取NSGA-Ⅱ和SPEA2 在30 次運算中獲得的部分武器消耗下的最優解，通過圖5 進行部分可視化顯示。

在圖5中，由“×”標出各武器瞄準點并顯示相應的殺傷范圍，箭頭所指目標為具有毀傷門限要求的目標，箭頭起始處第一個數字代表該目標當前生存概率，括號后的數字代表滿足毀傷門限時的最大生存概率，“-”連接的是偏好指派的武器-目標對wi-tj，aij= 1。由圖5（a）和5（e）可看出，當武器使用數量為3 時，武器分布在兩個區域，在左上角區域中，要求威脅目標6 的生存概率小于0.2，目標14 具有強制指派武器Ⅲ的要求，且目標6 和14 距離安全目標1 較近。此時NSGA-Ⅱ和SPEA2 均選擇一武器協同武器Ⅲ完成上述任務，此時協同武器的殺傷范圍不宜過大，否則難以滿足對目標6 的殺傷門限。NSGA-Ⅱ傾向于使用協同武器覆蓋目標8 和19，而在SPEA2下選擇攻擊威脅權值更高的目標4、10、16 和19，使得適應度達到4.204 0，顯然SPEA2 下的方案更優。在右下角區域，目標13 具有0.1 的期望生存概率要求且距離安全目標2 較近，NSGA-Ⅱ通過利用合適殺傷范圍的武器在規避安全目標2 的同時覆蓋右下角多目標，且使得目標13 的期望生存概率為0.05，而SPEA2 下覆蓋目標較少，且目標13 的期望生存概率剛達到0.1，此時NSGA-Ⅱ的決策明顯更優。同理，在其他武器消耗下求得的最優方案均能較好地滿足作戰需求。從圖5中可以看出，當武器數量較少時，各算法求得的方案對于武器殺傷范圍和作用區域的選擇具有較高的相似性。而隨著武器使用數量的上升，差異性越來越明顯，并且當武器使用數量達到10 時，已對所有目標都進行了火力覆蓋，繼續增加武器消耗的邊際收益不斷降低。在本算例中，綜合考慮最大化期望作戰效率和效費比。建議將武器使用數量設為12或13。

圖5 NSGA-Ⅱ和SPEA2在30次獨立運行中最優非支配解的可視化對比Fig 5 Visualization comparison of optimal non-dominated solutions obtained by NSGA-Ⅱand SPEA2 in 30 independent runs

算例2 本算例對本文中的進化操作和修復算法進行驗證。基于算例1中的參數設定，采用如下3種實驗設定:1）初始種群經過選擇、交叉、變異、修復進化操作后生成等規模的精英種群，分析對比兩個種群的適應度分布、多樣性保持等統計數據；2）基于算例1中的參數設定，對比分析未修復/修復下的種群個體的適應度f1和約束違反值；3）分別對比分析未修復/修復下NSGA-Ⅱ、SPEA2和MOEA/D算法的仿真結果。

對比結果如圖6所示。圖6為初始種群經過交叉、變異、修復后的相關統計數據。其中圖6（a）為各武器消耗下初始化種群和子代種群的解分布對比，圖6（b）為各武器消耗下初始化種群和子代種群的目標期望生存價值的均值對比，圖6（c）為各武器消耗下初始種群和子代種群的約束違反值的均值對比。

圖6 交叉、變異、修復下初始種群與子代種群的統計數據Fig. 6 Statistics of initial population and offspring population by crossover，mutation and repair

如圖6（a）所示，在本文提出的交叉、變異、修復策略下后，子代種群與隨機化的初始種群的個體分布相近，可見本文所提出的交叉、變異等進化操作未影響初始種群的多樣性分布。在圖6（b）中，子代種群的目標期望生存價值的均值在武器消耗小于9 時高于初始種群，大于9 時低于種群。在圖6（c）中，低武器消耗下，如武器消耗為1、2 時，子代種群的約束違反值的均值有明顯改善，而在個別武器消耗大于25 時，子代種群的約束違反值的均值出現大幅上升。并且，在種群適應度均值上，初始種群為2.841 7，子代種群為2.833 1；在種群約束違反值均值上，初始種群為0.326 4，子代種群為0.356 3。綜上可見，種群適應度均值略有下降，種群多樣性增加，其原因在于低武器消耗下的可行解比例增大，高武器消耗下的約束違反值均值增加。結合算例1 中得到的建議最大武器消耗量為12和13的結論，可見本文提出的交叉、變異、修復策略的合理性。

圖7為未修復/修復下不同武器消耗個體的目標期望生存價值的均值對比圖。如圖7 所示，修復后各武器消耗個體的適應度均值均得到了提升。

圖7 未修復/修復下各武器消耗個體的目標期望生存價值均值Fig. 7 Mean value of expected target value of different weapon consumption under non-repair/repair strategies

圖8為未修復/修復下不同武器消耗個體的各約束違反值的均值對比圖，其中圖8（a）～（c）分別為未修復/修復下安全規避、毀傷門限和偏好指派的約束違反值對比圖。

如圖8所示，修復后各武器消耗個體的適應度均值均得到了提升。由圖8（a）可知，修復后安全規避約束違反值反而上升，其原因在于修復算法中未有對安全規避約束的修復機制。但由于該約束結構簡單，違反值僅與‖S-C‖成正比關系，因此完全可交由進化算法的“優勝劣汰”選擇機制進行優化。在圖8（b）中，修復算法中對毀傷門限約束的修復使得該違反值得到大幅降低。在圖8（c）中，偏好指派約束修復使得該違反值在武器消耗達到8后才有明顯降低，其原因在于為了保持種群多樣性，偏好指派只在偏好武器被使用的個體中進行修復，而在隨機生成的初始種群中，武器消耗越少，偏好武器被使用的概率越小，反之武器消耗越大，修復算法對偏好指派約束的修復效果越明顯。且綜合圖7和8可知，修復后的種群中不存在武器消耗為29、30的個體，這是由于在初始化種群中武器消耗越大時，越易造成無效武器使用，而修復算法中的一致性修復會對此類武器進行修剪，因此修復算法在也一定程度上限定了合理的武器消耗上限。

表3 為未修復/修復NSGA-Ⅱ、SPEA2 和MOEA/D 算法下的Pareto 集合的統計數據。在表3 中，個體修復算法將NSGA-Ⅱ、SPEA2 和MOEA/D 的Convergence 值均提升了20%以上，其中未修復的NSGA-Ⅱ和SPEA2 在100 代時的Convergence 均值幾乎相等。同時個體修復算法也明顯提升了NSGA-Ⅱ和SPEA2 算法所求得的Pareto 集合的完整性，未修復NSGA-Ⅱ求得的Pareto 集合主要分布在16～20 區間，而修復后有11 例分布在［21，25］區間，同樣修復SPEA2 算法下的Pareto 集合也有17 例在［21，25］區間。但修復策略對MOEA/D 影響較小，略微提高了Pareto 集合的大小，但不可行解也由1個上升到6個。

圖8 未修復/修復策略下各武器消耗下各約束違反對比Fig. 8 Constraint violation comparison of different weapon consumption under non-repair/repair strategies

表3 NSGA-Ⅱ、SPEA2和MOEA/D在修復/未修復策略下獨立運行30次獲得的Pareto集合統計數據Tab. 3 Statistics of Pareto sets obtained by NSGA-Ⅱ，SPEA2 and MOEA/D algorithms in 30 independent runs under non-repair/repair strategies

為了直觀地分析個體修復算法對非支配解分布性的影響，圖9 給出了各算法在修復和未修復兩種策略下30 次獨立運行獲得的各武器消耗下非支配可行解個數。在NSGA-Ⅱ算法中，修復算法增強了對武器消耗大于12 的非支配解的搜索能力。在SPEA2算法中，未修復版本在武器消耗小于18時略有優勢，但當武器消耗大于25 時，已無法求得相應的非支配解，而修復算法的搜索能力在武器消耗達到18 后大幅反超未修復版本，且求得的非支配解相應的武器消耗可達到29。相似地，當武器消耗達到6 后，修復MOEA/D 算法的搜索能力反超未修復MOEA/D 算法。通過以上結果，可知本文提出的個體修復算法可以有效提高CMWTA 問題中Pareto 集合的分布性，且對SPEA2算法的提升更大。

圖10 比較了未修復/修復NSGA-Ⅱ、SPEA2 和MOEA/D 算法的各項性能指標。各算法獨立運行30次。圖10（a）為各算法下Convergence 均值隨進化代數的變化曲線；圖10（b）為各算法求得的Pareto 集合的Convergence 值盒圖分布；圖10（c）為各算法在不同武器消耗下的目標期望生存價值均值；圖10（d）～（f）分別為每種算法下修復和未修復版本進行Coverage對比的盒圖分布。

圖9 NSGA-Ⅱ、SPEA2和MOEA/D在修復/未修復策略下獨立運行30次獲得的非支配可行解在各武器消耗下的分布Fig. 9 Distribution of feasible non-dominated solutions of different weapon consumption obtained by NSGA-Ⅱ，SPEA2 and MOEA/D algorithms in 30 independent runs under non-repair/repair strategies

圖10 NSGA-Ⅱ、SPEA2和MOEA/D在修復/未修復策略下相關性能指標對比Fig. 10 Performance metrics comparison of non-repair/repair of NSGA-Ⅱ，SPEA2 and MOEA/D algorithms under non-repair/repair strategies

如圖10（a）所示，在每種算法下，修復后Convergence 值的收斂速度下降，但最優值得到了明顯提升，其中未修復NSGA-Ⅱ和SPEA2在100代時幾乎收斂到同一點。未修復SPEA2在進化初期存在一個急劇的下降階段，隨后開始緩慢上升，而其他算法處于單調下降趨勢，其原因在于各算法下種群不同的搜索選擇機制。由于CMWTA 模型中多約束的存在，使得算法進化初期可行解更易被輸出為非支配解，而NSGA-Ⅱ初期選擇的可行解數量較少，但適應度較高，在后續進化過程中更可能被作為非支配解輸出，從而表現為Convergence 值的單調遞減。而SPEA2 在進化初期可以搜索到較多的可行解，此時Convergence 值會快速下降，但隨著進化過程的推進，初期的可行解一旦被新搜索到的解支配，則不具備被選擇優勢，此時Pareto 前沿面由多個可行解退化為數量更少適應度更高的非支配解，表現為Convergence 值的緩慢上升。由圖10（b）可知修復算法使得各算法的收斂性得到了增強。在圖10（c）中除MOEA/D 外，修復算法進一步優化了其他算法中各武器消耗量下的目標期望生存價值均值。根據圖10（d）～（f）可知，修復算法在和對應的未修復算法進行Pareto 集合的Coverage 對比時具有明顯優勢，且對SPEA2的提升更為明顯。

根據以上分析，本文提出的個體修復算法使得NSGA-Ⅱ、SPEA2 和MOEA/D 在非支配解的分布性、適應度和Pareto 集合的收斂性方面均有明顯提升。

4 結語

綜上所述，本文提出的武器-目標分配問題可作為基于重疊目標分群的攻擊模式研究。在威脅評估過程中，若可對目標執行基于物理位置的目標分群，則可綜合考慮武器資源、殺傷范圍、目標類型和地形等因素，解得約束可行區域內的Pareto集合，以供決策者選擇。

本文建立了基于以上作戰需求的CMWTA 模型，在多目標進化算法框架下采用個體編碼、檢測修復和約束支配相結合的方式處理約束條件，并設計針對多目標WTA 問題的Convergence指標，對NSGA-Ⅱ、SPEA2和MOEA/D 三種求解框架進行了仿真對比，對個體修復算法進行了仿真驗證。隨著戰場環境的日益復雜，以特定的作戰需求為出發點，進行相應的模型和算法設計是未來WTA問題的研究方向。