基于NSGA-Ⅲ的UUV 集群打擊任務(wù)分配模型

吳思聰 ,吳 曦

(1.國(guó)防大學(xué) 聯(lián)合作戰(zhàn)學(xué)院,北京,100091;2.國(guó)防大學(xué) 研究生院,北京,100091)

0 引言

當(dāng)前,無(wú)人水下航行器(unmanned undersea vehicle,UUV)迅速發(fā)展,軍事化應(yīng)用步伐加快[1-2]。UUV 難以探測(cè)、續(xù)航時(shí)間長(zhǎng),軍事應(yīng)用前景廣闊。未來(lái),UUV 可能組成集群,搭載魚雷等進(jìn)攻性武器,對(duì)艦隊(duì)以伏擊或偷襲等方式進(jìn)攻,取得非對(duì)稱作戰(zhàn)效果。

對(duì)敵艦隊(duì)打擊過(guò)程中,如何進(jìn)行火力分配是UUV 集群指控過(guò)程中的關(guān)鍵問(wèn)題之一。UUV 集群火力分配是指在相應(yīng)約束條件下,為集群中的每艘UUV 分配打擊目標(biāo),從而使得整體作戰(zhàn)效能最大。整體作戰(zhàn)效能通常通過(guò)以下目標(biāo)衡量: 對(duì)敵方目標(biāo)的毀傷最大、己方彈藥消耗最小等。任務(wù)分配方案構(gòu)成的基本要素應(yīng)包括需打擊的目標(biāo)集合、對(duì)目標(biāo)發(fā)射的武器種類和數(shù)量等[3]。

UUV 集群的打擊任務(wù)分配問(wèn)題,是UUV 集群未來(lái)自主作戰(zhàn)的核心問(wèn)題之一。針對(duì)UUV 集群的任務(wù)分配,許多學(xué)者從不同方面采取不同方法進(jìn)行了研究。Ke 等[4]針對(duì)同構(gòu)UUV 集群任務(wù)分配,考慮UUV 約束、環(huán)境約束和任務(wù)約束,在蟻群算法基礎(chǔ)上引入禁忌表并改進(jìn)了信息素,將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)問(wèn)題。范學(xué)滿等[5]針對(duì)UUV 集群協(xié)同偵察任務(wù)分配問(wèn)題,提出一種人機(jī)融合的多種群遺傳算法,引入多種群更好地平衡全局尋優(yōu)和局部搜索能力,以先驗(yàn)知識(shí)作為啟發(fā)信息輔助種群進(jìn)行初始化,提高算法收斂效率;引入“遺忘策略”,緩解了可能出現(xiàn)的進(jìn)化不完全問(wèn)題。魏娜等[6]對(duì)多UUV 的動(dòng)態(tài)協(xié)同攻防問(wèn)題進(jìn)行了研究,考慮生存概率指標(biāo)函數(shù)和水下環(huán)境影響,建立了基于動(dòng)態(tài)博弈的多自主水下航行器的單元目標(biāo)分配模型,構(gòu)建博弈矩陣,使用粒子群算法求解博弈模型的納什均衡解,形成博弈對(duì)抗雙方的最優(yōu)任務(wù)分配方案。馬碩等[7]針對(duì)水下UUV 集群協(xié)作多目標(biāo)任務(wù)分配問(wèn)題,提出一種基于市場(chǎng)拍賣機(jī)制的分層聚類目標(biāo)分配方法,并研究了異步和同步2 種任務(wù)分配模式及模型。Zhou 等[8]使用改進(jìn)投標(biāo)方式和估價(jià)方式的合同網(wǎng)協(xié)議方法解決了多UUV 任務(wù)分配問(wèn)題。Zhu 等[9]提出使用自組織特征映射(self-organizing feature map,SOM)神經(jīng)網(wǎng)絡(luò),將目標(biāo)作為輸入層,不斷調(diào)整神經(jīng)元權(quán)重進(jìn)行學(xué)習(xí),從而對(duì)UUV 進(jìn)行任務(wù)分配。此外,無(wú)人機(jī)集群任務(wù)規(guī)劃相關(guān)研究[10-13]也有較大參考價(jià)值。

