基于匈牙利-模擬退火算法的多階段武器目標分配方法

常雪凝, 石建邁, 陳 超, 黃金才

(國防科技大學系統(tǒng)工程學院, 湖南 長沙 410003)

0 引 言

隨著自控技術(shù)、信息技術(shù)以及人工智能等技術(shù)的發(fā)展,以導彈為代表的精確制導武器裝備朝著精確化、智能化的方向變革,推動了信息化、智能化、無人化戰(zhàn)爭的進程[1-2]。在俄羅斯攻打烏克蘭的戰(zhàn)役中,遠程精確制導武器在戰(zhàn)場上發(fā)揮了重要的作用。精確制導武器作為一種典型的信息化武器[3],可以遠距離快速識別、命中并摧毀敵方目標,將軍事沖突限制在一個特定的區(qū)域,大大減少了戰(zhàn)場人員傷亡和財產(chǎn)損失,是快速摧毀敵軍重要設施、贏得局部作戰(zhàn)勝利的主要方式。然而,遠程精確制導武器也存在一些短板,首先是成本極高,從裝備到升級以及武器本身的花費都遠超常規(guī)武器系統(tǒng)[4]。其次是武器發(fā)射平臺數(shù)量有限,受到成本、技術(shù)和人員等限制,遠程精確制導系統(tǒng)的發(fā)射平臺數(shù)量有限,因此同一波次發(fā)射的武器數(shù)量也是有限的。面對大量需要攔截和打擊的目標群時,需要將作戰(zhàn)過程合理劃分為多個階段,利用有限的發(fā)射平臺將武器分配到目標,實現(xiàn)最佳的打擊效果。

為了提高遠程精確打擊的作戰(zhàn)效益,需要在改進武器裝備的同時,對智能指揮作戰(zhàn)系統(tǒng),尤其是武器分配方法進行重點研究[5]。武器目標分配(weapon target assignment, WTA)問題是軍事運籌領域的重要研究方向之一,是解決如何將多種作戰(zhàn)武器,分配給多個打擊目標,來最優(yōu)地實現(xiàn)指揮員的作戰(zhàn)意圖,也是指揮控制自動化、智能化需要解決的關(guān)鍵問題之一。作為WTA問題的一種重要擴展方向,多階段WTA(multi-stage WTA, MS-WTA)是在有限的武器通道和武器數(shù)量的約束下,對多元立體的打擊目標加以評估,依據(jù)重要性與緊急程度劃分階段,通過規(guī)劃各階段打擊目標清單緩解同波次武器攻擊的壓力,快速制定WTA方案。文獻[6]認為在作戰(zhàn)規(guī)劃過程中,“能力需求”會改變,WTA效益必然也相應發(fā)生變化。因此,研究高實時性的MS-WTA方法,已經(jīng)成為戰(zhàn)場火力分配研究的重點。

Flood[7]在普林斯頓大學線性規(guī)劃會議上首次提出目標分配模型,在軍事運籌領域引起了廣泛關(guān)注與研究。在WTA數(shù)學模型方面,Manne[8]首次建立了混合整數(shù)非線性規(guī)劃模型。Lloyd等[9]證明了WTA是非確定性多項式(nondeterministic polynomially, NP-hard)的,即在多項式時間內(nèi)是不可解的。因此,在不對模型進行轉(zhuǎn)化的情況下,很難做到使用精確求解技術(shù)來求解WTA大規(guī)模算例。Dirik等[10]提出了一種兩階段混合線性規(guī)劃建模方法來解決戰(zhàn)斗機WTA問題。Han等[11]建立了三階段(防御方-攻擊方-防御方)的完全信息零和博弈模型。Peng等[12]基于目標毀傷概率區(qū)間和時間窗約束,提出了一種新的協(xié)同空戰(zhàn)動態(tài)WTA多目標整數(shù)優(yōu)化模型。陸一平等[13]通過限定對目標分配武器的數(shù)量來降低整數(shù)線性規(guī)劃模型的維數(shù),提高問題的求解效率。針對多個武器攔截多個目標問題,Stieber等[14]將該問題近似為帶移動目標的多旅行商問題,建立了一個整數(shù)線性規(guī)劃模型。Guo等[15]則提出使用固定和自適應的分組策略來確保每個目標都能分配到適當?shù)臄r截資源,并使用罰函數(shù)將多約束優(yōu)化轉(zhuǎn)化為無約束優(yōu)化問題。Lu等[16]將WTA問題轉(zhuǎn)化為一個具有二進制列的線性整數(shù)規(guī)劃模型,實現(xiàn)了大規(guī)模WTA的求解。此外,更復雜的、更切合實際應用的WTA場景也被考慮。Xin等[17-19]提出了傳感器協(xié)同分配的WTA問題,Li等[20-21]提出使用多目標進化算法(multi-objective evolutionary algorithm, MOEA)來解決多目標WTA問題。

