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

吳思聰 ,吳 曦

(1.國防大學 聯合作戰學院,北京,100091;2.國防大學 研究生院,北京,100091)

0 引言

當前,無人水下航行器(unmanned undersea vehicle,UUV)迅速發展,軍事化應用步伐加快[1-2]。UUV 難以探測、續航時間長,軍事應用前景廣闊。未來,UUV 可能組成集群,搭載魚雷等進攻性武器,對艦隊以伏擊或偷襲等方式進攻,取得非對稱作戰效果。

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

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

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

1 UUV 集群打擊任務分配模型

UUV 集群打擊任務分配問題可以轉化為武器-目標分配(weapon-target assign,WTA)問題。WTA問題是解決如何將多種作戰武器分配給多個打擊目標,以最優地實現指揮員的作戰意圖,也是指揮控制自動化、智能化需要解決的關鍵問題。

1.1 模型定義

使用WTA 模型[15]對UUV 集群打擊任務分配進行建模。

首先定義UUV 集群為U={u1,u2,···,ui,···,uN}。其中:N為UUV 數量,i為UUV 編號。其載彈量為li,對應的彈藥成本為ci。則載彈量L向量和彈藥成本C向量分別為

目標集合為T={t1,t2,···,tj,···,tM},其中M為目標數量,j為目標編號。第j個目標Tj的目標價值為wj。第i個UUV 對j個目標發射一枚魚雷毀傷概率tj為pij。定義目標價值矩陣W和毀傷概率矩陣P毀為

xij為武器平臺ui向目標tj發射的魚雷數量,則發射數量矩陣

1.2 模型約束條件

1) 武器數量約束。對于第i個UUV,發射的魚雷數量不能超過其攜帶魚雷數量li,即

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

2) 毀傷概率門限約束。在執行任務前,為保證作戰效果,通常會設定目標的毀傷概率門限Kj。

UUV 集群可以依靠上級和集群中的偵察節點獲取目標的準確位置和運動狀態,在搜索中,對第j個目標tj的探測概率為

目標發現來襲魚雷時,會通過發射反魚雷魚雷(anti-torpedo torpedo,ATT)、高頻噪聲干擾等方式攔截魚雷,對于不同魚雷的攔截概率為

第i個UUV 對第j個目標tj的殺傷概率為

所有UUV 對目標tj的殺傷概率為

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

1.3 目標函數

優化目標為最大化目標打擊收益和最小化彈藥消耗成本。

UUV 對目標的打擊收益用敵方艦船的價值與毀傷概率的乘積衡量,因此UUV 集群打擊收益為

魚雷使用成本為

因此,模型的優化目標為

2 基于NSGA-Ⅲ的任務分配算法

2.1 任務分配算法設計

UUV 集群打擊任務分配模型是一個多目標優化問題,需優化2 個不可比較、相互沖突的目標,一個目標函數的優化以另一個目標劣化為代價,難以出現唯一最優解。

多目標優化問題可通過加權、分層優化等方法,將多目標優化問題轉化為單目標優化問題,運用單目標優化算法求解,但加權法難以確定系數、分層優化方法在沒有全局最優點時難以應用。多目標優化問題還可使用MOEA 進行研究,相較于單目標優化算法,MOEA 運算量較大,但能夠保存更多有用信息。因此,采用MOEA 求解上述模型。MOEA 在單目標智能算法的基礎上引入pareto前沿描述對多個目標優化形成的解集。pareto 前沿由非支配解組成,非支配解的含義為: 如對于2 個解S1、S2和所有目標函數而言,若S1均優于S2,則S1支配S2,若S1沒有被其他解支配,則S1為非支配解。pareto 前沿由非支配解組成,非支配解的含義為: 如對于2 個解S1、S2和所有目標函數而言,若S1均優于S2,則S1支配S2,若S1沒有被其他解支配,則S1為非支配解。

NSGA-Ⅲ是多目標優化領域代表性算法,速度和尋優能力保持了較好平衡,引入NSGA-Ⅲ對UUV 集群打擊任務分配模型進行求解。

2.2 打擊方案編碼策略

遺傳算法中染色體編碼方式通常有二進制編碼、格雷碼編碼和實數編碼等方式。二進制編碼和格雷碼編碼需進行編碼和解碼操作,運算量較大,且二進制編碼會產生“漢明懸崖”問題;而實數編碼符合日常認知習慣,理解容易。因此,文中采用十進制實整數編碼,每條染色體代表一個打擊方案。每條染色體上的一個基因為對應編號魚雷攻擊的艦船編號,則每條染色體用一個向量表示。染色體組成如下

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

