改進螢火蟲算法的武器目標分配問題研究

趙冬梅，李玲，宋陽

（海軍大連艦艇學(xué)院 基礎(chǔ)部，遼寧 大連 116018）

0 引言

武器目標分配（Weapon Target Assignment,WTA）問題是指揮控制與任務(wù)規(guī)劃領(lǐng)域的關(guān)鍵難點之一[1]，是在復(fù)雜的戰(zhàn)場環(huán)境中滿足一定的約束條件下，將多種作戰(zhàn)武器分配給多個目標，從而實現(xiàn)最優(yōu)的作戰(zhàn)效能。從求解武器目標分配問題的算法來看，既有匈牙利算法[2]、整數(shù)規(guī)劃算法[3]等最優(yōu)方法，還有遺傳算法[4]、蜂群優(yōu)化算法[5]、鯨魚優(yōu)化算法[6]、螢火蟲算法[7]等仿生智能算法[8-10]。

仿生智能算法具有結(jié)構(gòu)簡單、參數(shù)較少和實現(xiàn)便捷等優(yōu)點，在解決優(yōu)化問題領(lǐng)域有著廣泛的應(yīng)用[11]。文獻[12]設(shè)計了一種混沌自適應(yīng)螢火蟲算法，利用變尺度混沌方法改進光吸收系數(shù)，通過引入全局最優(yōu)值、自適應(yīng)慣性權(quán)重和步長提高算法的精度和收斂速度；文獻[13]將螢火蟲算法離散化，編碼并重新定義螢火蟲移動機制，提出變步長和多鄰域搜索機制，提高了算法的收斂性和全局搜索能力；文獻[14]在初始化螢火蟲種群時，融入Logistic 映射策略和逆向?qū)W習(xí)算子，提高了標準測試函數(shù)最優(yōu)解的質(zhì)量和穩(wěn)定性，但僅限于函數(shù)優(yōu)化，沒有將改進算法進行實際應(yīng)用；文獻[15]重新定義了螢火蟲距離、相對亮度公式和移動方式，利用混沌方法提高算法的局部搜索能力，但沒有改善算法的收斂性；文獻[16]提出了一種基于最大最小策略和非均勻變異的螢火蟲算法，提高了算法的尋優(yōu)能力，但存在效率較低的問題。

針對多目標的武器分配問題，綜合考慮時間窗和武器數(shù)量約束，建立問題模型，確定評價函數(shù)，基于傳統(tǒng)螢火蟲算法提出一種新的改進思路：初始化螢火蟲種群時利用PWLCM 方程融入混沌優(yōu)化，以增加種群搜索初期的多樣性，提高算法的全局搜索能力；為提高搜索效率，改進步長因子，設(shè)置其隨迭代次數(shù)服從半高斯遞減分布，以適應(yīng)不同時段的算法要求；設(shè)計基于排序的螢火蟲更新策略，同時融入交叉和變異操作，以解決算法陷入局部最優(yōu)和收斂速度之間的矛盾。最后通過仿真實驗驗證改進算法的優(yōu)越性。

1 武器目標分配問題建模

1.1 問題描述

假設(shè)有m種武器W={W1,W2,…,Wm}，對n個目標T={T1,T2,…,Tn}執(zhí)行攻擊任務(wù)，在滿足多種約束條件下，使武器實施攻擊目標任務(wù)的評價函數(shù)最好。

將武器分配給目標，規(guī)劃執(zhí)行或者不執(zhí)行攻擊任務(wù)，可看成0-1 規(guī)劃問題。首先建立武器和目標之間m×n階的決策變量矩陣，如式（1）所示：

式中：xij只能取1 或0，xij=1 表示武器Wi對目標Tj執(zhí)行攻擊任務(wù)，xij=0 則表示武器Wi不攻擊目標Tj。結(jié)合實際約束條件和評價函數(shù)求解出將m種武器分配給n個目標的最優(yōu)方案。

1.2 約束條件

1）時間窗約束

構(gòu)建模型時，通常要求指定的武器在合適的時間段對目標執(zhí)行攻擊任務(wù)[17]，時間窗約束如式（2）所示：

式中：startj和endj分別為指定的攻擊第j個目標的起始時間和結(jié)束時間；aj和bj分別為武器實際攻擊第j個目標的起始時間和結(jié)束時間。

2）武器數(shù)量約束

每個武器最多只能攻擊一次目標，每種武器的數(shù)量有限，若武器Wi的數(shù)量為Si，則武器數(shù)量約束如式（3）所示：