UUV 集群打擊任務(wù)分配問(wèn)題是一個(gè)多目標(biāo)優(yōu)化問(wèn)題。當(dāng)前,研究主要集中使用智能優(yōu)化算法建模求解,也有部分文獻(xiàn)從博弈論和神經(jīng)網(wǎng)絡(luò)的角度進(jìn)行研究,從多目標(biāo)優(yōu)化角度分析UUV 集群打擊任務(wù)分配的研究較少。運(yùn)用多目標(biāo)優(yōu)化問(wèn)題視角分析,相較于從單目標(biāo)優(yōu)化角度,能夠更加全面地掌握UUV 集群打擊任務(wù)分配中各個(gè)因素對(duì)結(jié)果的不同影響和制約,幫助指揮員更好地進(jìn)行決策。因此,在考慮載彈量、彈藥價(jià)值、目標(biāo)價(jià)值和毀傷概率等因素基礎(chǔ)上,建立打擊效益最大和彈藥耗費(fèi)成本最小2 個(gè)目標(biāo),構(gòu)建UUV 集群打擊任務(wù)分配模型。將第三代非支配排序遺傳算法(non-dominated sorting genetic algorithms-Ⅲ,NSGA-Ⅲ)[14]應(yīng)用于UUV 集群打擊任務(wù)分配,通過(guò)仿真實(shí)驗(yàn)將NSGA-Ⅲ與NSGA-Ⅱ和自適應(yīng)形狀估計(jì)多目標(biāo)進(jìn)化算法(adaptive geometry estimation-multiobjective evolutionary algorithms,AGE-MOEA)進(jìn)行比較,驗(yàn)證算法優(yōu)越性。

1 UUV 集群打擊任務(wù)分配模型

UUV 集群打擊任務(wù)分配問(wèn)題可以轉(zhuǎn)化為武器-目標(biāo)分配(weapon-target assign,WTA)問(wèn)題。WTA問(wèn)題是解決如何將多種作戰(zhàn)武器分配給多個(gè)打擊目標(biāo),以最優(yōu)地實(shí)現(xiàn)指揮員的作戰(zhàn)意圖,也是指揮控制自動(dòng)化、智能化需要解決的關(guān)鍵問(wèn)題。

1.1 模型定義

使用WTA 模型[15]對(duì)UUV 集群打擊任務(wù)分配進(jìn)行建模。

首先定義UUV 集群為U={u1,u2,···,ui,···,uN}。其中:N為UUV 數(shù)量,i為UUV 編號(hào)。其載彈量為li,對(duì)應(yīng)的彈藥成本為ci。則載彈量L向量和彈藥成本C向量分別為

目標(biāo)集合為T={t1,t2,···,tj,···,tM},其中M為目標(biāo)數(shù)量,j為目標(biāo)編號(hào)。第j個(gè)目標(biāo)Tj的目標(biāo)價(jià)值為wj。第i個(gè)UUV 對(duì)j個(gè)目標(biāo)發(fā)射一枚魚雷毀傷概率tj為pij。定義目標(biāo)價(jià)值矩陣W和毀傷概率矩陣P毀為

xij為武器平臺(tái)ui向目標(biāo)tj發(fā)射的魚雷數(shù)量,則發(fā)射數(shù)量矩陣

1.2 模型約束條件

1) 武器數(shù)量約束。對(duì)于第i個(gè)UUV,發(fā)射的魚雷數(shù)量不能超過(guò)其攜帶魚雷數(shù)量li,即

式中,xij取值范圍為[0,li]。

2) 毀傷概率門限約束。在執(zhí)行任務(wù)前,為保證作戰(zhàn)效果,通常會(huì)設(shè)定目標(biāo)的毀傷概率門限Kj。

UUV 集群可以依靠上級(jí)和集群中的偵察節(jié)點(diǎn)獲取目標(biāo)的準(zhǔn)確位置和運(yùn)動(dòng)狀態(tài),在搜索中,對(duì)第j個(gè)目標(biāo)tj的探測(cè)概率為