表1 pareto 前沿對應函數值Table 1 Pareto Frontier corresponding function value

2.3 約束處理

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

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

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

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

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

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

2.4 NSGA-Ⅲ算法流程

NSGA-Ⅲ由NSGA[17]和NSGA-Ⅱ[18]發展而來。NSGA-Ⅲ算法在遺傳算法的基礎上,將擁擠距離改進為引入參考點,通過判斷區域的密度選擇搜索方向,達到充分探索解空間的目的,具體算法流程如下。

1) 采用Das-Dennis 方法[19]選取參考點?？紤]O個目標的優化問題,在一個(O-1)維超平面上選取參考點。每個目標維度有d個劃分,那么參考點數量

2) 初始化種群并采用錦標賽方式選取最優個體成為父代。

3) 通過模擬二進制交叉、多項式變異運算產生新子代。

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

執行多項式變異后,新的染色體

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

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

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

5) 對個體進行非支配排序。

6) 個體與歐式距離最近的參考點關聯。

7) 在被關聯較少參考點周圍選擇K個非支配個體成為新父代。

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

9) 輸出結果。

算法流程如圖1 所示。

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

關于NSGA-Ⅲ算法的詳細分析和進一步討論可參見文獻[14]和[16]。

3 仿真實驗及分析

3.1 想定設計

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

3.2 實驗環境及評價指標

以優化平臺PlatEMO[21]為基礎,選取能夠處理帶約束優化問題的NSGA-Ⅱ和AGE-MOEA 算法與NSGA-Ⅲ進行比較。實驗計算機CPU 為Intel(R)Core(TM) i5-10300H CPU @2.50 GHz,內存8 GB,軟件為MATLAB R2022a。

MOEA 的評價指標包括運行時間和反世代距離(inverted generational distance,IGD) 2 個,運行時間用于評價相同問題規模情況下算法的速度,IGD 用于評價算法的收斂性。

運行時間是算法最通用、最直觀的評價指標,能夠有效衡量在一定的空間復雜度下算法的速度。

IGD通過計算每個在真實pareto 前沿面上的點到算法獲取的個體集合之間的最小距離來評價算法的收斂性能和分布性能。IGD 值越小,算法的綜合性能包括收斂性和分布性能越好。IGD 的計算方法為

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

3.3 實驗結果及分析

UUV 集群任務分配方案的pareto 前沿如圖2所示,對應編號的函數值見表1。在實際決策中,可以根據決策偏好進一步選擇方案。

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

根據戰場情況,可以進一步對方案進行篩選。如,在該想定中,方案1～5 的打擊收益最大相差為4.6%,差異較小,主要考慮彈藥消耗成本,可以選擇彈藥消耗成本最小的方案5。此時對應的打擊方案為

其含義為：1 號UUV 向2 號驅逐艦發射1 枚魚雷、向1 號巡洋艦發射2 枚魚雷；2 號UUV 向2 號驅逐艦發射1 枚魚雷、向5 號護衛艦發射1 枚魚雷、向1 號巡洋艦發射2 枚魚雷；3 號UUV 向3 號驅逐艦發射2 枚魚雷、向2 號驅逐艦發射1 枚魚雷，向1 號巡洋艦發射1 枚魚雷；4 號UUV 向5 號護衛艦發射1 枚魚雷、向4 號護衛艦發射1 枚魚雷、向3 號驅逐艦發射1 枚魚雷；5 號UUV 向4 號護衛艦發射2 枚魚雷、向5 號護衛艦發射1 枚魚雷；6 號UUV 向6 號補給艦發射2 枚魚雷、向3 號驅逐艦發射1 枚魚雷。對應毀傷價值期望為2.976、魚雷使用成本為14200 萬元。

設置種群規模分別為100、200,迭代次數分別設置為5 000、10 000,每種組合運行20 回,平均時間如表2 所示。

表2 平均總運行時間Table 2 Average total running time

從表2 可以看出,NSGA-Ⅲ在問題規模相同時,運算速度上具有優勢,種群規模對總運行時間運行較小,迭代次數對總運行時間影響較大。

IGD 指標是動態指標,圖3 展示了在種群規模為100、迭代次數10 000 時3 種算法的IGD 指標。

圖3 3 種算法IGD 指標對比Fig.3 Comparison of IGD indicators among three algorithms

可以看出,NSGA-Ⅲ在運行時間和IGD 2 項指標上均優于NSGA-Ⅱ和AGE-MOEA 算法,證明了NSGA-Ⅲ算法在求解UUV 集群打擊任務分配模型上的優越性。

4 結束語

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