基于NSGA-Ⅲ算法的集群目標來襲火力分配建模與優化

聶俊峰， 陳行軍， 蘇琦

(海軍大連艦艇學院 作戰軟件與仿真研究所, 遼寧 大連 116018)

0 引言

無人作戰系統作為智能化的新型裝備，具有使用靈活、全壽命費用低、作戰效益高等顯著特點，在軍事領域應用廣泛。無人機、無人潛航器、無人水面艇、無人地面車輛等無人作戰系統已經成為現代戰爭中執行偵察監視、情報搜集、陣地防護、武裝打擊等任務的重要手段[1]。2018年美國國防部發布的《無人系統綜合路線圖(2017—2042)》，對各軍種無人系統的作戰需求、關鍵技術和無人系統之間互聯互通性進行了總體規劃，并指出未來各類無人系統必須具備無縫互操作能力[2]。因此，為加速戰爭形態向智能化演進，實現無人系統全域作戰潛能最大化，無人系統的集群作戰必將成為未來作戰的主要形式。

上述日益復雜的作戰態勢對傳統防御系統提出了極大的挑戰，無人系統集群目標來襲的防御具有以下顯著特點：首先，武器資源數量一般小于來襲集群目標數量，可通過配置合適的武器種類并選擇合理的作用位置來實現火力覆蓋，以達到最大殺傷效果；其次，集群目標普遍成本低廉，使得傳統對其實施點對點飽和攻擊效費比極低；再次，集群目標各節點之間存在互聯互通，攻擊目標的同時也會在一定程度上導致敵方網絡節點受損，獲得一定程度的網絡收益；最后，集群目標呈現典型異構性，可以根據各無人系統不同性能編排組成編隊，執行不同的作戰任務。

火力分配是集群目標來襲防御過程中的核心決策問題，是亟需解決的關鍵問題。構建特定態勢下的火力分配模型和開發準確高效的智能優化算法，是集群目標火力分配研究的重點和難點[3]。

在目前提出的火力分配模型中，由于單目標火力分配模型存在資源浪費、不符合實際的明顯缺陷[4-5]，現在主流的火力分配模型一般為多目標火力分配模型[6-8]。但多目標火力分配模型的研究重點大部分是武器數量大于目標數量的點對點飽和攻擊，目標函數一般是以費效比為主，決策約束一般僅限于武器數量約束[9-11]，傳統的多目標火力分配模型已經不適用于集群目標來襲條件下的火力分配。因此，針對實際作戰需求：張凱等[12]面向毀傷門限、安全規避、偏好指派等實際作戰約束，提出了基于武器資源消耗最小和目標生存價值最小的多約束多目標火力分配數學模型；Ma[13]針對集群目標提出了涵蓋目標信息、受保護對象、毀傷半徑、毀傷門限等因素的約束目標聚類模型，在實例仿真中取得了較好效果。上述研究成果雖然在一定程度上深化了對集群目標火力分配問題的認知水平，但仍存在兩點不足：1)模型并未充分考慮集群目標各節點之間的網絡通信和武器資源自身損傷情況[14-15]，未完全貼合作戰實際；2)模型中對集群目標的定義表述和邊界界定還比較模糊，模型的適用性仍需進一步檢驗。為解決以上問題，本文在充分考慮集群目標相互組網、集群目標組成異構性、集群目標個體成本低等特點的基礎上，采用拓撲結構對目標攻擊價值進行科學描述，以攻擊效益最大、自身剩余價值最大、武器消耗最小為目標函數，以毀傷門限、武器資源總數和0-1整數約束為約束條件構建集群目標火力分配模型。

