基于海洋捕食者算法的武器目標分配問題研究

張 青，曾慶華，張宗宇，葉宵宇

(中山大學 航空航天學院， 廣東 深圳 518107)

1 引言

求解武器-目標分配優化問題是空戰決策的重要內容，也是決定能否達成作戰效益的重要因素[1]。目前圍繞該問題的解決方法主要包括傳統的分支定界、動態規劃與合同法等，以及智能優化算法，如遺傳算法、模擬退火算法、蟻群及粒子群算法等[2]。傳統分配方法雖然理論基礎較簡單，但求解時間長、效率低，難以滿足分配的實時性要求且難以處理多維目標分配問題。而智能優化算法雖然在解決上述問題方面有所突破，但也存在一定局限性，如容易早熟收斂，陷入局部最優，收斂速度慢等[3]。

圍繞上述問題，近年來越來越多的學者青睞采用基于生物特性啟發的新穎智能算法來解決上述問題[4]。Jun Wang等[5]從非線性整數規劃角度出發，結合局部搜索算法，提出了一種混合離散灰狼優化算法，極大地提升了大規模分配問題的可擴展性。Rafet Durgut等[6]受蜜蜂智能行為啟發，構建了求解目標分配問題的人工蜂群算法，取得了良好的分配效果。You li等[7]構建了雙目標武器-分配模型，使用帕累托蟻群優化算法，提出改進的運動概率規則來緩解早熟收斂，有效提升了傳統蟻群算法的性能。Yao jishuai等[8]通過改進帝王蝶優化算法，使用貪心策略遷移操作和自適應交叉算子解決了收斂速度和精度低的問題。

上述研究能夠不同程度地提高算法的全局尋優能力和收斂速度，但仍存在收斂精度不高、對不同復雜函數魯棒性較差和難以跳出局部最優的現象。為提高武器-目標分配問題的求解效率和提高求解質量，本文給出了一種基于改進的海洋捕食者算法的求解策略。

2 武器-目標分配問題建模

2.1 目標分配問題描述

目標分配屬于典型的規劃問題，通過對戰場環境、給定資源以及各種約束條件的分析計算，對任務目標進行合理規劃分配，以達到最佳作戰效果[9]。由圖1可見敵我雙方作戰場景。圖中黃色區域為我方陣營，武器配置為m枚導彈。紅色區域為敵方陣營，具有n個目標。我方的任務為最大程度地摧毀敵方目標，因此，需要在考慮作戰意圖、武器性能、目標價值等因素的基礎上，以摧毀效益最大值為目標函數，建立武器-目標分配模型。

圖1 敵我雙方作戰場景示意圖Fig.1 Distribution Diagram

首先，在此場景中，我方武器m枚，敵方目標n個。xij為分配狀態，確定其分配矩陣X：

(1)

該矩陣中，第i行代表第i個武器，第j列代表第j個目標。xij為布爾值，代表分配狀態。當xij=1時，意為第i個武器被分配打擊第j個目標，當xij=0時，代表未分配第i個武器打擊第j個目標。

2.2 目標函數及假設約束

目標函數通常由作戰任務與指揮決策的側重點決定，我方作戰意圖為最大程度地摧毀敵方目標，因此，以摧毀效益為目標函數。同時考慮武器性能、目標價值、武器成本、摧毀概率等因素，摧毀效益Λ可表達為摧毀收益Α減去打擊成本g：

(2)

因此設定摧毀效益最大值為目標函數：

(3)

對求解問題進行如下假設：不考慮武器發射的時間順序以及過程中的突發情況；不同武器與不同目標之間的打擊結果相互獨立，互不干擾；武器數量大于目標數量，一枚武器只能打擊一個目標，但一個目標可被多枚武器攻擊。

此外，模型需滿足式(4)約束條件，該約束表示一個目標至少會被分配到一個武器，最多會被分配到uj個武器；一個武器只能分配給一個目標。

(4)

3 改進的海洋捕食者算法

海洋捕食者算法(marine predator algorithm，MPA)是Faramarzi于2020年提出的一種新穎的群智能算法，該算法受海洋捕食者與獵物之間的行為特性啟發而提出[10]。并在COVID-19感染人數的預測[11]、光伏模型參數優化[12]等領域得到廣泛應用。

3.1 基本的海洋捕食者算法原理及步驟

海洋捕食者算法主要靈感來源于海洋捕食者的覓食策略—萊維運動與布朗運動，以及捕食者和獵物之間相互作用的最佳遭遇策略。捕食者意為最優解，獵物意為當前解，核心步驟在于獵物位置不斷地更新變化，同時其適應度值與捕食者的適應度值相比較，若優于捕食者，則此獵物將被捕食者“捕捉”，捕食者位置將會進行更新[10]。算法中的獵物位置根據其與捕食者的相對關系而改變，此外，還會根據環境而改變，例如因渦流形成或魚類聚集裝置(FAD)效應而使獵物長時間聚集在FAD附近的現象被視為局部最優解。若要擺脫當前局部最優解，則需要一個長跳躍操作。

