基于多目標(biāo)鯨魚(yú)優(yōu)化算法的動(dòng)態(tài)武器目標(biāo)分配

邱少明，柏陳城，呂亞娜，李 傲

(大連大學(xué) 通信與網(wǎng)絡(luò)重點(diǎn)實(shí)驗(yàn)室，遼寧 大連 116622)

1 引言

武器目標(biāo)分配(weapon target assignment，WTA)問(wèn)題是戰(zhàn)場(chǎng)上作戰(zhàn)指揮與控制(C2)[1]自動(dòng)化的關(guān)鍵問(wèn)題之一，是軍事運(yùn)籌學(xué)領(lǐng)域中典型的帶有約束條件的非線性組合優(yōu)化問(wèn)題，并且已被證明是NP(non-deterministic polynomial)完全問(wèn)題[2]。它的基本目標(biāo)是在武器資源有限的情況下，產(chǎn)生的武器打擊分配方案，使得武器對(duì)來(lái)襲目標(biāo)的毀傷程度最大化。武器目標(biāo)分配的最優(yōu)化是充分發(fā)揮武器系統(tǒng)的作戰(zhàn)效能,達(dá)到對(duì)敵最佳毀傷效果的重要因素[3]。

WTA通常被分為兩類，一類是靜態(tài)武器目標(biāo)分配(static weapon target assignment，SWTA)，另一類是動(dòng)態(tài)武器目標(biāo)分配(dynamic weapon target assignment，DWTA)[4]。SWTA模型中，已知該問(wèn)題的所有參數(shù)，在一次武器打擊過(guò)程中將所有武器分配完，而DWTA模型，是武器平臺(tái)的武器分成幾個(gè)階段打擊目標(biāo)，并且一個(gè)階段產(chǎn)生的武器分配方案對(duì)目標(biāo)的毀傷效果，影響下一個(gè)階段的交戰(zhàn)分配策略，是一個(gè)動(dòng)態(tài)決策的過(guò)程[5]。

使用武器打擊來(lái)襲目標(biāo)，并獲取最佳的打擊收益，受武器資源、目標(biāo)威脅和武器成本等多方面的戰(zhàn)場(chǎng)環(huán)境約束。DWTA是一個(gè)多階段的分配過(guò)程，在整個(gè)決策過(guò)程中需考慮其不斷變化的戰(zhàn)場(chǎng)信息，打擊目標(biāo)過(guò)程通常采用“觀察-射擊-觀察”的策略[6]，因此DWTA要比SWTA要復(fù)雜很多?，F(xiàn)有的WTA研究，主要集中在SWTA的研究，在早期，SWTA問(wèn)題主要使用枚舉法，分支定界算法，動(dòng)態(tài)規(guī)劃等傳統(tǒng)算法進(jìn)行求解[7-8]，伴隨著智能算法的興起和計(jì)算機(jī)技術(shù)的快速發(fā)展，出現(xiàn)了進(jìn)化算法[9]、粒子群算法[10]、模擬退火[11]等優(yōu)化算法。例如，Jun Wang等[12]將灰狼優(yōu)化算法與本地搜索算法結(jié)合提出HDGWOA算法，驗(yàn)證了所提算法的可行性和大規(guī)模WTA問(wèn)題可擴(kuò)展性。王力超等[13]提出改進(jìn)粒子群優(yōu)化算法，提高求解武器目標(biāo)分配問(wèn)題算法的效率和準(zhǔn)確性。王平等提出用模擬退火算法對(duì)WTA問(wèn)題進(jìn)行求解，但在具體的實(shí)驗(yàn)中，參數(shù)的選擇有局限性。相對(duì)來(lái)說(shuō)只有較少的關(guān)于DWTA問(wèn)題的研究，Bin Xin等[14]通過(guò)設(shè)計(jì)本地搜索運(yùn)算符，避免重復(fù)產(chǎn)生相同的決策，但其求解質(zhì)量不高，計(jì)算過(guò)程過(guò)于復(fù)雜，Chyh-Ming Lai等[15]為減小算法的復(fù)雜性，提出一種簡(jiǎn)化粒子群優(yōu)化算法，通過(guò)生成初始化方案和交換分配方案簡(jiǎn)化計(jì)算過(guò)程，提高了目標(biāo)分配效率。Tianqing Chang等[16]針對(duì)ABC算法在求解DWTA問(wèn)題中存在收斂速度慢和搜索效率低的問(wèn)題，提出一種改進(jìn)ABC算法，改進(jìn)ABC結(jié)合多種啟發(fā)式因子初始化武器分配方案，提高DWTA收斂速度。但這都僅僅以目標(biāo)的毀傷程度為目標(biāo)。