集群目標火力分配屬于高維多目標優化問題。多目標進化算法是求解該類問題的有效算法，特別是非支配排序遺傳算法(NSGA)系列。Deb等[16]于1995年針對遺傳算法難以處理高維多目標優化問題的困境，提出了NSGA，但該算法存在計算復雜度高、效率低下等問題?；诖耍珼eb等[17]于2002年又提出了改進的NSGA-Ⅱ，該算法能夠高效快速地求解多目標優化問題，有效降低了計算復雜度，但在3個及以上目標的高維多目標優化問題的研究中，基于擁擠度算子的NSGA-Ⅱ存在收斂性不足的缺陷。為此，Deb 等[18]于2014年提出了面向參考點選擇機制的NSGA-Ⅲ，該算法在解決目標數目較多的高維多目標優化問題中取得了很好的效果。作為求解多目標優化問題的新算法，NSGA-Ⅲ具有很好的適應性，在提升運行效率、增加解空間的多樣性、降低計算復雜度等方面具有顯著優勢，有效彌補了其他方法的諸多不足。有相關研究表明，NSGA-Ⅲ在求解3個及以上目標優化問題時表現優異：馬武彬等[19]建立了以資源服務中心計算及存儲資源利用率、負載均衡率和微服務實際使用率等為優化目標的微服務組合部署與調度最優化問題模型，并提出基于NSGA-Ⅲ的求解方法，在全部滿足用戶服務請求的約束下，該策略取得了很好的效果；蔣寧等[20]針對換熱網絡高維多目標優化問題，比較了NSGA-Ⅱ與NSGA-Ⅲ在實際應用中的性能，結果表明，一定條件下NSGA-Ⅲ比NSGA-Ⅱ求解收斂困難的高維多目標優化問題更具優勢。

基于以上論述，本文首先構建集群目標來襲多目標多約束火力分配模型；進而基于NSGA-Ⅲ對集群目標火力分配優化進行實現；最后通過仿真實驗對算法的有效性進行驗證。結果表明，NSGA-Ⅲ在求解集群目標火力分配優化問題時具有更好的運行效率和收斂能力。

1 集群目標火力分配建模

1.1 模型假設

假設m個武器資源參與作戰，攔截n個來襲集群目標，對應的問題變量為：己方武器集合W={w1,w2,…,wi,…,wm}；目標個體集合T={t1,t2,…,tj,…,tn}；目標位置集合L={l1,l2,…,lj,…,ln}；武器的成本向量E=(e1,e2,…,ei,…,em)；目標個體的價值向量V=(v1,v2,…,vj,…,vn)；目標之間通過可靠網絡相連，目標個體tj1與tj2之間的網絡通信能力為dj1j2∈[0,1]；第i號武器打擊目標時自身損傷概率為hi；目標收益、網絡收益權重分別為γt、γn.

決策變量為：武器決策向量X=(x1,x2,…,xi,…,xm)，xi∈[0,1]；武器作用點集合Cp={cp1,cp2,…,cpi,…,cpm}。

集群目標火力分配網絡結構示意圖如圖1所示，圖1中：Ri為武器wi的殺傷半徑。

圖1 集群目標火力分配網絡結構示意圖Fig.1 Weapon-target assignment network topology for the group targets defense

1.2 目標函數

基于攔截效益最大化、自身剩余價值最大化、武器消耗最小化3個目標函數構建集群目標火力分配模型。

1)目標攔截效益最大化函數。目標的攔截效益由攻擊敵方目標得到的直接收益和導致敵方目標網絡節點受損所獲得的間接收益兩部分構成[14]：

(1)

式中：D為目標坐標殺傷規律，在計算中一般用簡化圓概率誤差(CEP)[12]表示；gj1j2為tj1和tj2之間的連通性，gj1j2=1表示對tj1和tj2中任一目標的毀傷概率大于門限條件，否則gj1j2=0.

2)自身剩余價值最大化函數為

(2)

式中：ε(xi)為階躍函數。

3)武器消耗最小化函數為

(3)

1.3 約束條件

集群目標火力分配不僅需要考慮資源總數、資源整數等基本約束，還需考慮毀傷門限等實際約束。

1.3.1 武器資源數量約束

武器資源總數和0-1整數約束為集群目標火力分配模型中的基本約束條件，資源數量之和不超過武器資源總數，且各武器資源僅存在已消耗和未消耗兩種狀態：

(4)

1.3.2 毀傷門限約束

為限制敵方某些關鍵目標節點的效能發揮，作戰指揮系統往往期望將其生存概率壓制于設定毀傷門限值之內[12]：

(5)

式中：α為滿足不等式‖lj-cpi‖≤Ri的數量；ρ=(ρ1,ρ2,…,ρj,…,ρn)，ρj為目標tj的預設毀傷門限值，0≤ρj≤1，ρj=1表示對目標tj無門限值要求。

1.4 數學模型

綜上所述，構建的集群目標火力分配數學模型為

max(yt,ys,-yc)，