目標(biāo)發(fā)現(xiàn)來(lái)襲魚雷時(shí),會(huì)通過(guò)發(fā)射反魚雷魚雷(anti-torpedo torpedo,ATT)、高頻噪聲干擾等方式攔截魚雷,對(duì)于不同魚雷的攔截概率為

第i個(gè)UUV 對(duì)第j個(gè)目標(biāo)tj的殺傷概率為

所有UUV 對(duì)目標(biāo)tj的殺傷概率為

因此殺傷概率pkill(j)≥kj。

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

優(yōu)化目標(biāo)為最大化目標(biāo)打擊收益和最小化彈藥消耗成本。

UUV 對(duì)目標(biāo)的打擊收益用敵方艦船的價(jià)值與毀傷概率的乘積衡量,因此UUV 集群打擊收益為

魚雷使用成本為

因此,模型的優(yōu)化目標(biāo)為

2 基于NSGA-Ⅲ的任務(wù)分配算法

2.1 任務(wù)分配算法設(shè)計(jì)

UUV 集群打擊任務(wù)分配模型是一個(gè)多目標(biāo)優(yōu)化問(wèn)題,需優(yōu)化2 個(gè)不可比較、相互沖突的目標(biāo),一個(gè)目標(biāo)函數(shù)的優(yōu)化以另一個(gè)目標(biāo)劣化為代價(jià),難以出現(xiàn)唯一最優(yōu)解。

多目標(biāo)優(yōu)化問(wèn)題可通過(guò)加權(quán)、分層優(yōu)化等方法,將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題,運(yùn)用單目標(biāo)優(yōu)化算法求解,但加權(quán)法難以確定系數(shù)、分層優(yōu)化方法在沒(méi)有全局最優(yōu)點(diǎn)時(shí)難以應(yīng)用。多目標(biāo)優(yōu)化問(wèn)題還可使用MOEA 進(jìn)行研究,相較于單目標(biāo)優(yōu)化算法,MOEA 運(yùn)算量較大,但能夠保存更多有用信息。因此,采用MOEA 求解上述模型。MOEA 在單目標(biāo)智能算法的基礎(chǔ)上引入pareto前沿描述對(duì)多個(gè)目標(biāo)優(yōu)化形成的解集。pareto 前沿由非支配解組成,非支配解的含義為: 如對(duì)于2 個(gè)解S1、S2和所有目標(biāo)函數(shù)而言,若S1均優(yōu)于S2,則S1支配S2,若S1沒(méi)有被其他解支配,則S1為非支配解。pareto 前沿由非支配解組成,非支配解的含義為: 如對(duì)于2 個(gè)解S1、S2和所有目標(biāo)函數(shù)而言,若S1均優(yōu)于S2,則S1支配S2,若S1沒(méi)有被其他解支配,則S1為非支配解。

NSGA-Ⅲ是多目標(biāo)優(yōu)化領(lǐng)域代表性算法,速度和尋優(yōu)能力保持了較好平衡,引入NSGA-Ⅲ對(duì)UUV 集群打擊任務(wù)分配模型進(jìn)行求解。

2.2 打擊方案編碼策略

遺傳算法中染色體編碼方式通常有二進(jìn)制編碼、格雷碼編碼和實(shí)數(shù)編碼等方式。二進(jìn)制編碼和格雷碼編碼需進(jìn)行編碼和解碼操作,運(yùn)算量較大,且二進(jìn)制編碼會(huì)產(chǎn)生“漢明懸崖”問(wèn)題;而實(shí)數(shù)編碼符合日常認(rèn)知習(xí)慣,理解容易。因此,文中采用十進(jìn)制實(shí)整數(shù)編碼,每條染色體代表一個(gè)打擊方案。每條染色體上的一個(gè)基因?yàn)閷?duì)應(yīng)編號(hào)魚雷攻擊的艦船編號(hào),則每條染色體用一個(gè)向量表示。染色體組成如下