為滿足現(xiàn)代化戰(zhàn)爭(zhēng)需求，本文建立一種以目標(biāo)生存值最小和武器消耗最小為目標(biāo)，設(shè)計(jì)一種多目標(biāo)的DWTA數(shù)學(xué)模型，提出一種非支配排序的多目標(biāo)鯨魚(yú)優(yōu)化算法(Non-dominated sorting Multi-objective whale optimization algorithm，NSMWOA)用于提高尋優(yōu)精度。通過(guò)3個(gè)多目標(biāo)測(cè)試函數(shù)驗(yàn)證本文算法的性能，并與NSGA-Ⅱ和MOPSO進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明本文所提算法尋優(yōu)能力明顯優(yōu)于其他算法，在DWTA的數(shù)學(xué)模型中進(jìn)行仿真測(cè)試，實(shí)驗(yàn)結(jié)果表明本文所提算法得出PF優(yōu)于其他算法，所得出的武器分配方案更合理。

2 基本概念

2.1 多目標(biāo)優(yōu)化

多目標(biāo)優(yōu)化問(wèn)題指將多個(gè)子目標(biāo)同時(shí)尋優(yōu)，但是這些子目標(biāo)之間的利益存在相互沖突的問(wèn)題，很難客觀地使各個(gè)子目標(biāo)都達(dá)到最優(yōu)解，所以對(duì)于一個(gè)多目標(biāo)優(yōu)化問(wèn)題，沒(méi)有絕對(duì)的或者說(shuō)是唯一的最好解[17]。一個(gè)多目標(biāo)優(yōu)化問(wèn)題可以被描述如下所示：

minf(x)=[f1(x),f2(x),…,fn(x)]T

(1)

約束條件：

其中：x=(x1,x2,…,xi,…,xn)，xi表示第i個(gè)決策變量，gi(x)≤0表示不等式約束條件，hi(x)≤0表示等式約束條件，D表示n維決策空間，Rm表示基本空間。

任意的2個(gè)決策變量xa,xb，如果滿足下面2個(gè)條件，則稱xa支配xa。

1)?i∈{1,…,n}，都有fi(xa)≤fi(xb)成立。

2)?i∈{1,…,n}，都有fi(xa)

所有非支配解的集合稱為非支配集或非劣解集，對(duì)于不存在其他決策變量能支配該變量，則稱該決策變量為非支配解。在n維決策空間中，多個(gè)目標(biāo)函數(shù)都找不到其他的解能夠優(yōu)于當(dāng)前解，則稱該解為Pareto最優(yōu)解。所有的Pareto最優(yōu)解構(gòu)成Pareto最優(yōu)解集，所有Pareto最優(yōu)解組成的曲面為Pareto前沿。對(duì)于單目標(biāo)優(yōu)化問(wèn)題與多目標(biāo)優(yōu)化問(wèn)題相比較，一個(gè)很大的區(qū)別就是多目標(biāo)的解并不是唯一的，而是存在一個(gè)最優(yōu)解的集合。

2.2 鯨魚(yú)優(yōu)化算法

鯨魚(yú)優(yōu)化算法(whale optimization algorithm,WOA)是2016年由Seyedali Mirjalili教授提出的一種群智能優(yōu)化算法，通過(guò)模仿鯨魚(yú)在海洋中捕捉食物的搜尋過(guò)程，來(lái)尋找最優(yōu)解。該算法具有結(jié)構(gòu)簡(jiǎn)單、自身參數(shù)少的特點(diǎn)，在多元函數(shù)求解方面比傳統(tǒng)粒子群優(yōu)化算法和遺傳算法的速度更快、精度更高[18]。

座頭鯨能夠識(shí)別獵物的位置并將其包圍，鯨魚(yú)優(yōu)化算法的數(shù)學(xué)模型包括以下3個(gè)方面：搜索獵物、包圍獵物和泡泡網(wǎng)攻擊[19]。

