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

趙冬梅，李玲，宋陽

（海軍大連艦艇學院 基礎部，遼寧 大連 116018）

0 引言

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

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

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

1 武器目標分配問題建模

1.1 問題描述

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

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

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

1.2 約束條件

1）時間窗約束

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

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

2）武器數量約束

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

3）目標承受武器數量約束

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

1.3 編碼與解碼

考慮武器數量約束條件，設置編碼序列的維度為武器的總數D，D=，Si為第i種武器的數量。為體現武器目標分配方案，設置每一維序列代表相應武器攻擊的目標編號，例如武器W1、W2、W3、W4的數量分別為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目標數之間的整數，0 表示不分配該武器執行任務，當算法迭代出現非整數時，需要對其進行取整處理。

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

1.4 武器目標分配評價函數

武器目標分配問題的研究內容是如何分配武器使作戰任務效益最大化，常規的任務效益模型[18]如式（5）所示：

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

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

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

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

2.1 螢火蟲算法原理

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

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

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

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

式中β0為最大吸引度。

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

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

2.2 混沌初始化螢火蟲

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

式中：l為迭代次數，l=1 時隨機產生初始值k(1)，經循環迭代得到[0，1]的隨機序列；p為混沌映射的控制參數，在[0，1]內取值。

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

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

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

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

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

2.3 非均勻步長因子

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

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

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

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

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

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

2）選擇隨機螢火蟲的兩個交叉位置，將兩位置之間的片段用“最優”螢火蟲相應位置之間的片段替換，產生“交叉”螢火蟲；

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

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

2.5 算法流程

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

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

3 仿真實驗與結果分析

3.1 算法分析與對比

3.1.1 實驗測試函數

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

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

3.1.2 實驗設置

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

3.1.3 實驗結果與分析

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

表1 改進螢火蟲算法對4 個測試函數的優化結果

圖2 Sphere 函數最優解及收斂曲線對比圖

圖3 Rosenbrock 函數最優解及收斂曲線對比圖

圖4 Griewank 函數最優解及收斂曲線對比圖

圖5 Rastrigin 函數最優解及收斂曲線對比圖

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

3.2 WTA 問題仿真實驗與結果分析

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

表2 目標威脅值信息

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

圖6 傳統算法和改進算法評價函數值對比圖

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

表4 傳統算法和改進算法的性能對比

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

4 結語

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