其中,編號(hào)1～l1的染色體代表1 號(hào)UUV 攜帶的魚雷,l1+1～l1+l2為2 號(hào)UUV 攜帶魚雷,以此類推。采取此種編碼方式時(shí),無(wú)需考慮每艘UUV 攜帶彈藥量約束,可以減少判斷約束條件產(chǎn)生的運(yùn)算量。

表1 pareto 前沿對(duì)應(yīng)函數(shù)值Table 1 Pareto Frontier corresponding function value

2.3 約束處理

通過(guò)設(shè)計(jì)編碼策略滿足了載彈量約束,針對(duì)殺傷概率門限約束,采用Deb 等[16]提出的約束支配方法。具體定義如下。

如果一個(gè)解X(1)約束支配解X(2),需要滿足以下任一條件:

1) 如果X(1)可行,X(2)不可行;

2) 如果X(1)和X(2)都不可行,X(1)違反約束程度更小;

3) 如果2 個(gè)解都可行,X(1)支配X(2)。

違反約束值CV(X)的計(jì)算公式為

2.4 NSGA-Ⅲ算法流程

NSGA-Ⅲ由NSGA[17]和NSGA-Ⅱ[18]發(fā)展而來(lái)。NSGA-Ⅲ算法在遺傳算法的基礎(chǔ)上,將擁擠距離改進(jìn)為引入?yún)⒖键c(diǎn),通過(guò)判斷區(qū)域的密度選擇搜索方向,達(dá)到充分探索解空間的目的,具體算法流程如下。

1) 采用Das-Dennis 方法[19]選取參考點(diǎn)?？紤]O個(gè)目標(biāo)的優(yōu)化問(wèn)題,在一個(gè)(O-1)維超平面上選取參考點(diǎn)。每個(gè)目標(biāo)維度有d個(gè)劃分,那么參考點(diǎn)數(shù)量

2) 初始化種群并采用錦標(biāo)賽方式選取最優(yōu)個(gè)體成為父代。

3) 通過(guò)模擬二進(jìn)制交叉、多項(xiàng)式變異運(yùn)算產(chǎn)生新子代。

模擬二進(jìn)制交叉模擬的是二進(jìn)制編碼遺傳算法中的單點(diǎn)交叉操作。執(zhí)行交叉操作后2 個(gè)子染色體C(1)、C(2)分別為

執(zhí)行多項(xiàng)式變異后,新的染色體

式中,a、b分別是染色體基因取值范圍上下界。

式中:u為[0,1]之間的隨機(jī)數(shù);ηm為分布指數(shù),文中取20[21]。

4) 父代、子代合并以增加種群規(guī)模。

5) 對(duì)個(gè)體進(jìn)行非支配排序。

6) 個(gè)體與歐式距離最近的參考點(diǎn)關(guān)聯(lián)。

7) 在被關(guān)聯(lián)較少參考點(diǎn)周圍選擇K個(gè)非支配個(gè)體成為新父代。

8) 重復(fù)步驟3)～7)直到最大迭代次數(shù)。

9) 輸出結(jié)果。

算法流程如圖1 所示。

圖1 NSGA-Ⅲ算法流程Fig.1 Flowchart of NSGA-Ⅲ

關(guān)于NSGA-Ⅲ算法的詳細(xì)分析和進(jìn)一步討論可參見文獻(xiàn)[14]和[16]。

3 仿真實(shí)驗(yàn)及分析

3.1 想定設(shè)計(jì)