3）目標承受武器數(shù)量約束

為避免出現(xiàn)多個武器攻擊目標過于集中的現(xiàn)象，要求對某個目標使用的武器總數(shù)有限，即對目標Tj最多可使用Rj個武器，目標承受武器數(shù)量約束如式（4）所示：

1.3 編碼與解碼

考慮武器數(shù)量約束條件，設(shè)置編碼序列的維度為武器的總數(shù)D，D=，Si為第i種武器的數(shù)量。為體現(xiàn)武器目標分配方案，設(shè)置每一維序列代表相應(yīng)武器攻擊的目標編號，例如武器W1、W2、W3、W4的數(shù)量分別為2、4、3、2，計劃攻擊4 個目標，如果序列編碼為[1,3,1,4,2,0,3,2,1,4,2]，說明W1攻擊1號和3號目標，W2攻擊1 號、4號和2 號目標，W3攻擊3 號、2號和1 號目標，W4攻擊4 號和2 號目標，故序列編碼的取值范圍為0～n目標數(shù)之間的整數(shù)，0 表示不分配該武器執(zhí)行任務(wù)，當算法迭代出現(xiàn)非整數(shù)時，需要對其進行取整處理。

對序列進行解碼時，先依據(jù)武器數(shù)Si依次提取每種武器攻擊的目標序號，根據(jù)武器Wi和目標Tj的對應(yīng)關(guān)系，更新決策變量xij的值，武器被分配時為1，否則為0。

1.4 武器目標分配評價函數(shù)

武器目標分配問題的研究內(nèi)容是如何分配武器使作戰(zhàn)任務(wù)效益最大化，常規(guī)的任務(wù)效益模型[18]如式（5）所示：

式中：Gj為目標Tj對我方的威脅值；pij為武器Wi攻擊目標Tj的命中率；xij為式（1）中定義的Wi攻擊目標Tj的決策變量；1-(1-pij)xij為所有武器對目標Tj的命中率，任務(wù)效益F為所有目標威脅值和對應(yīng)命中率的乘積之和，該值越大，表示執(zhí)行攻擊任務(wù)的效益越高。

對于時間窗約束和目標承受武器數(shù)量約束，需要加入懲罰函數(shù)，最終的評價函數(shù)如式（6）所示：

式中：F為式（5）中定義的任務(wù)效益；λ1、λ2、δ分別為違反左時間窗約束、右時間窗約束和目標承受武器數(shù)量約束的懲罰因子。當武器攻擊目標的時間未達到左時間窗或者超過右時間窗時，需要給予時間懲罰，且時間差越大，懲罰越大；當對目標使用的武器數(shù)超量時，需要給予超限懲罰，且超出數(shù)量越多，懲罰越大。評價函數(shù)等于任務(wù)效益減去懲罰函數(shù)，故評價函數(shù)值越大，武器目標分配方案越好[19]。

2 改進螢火蟲算法求解WTA 問題

2.1 螢火蟲算法原理

螢火蟲算法模擬螢火蟲的閃爍行為，通過個體發(fā)光和相互間的吸引不斷更新迭代，實現(xiàn)對復(fù)雜空間最優(yōu)解的搜索[20]。

如式（7）所示，螢火蟲的亮度I會隨著距離r的增加和媒介的吸收逐漸減弱。

式中：I0為自身熒光亮度，是亮度的最大值，和螢火蟲所在位置對應(yīng)的目標函數(shù)值有關(guān)，目標函數(shù)值越優(yōu)，自身熒光亮度越大；γ為光吸收系數(shù)；rij為螢火蟲i和螢火蟲j之間的距離。

較亮的螢火蟲吸引較暗的螢火蟲移動，吸引度β也與光吸收系數(shù)和距離相關(guān)，如式（8）所示：

式中β0為最大吸引度。

第i個螢火蟲被第j個螢火蟲吸引移動的位置更新公式如式（9）所示：

式中：zi和zj分別表征第i個螢火蟲和第j個螢火蟲所在的空間位置；α為步長因子，決定螢火蟲的自身搜索；rand 為[0，1]間服從均勻分布的隨機因子，以增加螢火蟲飛行的隨機性，避免陷入局部最優(yōu)。由公式（9）可以看出，螢火蟲算法的更新規(guī)則兼顧“對方吸引”和“自身隨機”，以便更快、更準確地搜索出最優(yōu)解。