1) 搜索獵物。座頭鯨根據(jù)彼此間的位置信息隨機(jī)搜索獵物，數(shù)學(xué)模型如下：

D1=|C·Xrand(t)-X(t)|

(2)

X(t+1)=Xrand(t)-A·D1

(3)

其中:Xrand(t)表示隨機(jī)選擇的鯨魚(yú)位置，X(t)表示當(dāng)前鯨魚(yú)的位置信息，D1表示隨機(jī)選擇的鯨魚(yú)與當(dāng)前鯨魚(yú)之間的距離，t表示當(dāng)前的迭代次數(shù)，A,C表示向量系數(shù)，定義如下：

其中：a是從2線性減小到0的收斂因子，r表示0～1之間的隨機(jī)數(shù)。

2) 包圍獵物。座頭鯨在找到獵物后將其包圍，數(shù)學(xué)模型如下所示：

D2=|C·X*(t)-X(t)|

(4)

X(t+1)=X*(t)-A·D2

(5)

其中：X*(t)表示獵物的位置,D2表示當(dāng)前鯨魚(yú)距離獵物個(gè)體之間的位置距離。

3) 泡泡網(wǎng)攻擊。座頭鯨在找到獵物后以螺旋方式不斷減小包圍范圍，數(shù)學(xué)模型如下：

D3=|X*(t)-X(t)|

(6)

X(t+1)=D3·ebl·cos(2πl(wèi))+X*(t)

(7)

其中：D3表示當(dāng)前鯨魚(yú)距離獵物之間的位置距離，b表示螺旋方式的常數(shù)，l表示[-1,1]之間的隨機(jī)數(shù)。

3 動(dòng)態(tài)武器目標(biāo)分配數(shù)學(xué)模型

DWTA模型與SWTA有很多類似的地方，但DWTA是一個(gè)多階段的武器目標(biāo)分配問(wèn)題，前一個(gè)階段的分配結(jié)果產(chǎn)生的打擊收益會(huì)對(duì)下一個(gè)階段的分配方案產(chǎn)生影響。簡(jiǎn)單的說(shuō)，SWTA在整個(gè)防御階段由武器和目標(biāo)配對(duì)構(gòu)成，DWTA是由武器、目標(biāo)和階段3個(gè)進(jìn)行配對(duì)組成，DWTA可以簡(jiǎn)單看出是多個(gè)階段的SWTA[20]。

(8)

(9)

約束條件：

其中，式(8)、式(9)是建立DWTA的2個(gè)目標(biāo)函數(shù)，F(xiàn)1和F2分別表示目標(biāo)生存期望值和武器打擊成本，約束1表示在每個(gè)階段中，武器打擊目標(biāo)的能力，通常ni設(shè)置為1，表示一個(gè)武器在同一階段對(duì)一個(gè)目標(biāo)打擊一次，約束2表示武器的彈藥量，使用的武器數(shù)量不能超出武器所擁有的數(shù)量，約束3中xij取值范圍1或者0，表示打擊或者不打擊。

4 多目標(biāo)鯨魚(yú)優(yōu)化算法求解DWTA

Mirjalili等在2016年提出的WOA算法是一種模擬座頭鯨的覓食行為的群體智能優(yōu)化算法，其中通過(guò)最佳搜索代理來(lái)模擬捕獵行為，使得WOA本身具有精英指導(dǎo)能力，但WOA算法本身鯨魚(yú)位置是隨機(jī)初始化，可能出現(xiàn)種群聚集的情況，并且該算法只能求解單個(gè)目標(biāo)函數(shù)問(wèn)題，對(duì)于多目標(biāo)優(yōu)化問(wèn)題無(wú)法處理。Logistic映射是一種非常簡(jiǎn)單卻被廣泛應(yīng)用的經(jīng)典混沌映射,該模型看來(lái)似乎很簡(jiǎn)單,并且是確定性的,但具有極為復(fù)雜的動(dòng)力學(xué)行為，Logistic映射序列還具有較好的自相關(guān)性和互相關(guān)性[21]。因此，本文通過(guò)兩次logistic映射初始化種群，使得種群分布均勻，對(duì)鯨魚(yú)種群間個(gè)體進(jìn)行支配關(guān)系和擁擠度進(jìn)行排序，對(duì)傳統(tǒng)WOA進(jìn)行改進(jìn)，使得改進(jìn)WOA算法可以解決多目標(biāo)優(yōu)化問(wèn)題的能力。

