基于信息素啟發狼群算法的UAV集群火力分配

劉森琪，王鴻，于寧宇，郝禮楷

（中國人民解放軍66133部隊，北京100041）

隨著無人機（Unmanned Aerial Vehicle，UAV）技術和人工智能的快速發展，利用大量具有自主作戰能力且成本低廉的UAV組成UAV集群突破對手防御體系，對目標實施飽和打擊以及對入侵機群進行空中攔截是UAV集群作戰的重要手段［1-2］。美軍已經開展了多項關于UAV集群研究及試驗驗證，并將UAV“蜂群”戰術進一步向實戰推進［3］。UAV集群作戰系統在高對抗的戰場環境中，如何充分發揮整體協調優勢，高效合理進行攻擊火力資源規劃，實現多個作戰單元協同攻擊，同時盡可能減少作戰單元消耗，使得作戰效能最佳，是UAV集群遂行作戰任務需要研究解決的重要問題。火力分配問題，即武器-目標分配（Weapon-Target Assignment，WTA）問題，歷來是作戰指揮輔助決策研究中的核心內容之一，其解空間隨著武器數目和目標總數的增加而呈指數級遞增，是多參數、多約束的離散非確定性多項式完全問題［4］。求解火力資源分配問題的算法，分為傳統算法和智能優化算法。傳統算法如文獻［5］采用線性規劃解決了艦空火力分配問題，其他算法還包括分支定界法、動態規劃法等；智能優化算法如文獻［6-7］分別采用改進的遺傳算法，文獻［8-9］采用蟻群算法，文獻［10］提出了自適應灰狼優化算法；混合優化策略如文獻［11-12］以粒子群算法為基礎分別混合模擬退火、引力搜索算法，文獻［13］以自適應蟻群優化（ACO）算法為基礎結合了遺傳算法和粒子群算法特點設計了融合算法，文獻［14］采用了動態差分改進的蝙蝠算法等。這些算法都能夠獲得滿意解，但不同程度存在以下缺陷：易早熟、進化速度慢或者算法設計實現困難。在實際允許的時間內求解其最優解是不現實的，只能根據假設的作戰原則求其滿意解。

狼群算法（Wolf Pack Algorithm，WPA）作為群體智能優化算法［15］，已成功在高維復雜函數優化、背包問題［16-17］、無人機航跡規劃［18］等優化問題領域得到了很好的應用，但文獻［19-20］指出了WPA還存在尋優精度較低、易陷局部最優、效率不高的弊端，并進行了有效改進。WPA在搜索能力方面還存在上升空間，本文引入了蟻群算法［21-22］中信息素啟發規則改進WPA，針對游走行為中人工狼的更新規則，提出使用信息素引導搜索過程，通過不斷更新信息素形成狼群對歷次捕獵的“記憶”，并應用于狼群更新機制，以改善算法的全局搜索能力。本文將這種新的信息素啟發狼群算法（Pheromone Heuristic Wolf Pack Algorithm，PHWPA）應用于UAV集進攻中的火力分配問題，構建了問題的數學模型，進而給出了算法實現過程，并通過仿真實驗驗證了該方法的可行性及有效性。

1 構建火力分配數學模型

UAV集群在進攻作戰中突出系統整體優勢，可根據目標情況進行調整，快速適應任務要求，進而協同作戰，以較少的消耗達成作戰目的。假設UAV集群作戰攻擊多個目標的具體場景如下：

所有v型UAV對第g個目標的綜合殺傷概率Pg為

火力分配是以UAV集群作戰系統的整體作戰效能最優為目標的，即在保證任務完成的情況下，消耗較少的UAV作戰單元，使得攻擊后的目標價值收益F最大。本文采用了帶有殺傷概率門限的火力分配數學模型［11］。

模型約束條件包括：

1）任務完成約束。每個目標至少分配1架UAV對其進行攻擊。

式中：Ag為第g個目標分配的UAV總數。

2）有效殺傷約束。該約束條件要求對每個目標的綜合殺傷概率大于預設的殺傷概率門限。

式中：Pdg為第g個目標的預設殺傷門限，可根據具體情況指定。

3）攻擊消耗約束。用于攻擊的任何一型UAV不能超過其數量限制。

整個模型的特征如下：

1）保證每個目標均能被有效殺傷。通過衡量目標綜合殺傷概率是否超過預設殺傷概率門限，判定目標是否被有效殺傷，若低于預設殺傷概率門限，則認為對目標的分配為無效分配。

2）目標價值Wg可以保證高價值目標被優先分配。

3）Ag的大小比pzg對Pg值的影響更大，Ag值越小，綜合殺傷概率的平均值就越大，所以模型可以保證使用較少的UAV火力單元。

