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

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

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

0 引 言

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

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

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

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

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

1 問題分析與建模

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

表1 參數與變量符號說明

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

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

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

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

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

(1)

(2)

(3)

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

(4)

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

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

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

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

2.1 RC調整準則

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

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

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

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

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

圖1 RC更新

(3) RC值的更新方法

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

2.2 HSA算法

2.2.1 匈牙利算法

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

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

2.2.2 模擬退火算法

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

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

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

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

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

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

圖2 兩交換階段調整算子

(2) 段式階段調整算子

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

圖3 段式階段調整算子

3 實驗分析

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

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

表2 算例規模

表3 算法參數

表4 算法運行時間對比

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

圖4 所提算法和VNS算法解的質量對比

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

4 結束語

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

在下一步的研究中,將建立更加普適情形下的WTA模型,并針對常規導彈作戰中的一對多、多對一和多對多等典型打擊場景,研究數據和知識協同驅動的智能優化算法,探索大規模MS-WTA問題的高效求解算法。