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

聶俊峰， 陳行軍， 蘇琦

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

0 引言

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

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

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

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

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

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

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

1.1 模型假設(shè)

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

決策變量為：武器決策向量X=(x1,x2,…,xi,…,xm)，xi∈[0,1]；武器作用點(diǎn)集合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ù)

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

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

(1)

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

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

(2)

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

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

(3)

1.3 約束條件

集群目標(biāo)火力分配不僅需要考慮資源總數(shù)、資源整數(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é)點(diǎn)的效能發(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表示對(duì)目標(biāo)tj無(wú)門限值要求。

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)化范疇，難點(diǎn)在于多目標(biāo)問題Pareto前沿的求解。另外，由于多約束條件的存在，也對(duì)尋優(yōu)算法提出了更高要求。

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

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

2.1 種群初始化

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

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

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

2.2 非支配排序

1)隨機(jī)生成種群At，通過隨機(jī)選擇、模擬二進(jìn)制交叉和多項(xiàng)式變異生成子種群Bt.

從父代種群中隨機(jī)選取個(gè)體P1、P2，進(jìn)入交叉操作后，其子代個(gè)體Q1、Q2可計(jì)算為

(8)

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

(9)

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

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

(10)

式中：ηv為變異分布指數(shù)，可依據(jù)進(jìn)化情況予以調(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 參考點(diǎn)機(jī)制

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

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

2)計(jì)算理想點(diǎn)。針對(duì)U維的多目標(biāo)優(yōu)化問題，理想點(diǎn)集Zmin可定義為種群在目標(biāo)每個(gè)維度上最小值z(mì)i,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)計(jì)算極值點(diǎn)zi,max.通過標(biāo)量化函數(shù)計(jì)算第i維目標(biāo)的極值點(diǎn)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為超平面上任意一點(diǎn)坐標(biāo)。

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

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

(15)

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

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

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

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

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

2.4 性能度量

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

2.4.1 收斂性指標(biāo)

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

(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 仿真計(jì)算及結(jié)果分析

3.1 仿真條件

為驗(yàn)證NSGA-Ⅲ求解集群目標(biāo)火力分配優(yōu)化問題的有效性，分別采用第2代強(qiáng)度Pareto優(yōu)化算法(SPEA2)、NSGA-Ⅱ和NSGA-Ⅲ 3類具有代表性的多目標(biāo)進(jìn)化算法進(jìn)行仿真求解，并對(duì)仿真結(jié)果進(jìn)行對(duì)比分析。相關(guān)作戰(zhàn)想定如下：假設(shè)在三維場(chǎng)景中，戰(zhàn)場(chǎng)環(huán)境大小為10×10×10，設(shè)計(jì)3組(M1、M2、M3)仿真實(shí)驗(yàn)，其中M1、M2、M3中集群威脅目標(biāo)個(gè)體數(shù)量分別為20個(gè)、30個(gè)、40個(gè)，己方可用武器數(shù)量均為10個(gè)。每組實(shí)驗(yàn)獨(dú)立進(jìn)行10次仿真計(jì)算，表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的計(jì)算機(jī)，MATLAB 2013a環(huán)境下進(jìn)行仿真實(shí)驗(yà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-Ⅲ能夠較好地實(shí)現(xiàn)集群目標(biāo)火力分配優(yōu)化，驗(yàn)證了方法的有效性。

SPEA2、NSGA-Ⅱ和NSGA-Ⅲ求解的平均計(jì)算時(shí)間如表4所示。

表4 各算法平均計(jì)算時(shí)間

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

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

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

圖5 SPEA2、NSGA-Ⅱ和NSGA-Ⅲ的S值對(duì)比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é)論

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

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

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

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