4）Pg保證目標g在分配UAV火力單元目相同的情況下，即Ag相同，選擇Pg大的UAV組合，使綜合殺傷概率盡可能大。

上述模型帶有非線性約束，采用罰函數法將其轉化為一個無約束優化問題來求解。該問題屬于非線性整數規劃問題，這里采用PHWPA進行解決。

2 算法實現

2.1 狼群算法

狼群組織嚴密，分工明確，通過各自履行責任進而完成共同協作，保證狼群的生存和發展。WPA模擬狼群分工協作式捕獵行為、獵物分配規則，通過狼群個體對獵物氣味、環境信息的探知、人工狼群相互間信息的共享和交互以及人工狼基于自身職責的個體行為決策最終實現了狼群捕獵的全過程，相互關系如圖1所示［15］。

圖1 狼群的捕獵模型Fig.1 Hunting model of wolf pack

根據狼群特征，WPA采用基于人工狼主體的自下而上的設計方法和基于職責分工的協作搜索路徑結構，將人工狼區分為頭狼、探狼、猛狼，整個捕獵過程抽象為游走、召喚、圍攻3種智能行為以及“勝者為王”的頭狼產生規則和“強者生存”的狼群更新機制，相關含義參見文獻［15］。

2.2 求解火力分配問題的W PA

圍繞火力分配模型，首先進行了火力分配問題的算法描述，并借鑒文獻［17］中運動算子設計方法，重新設計了游走、召喚2個算子改進WPA，以便于問題的求解；進而給出了頭狼產生規則、游走行為、召喚行為、圍攻行為、狼群更新機制等智能行為的詳細描述以及新算子在具體智能行為中的應用。

在解決WTA問題中采用了基于整數的編碼方式，分配方案X=（x1，x2，…，xj，…，xm），變量xj為0～n之間的整數，xj=t表示將第j架UAV分配給第t個目標；xj=0表示第j架UAV沒有分配給任一目標［6］。用人工狼的位置代表一種候選分配方案，設人工狼位置矢量維度為m（UAV總數量），N為人工狼總數，在N×m的歐式空間中人工狼i的位置X=（xi1，xi2，…，xij，…，xim），xij為第i（i=1，2，…，N）匹人工狼在第j（j=1，2，…，m）維變量空間中所處的位置。人工狼感知到的獵物氣味濃度Y=f（X），即目標函數值；人工狼p與人工狼q之間距離dpq為兩者位置編碼的Manhattan距離：

定義1游走算子Ω（Xi，Ma，r），人工狼i的位置為Xi=（xi1，xi2，…，xij，…，xim），Ma= ｛1，2，…，m｝為編碼位集合，可理解為人工狼的可活動范圍，r為進行改變的編碼位的數目，可理解為人工狼的游走步長。游走算子表示在Ma中隨機選擇r個編碼位形成集合R，將xij（j∈R）改變為第j維變量空間中選取的隨機數。

定義2召喚算子Ψ（Xi，Mb，r），人工狼i的位置為Xi=（xi1，xi2，…，xij，…，xim），Mb為人工狼位置Xi和頭狼位置Xd不相同編碼位的集合且不為空集，集合Mb為

式中：j=1，2，…，m；k的初值為1；null表示空值；xdj表示頭狼位置第j維取值。召喚算子Ψ 為在Mb中隨機選擇r個編碼位形成集合R，并將xij值按式（9）進行改變，可理解為人工狼i接收到了頭狼傳遞的部分信息。

WPA的規則和智能行為［15-17］如下：

1）頭狼產生規則。算法中具有最優目標函數值的人工狼為頭狼，迭代過程中根據目標函數進行頭狼更替，頭狼不執行游走、召喚、圍攻行為。

4）圍攻行為。將頭狼所在位置Xd視為獵物的位置，參與圍攻的人工狼i的位置Xi依式（10）進行位置變換得到新位置：比較人工狼實施圍攻行為前后在新舊位置所感知到的獵物氣味濃度并進行貪婪決策。

上述智能行為所涉及的游走步長stepa、奔襲步長stepb、圍攻步長stepc皆為整數，表示人工狼搜索的精細程度。

5）狼群更新機制。按照狼群更新機制進行群體更新，即淘汰Nnew匹人工狼，Nnew為［N/（2U），N/U］之間的隨機整數，U為更新比例因子。算法模擬自然界狼群繁衍方式，新人工狼作為頭狼子女繼承頭狼的優良基因，即頭狼的部分編碼位，新的人工狼位置Xnew由式（11）計算得到：

式中：Xd為頭狼所在位置；Ma=｛1，2，…，m｝；編碼位改變的數目L由式（12）計算得到：