4.1 編碼

圖1 DWTA分配編碼Fig.1 DWTA assignment code

h1表示第一個(gè)打擊階段，h2表示第二個(gè)打擊階段，Wi表示第i個(gè)武器單元，Ti表示打擊的目標(biāo)單位，取值范圍為 [1,n]之間的整數(shù)。

4.2 種群初始化

群智能優(yōu)化算法中初始種群位置的選取對(duì)算法的收斂速度和尋優(yōu)精度的影響是至關(guān)重要的，一個(gè)分布均勻的種群，有利于算法搜索范圍更廣，提高收斂精度，相反一個(gè)隨機(jī)產(chǎn)生的種群，造成的種群個(gè)體將分布不均衡，導(dǎo)致算法搜索速度慢，增加算法陷入局部最優(yōu)的概率。Logistic映射是經(jīng)典的混沌映射之一，具有計(jì)算量小，易實(shí)現(xiàn)的特點(diǎn)，而在WOA算法中，鯨魚(yú)種群間個(gè)體都是采用隨機(jī)初始化的，為增加這種隨機(jī)性，采用Logistic映射初始化種群，表達(dá)式如下所示：

zk+1=uzk(1-zk)zk∈(0,1)

(10)

其中，μ∈[0,4]，當(dāng)3.569 945≤μ≤4時(shí)，Logistic映射才具有混沌性質(zhì)，但Logistic本身產(chǎn)生的偽隨機(jī)序列，兩端部分的分布情況相比其他部分過(guò)于密集，為增加混沌效果，本文采用兩次Logistic映射初始化，在第一次Logistic映射產(chǎn)生的鯨魚(yú)位置信息的基礎(chǔ)上，在增加一次Logistic映射，使得種群間分布均勻。

4.3 排序

由于智能優(yōu)化算法在迭代過(guò)程中存在部分的隨機(jī)性，有時(shí)產(chǎn)生的子代個(gè)體并沒(méi)有父代個(gè)體優(yōu)秀，另一方面，有些父代個(gè)體雖沒(méi)有其子代個(gè)體優(yōu)秀，但優(yōu)于其他子代個(gè)體，如果只是簡(jiǎn)單的將子代個(gè)體替換父代個(gè)體，降低了算法的收斂精度。因此，本文中先將父代與子代個(gè)體合并，對(duì)合并后的種群根據(jù)非支配等級(jí)和擁擠度大小進(jìn)行排序，保留優(yōu)秀個(gè)體。

4.3.1非支配等級(jí)

WOA算法只適合處理目標(biāo)函數(shù)只有一個(gè)的問(wèn)題，而對(duì)于擁有多個(gè)優(yōu)化目標(biāo)的函數(shù)問(wèn)題來(lái)說(shuō)，鯨魚(yú)個(gè)體對(duì)應(yīng)的多個(gè)目標(biāo)函數(shù)值之間存在相互沖突的問(wèn)題，由于無(wú)法處理各個(gè)目標(biāo)函數(shù)值之間的關(guān)系，導(dǎo)致WOA無(wú)法處理這類問(wèn)題。為此，將鯨魚(yú)個(gè)體間引入一種非支配關(guān)系，計(jì)算出每個(gè)個(gè)體的非支配等級(jí)，進(jìn)而比較種群間個(gè)體的優(yōu)劣，非支配等級(jí)計(jì)算具體流程如下所示：

Step1 遍歷鯨魚(yú)種群個(gè)體，計(jì)算每個(gè)個(gè)體的被支配個(gè)數(shù)和支配解的集合；

Step2 找出被支配個(gè)數(shù)為0的個(gè)體，記為第一支配層；

Step3 將第一支配層的個(gè)體，從剩余個(gè)體中刪除，剩余個(gè)體的支配個(gè)數(shù)減一；

Step4 重復(fù)Step2-Step3步驟，算出其他層的支配個(gè)體，直到鯨魚(yú)種群分層完為止。

4.3.2擁擠度大小

