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

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

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

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

1 構建火力分配數(shù)學模型

UAV集群在進攻作戰(zhàn)中突出系統(tǒng)整體優(yōu)勢，可根據(jù)目標情況進行調整，快速適應任務要求，進而協(xié)同作戰(zhàn)，以較少的消耗達成作戰(zhàn)目的。假設UAV集群作戰(zhàn)攻擊多個目標的具體場景如下：

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

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

模型約束條件包括：

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

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

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

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

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

整個模型的特征如下：

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

2）目標價值Wg可以保證高價值目標被優(yōu)先分配。

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

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

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

2 算法實現(xiàn)

2.1 狼群算法

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

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

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

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

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

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

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

定義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的規(guī)則和智能行為［15-17］如下：

1）頭狼產生規(guī)則。算法中具有最優(yōu)目標函數(shù)值的人工狼為頭狼，迭代過程中根據(jù)目標函數(shù)進行頭狼更替，頭狼不執(zhí)行游走、召喚、圍攻行為。

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

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

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

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

2.3 蟻群算法中的信息素啟發(fā)規(guī)則

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

1）狀態(tài)轉移規(guī)則。螞蟻s依據(jù)偽隨機規(guī)則選擇目標g分配給第u架UAV。

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

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

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

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

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

2.4 算法改進策略

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

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

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

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

2.5 PHWPA的實現(xiàn)步驟

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

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

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

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

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

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

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

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

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

3 算法驗證及仿真

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

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

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

UAV集群中作戰(zhàn)單元對目標的殺傷概率矩陣為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分別對該火力分配問題進行優(yōu)化求解。最大迭代次數(shù)均為100，涉及WPA的參數(shù)：狼群規(guī)模Nw=32，更新比例因子Uw=6，游走次數(shù)Tmax=10，游走步長stepa=2，奔襲步長stepb=4，圍攻步長stepc=1，判定距離dnear=2stepb；涉及ACO算法的參數(shù)：蟻群規(guī)模Na=32，α=2，β=5，Q=20，ρ=0.4，q0=0.8，信息素初始值τinitial=10，信息素最大值τmax=10，信息素最小值τmin=2。

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

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

表2 最優(yōu)攻擊分配方案Table 2 Optimal UAV-target assignment

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

圖4 各算法最優(yōu)值迭代過程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與各算法目標函數(shù)值變化情況如圖5所示，可以看出，PHWPA能夠迅速收斂至全局最優(yōu)解，并且每次仿真均可以收斂至最優(yōu)解；WPA收斂至全局最優(yōu)解時間較長，收斂速度相對較慢，且部分解是局部最優(yōu)解；基本ACO算法收斂速度慢，且常陷入局部最優(yōu)解；MMAS算法收斂趨勢與WPA 相近，且部分解為局部最優(yōu)解；SA-DPSO算法能夠穩(wěn)定收斂，但常陷入局部最優(yōu)解；PHWPA1、PHWPA2收斂趨勢與PHWPA較為接近，但實驗中這2種算法也存在收斂速度慢、陷入局部最優(yōu)解的情況，不如PHWPA收斂情況穩(wěn)定。因此，本文提出的PHWPA能夠有效提高對全局最優(yōu)解的尋優(yōu)效率。

4 結 論

UAV集群作戰(zhàn)是UAV自主作戰(zhàn)發(fā)展的必然趨勢，戰(zhàn)場環(huán)境下UAV集群協(xié)同攻擊多目標的火力分配問題研究具有重要意義。

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

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

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

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