2.3 蟻群算法中的信息素啟發規則

蟻群算法模擬自然界中蟻群覓食機制，采用了分布式正反饋并行計算機制［21-22］。WTA問題中螞蟻各自構建其目標分配方案，螞蟻從第1架UAV開始在所有目標中選擇一個目標分配給該UAV；接著對第2架UAV，螞蟻s在當前運行分配的目標集合中選擇一個目標分配給該UAV；依此順序分配，指導完成全部目標分配［8］。算法中信息素啟發的具體規則如下：

1）狀態轉移規則。螞蟻s依據偽隨機規則選擇目標g分配給第u架UAV。

式中：τut（k）為k時第u架UAV與目標t之間的信息素，k即迭代次數；ηut為與問題相關的啟發信息，在火力分配問題中，ηut根據數學模型的最優準則給定，本文設為第u架UAV對目標t單次殺傷概率與目標t價值的積；α和β分別為τut和ηut的相對重要性；q為0～1之間均勻分布的隨機數；q0（0≤q0≤1）為一個指定常數；G為依據如下隨機比例規則從alloweds中選擇一個目標。

式中：alloweds為螞蟻s當前可分配的目標集；ηug為第u架UAV對目標g單次殺傷概率與目標g價值的積；τug（k）為k時第u架UAV與目標g之間的信息素。

2）信息素更新規則。當一次迭代過程結束后，根據當前最優目標函數值Fmax及其對應解Xbest，按式（15）全局更新規則對信息素進行調整：

式中：Δτug為第u架UAV選擇目標g相應信息素增量；ρ為信息素揮發因子，0＜ρ＜1。

式中：Q為信息素強度，是一個常數；Fmax（k）為第k次迭代目標函數最優值；Xbest（k）為對應的最優解。

2.4 算法改進策略

為強化對解空間的學習，避免陷入局部最優，提高算法尋優效率，在求解火力分配的WPA基礎上提出了PHWPA，針對WPA的游走行為和更新機制做出如下改進：

1）在人工狼搜索過程中，增加信息素引導，可以理解為狼群搜捕獵物的過程形成了一定記憶。在游走行為中，對人工狼位置執行游走算子時，相應編碼位由選取隨機數改為按照式（13）、式（14）選取新位置。

2）在更新狼群過程中使用信息素，這一過程可以理解為：一方面新的人工狼繼承了頭狼的優良基因，另一方面采用信息素引導使新的人工狼傳承了整個狼群在捕獵中形成的“智慧”，符合自然界種群繁衍進化的特點。在狼群更新機制中，新人工狼按照式（12）產生時，同樣其編碼位按照式（13）、式（14）計算其改變值。

信息素更新的時機選擇在每次迭代時狼群完成圍獵之后、更新狼群之前，利用頭狼位置信息及其目標函數值按式（15）對信息素進行全局更新，不斷更新的信息素代表著狼群在整個捕獵過程中形成的捕獵“智慧”，有利于該智能優化算法對解空間進行更好的學習。

2.5 PHWPA的實現步驟

步驟1初始化。人工狼總數N，初始化每匹人工狼的位置Xi，最大迭代次數kmax，更新比例因子U，最大游走次數Tmax，各步長stepa、stepb、stepc，判定距離dnear，信息素的啟發因子α，期望啟發因子β，信息素強度Q，信息素揮發因子ρ以及常數q0，信息素初值τinitial，最大值τmax，最小值τmin。

步驟2計算各人工狼的目標函數值。選取頭狼，其余人工狼執行游走行為，利用式（13）、式（14）更新，直到某匹人工狼感知的獵物氣味濃度（目標函數值）大于頭狼感知的氣味濃度，或達到最大游走限制次數，轉入步驟3。

步驟3除頭狼外的所有人工狼執行召喚行為，向發出召喚的頭狼進行奔襲。若奔襲過程中，人工狼感知的氣味濃度大于頭狼所感知的氣味濃度，則進行頭狼更替，之后人工狼向新的頭狼位置奔襲，直到人工狼與頭狼的距離d≤dnear，轉入步驟4。

步驟4除頭狼外的所有人工狼執行圍攻行為。將頭狼所在位置視為獵物的位置，參與圍攻的人工狼位置根據式（10）進行變換并進行貪婪決策。

步驟5全局信息素更新。根據當前頭狼位置信息及其所感知的獵物氣味濃度，根據式（15）、式（16）對全局信息素進行更新。

步驟6狼群更新。按照狼群更新機制，更新Nnew匹人工狼，新人工狼變化的編碼位相應數值按照式（13）、式（14）計算得到。