2.2 混沌初始化螢火蟲

混沌優(yōu)化具有隨機性和遍歷性[21]，常用來提高智能優(yōu)化算法的全局搜索能力。分段線性混沌映射（Piece-Wise Linear Chaotic Map,PWLCM）是典型的混沌映射，映射均勻且分布穩(wěn)定，表達式如式（10）所示[22]：

式中：l為迭代次數(shù)，l=1 時隨機產(chǎn)生初始值k(1)，經(jīng)循環(huán)迭代得到[0，1]的隨機序列；p為混沌映射的控制參數(shù)，在[0，1]內(nèi)取值。

為避免算法早熟收斂，在螢火蟲種群初始化時融入PWLCM 混沌優(yōu)化，具體步驟如下：

1）隨機產(chǎn)生取值在0～n之間的N×D維初始螢火蟲序列Fs，n為目標數(shù)，N為螢火蟲個數(shù)，D為武器總數(shù)；

2）隨機產(chǎn)生一個D維向量y1=[y11,y12,…,y1D]，設(shè)置控 制系數(shù)p為0.4，根據(jù)式（10）得到N個D維向量y1,y2,…,yN；

3）通過將初始螢火蟲序列Fs和y向量相乘再取整的運算規(guī)則，將混沌的y向量映射到螢火蟲的位置向量，如公式（11）所示：

式中ceil()表示取整運算。

2.3 非均勻步長因子

步長因子是影響螢火蟲算法搜索能力的主要因素之一，是平衡局部搜索和全局搜索能力的重要參數(shù)，合理設(shè)置步長因子是螢火蟲算法有效實現(xiàn)的重要保證。

傳統(tǒng)螢火蟲算法設(shè)置固定的步長因子，其值較大時，算法不易收斂，其值較小時，算法易陷入局部最優(yōu)。為兼顧全局搜索能力和收斂性，以算法迭代次數(shù)為變量控制步長因子α的取值。在算法迭代初期，設(shè)置較大的α，加強螢火蟲的隨機性以提高算法的全局搜索能力；在算法迭代后期，種群已基本找到最優(yōu)分配方案，設(shè)置較小的α，加強螢火蟲對全局最優(yōu)值的追隨以提高搜索效率。因此，設(shè)計步長因子α隨迭代次數(shù)服從半高斯分布，如式（12）所示：

式中：l為迭代次數(shù)；NC 為最大迭代次數(shù)；σ取值為最大迭代次數(shù)的14；設(shè)置步長因子α的取值范圍在[αmin,αmax]區(qū)間內(nèi)。這種設(shè)計突出了不同時段對螢火蟲全局和局部搜索能力的動態(tài)調(diào)整，提高了算法的效率和準確性。

2.4 基于排序的螢火蟲更新策略

為提高算法的搜索效率，參考基于排序的蟻群算法[23]，在螢火蟲種群迭代更新時，剔除“劣質(zhì)”，遴選“優(yōu)質(zhì)”。具體步驟為：

1）在每次迭代完成后，依據(jù)評價函數(shù)值將所有螢火蟲進行排序，刪除較差的w只螢火蟲，同時隨機產(chǎn)生新的w只螢火蟲；

2）選擇隨機螢火蟲的兩個交叉位置，將兩位置之間的片段用“最優(yōu)”螢火蟲相應(yīng)位置之間的片段替換，產(chǎn)生“交叉”螢火蟲；

3）隨機選擇“交叉”螢火蟲的兩個變異位置，將變異位置的基因進行交換，即得到交叉變異后的新螢火蟲。

這種基于排序又融入遺傳算法的更新策略充分揚長避短，大大提高了算法的效率和搜索能力。

2.5 算法流程

應(yīng)用改進螢火蟲算法進行武器目標分配的流程如圖1 所示。

圖1 改進螢火蟲算法流程圖

3 仿真實驗與結(jié)果分析

3.1 算法分析與對比

3.1.1 實驗測試函數(shù)

為了驗證并定量分析上述改進螢火蟲算法的性能，使用群智能算法最常用的4 個測試函數(shù)Sphere、Rosenbrock、Griewank 和Rastrigin 對其和傳統(tǒng)螢火蟲算法進行對比[24]。在用改進螢火蟲算法進行函數(shù)最優(yōu)解求解時，需要將實數(shù)解轉(zhuǎn)化為二進制編碼，按照式（13）確定最優(yōu)解對應(yīng)的二進制編碼長度[25]。