WTA問題是一個多參數(shù)、多約束的NP-complete問題,解空間往往是不可微、不連續(xù)以及高度非線性的。目前,WTA的求解方法可以分為兩類,第一類使用精確求解技術(shù),如分支定界法、拉格朗日松弛方法和匈牙利方法等[22-24],直接求解混合整數(shù)非線性形式的WTA問題。Kline等[23]設計了一種基于深度優(yōu)先搜索的分支定界算法,解決了較小規(guī)模的非線性整數(shù)規(guī)劃WTA問題。Chopra等[25-26]在匈牙利方法的基礎上提出“加邊補零”的擴增方法來統(tǒng)一效率矩陣,實現(xiàn)了小規(guī)模WTA問題的快速求解。郭斐然等[27]提出使用層次分析技術(shù)和匈牙利算法解決了不同類型部件和裝備體系的配對問題。為了找到大規(guī)模WTA的精確解,可通過一些假設和模型轉(zhuǎn)換適當?shù)睾喕瘑栴}。例如,Lu等[16]建立了一種線性規(guī)劃WTA模型,采用列生成和分支定界結(jié)合的方法有效解決了大規(guī)模WTA問題。第二類求解技術(shù)是基于啟發(fā)式方法,通過適當降低解的質(zhì)量來實現(xiàn)大規(guī)模WTA問題的快速求解。Lee等[28]提出將領域知識融入遺傳算法的交叉和變異過程,用于求解中等規(guī)模的WTA問題。Xin等[29]設計了一種基于規(guī)則的啟發(fā)式構(gòu)造算法求解動態(tài)WTA問題,通過動態(tài)驗證約束是否飽和來生成可行解。Liang等[30]實現(xiàn)了自適應混沌并行克隆選擇算法求解艦艇編隊防空WTA問題。Sonuc等[31]提出了并行模擬退火算法求解大規(guī)模WTA的問題。Zhang等[19]建立了一種基于滾動時域分解策略模型,設計了一種基于統(tǒng)計邊際收益的啟發(fā)式算法,實現(xiàn)了基于資產(chǎn)的動態(tài)WTA問題的求解。

綜上所述,WTA問題經(jīng)過幾十年的發(fā)展,在模型、求解算法以及應用場景方面都取得了大量研究成果,以靜態(tài)WTA和動態(tài)WTA為基礎不斷發(fā)展,但是現(xiàn)有的研究很少關(guān)注MS-WTA問題。在實際的應用中,由于武器發(fā)射平臺不足以及武器存在轉(zhuǎn)火時間的原因,無法一次性完成對所有目標的打擊任務,必須將作戰(zhàn)劃分為多個階段,制定出整體效益最大化的火力打擊計劃。此外,對于大規(guī)模的WTA問題,大多數(shù)精確算法不能在有效時間給出解決方案或者解決方案質(zhì)量較低[32]。啟發(fā)式方法雖然通過降低解的質(zhì)量來實現(xiàn)快速求解,但是不可避免地出現(xiàn)過早收斂、解的質(zhì)量穩(wěn)定性差等問題。因此,在精確打擊的背景下,本文立足于一般形式的WTA問題,考慮階段間分配方案的相互影響,提出一種啟發(fā)式和精確式算法結(jié)合的MS-WTA算法,最大化整體打擊效能。

1 問題分析與建模