步驟7判斷是否結束。判斷是否達到優化精度要求或最大迭代次數kmax，若達到則輸出頭狼的位置，即所求問題的最優解，否則轉步驟2。

綜上，可得出基于PHWPA的火力分配流程，如圖2所示。

圖2 基于PHWPA的火力分配流程Fig.2 WTA flowchart based on PHWPA

3 算法驗證及仿真

為驗證PHWPA求解火力分配問題的可行性和有效性，進行了仿真實驗，算例參考文獻［11］。

設UAV集群共有4種型號，每型4架，需要協同攻擊10個目標。UAV編號與目標標號如表1所示。

表1 無人機編號與目標編號Table 1 UAV number and target number

UAV集群中作戰單元對目標的殺傷概率矩陣為P。

各目標的殺傷概率門限Pdj均設為0.9。各目標的價值矩陣W =［0.6，0.7，0.3，0.5，0.6，0.35，0.65，0.55，0.4，0.75］。

采用本文的PHWPA、WPA、ACO算法、最大最小蟻群（MMAS）算法、模擬退火離散粒子群算法（SA-DPSO）［11］以及僅在更新狼群時使用信息素的PHWPA1、僅在探狼搜索過程使用信息素引導的PHWPA2分別對該火力分配問題進行優化求解。最大迭代次數均為100，涉及WPA的參數：狼群規模Nw=32，更新比例因子Uw=6，游走次數Tmax=10，游走步長stepa=2，奔襲步長stepb=4，圍攻步長stepc=1，判定距離dnear=2stepb；涉及ACO算法的參數：蟻群規模Na=32，α=2，β=5，Q=20，ρ=0.4，q0=0.8，信息素初始值τinitial=10，信息素最大值τmax=10，信息素最小值τmin=2。

圖3表示采用PHWPA得出的最優方案，該火力分配方案共使用4型13架UAV攻擊10個目標，具體UAV與目標對應分配情況如表2所示。表3中各目標殺傷概率均達到殺傷概率門限指標要求，方案表明在保證任務完成的情況下減少了UAV作戰單元的消耗，有利于保持UAV集群整體優勢。

圖3 無人機-目標最優分配方案Fig.3 Optimal UAV-target assignment

表2 最優攻擊分配方案Table 2 Optimal UAV-target assignment

表3 各目標殺傷概率Table 3 Kill probability of each target

圖4 各算法最優值迭代過程Fig.4 Iterative process of optimal value of each algorithm

圖5 PHWPA與其他算法迭代過程比較Fig.5 Comparison of iterative process between PHWPA and other algorithms

由圖4、圖5可看出，因為初始狼群、蟻群是隨機產生的，所以每次迭代會略有不同，為檢驗PHWPA的收斂性，并證明其有效性。對各算法分別進行了100多次仿真實驗，算法收斂趨勢基本一致，PHWPA與各算法目標函數值變化情況如圖5所示，可以看出，PHWPA能夠迅速收斂至全局最優解，并且每次仿真均可以收斂至最優解；WPA收斂至全局最優解時間較長，收斂速度相對較慢，且部分解是局部最優解；基本ACO算法收斂速度慢，且常陷入局部最優解；MMAS算法收斂趨勢與WPA 相近，且部分解為局部最優解；SA-DPSO算法能夠穩定收斂，但常陷入局部最優解；PHWPA1、PHWPA2收斂趨勢與PHWPA較為接近，但實驗中這2種算法也存在收斂速度慢、陷入局部最優解的情況，不如PHWPA收斂情況穩定。因此，本文提出的PHWPA能夠有效提高對全局最優解的尋優效率。

4 結 論

UAV集群作戰是UAV自主作戰發展的必然趨勢，戰場環境下UAV集群協同攻擊多目標的火力分配問題研究具有重要意義。

1）針對UAV集群進攻作戰火力分配問題進行了研究，主要考慮達成有效殺傷目的、同時節約UAV火力資源且滿足任務約束等要求，建立了合理的火力分配數學模型。

2）在使用WPA進行模型求解中，重新設計了游走、召喚算子，并在智能行為中描述新算子的具體應用。

3）針對WPA在解決火力分配問題時易陷入局部最優解的問題，提出了PHWPA，引入ACO算法中信息素啟發機制，強化了人工狼群對搜索空間的認知，對狼群算法搜索環節進行啟發式引導，賦予了人工狼群“記憶”，在人工狼群更新環節引入信息素啟發，繼承了狼群的捕獵“智慧”，提升了狼群算法的搜索效率。

仿真結果表明，該優化算法是快速且有效的，在尋優精度和穩定上都有較好的表現，為研究UAV集群作戰系統火力分配問題提供了一種新的解決方案。