為驗(yàn)證模型及求解算法有效性,采用以下想定進(jìn)行仿真。紅方派出6 艘UUV 集群伏擊藍(lán)方艦隊(duì),每艘UUV 攜帶4 枚魚雷,其中1、2、3 號(hào)攜帶Ⅰ型魚雷,成本為800 萬(wàn)元,4、5、6 號(hào)攜帶Ⅱ型魚雷,成本為600 萬(wàn)元。藍(lán)方艦隊(duì)由1 艘巡洋艦、2 艘驅(qū)逐艦、2 艘護(hù)衛(wèi)艦和1 艘補(bǔ)給艦組成,按順序編為1～6 號(hào),分別為1 號(hào)巡洋艦、2 號(hào)驅(qū)逐艦、3 號(hào)驅(qū)逐艦、4 號(hào)護(hù)衛(wèi)艦、5 號(hào)護(hù)衛(wèi)艦和6 號(hào)補(bǔ)給艦。經(jīng)過(guò)歸一化處理后,敵艦隊(duì)目標(biāo)價(jià)值矩陣W=[1 0.7 0.7 0.5 0.5 0.4]。對(duì)目標(biāo)的毀傷概率門限通常在行動(dòng)前確定,仿真中毀傷概率門限kj均設(shè)定為0.75。紅方UUV 魚雷對(duì)目標(biāo)的毀傷概率矩陣P毀如式(20)所示。紅方對(duì)藍(lán)方的探測(cè)概率p探j(luò)均為0.95,藍(lán)方對(duì)紅方魚雷的攔截概率p攔ij均為0.3。

3.2 實(shí)驗(yàn)環(huán)境及評(píng)價(jià)指標(biāo)

以優(yōu)化平臺(tái)PlatEMO[21]為基礎(chǔ),選取能夠處理帶約束優(yōu)化問(wèn)題的NSGA-Ⅱ和AGE-MOEA 算法與NSGA-Ⅲ進(jìn)行比較。實(shí)驗(yàn)計(jì)算機(jī)CPU 為Intel(R)Core(TM) i5-10300H CPU @2.50 GHz,內(nèi)存8 GB,軟件為MATLAB R2022a。

MOEA 的評(píng)價(jià)指標(biāo)包括運(yùn)行時(shí)間和反世代距離(inverted generational distance,IGD) 2 個(gè),運(yùn)行時(shí)間用于評(píng)價(jià)相同問(wèn)題規(guī)模情況下算法的速度,IGD 用于評(píng)價(jià)算法的收斂性。

運(yùn)行時(shí)間是算法最通用、最直觀的評(píng)價(jià)指標(biāo),能夠有效衡量在一定的空間復(fù)雜度下算法的速度。

IGD通過(guò)計(jì)算每個(gè)在真實(shí)pareto 前沿面上的點(diǎn)到算法獲取的個(gè)體集合之間的最小距離來(lái)評(píng)價(jià)算法的收斂性能和分布性能。IGD 值越小,算法的綜合性能包括收斂性和分布性能越好。IGD 的計(jì)算方法為

式中:G為均勻分布在真實(shí)pareto 前沿上的點(diǎn)集;|G|為分布在真實(shí)pareto 前沿面上的點(diǎn)集的個(gè)體數(shù);Q為算法獲得的最優(yōu)pareto 最優(yōu)解集;d(v,Q)為P中個(gè)體v到種群Q的最小歐氏距離[22]。

3.3 實(shí)驗(yàn)結(jié)果及分析

UUV 集群任務(wù)分配方案的pareto 前沿如圖2所示,對(duì)應(yīng)編號(hào)的函數(shù)值見表1。在實(shí)際決策中,可以根據(jù)決策偏好進(jìn)一步選擇方案。

圖2 UUV 打擊任務(wù)分配pareto 前沿Fig.2 Pareto frontier of UUV strike task allocation

根據(jù)戰(zhàn)場(chǎng)情況,可以進(jìn)一步對(duì)方案進(jìn)行篩選。如,在該想定中,方案1～5 的打擊收益最大相差為4.6%,差異較小,主要考慮彈藥消耗成本,可以選擇彈藥消耗成本最小的方案5。此時(shí)對(duì)應(yīng)的打擊方案為