MS-WTA問題屬于經(jīng)典WTA問題的擴展。考慮到遠程精確制導裝備在單波次攻擊中武器發(fā)射數(shù)量有限,當目標數(shù)量龐大時,只有主動地將打擊過程分成多個階段來分配武器,才能發(fā)揮精導武器的最大作戰(zhàn)效益。MS-WTA問題假定需要在較短時間內(nèi)完成對敵軍的n個目標的摧毀任務,目標j的威脅程度記為Vj,其中j∈N={1,2,…,n};現(xiàn)有武器發(fā)射平臺M個,每個平臺在一個階段至多可以發(fā)射1個武器;整個打擊過程劃分為w個階段,一枚武器僅能攻擊一個目標。其中,建模過程中采用的參數(shù)與變量如表1所示。

表1 參數(shù)與變量符號說明

在精確制導武器多階段打擊的背景下,給出以下設定。

(1) 每一個目標僅被一枚武器的攻擊,打擊目標體積大或者防御性過強時,通過增設虛擬目標來拆分原目標以及相關(guān)參數(shù)。

(2) 一個武器在一個階段只能攻擊一個目標,并且武器在完成發(fā)射之后,僅追蹤與打擊預設的目標。

對于一個初始目標集合N,需要經(jīng)過信息評估后將所有目標分配到s個集合,任意一個階段的待打擊目標集合用Nt表示。在本問題中,Nt的目標類型和數(shù)量是可變的,以目標j和目標k為例(其中j∈Nt,k∈Nt-1),當目標j經(jīng)過評估是可松弛的,即松馳系數(shù)(relaxation coefficient, RC)為1,那么其可以向相鄰的后續(xù)階段調(diào)整,與相鄰的后續(xù)階段的某個目標k交換打擊次序;階段調(diào)整完成后,目標j被標記為不可松弛的,并且此時j∈Nt-1。相應地,目標k向前一個階段調(diào)整,且無論之前評估信息如何,由于當前所屬階段處于較早的攻擊波次,可以對其進行可松弛標記,即RC=1,此時k∈Nt。階段調(diào)整完成后,目標的打擊階段被確定,可以在此基礎上進行WTA以找到局部最優(yōu)解。

從攻擊方角度,旨在降低敵方目標的威脅程度,當武器被分配給目標并完成打擊任務時,敵方的總體威脅越小越好。因此,MS-WTA問題以最小化敵方目標的總體期望威脅值作為優(yōu)化目標,計算統(tǒng)一效率矩陣,具體數(shù)學模型如下:

(1)

(2)

(3)

xtij∈{0,1}, ?t∈S;i∈W;j∈N

(4)

模型中,式(1)為目標函數(shù),目標威脅值將會根據(jù)武器毀傷概率大小非線性降低。式(2)～式(4)為約束條件,其中式(2)約束了在每一個攻擊階段,目標j只能被一個武器打擊;式(3)約束了一個武器最多追蹤并襲擊一個目標。在式(2)和式(3)的約束下,每一個階段發(fā)射的武器數(shù)量等于需要打擊的目標數(shù)量。當所有目標的初始攻擊階段被確定下來,指揮員需要優(yōu)化武器和目標之間的分配關(guān)系來實現(xiàn)作戰(zhàn)效能的最大化,式(4)是0-1決策變量約束。

2 基于匈牙利-模擬退火的雙層搜索算法

為了解決MS-WTA問題,基于匈牙利算法和模擬退火算法,設計了一種雙層搜索算法,簡稱為匈牙利模擬退火(Hungarian simulated annealing, HSA)算法。首先,根據(jù)目標的重要性與緊急程度確定目標的初始攻擊階段,再利用精確制導武器典型打擊場景中目標一對一精準打擊情況下的應用特點,使用匈牙利算法計算MS-WTA問題的初始解。隨后,在模擬退火算法框架下,調(diào)用階段調(diào)整算子重新對目標的攻擊波次進行調(diào)整,并再次調(diào)用匈牙利算法求解當前狀態(tài)下的局部最優(yōu)解,在退火降溫過程中利用概率突跳重新對目標的攻擊波次進行調(diào)整,重復循環(huán)這一過程,直至滿足停止準則,得到高質(zhì)量打擊方案。基于HSA的雙層搜索算法的主要流程如算法1所示。