式中：L表示二進制編碼的位數(shù)；[a,b]表示測試函數(shù)的定義域；eps 表示自變量的精度。

3.1.2 實驗設(shè)置

實驗中設(shè)置螢火蟲規(guī)模為50，最大迭代次數(shù)為100，最大吸引度β0為2，光吸收系數(shù)γ為1，步長因子α的取值范圍在[0.2，0.8]之間，每個測試函數(shù)均獨立測試20次，得到的結(jié)果有最小值（min）、平均值（mean）和標準差（std）。

3.1.3 實驗結(jié)果與分析

圖2～圖5 為應(yīng)用改進螢火蟲算法求解4 個測試函數(shù)的最優(yōu)解及與傳統(tǒng)螢火蟲算法的收斂曲線對比圖，表1 為4 種改進螢火蟲算法對4 個測試函數(shù)進行尋優(yōu)后的結(jié)果，指標分別有最小值、平均值和標準差，加粗字體為同一行中的最優(yōu)值。

表1 改進螢火蟲算法對4 個測試函數(shù)的優(yōu)化結(jié)果

圖2 Sphere 函數(shù)最優(yōu)解及收斂曲線對比圖

圖3 Rosenbrock 函數(shù)最優(yōu)解及收斂曲線對比圖

圖4 Griewank 函數(shù)最優(yōu)解及收斂曲線對比圖

圖5 Rastrigin 函數(shù)最優(yōu)解及收斂曲線對比圖

由圖2～圖5 可見，不論單峰函數(shù)還是多峰函數(shù)，本文提出的改進螢火蟲算法的收斂速度和收斂精度都優(yōu)于傳統(tǒng)算法。根據(jù)表1 可以看出，改進螢火蟲算法的最小值、平均值和標準差都能達到較優(yōu)的結(jié)果，證明了非均勻自適應(yīng)步長因子的優(yōu)勢；特別是對于較復(fù)雜的多峰函數(shù)，傳統(tǒng)算法尋優(yōu)較為困難，極易陷入局部最優(yōu)，而本文提出的基于排序的螢火蟲更新策略既保證了前期的收斂步長，又防止陷入局部最優(yōu)導(dǎo)致算法無法進行。

3.2 WTA 問題仿真實驗與結(jié)果分析

為檢驗本文提出的改進螢火蟲算法求解WTA 問題的先進性，進行如下仿真實驗。設(shè)置螢火蟲數(shù)量N為40，最大迭代次數(shù)NC=200，最大吸引度β0為2，光吸收系數(shù)γ為1，步長因子α的最小值和最大值分別為0.2 和0.8，武器的種類為3，每種武器的數(shù)量為3，待打擊的目標數(shù)量為5，根據(jù)評價函數(shù)各組成部分的重要程度，同時均衡各參數(shù)的數(shù)值量級，設(shè)置懲罰因子λ1、λ2、δ分別為0.5、0.5、0.2，目標威脅值、左時間窗和右時間窗如表2所示。各武器對目標的命中概率如表3 所示。

表2 目標威脅值信息

傳統(tǒng)算法和改進螢火蟲算法的評價函數(shù)值隨迭代次數(shù)變化的曲線如圖6 所示。

圖6 傳統(tǒng)算法和改進算法評價函數(shù)值對比圖

隨機進行20 次實驗，記錄兩種算法評價函數(shù)的最大值（max）、平均值（mean）、標準差（std）和迭代次數(shù)的最小值（min）、平均值（mean）、標準差（std），結(jié)果如表4所示。

表4 傳統(tǒng)算法和改進算法的性能對比

由仿真實驗結(jié)果可知，與傳統(tǒng)螢火蟲算法相比，改進后的算法具有較強的全局搜索能力和收斂性，整體迭代次數(shù)更少，規(guī)劃的目標分配方案收益更高，充分說明了改進算法的優(yōu)越性。

4 結(jié)語

采用改進螢火蟲算法求解武器目標分配問題，為提高算法的全局搜索能力，初始化螢火蟲序列時融入PWLCM 混沌優(yōu)化策略；設(shè)計服從半高斯分布的非均勻步長因子α，以兼顧算法的收斂速度和全局搜索能力；采用螢火蟲排序策略，并融入交叉和變異更新機制，有效提高算法的搜索效率。仿真實驗表明：改進后的算法改善了傳統(tǒng)算法易陷入局部極值的缺點，具有較高的收斂速度和精度，提高了武器目標分配的效果。