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

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

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

1 引言

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

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

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

2 武器-目標(biāo)分配問題建模

2.1 目標(biāo)分配問題描述

目標(biāo)分配屬于典型的規(guī)劃問題，通過對(duì)戰(zhàn)場(chǎng)環(huán)境、給定資源以及各種約束條件的分析計(jì)算，對(duì)任務(wù)目標(biāo)進(jìn)行合理規(guī)劃分配，以達(dá)到最佳作戰(zhàn)效果[9]。由圖1可見敵我雙方作戰(zhàn)場(chǎng)景。圖中黃色區(qū)域?yàn)槲曳疥嚑I(yíng)，武器配置為m枚導(dǎo)彈。紅色區(qū)域?yàn)閿撤疥嚑I(yíng)，具有n個(gè)目標(biāo)。我方的任務(wù)為最大程度地摧毀敵方目標(biāo)，因此，需要在考慮作戰(zhàn)意圖、武器性能、目標(biāo)價(jià)值等因素的基礎(chǔ)上，以摧毀效益最大值為目標(biāo)函數(shù)，建立武器-目標(biāo)分配模型。

圖1 敵我雙方作戰(zhàn)場(chǎng)景示意圖Fig.1 Distribution Diagram

首先，在此場(chǎng)景中，我方武器m枚，敵方目標(biāo)n個(gè)。xij為分配狀態(tài)，確定其分配矩陣X：

(1)

該矩陣中，第i行代表第i個(gè)武器，第j列代表第j個(gè)目標(biāo)。xij為布爾值，代表分配狀態(tài)。當(dāng)xij=1時(shí)，意為第i個(gè)武器被分配打擊第j個(gè)目標(biāo)，當(dāng)xij=0時(shí)，代表未分配第i個(gè)武器打擊第j個(gè)目標(biāo)。

2.2 目標(biāo)函數(shù)及假設(shè)約束

目標(biāo)函數(shù)通常由作戰(zhàn)任務(wù)與指揮決策的側(cè)重點(diǎn)決定，我方作戰(zhàn)意圖為最大程度地摧毀敵方目標(biāo)，因此，以摧毀效益為目標(biāo)函數(shù)。同時(shí)考慮武器性能、目標(biāo)價(jià)值、武器成本、摧毀概率等因素，摧毀效益Λ可表達(dá)為摧毀收益Α減去打擊成本g：

(2)

因此設(shè)定摧毀效益最大值為目標(biāo)函數(shù)：

(3)

對(duì)求解問題進(jìn)行如下假設(shè)：不考慮武器發(fā)射的時(shí)間順序以及過程中的突發(fā)情況；不同武器與不同目標(biāo)之間的打擊結(jié)果相互獨(dú)立，互不干擾；武器數(shù)量大于目標(biāo)數(shù)量，一枚武器只能打擊一個(gè)目標(biāo)，但一個(gè)目標(biāo)可被多枚武器攻擊。

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

(4)

3 改進(jìn)的海洋捕食者算法

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

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

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

3.2 改進(jìn)的基于反向?qū)W習(xí)策略的種群初始化

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

X0=Xmin+rand(Xmax-Xmin)

(5)

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

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

(6)

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

3.3 基于自適應(yīng)參數(shù)輪盤賭的獵物更新方式

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

第一階段(迭代前期)：當(dāng)獵物運(yùn)動(dòng)速度很快時(shí)，即高速比情況下，獵物采取布朗運(yùn)動(dòng)，捕食者最佳策略是靜止不動(dòng)，對(duì)應(yīng)的數(shù)學(xué)模型為：

(7)

第二階段(迭代中期)：當(dāng)獵物運(yùn)動(dòng)速度與捕食者運(yùn)動(dòng)速度相當(dāng)，即速度比接近1時(shí)，此時(shí)由全局搜索逐漸轉(zhuǎn)化為局部搜索，在這個(gè)階段，全局與局部搜索能力都很重要。因此對(duì)一半獵物注重其探索能力，對(duì)另一半獵物則注重開發(fā)能力(即局部搜索能力)。其數(shù)學(xué)模型為：

(8)

(9)

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

(10)