3.2 改進的基于反向學習策略的種群初始化

海洋捕食者算法作為元啟發式算法，是一種基于種群的方法。原始算法中種群初始解隨機均勻分布在搜索空間上：

X0=Xmin+rand(Xmax-Xmin)

(5)

其中，Xmax與Xmin分別代表解變量的上下限，rand是0～1的均勻隨機向量。

優化算法計算時間與初始種群中個體和最優個體間的距離有關，若初始種群靠近最優解附近，則種群所有個體會快速收斂。然而隨機生成的初始種群收斂速度不可估計，若在初始解中考慮反向種群，那么個體與反向個體更靠近最優個體的概率是50%，選中更靠近最優個體的個體作為初始種群，會加快算法收斂速度，因此初始種群前一半采用式(5)生成，另一半基于式(5)采用式(6)生成，其數學表達如式(6)：

(6)

在算法初期建立2個矩陣，分別為捕食者矩陣E(E∈Rs×d)與獵物矩陣P(P∈Rs×d)，依次儲存最優解與當前解。當種群初始化時，捕食者矩陣與獵物矩陣都儲存著初始種群，隨著獵物位置(當前解)的不斷更新，捕食者位置(最優解)也會隨著之更新。

3.3 基于自適應參數輪盤賭的獵物更新方式

MPA優化過程主要模擬海洋中捕食者與獵物之間的捕食過程，根據捕食者與獵物之間的速度比，可將整個迭代過程分為3個更新階段：

第一階段(迭代前期)：當獵物運動速度很快時，即高速比情況下，獵物采取布朗運動，捕食者最佳策略是靜止不動，對應的數學模型為：

(7)

第二階段(迭代中期)：當獵物運動速度與捕食者運動速度相當，即速度比接近1時，此時由全局搜索逐漸轉化為局部搜索，在這個階段，全局與局部搜索能力都很重要。因此對一半獵物注重其探索能力，對另一半獵物則注重開發能力(即局部搜索能力)。其數學模型為：

(8)

(9)

原始算法機械地規定前一半種群注重開發能力，后一半種群注重探索能力，這樣勢必導致算法全局搜索能力和局部搜索能力之間的不平衡。而本文采用基于自適應參數輪盤賭的更新方式，能夠增強種群變化的隨機性。具體而言，即自主生成探索與開發能力在輪盤上的占比如式(10)：

(10)

其中，w為自適應參數，fitn為當前解的適應度值，fitw為上一代的最差的適應度值,fitb為上一代最優的適應度值。

式(10)表明：當w<0.5時，此時當前解適應度值落在靠左處，需要較大的步長跳出局部最優，需要增強全局搜索能力；當w>0.5時，此時當前解適應度值落在靠右處，靠近最優值，只需要較小的步長繼續局部搜索。輪盤賭中探索與開發占比如圖2所示，輪盤賭法可以生成0～1的隨機數r，當r

圖2 輪盤賭中探索與開發占比示意圖Fig.2 Roulette diagram

第三階段(迭代后期)：當獵物速度很慢，即低速比時，捕食者的最佳策略是采取萊維運動，其數學表示為：

(11)

3.4 算法步驟

