基于NSGA-Ⅲ算法的集群目標(biāo)來襲火力分配建模與優(yōu)化

聶俊峰， 陳行軍， 蘇琦

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

0 引言

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

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

火力分配是集群目標(biāo)來襲防御過程中的核心決策問題，是亟需解決的關(guān)鍵問題。構(gòu)建特定態(tài)勢下的火力分配模型和開發(fā)準(zhǔn)確高效的智能優(yōu)化算法，是集群目標(biāo)火力分配研究的重點和難點[3]。

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

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

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

1 集群目標(biāo)火力分配建模

1.1 模型假設(shè)

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

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

集群目標(biāo)火力分配網(wǎng)絡(luò)結(jié)構(gòu)示意圖如圖1所示，圖1中：Ri為武器wi的殺傷半徑。

圖1 集群目標(biāo)火力分配網(wǎng)絡(luò)結(jié)構(gòu)示意圖Fig.1 Weapon-target assignment network topology for the group targets defense

1.2 目標(biāo)函數(shù)

基于攔截效益最大化、自身剩余價值最大化、武器消耗最小化3個目標(biāo)函數(shù)構(gòu)建集群目標(biāo)火力分配模型。

1)目標(biāo)攔截效益最大化函數(shù)。目標(biāo)的攔截效益由攻擊敵方目標(biāo)得到的直接收益和導(dǎo)致敵方目標(biāo)網(wǎng)絡(luò)節(jié)點受損所獲得的間接收益兩部分構(gòu)成[14]：

(1)

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

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

(2)

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

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

(3)

1.3 約束條件

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

1.3.1 武器資源數(shù)量約束

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

(4)

1.3.2 毀傷門限約束

為限制敵方某些關(guān)鍵目標(biāo)節(jié)點的效能發(fā)揮，作戰(zhàn)指揮系統(tǒng)往往期望將其生存概率壓制于設(shè)定毀傷門限值之內(nèi)[12]：

(5)

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

1.4 數(shù)學(xué)模型

綜上所述，構(gòu)建的集群目標(biāo)火力分配數(shù)學(xué)模型為

max(yt,ys,-yc)，

(6)

(7)

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

2 基于NSGA-Ⅲ的集群目標(biāo)火力分配優(yōu)化

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

2.1 種群初始化

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

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

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

2.2 非支配排序

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

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

(8)

式中：β與隨機數(shù)μ∈[0,1]有關(guān)，公式為

(9)

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

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

(10)

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

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

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

2.3 參考點機制

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

1)生成參考點?；贒as等[21]提出的正交邊界交叉算法生成參考點。

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

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

(11)

3)轉(zhuǎn)譯目標(biāo)值。轉(zhuǎn)譯種群S′t的目標(biāo)值f′i(x)為

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

(12)

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

(13)

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

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

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

(14)

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

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

6)種群目標(biāo)值歸一化，可表示為

(15)

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

7)關(guān)聯(lián)參考點。將距離種群個體最近的參考線對應(yīng)的參考點定義為與該個體關(guān)聯(lián)。

8)個體選擇?；谛∩R保留操作進行個體選擇[22-23]，直到滿足種群規(guī)模。

三維目標(biāo)的參考點機制示意圖如圖2所示。

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

2.4 性能度量

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

2.4.1 收斂性指標(biāo)

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

(16)

(17)

式中：C值越小，得到的最優(yōu)解收斂性越優(yōu)。

2.4.2 間距指標(biāo)

間距指標(biāo)定義為

(18)

基于NSAG-Ⅲ的集群目標(biāo)火力分配優(yōu)化算法流程如圖3所示。

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

3 仿真計算及結(jié)果分析

3.1 仿真條件

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

表1 威脅目標(biāo)參數(shù)取值表Tab.1 Parameter values of threat targets

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

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

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

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

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

3.2 仿真結(jié)果及分析

各算法求解結(jié)果中的最優(yōu)值如表3所示。

表3 各算法的最優(yōu)值Tab.3 Best results of 3 kinds of algorithms

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

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

表4 各算法平均計算時間

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

為定量比較SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的性能指標(biāo)，圖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-Ⅱ占優(yōu)，表明NSGA-Ⅲ得到的近似Pareto最優(yōu)解的收斂性更好，在目標(biāo)空間上的分布更均勻。

4 結(jié)論

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

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

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

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