其中，w為自適應(yīng)參數(shù)，fitn為當(dāng)前解的適應(yīng)度值，fitw為上一代的最差的適應(yīng)度值,fitb為上一代最優(yōu)的適應(yīng)度值。

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

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

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

(11)

3.4 算法步驟

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

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

步驟1：參數(shù)設(shè)定。設(shè)置種群數(shù)量，解的維數(shù)，最大迭代次數(shù)，F(xiàn)ADs等；

步驟2：目標(biāo)函數(shù)的確定。通過式(3)來求解每個(gè)獵物的適應(yīng)度值，從而達(dá)到篩選的過程；

步驟3：種群初始化。通過反向?qū)W習(xí)的方式來確定初始種群，增加收斂速度；

步驟4：形成初始獵物矩陣后，計(jì)算每個(gè)獵物的適應(yīng)度值并進(jìn)行排序替換，形成捕食者矩陣；

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

步驟6：獵物更新后，重新計(jì)算每個(gè)獵物的適應(yīng)度值，同樣對(duì)適應(yīng)度值進(jìn)行排序替換，形成捕食者獵物，并進(jìn)行海洋記憶儲(chǔ)存；

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

步驟8：判斷算法當(dāng)前迭代次數(shù)Iter是否達(dá)到最大迭代次數(shù)Max_Iter，若滿足則終止算法；輸出最佳適應(yīng)度值與最佳解，若不滿足，則轉(zhuǎn)至步驟5。

4 仿真校驗(yàn)

4.1 任務(wù)描述及參數(shù)設(shè)定

本小節(jié)通過數(shù)值仿真手段對(duì)所提算法有效性進(jìn)行驗(yàn)證，給定敵我雙方的作戰(zhàn)場(chǎng)景如下，我方無人機(jī)偵察到敵方8個(gè)目標(biāo)，派遣我方10枚導(dǎo)彈攻擊敵方目標(biāo)。假設(shè)我方有兩種武器，并且武器對(duì)目標(biāo)的摧毀概率只與武器類別有關(guān)。此外，目標(biāo)具有一定的防御系統(tǒng)，決定了擊落武器的概率?；谝陨霞僭O(shè)，設(shè)定模型參數(shù)與算法參數(shù)，如表1所示。

表1 模型參數(shù)及算法參數(shù)Table 1 Model parameters and algorithm parameters

4.2 仿真驗(yàn)證

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

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

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

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

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

圖5 適應(yīng)度值曲線Fig.5 Comparison of the degree of data fluctuation

圖6給出重復(fù)100次實(shí)驗(yàn)中MPA與IMPA算法解算出的最優(yōu)值的迭代過程，MPA解算出的最優(yōu)適應(yīng)度值為1.873 3，IMPA解算出最優(yōu)適應(yīng)度值為1.885 3。將其迭代過程進(jìn)行對(duì)比，MPA于120代左右收斂到最優(yōu)值，而IMPA于20代左右就收斂到最優(yōu)值?？芍琁MPA的收斂速度高于MPA。

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

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

表3給出了最優(yōu)的分配方案及摧毀收益的具體數(shù)值，第一行表明了導(dǎo)彈的數(shù)量與序號(hào)，第二行給出導(dǎo)彈序號(hào)所對(duì)應(yīng)的打擊目標(biāo)序號(hào)。在此分配方案中，有3枚導(dǎo)彈對(duì)目標(biāo)5進(jìn)行攻擊，而通過表1可知，目標(biāo)5的價(jià)值度最高，因此將較多火力集中在價(jià)值度高的目標(biāo)上，獲得最大的收益。通過表2可知，IMPA能夠解算出最優(yōu)的適應(yīng)度值，因此最大適應(yīng)度值對(duì)應(yīng)的分配方案最優(yōu)。

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

5 結(jié)論

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

2) 通過反向?qū)W習(xí)策略對(duì)海洋捕食者算法種群初始化的改進(jìn)，增加了算法的收斂速度；通過自適應(yīng)參數(shù)輪盤賭法對(duì)獵物更新方式的改進(jìn)，增加了種群更新的隨機(jī)性，以及平衡了算法全局與局部搜索能力。