(6)

(7)

根據(6)式和(7)式可知，集群目標火力分配數學模型屬于混合整數非線性多目標優化范疇，難點在于多目標問題Pareto前沿的求解。另外，由于多約束條件的存在，也對尋優算法提出了更高要求。

2 基于NSGA-Ⅲ的集群目標火力分配優化

基于NSGA-Ⅲ求解集群目標火力分配優化問題的關鍵內容可分為種群初始化、非支配排序、參考點機制和性能度量4個部分。

2.1 種群初始化

種群初始化包括編碼和生成初始種群兩部分：

1)采用連續實數編碼方式，種群個體為武器資源使用情況及作用點。

2)初始種群需具備均勻性、多樣性和可行性。需在生成大量滿足約束條件的均勻分布隨機個體的前提下，遴選性能最優的個體形成初始種群。

2.2 非支配排序

1)隨機生成種群At，通過隨機選擇、模擬二進制交叉和多項式變異生成子種群Bt.

從父代種群中隨機選取個體P1、P2，進入交叉操作后，其子代個體Q1、Q2可計算為

(8)

式中：β與隨機數μ∈[0,1]有關，公式為

(9)

ηc為交叉分布指數，ηc越大，子代個體與父代越相近。

若進入變異操作，則從父代種群中隨機選取個體P3，變異產生其子代個體Q3的公式為

(10)

式中：ηv為變異分布指數，可依據進化情況予以調整；xmax、xmin分別為變量x的上、下邊界。

2)父代種群At和子代種群Bt合并為Rt，|At|=N，|Bt|=N，|Rt|=2N.

3)構建新種群St，將Rt劃分為若干不同非支配層(F1,F2,…)，自F1開始，將各非支配層的解依次填充到St，直至|St|≥N.若最終可接受的非支配層是第O層，則舍棄在第O+1層及之后的解。

2.3 參考點機制

NSGA-Ⅲ采用參考點機制保持種群的多樣性[20]，歸一化操作是參考點機制的核心[18]，具體步驟如下：

1)生成參考點。基于Das等[21]提出的正交邊界交叉算法生成參考點。

2)計算理想點。針對U維的多目標優化問題，理想點集Zmin可定義為種群在目標每個維度上最小值zi,min的集合。

Zmin=(z1,min,z2,min,…,zU,min).

(11)

3)轉譯目標值。轉譯種群S′t的目標值f′i(x)為

f′i(x)=fi(x)-zi,min,x∈St.

(12)

4)計算極值點zi,max.通過標量化函數計算第i維目標的極值點zi,max為

(13)

式中：ωi=(ε,ε,…,ωi,i,…,ε)，ωi,i=1，ε=10-6.

5)構建線性超平面，其通用方程為

A1x1+A2x2+A3x3+…+AUxU=1，

(14)

式中：A1,A2,…,AU為不全為0的常數；x1,x2,…,xU為超平面上任意一點坐標。

輸入每個維度上的極值點Zmax即可構建超平面，并可計算超平面截距ai.

6)種群目標值歸一化，可表示為

(15)

式中：i=1,2,3,…,U；上標n表示歸一化；x∈St或S′t.

7)關聯參考點。將距離種群個體最近的參考線對應的參考點定義為與該個體關聯。

8)個體選擇。基于小生鏡保留操作進行個體選擇[22-23]，直到滿足種群規模。

三維目標的參考點機制示意圖如圖2所示。

圖2 三維目標的參考點機制示意圖Fig.2 Reference points on a normalized hyperplane

2.4 性能度量

一般通過評估所得Pareto前沿面的收斂性和分布的均勻性對算法性能進行度量。依據Zitzler等[24]的研究結果，采用收斂性指標C和間距指標S評估。

2.4.1 收斂性指標

令P*=(p1,p2,…,p|P*|)為理想Pareto前端面上均勻分布的Pareto最優解集合，而B=(b1,b2,…,b|B|)是通過NSGA-Ⅲ得到的近似Pareto最優解集。集合B中每個解bi距離P*的最小歸一化歐氏距離可計算為

(16)

(17)

式中：C值越小，得到的最優解收斂性越優。

2.4.2 間距指標

間距指標定義為

(18)

基于NSAG-Ⅲ的集群目標火力分配優化算法流程如圖3所示。