算法 1 HSA算法步驟 1 參數(shù)初始化;步驟 2 基于一定的規(guī)則構(gòu)造多階段目標攻擊初始序列F={F1,F2,…,Fs};步驟 3 在初始序列F的基礎上,標記各目標松弛系數(shù)rj;步驟 4 調(diào)用匈牙利算法求解MS-WTA的局部最優(yōu)解F*={F*1,F*2,…,F*s};步驟 5 計算目標函數(shù)值;步驟 6 在局部最優(yōu)解F*的基礎上,根據(jù)松弛系數(shù)調(diào)整準則改變目標打擊階段,構(gòu)造新序列F;步驟 7 依據(jù)一定的概率準則更新RC值;步驟 8 重復步驟4和步驟5;步驟 9 調(diào)用模擬退火算法轉(zhuǎn)到步驟6^步驟8;步驟 10 直至到達算法終止準則,解算出全局最優(yōu)解。

2.1 RC調(diào)整準則

RC是調(diào)整目標打擊階段的重要數(shù)值標記,同時也能反映出目標重要性。目標j的RC記為rj,給予緊迫性強、優(yōu)先級高的目標RC值為rj=0,反之為1。在后續(xù)的WTA過程中,RC值決定了該目標是否可以調(diào)整打擊階段以產(chǎn)生更優(yōu)的打擊方案。使用RC準則來調(diào)整打擊階段,需要遵循如下幾條規(guī)則。

(1) 目標優(yōu)先級越高,打擊階段越靠前

在預分配階段,進行初始目標劃分和標記時,目標的重要性越強,優(yōu)先級越高,相應的初始打擊階段越靠前。對同波次目標來說,RC標記能反映出目標的相對重要性,rj=0代表目標處于重要而緊迫的地位。比如,敵方指揮機構(gòu)和預警探測類目標(如雷達站)相對于防御工事和保障部隊等具有更優(yōu)先的打擊次序,應當分配到較早的波次中,若兩者可以在同一階段被打擊則可以通過RC值來標記相對重要性。

(2) 目標只能向相鄰階段進行調(diào)整

對當前目標進行階段調(diào)整時,只能選擇相鄰的階段進行改變。本文提出的算法每次以隨機的方式選擇相鄰的任務集合,再以同進同出的方式交換兩個目標的打擊階段。如圖1所示,不允許交換第1和第3階段的目標(對應圖1序號③)。因為較早階段的目標本身具有很強的優(yōu)先級,跨階段調(diào)整違背了“目標優(yōu)先級越高,打擊次序越靠前”的原則。

圖1 RC更新

(3) RC值的更新方法

選定兩個階段的目標集合后,后續(xù)階段的目標可以無條件向前一階段遷移,遷移完成后RC值更新為1;但是對于前階段目標,只有RC值為1時才可以向臨近的后續(xù)階段遷移,同時RC值更新為0,意味著盡管該目標在原先階段優(yōu)先級并不大,可以向后調(diào)整,但是仍然有很重要的地位,不允許繼續(xù)向后續(xù)階段繼續(xù)調(diào)整。

2.2 HSA算法

2.2.1 匈牙利算法

WTA問題與傳統(tǒng)運籌學中的指派問題有很多相似之處,當規(guī)定武器對目標實施一對一精準打擊時,兩者的數(shù)學模型擁有相似的形式,如式(1)～式(3)。匈牙利算法是Kuhn在1955年利用匈牙利數(shù)學家K?nig提出的獨立零元素定理構(gòu)造求解方法,被認為是指派問題標準的解法,具有求解速度快、解的質(zhì)量穩(wěn)定的特點[23]。當武器和目標數(shù)量相等時,可以構(gòu)建標準的效率矩陣,借助于獨立零元素定理,對矩陣做有限步數(shù)的初等變化即可求出問題的精確解。近年來,隨著對匈牙利算法和WTA問題的深入研究,武器與目標已經(jīng)不局限于一對一形式,這意味著本文提出的混合算法在改進匈牙利算法之后能夠解決更一般情形下的MS-WTA問題。