改進的海洋捕食者算法((improved marine predator algorithms，IMPA)實現步驟如圖3所示。

圖3 算法流程框圖Fig.3 Algorithm flow chart

步驟1：參數設定。設置種群數量，解的維數，最大迭代次數，FADs等；

步驟2：目標函數的確定。通過式(3)來求解每個獵物的適應度值，從而達到篩選的過程；

步驟3：種群初始化。通過反向學習的方式來確定初始種群，增加收斂速度；

步驟4：形成初始獵物矩陣后，計算每個獵物的適應度值并進行排序替換，形成捕食者矩陣；

步驟5：獵物更新。在迭代不同時期采用不同的更新方式(迭代前1/3時，獵物采取布朗運動；在迭代中期，即1/3～2/3時，通過自適應參數輪盤賭法來確定采用萊維運動還是布朗運動；在迭代后1/3時，捕食者采用的策略是萊維運動。)

步驟6：獵物更新后，重新計算每個獵物的適應度值，同樣對適應度值進行排序替換，形成捕食者獵物，并進行海洋記憶儲存；

步驟7：考慮渦流形成與FAD效應：在迭代完成后，為脫離局部最優解，通過FAD效應進一步改變獵物的位置，計算其適應度值，并對捕食者矩陣進行更新；

步驟8：判斷算法當前迭代次數Iter是否達到最大迭代次數Max_Iter，若滿足則終止算法；輸出最佳適應度值與最佳解，若不滿足，則轉至步驟5。

4 仿真校驗

4.1 任務描述及參數設定

本小節通過數值仿真手段對所提算法有效性進行驗證，給定敵我雙方的作戰場景如下，我方無人機偵察到敵方8個目標，派遣我方10枚導彈攻擊敵方目標。假設我方有兩種武器，并且武器對目標的摧毀概率只與武器類別有關。此外，目標具有一定的防御系統，決定了擊落武器的概率。基于以上假設，設定模型參數與算法參數，如表1所示。

表1 模型參數及算法參數Table 1 Model parameters and algorithm parameters

4.2 仿真驗證

為了驗證海洋捕食者算法及改進后的海洋捕食者算法性能，將其與經典的啟發式智能算法與新穎的智能算法進行對比。取海洋捕食者算法、遺傳算法[13](genetic algorithms，GA)、粒子群算法(particle swarm optimization，PSO)以及蜻蜓優化算法[14](dragonfly algorithm，DA)與鯨魚優化算法[15](whale optimization algorithm，WOA)作為對比算法。為避免智能算法的隨機性對結果造成的誤差，將各類算法獨立運行100次進行分析。表2給出了各個算法解算得到的100組適應度值中最大值、最小值、平均值、單次運行時間、100次總運行時間、所計算適應度值的方差與未算出解的次數等統計數據。

表2 不同算法求解結果Table 2 Comparison table of solution results of different algorithms

為了更直觀地顯示IMPA的尋優效果，圖4為6種算法解算此模型的箱線圖。由圖可知，IMPA所解算出的適應度值中最大值、最小值都大于其余算法。其次，IMPA的箱體最窄，說明IMPA的100組數據波動程度最小，最穩定。PSO算法最大值與IMPA算法一致，但PSO算法箱體最長，其算法穩定性較差。因此，IMPA在適應度平均水平以及波動程度等方面于6種算法中表現最優。

圖4 算法性能箱線圖Fig.4 Comparison diagram of algorithm performance

圖5為6種算法適應度值統計曲線，首先，由整體圖5可知，重復進行100次的實驗，只有MPA與IMPA算法每次都解算出了解，而其余4種算法皆出現了未解算出解的情況。因此MPA與IMPA的求解能力高于其余4種算法。其次，MPA與IMPA解算出的適應度值波動程度整體優于其余4種算法，而粒子群算法波動最大，通過局部放大圖可知，MPA與IMPA數據波動程度接近，但從表2的方差來看，MPA的方差為0.002 0，IMPA的方差為0.001 6，IMPA的穩定程度要優于MPA。

圖5 適應度值曲線Fig.5 Comparison of the degree of data fluctuation

圖6給出重復100次實驗中MPA與IMPA算法解算出的最優值的迭代過程，MPA解算出的最優適應度值為1.873 3，IMPA解算出最優適應度值為1.885 3。將其迭代過程進行對比，MPA于120代左右收斂到最優值，而IMPA于20代左右就收斂到最優值。可知，IMPA的收斂速度高于MPA。

圖6 MPA與IMPA適應度值迭代過程曲線Fig.6 Iterative process of MPA and IMPA fitness values

以上內容主要針對不同算法求解目標函數的適應度值進行了最值和方差分析，另外對算法的求解時間與求解能力進行分析。由于在目標函數中引入了懲罰因子，可能會出現無解的情況。通過表2可知，MPA以及IMPA得出解的概率為100%，GA算法為97%、PSO算法為73%、DA算法為72%、 WOA算法為54%，因此海洋捕食者算法有很強的求解能力。此外，通過事后統計法對算法的時間復雜度進行分析，由運行時間來看，MPA、IMPA、WOA，處于第一梯隊，PSO處于第二梯隊、GA處于第三梯隊，DA運行時間最長，處于第四梯隊。同時在時間相近的情況下，MPA、IMPA、WOA三者中IMPA的適應度值最大，得出的解最優。因此，用IMPA算法得出的最優適應度值對應的分配方案為最佳分配方案，其方案為表3。

表3給出了最優的分配方案及摧毀收益的具體數值，第一行表明了導彈的數量與序號，第二行給出導彈序號所對應的打擊目標序號。在此分配方案中，有3枚導彈對目標5進行攻擊，而通過表1可知，目標5的價值度最高，因此將較多火力集中在價值度高的目標上，獲得最大的收益。通過表2可知，IMPA能夠解算出最優的適應度值，因此最大適應度值對應的分配方案最優。

表3 最佳分配方案Table 3 Optimal allocation scheme

5 結論

1) 將海洋捕食者算法應用于武器-目標分配問題，很好地解決了其余算法易陷入局部最優解的問題；

2) 通過反向學習策略對海洋捕食者算法種群初始化的改進，增加了算法的收斂速度；通過自適應參數輪盤賭法對獵物更新方式的改進，增加了種群更新的隨機性，以及平衡了算法全局與局部搜索能力。