其含義為：1 號(hào)UUV 向2 號(hào)驅(qū)逐艦發(fā)射1 枚魚雷、向1 號(hào)巡洋艦發(fā)射2 枚魚雷；2 號(hào)UUV 向2 號(hào)驅(qū)逐艦發(fā)射1 枚魚雷、向5 號(hào)護(hù)衛(wèi)艦發(fā)射1 枚魚雷、向1 號(hào)巡洋艦發(fā)射2 枚魚雷；3 號(hào)UUV 向3 號(hào)驅(qū)逐艦發(fā)射2 枚魚雷、向2 號(hào)驅(qū)逐艦發(fā)射1 枚魚雷，向1 號(hào)巡洋艦發(fā)射1 枚魚雷；4 號(hào)UUV 向5 號(hào)護(hù)衛(wèi)艦發(fā)射1 枚魚雷、向4 號(hào)護(hù)衛(wèi)艦發(fā)射1 枚魚雷、向3 號(hào)驅(qū)逐艦發(fā)射1 枚魚雷；5 號(hào)UUV 向4 號(hào)護(hù)衛(wèi)艦發(fā)射2 枚魚雷、向5 號(hào)護(hù)衛(wèi)艦發(fā)射1 枚魚雷；6 號(hào)UUV 向6 號(hào)補(bǔ)給艦發(fā)射2 枚魚雷、向3 號(hào)驅(qū)逐艦發(fā)射1 枚魚雷。對(duì)應(yīng)毀傷價(jià)值期望為2.976、魚雷使用成本為14200 萬(wàn)元。

設(shè)置種群規(guī)模分別為100、200,迭代次數(shù)分別設(shè)置為5 000、10 000,每種組合運(yùn)行20 回,平均時(shí)間如表2 所示。

表2 平均總運(yùn)行時(shí)間Table 2 Average total running time

從表2 可以看出,NSGA-Ⅲ在問(wèn)題規(guī)模相同時(shí),運(yùn)算速度上具有優(yōu)勢(shì),種群規(guī)模對(duì)總運(yùn)行時(shí)間運(yùn)行較小,迭代次數(shù)對(duì)總運(yùn)行時(shí)間影響較大。

IGD 指標(biāo)是動(dòng)態(tài)指標(biāo),圖3 展示了在種群規(guī)模為100、迭代次數(shù)10 000 時(shí)3 種算法的IGD 指標(biāo)。

圖3 3 種算法IGD 指標(biāo)對(duì)比Fig.3 Comparison of IGD indicators among three algorithms

可以看出,NSGA-Ⅲ在運(yùn)行時(shí)間和IGD 2 項(xiàng)指標(biāo)上均優(yōu)于NSGA-Ⅱ和AGE-MOEA 算法,證明了NSGA-Ⅲ算法在求解UUV 集群打擊任務(wù)分配模型上的優(yōu)越性。

4 結(jié)束語(yǔ)

文中從有約束多目標(biāo)優(yōu)化視角分析,將UUV集群打擊艦隊(duì)任務(wù)分配問(wèn)題轉(zhuǎn)化為WTA 問(wèn)題,考慮對(duì)敵艦探測(cè)概率、載彈量、彈藥成本、殺傷概率、目標(biāo)價(jià)值以及對(duì)魚雷的攔截概率等因素,建立打擊收益、彈藥消耗成本2 個(gè)目標(biāo)函數(shù),構(gòu)建UUV打擊任務(wù)分配模型。應(yīng)用NSGA-Ⅲ算法求解UUV集群打擊任務(wù)分配問(wèn)題,分析了編碼策略和約束處理方法,介紹了算法流程和關(guān)鍵步驟。設(shè)計(jì)想定并采用NSGA-Ⅲ算法求解模型pareto 前沿,對(duì)解集進(jìn)行分析,給出了打擊方案。對(duì)NSGA-Ⅲ、NSGA-Ⅱ和AGE-MOEA 3 種算法運(yùn)行時(shí)間和IGD指標(biāo)進(jìn)行比較,驗(yàn)證了NSGA-Ⅲ算法的優(yōu)勢(shì)。多目標(biāo)優(yōu)化算法能夠更加全面地體現(xiàn)不同方案造成的影響,更加適應(yīng)戰(zhàn)場(chǎng)的復(fù)雜情況,更好為指揮員提供決策支持。下一步研究將考慮更多目標(biāo)函數(shù),引入通信能力、海浪干擾和UUV 可靠性等約束條件,提高模型真實(shí)度。智能化算法在并行方面具有先天優(yōu)勢(shì),在進(jìn)一步研究中可通過(guò)并行化提升算法速度。