本文選擇匈牙利算法作為初始解的生成策略,當所有階段的待打擊目標集合生成后,從武器庫中選擇一定數(shù)量的武器,計算統(tǒng)一效率矩陣,調(diào)用匈牙利算法計算當前打擊次序下的局部最優(yōu)解,然后作為初始解傳入模擬退火算法。

2.2.2 模擬退火算法

模擬退火算法的設計借鑒了蒙特卡羅抽樣思想和自然界中固體“退火”現(xiàn)象,常被用作求解組合優(yōu)化問題,在解空間中尋找近似全局最優(yōu)解[33]。在MS-WTA研究中,目標函數(shù)可以認為是固體的內(nèi)能,在高溫情況下算法在內(nèi)部迭代中可以以較高概率接受差解,隨著溫度下降、算法逐漸趨于穩(wěn)態(tài),直至到達停止準則,找到問題的近似最優(yōu)解。本文使用該算法求解MS-WTA問題的流程如算法2所示。

算法 2 模擬退火算法輸入: 初始解s0,初始目標函數(shù)值f0輸出: 全局最優(yōu)解和最優(yōu)目標函數(shù)值sg,fg1 參數(shù)初始化:T0、Tk、Tf、Δd、ψ2 while T>Tk do3 for i in range (1,ψ) do4 調(diào)用階段調(diào)整算子獲取新解stemp5 if failflag=0 then6 基于HA計算局部最優(yōu)解Snew,fnew7 if Metrospoli’s mark=1 then8 更新松弛系數(shù)值RC9 S0←snew; f0←fnew10 end if11 end if12 end for13 if f0

在模擬退火的框架下,通過隨機方式選擇相鄰兩個階段,通過實現(xiàn)階段間機動性強的目標的波次改變來調(diào)整各階段打擊順序。本文設計了兩交換(點式)階段調(diào)整算子和段式調(diào)整算子。其中,點式階段調(diào)整算子用于小規(guī)模WTA的最優(yōu)解搜索,而段式調(diào)整算子通過批量式交換打擊階段,實現(xiàn)原打擊序列的大范圍調(diào)整。本文使用的階段調(diào)整算子的流程如算法3所示。

算法 3 目標的階段調(diào)整算法輸入: 初始目標打擊序列F輸出: 新的目標打擊序列F', 階段調(diào)整成功參數(shù)failflag參數(shù)初始化:recycleflag,counter=0,failflag=0根據(jù)所求解問題的規(guī)模選擇階段調(diào)整算子,隨機地選擇相鄰的階段(Nt,Nt+1)While recycleflag=1 do在Nt中隨機選擇可交換的目標g1基于RC調(diào)整準則判斷可行性if RC(g1)=1 dorecycleflag=0elif counter 超出武器超出目標數(shù)量dofailflag=0breakend whileif failflag=0 do在Nt+1中隨機選擇相等數(shù)量的目標g2產(chǎn)生并輸出新序列F',否則輸出F

(1) 兩交換階段調(diào)整算子

將WTA分成s個階段,算法將從s-1對相鄰階段中選取階段調(diào)整的對象。該過程如圖2所示,從第t階段的可松弛目標集合中隨機選取交換的對象,同時從第t+1階段任意選擇目標,兩兩交換完成階段的調(diào)整。該算子適用于小規(guī)模WTA,通過小的擾動搜索出高質(zhì)量目標階段分配。

圖2 兩交換階段調(diào)整算子

(2) 段式階段調(diào)整算子

段式階段調(diào)整算子同樣以隨機方式選取相鄰階段的目標集合,但是兩階段目標的交換不再是“點對點”的小規(guī)模改變。如圖3所示,首先在第t階段的目標序列中選取一個固定長度的目標片段,同時在第t+1個階段中選取任意一個等長目標序列,交換打擊的階段,最后根據(jù)RC調(diào)整準則檢查不合法的目標對,不改變原先的打擊次序。大范圍調(diào)整目標的打擊次序的方式適合大規(guī)模WTA,能夠劇烈地改變原先目標的攻擊波次。對t和t+1階段的目標集合來說,目標的數(shù)量不發(fā)生改變,避免了不對等交換造成各階段待打擊目標數(shù)量差異過大的問題,緩和了單波次武器發(fā)射的壓力。