對(duì)于合并后的種群，如果只是篩選非支配等級(jí)高的個(gè)體，導(dǎo)致種群個(gè)體出現(xiàn)聚集的情況，不利于算法的全局尋優(yōu)，為增加種群的多樣性，通過(guò)計(jì)算種群中距離最近的兩個(gè)個(gè)體之間形成的面積，稱為擁擠度。擁擠度越小，表明當(dāng)前種群間的分布越密集，反之，表明種群之間的多樣性越大。在相同的非支配等級(jí)下根據(jù)每一目標(biāo)函數(shù)值的大小的升序順序?qū)ΨN群進(jìn)行排序，其中邊界解指定為無(wú)窮大的解，鯨魚(yú)個(gè)體i的擁擠度等于與i相鄰的2個(gè)個(gè)體i+1和i+1之間形成的矩形邊長(zhǎng)和，擁擠度具體計(jì)算過(guò)程如下：

Step1 初始化種群個(gè)體擁擠度di=0；

Step2 根據(jù)目標(biāo)函數(shù)值，對(duì)非支配等價(jià)相同的個(gè)體進(jìn)行排序，并記錄最大的目標(biāo)函數(shù)值fmax，fmin。

Step3 將非支配等價(jià)相同的個(gè)體的邊界指定為無(wú)窮大，其他鯨魚(yú)個(gè)體根據(jù)di=di+(fk(i+1)-fk(i-1))/(fmax-fmin)計(jì)算擁擠度計(jì)算；

4.4 算法流程

基于多目標(biāo)鯨魚(yú)優(yōu)化算法的DWTA問(wèn)題的步驟描述如下：

Step1 初始化鯨魚(yú)種群大小NP，最大迭代次數(shù)tmax，通過(guò)2次Logistic映射生成分布均勻的鯨魚(yú)種群；

Step2 根據(jù)式(2)—式(7)產(chǎn)生第一代鯨魚(yú)種群，當(dāng)前代與新產(chǎn)生的一代進(jìn)行合并；

Step3 計(jì)算合并后所有鯨魚(yú)個(gè)體的非支配等級(jí)并依據(jù)該等級(jí)從小到大排序；

Step4 在Step3的順序上，計(jì)算非支配等級(jí)相同的個(gè)體的擁擠度大小，并對(duì)等級(jí)相同的個(gè)體進(jìn)行擁擠度從大到小排序；

Step5 根據(jù)Step3、Step4的排序結(jié)果，篩選最大值作為優(yōu)秀個(gè)體，并記錄最優(yōu)鯨魚(yú)個(gè)體位置信息x(t)；

Step6t=t+1，判斷是否達(dá)到最大迭代次數(shù)，若是，輸出武器目標(biāo)分配方案，否則跳轉(zhuǎn)到Step2。

5 仿真與分析

5.1 多目標(biāo)函數(shù)測(cè)試函數(shù)

為了驗(yàn)證本文中所提NSMWOA算法的優(yōu)勢(shì)，測(cè)試3個(gè)多目標(biāo)函數(shù)ZDT1，ZTD2，ZTD3，與NSGA-Ⅱ[22]，MOPSO[23]作對(duì)比實(shí)驗(yàn)。另外，因?yàn)樵糤OA算法存在一定的缺陷，無(wú)法解決多目標(biāo)問(wèn)題，所以本文中未加入消融實(shí)驗(yàn)。為保證實(shí)驗(yàn)的公平性，所有測(cè)試都在Windows 10(64位)操作系統(tǒng)，編程軟件使用MATLAB R2016a的計(jì)算機(jī)上設(shè)計(jì)實(shí)現(xiàn)。3種算法的種群大小均為50，迭代次數(shù)均為100。為減小算法在測(cè)試函數(shù)中帶來(lái)的隨機(jī)性，獨(dú)立重復(fù)20次實(shí)驗(yàn)并記錄各個(gè)評(píng)價(jià)指標(biāo)的平均值，如表2所示。仿真結(jié)果如圖2—圖4所示。

表1 3個(gè)多目標(biāo)測(cè)試函數(shù)Table 1 3 multi-objective test functions

表2 3個(gè)函數(shù)評(píng)價(jià)指標(biāo)平均值Table 2 Average value of evaluation indexes of the three functions