圖3 基于NSGA-Ⅲ的集群目標火力分配優化算法流程Fig.3 Flowchart of optimized weapon-target assignment algorithm based on NSGA-Ⅲ

3 仿真計算及結果分析

3.1 仿真條件

為驗證NSGA-Ⅲ求解集群目標火力分配優化問題的有效性，分別采用第2代強度Pareto優化算法(SPEA2)、NSGA-Ⅱ和NSGA-Ⅲ 3類具有代表性的多目標進化算法進行仿真求解，并對仿真結果進行對比分析。相關作戰想定如下：假設在三維場景中，戰場環境大小為10×10×10，設計3組(M1、M2、M3)仿真實驗，其中M1、M2、M3中集群威脅目標個體數量分別為20個、30個、40個，己方可用武器數量均為10個。每組實驗獨立進行10次仿真計算，表1為威脅目標參數取值情況，表2為武器資源參數取值情況，相關數據已經歸一化處理。

表1 威脅目標參數取值表Tab.1 Parameter values of threat targets

表2 武器資源參數取值表Tab.2 Parameter values of weapons

本算例中SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的初始參數設置如下：

SPEA2：種群規模為50，存檔集規模為50，終止代數為50，交叉概率為0.8，變異概率為0.05.

NSGA-Ⅱ、NSGA-Ⅲ：種群規模為50，終止代數為50，交叉概率為0.8，變異概率為0.05.

在Core i5 3.3 GHz、內存4 GB的計算機，MATLAB 2013a環境下進行仿真實驗。

3.2 仿真結果及分析

各算法求解結果中的最優值如表3所示。

表3 各算法的最優值Tab.3 Best results of 3 kinds of algorithms

由表3可知，M1、M2、M3組求得的最優解yt、yc、ys中，雖然SPEA2與NSGA-Ⅱ各有優劣，但NSGA-Ⅲ都比SPEA2、NSGA-Ⅱ明顯占優，表明基于NSGA-Ⅲ能夠較好地實現集群目標火力分配優化，驗證了方法的有效性。

SPEA2、NSGA-Ⅱ和NSGA-Ⅲ求解的平均計算時間如表4所示。

表4 各算法平均計算時間

由表4可知，NSGA-Ⅲ相對SPEA2、NSGA-Ⅱ，在M1組的運行時間基本持平，而在M2組和M3組的運行時間明顯占優，運行效率高。一般來說，針對集群目標來襲的防御任務具有非常強的時間緊迫性，計算效率會在很大程度上影響任務的執行情況，故NSGA-Ⅲ更符合大規模集群目標來襲火力分配對時效的要求。

為定量比較SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的性能指標，圖4和圖5分別給出了3種算法下各組C值及S值情況。

圖4 SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的C值對比Fig.4 Comparison of C values of SPEA2,NSGA-Ⅱ and NSGA-Ⅲ

圖5 SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的S值對比Fig.5 Comparison of S values of SPEA2,NSGA-Ⅱ and NSGA-Ⅲ

由圖4和圖5可以看出，M1、M2、M3組中NSGA-Ⅲ的C值和S值都明顯比SPEA2、NSGA-Ⅱ占優，表明NSGA-Ⅲ得到的近似Pareto最優解的收斂性更好，在目標空間上的分布更均勻。

4 結論

面向無人作戰系統集群目標來襲條件下火力分配優化問題的研究具有重要現實意義。本文在充分考慮集群目標相互組網、集群目標組成異構性、集群目標個體成本低等特點的基礎上，面向拓撲結構描述目標的攻擊價值，構建集群目標下多目標多約束火力分配模型，并基于NSGA-Ⅲ對集群目標火力分配優化進行了實現。得出主要結論如下：

1)面向集群目標來襲的作戰需求，以攻擊效益最大、自身剩余價值最大、武器消耗最小為目標函數，以毀傷門限、武器資源總數和0-1整數約束為約束條件，構建了集群目標火力分配模型，充分考慮了集群目標來襲的特點，提高了模型的有效性和適用性，較以往模型有較大改進。

2)采用收斂性指標和間距指標對SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的集群目標火力分配模型求解結果進行了對比驗證，實現了閉環研究。

3)在約束可行范圍內得到了分布良好的Pareto集合，可為指揮人員提供更多有價值的選擇方案。