圖3 段式階段調(diào)整算子

3 實驗分析

為了驗證模型和算法的有效性,在配置Intel(R) Core(TM) i5-10210U CPU @ 1.60 GHz 2.11 GHz的計算機上,使用PyCharm編譯器在python3.8.5的環(huán)境下開展實驗分析。

實驗采用10個隨機生成的測試算例來驗證算法的性能,并與變鄰域搜索(variable neighborhood search, VNS)方法進行了對比實驗,該算例中的數(shù)據(jù)使用了隨機案例生成器產(chǎn)生,算例的規(guī)模和算法涉及的基本參數(shù)如表2和表3所示。表4展示了HSA算法和VNS算法在同樣的環(huán)境下運行20次得出的平均目標函數(shù)值和平均運行時間,其中“-”表示VNS求解該問題耗時過長,不可接受。

表2 算例規(guī)模

表3 算法參數(shù)

表4 算法運行時間對比

為了驗證本文算法的求解效果,統(tǒng)計了兩種算法在外層循環(huán)框架下搜索到的解的分布,采用圖4和圖5所示的箱線圖展示算法的求解效果。為了方便展示,選取了前4個算例的實驗結(jié)果,其中圖5是算例4更詳細的展示。由實驗結(jié)果可知,HSA算法在求解質(zhì)量方面高于VNS算法,并且目標函數(shù)值分布集中,這是使用精確算法求解的優(yōu)勢所在。如圖5所示,該場景包含4個階段,15種武器類型以及60個目標(算例4),算法每次搜索出的局部最優(yōu)解分布在355～360,對比VNS算法,解分布范圍更大并且質(zhì)量較差。在8個場景下,算法運行得到的目標函數(shù)值均優(yōu)于VNS算法,并且實驗表明,在目標數(shù)量相同的情況下,多波次籌劃打擊可以在更短的時間內(nèi)取得更好的作戰(zhàn)效果,如表4中算例5和算例6的對比結(jié)果。盡管算例6使用了較少的武器種類,但是通過增加打擊階段可以把運行時間縮短39%,目標函數(shù)下降2%。在10個算例的運行時間上,本文算法均明顯優(yōu)于VNS,說明本文提出以匈牙利算法替代局部搜索來尋找局部最優(yōu)解的方式有著良好的計算性能。

圖4 所提算法和VNS算法解的質(zhì)量對比

圖5 算例4的解的分布情況

4 結(jié)束語

針對戰(zhàn)場遠程精確打擊過程中武器發(fā)射平臺數(shù)量有限的問題,提出一種MS-WTA模型,依據(jù)重要性和目標打擊的時間窗等因素給目標排列打擊順序、標記松弛符號,為目標的階段劃分提供了一種靈活的調(diào)整策略。在求解算法方面,設計了一種匈牙利-模擬退火結(jié)合的混合智能搜索算法,通過匈牙利算法計算每個階段間武器和目標的精確匹配方案,減少了傳統(tǒng)模擬退火方法以局部搜索尋找局部最優(yōu)解的搜索時間。再借助于模擬退火框架對各階段的可松弛目標進行調(diào)整,直到得出多階段全局最優(yōu)解。實驗結(jié)果表明,在啟發(fā)式方法中嵌入精確搜索方法對于提高解的質(zhì)量和縮短求解時間有著顯著優(yōu)勢,通過與HSA算法和VNS算法的對比實驗進一步驗證了HSA算法的有效性。

在下一步的研究中,將建立更加普適情形下的WTA模型,并針對常規(guī)導彈作戰(zhàn)中的一對多、多對一和多對多等典型打擊場景,研究數(shù)據(jù)和知識協(xié)同驅(qū)動的智能優(yōu)化算法,探索大規(guī)模MS-WTA問題的高效求解算法。