從圖2—圖4中可以看出，本文中所提算法相比文獻(xiàn)[19]NSGA-Ⅱ和文獻(xiàn)[21]MOPSO算法更加貼近真實(shí)的Pareto前沿，表明本文算法尋優(yōu)精度明顯優(yōu)于其他算法，為減小文章篇幅，只列出3個(gè)算法在ZTD1函數(shù)上的世代距離(GD)、反世代距離(IGD)、超體積指標(biāo)(HV)、空間度量指標(biāo)(Spacing)指標(biāo)來(lái)說(shuō)明算法的性能，如圖5—圖8所示。

圖2 ZDT1測(cè)試曲線Fig.2 ZDT1 test curve

圖3 ZDT2測(cè)試曲線Fig.3 ZDT2 test curve

圖4 ZDT3測(cè)試曲線Fig.4 ZDT3 test curve

圖5 GD曲線Fig.5 GD curve

圖6 HV曲線Fig.6 HV curve

圖7 IGD曲線Fig.7 IGD curve

圖8 Spacing曲線Fig.8 Spacing curve

如表2所示，GD值越小，說(shuō)明算法的收斂性越好，HV值越大，說(shuō)明算法的綜合性越好，IGD值越小，說(shuō)明算法的綜合性越好，Spacing值越小，說(shuō)明該解集越均勻。從圖可以看出NSMWOA算法在收斂性、綜合性能明顯優(yōu)于其他算法。平均提升效果均在34%以上，其中，在目標(biāo)函數(shù)ZDT2中的HV指標(biāo)上更是有223.837%的提升效果。

5.2 NSMWOA在DWTA分配中的應(yīng)用

假設(shè)某次軍事行動(dòng)中，有10種類型的武器平臺(tái)打擊8個(gè)來(lái)襲目標(biāo)，每個(gè)武器平臺(tái)所用的武器數(shù)量均為2，每個(gè)武器在每個(gè)階段只能使用一次，并且武器只能打擊一個(gè)目標(biāo)，武器對(duì)目標(biāo)的毀傷概率、目標(biāo)的價(jià)值以及武器每個(gè)階段的使用成本值采用文獻(xiàn)[24]方法生成。以目標(biāo)函數(shù)式(8)、式(9)為DWTA模型，種群大小和迭代次數(shù)均設(shè)置為100，對(duì)比算法求解DWTA問(wèn)題得出的Pareto前沿，如圖9所示。

圖9 3種算法得出DWTA的Pareto前沿對(duì)比Fig.9 Pareto frontier comparison of DWTA obtained by the three algorithms

為了增加實(shí)驗(yàn)的公平性，將獨(dú)立重復(fù)運(yùn)行20次，取函數(shù)F1、函數(shù)F2的平均值。為了便于分析，表3展示了3種算法的武器成本F2為13.21時(shí)，對(duì)應(yīng)的目標(biāo)函數(shù)F1的值，由于函數(shù)F1是毀傷概率的倒數(shù)，F(xiàn)1值越小，表明毀傷效果值就越大，由表3中數(shù)據(jù)可知本文所提算法的在武器成本一樣的情況下，得出的武器分配方案使得目標(biāo)的毀傷效果最大。

表3 3種算法性能對(duì)比Table 3 Performance comparison of the three algorithms

6 結(jié)論

本文中建立一種多目標(biāo)優(yōu)化的動(dòng)態(tài)武器目標(biāo)分配模型，并提出一種多目標(biāo)鯨魚(yú)優(yōu)化算法用于求解，首先通過(guò)兩次logistic映射對(duì)鯨魚(yú)種群進(jìn)行初始化，使得種群分配均勻，其次合并父代與子代種群，并引入非支配等級(jí)和擁擠度大小對(duì)種群間個(gè)體進(jìn)行排序，篩選優(yōu)秀個(gè)體。通過(guò)與其他算法在3個(gè)多目標(biāo)函數(shù)中，獨(dú)立重復(fù)20次實(shí)驗(yàn)記錄的各個(gè)評(píng)價(jià)指標(biāo)的平均值表明，本算法的在Spacing、IGD、HV、GD上均有不小于34%的效果提升，收斂較好；在動(dòng)態(tài)武器目標(biāo)分配模型測(cè)試中，在打擊成本相同的前提下，所得出的分配方案使得目標(biāo)的毀傷效果最好，尋優(yōu)精度更高。