基于可適應匈牙利算法的武器-目標分配問題

張進，郭浩，陳統

(1.江蘇自動化研究所, 江蘇 連云港 222006; 2.91431部隊, 海南 海口 570100)

0 引言

武器-目標分配是指根據作戰目的、戰場態勢和武器性能等因素，按照一定的最優分配原則將多種武器分配給多個來襲目標，從而取得最佳打擊效果的方法[1]，其常見的數學模型包括最大毀傷模型以及最大價值模型[2]，如(1)式～(3)式所示：

(1)

(2)

(3)

式中：n表示目標數量；rj表示第j個目標的威脅程度；m表示武器數量；pij為第i個火力單元對第j個目標的命中概率；aij=0或1，0表示不選中，1表示選中。

武器-目標分配問題作為一種最優化問題，近年來被許多學者采用各種智能算法求解。楊飛等[3]采用整數域粒子群優化(PSO)算法研究多平臺武器目標分配問題；董朝陽等[4]利用改進的遺傳算法(GA)求解航空兵編隊對地攻擊武器目標分配模型；劉家義等[5]基于改進加速梯度下降算法研究了目標分配問題等。然而，武器目標分配問題本質上屬于非線性0-1整數規劃問題，是一類特殊的最優化問題，智能算法雖然能夠用于求解但是卻無法充分發揮其優勢，存在求解耗時長、優化結果不唯一等缺陷，實際作戰中這是致命的且不被允許的，必須在保證有解的基礎上，提高求解的質量和速度[6]。

指派問題作為運籌學中的經典問題，與武器-目標分配問題有著眾多相似之處，指派問題的定義為：由L個人完成K項工作，且每個人完成每項工作的效率不同，確定任務指派方案使得完成任務總的效率最高[7]。標準指派問題的數學模型可以表示為(4)式～(5)式：

(4)

(5)

式中：Clk表示第l個人做第k項工作的效率；blk=0或1，0表示不選擇，1表示選擇。對比(1)式～(3)式與(4)式～(5)式可知，武器-目標分配問題與指派問題的差別在于約束條件的不同，當約束條件變為某一目標只能被一種武器攻擊時，武器-目標分配問題就轉換為標準的指派問題。一直以來，匈牙利算法(HA)被公認為是指派問題的標準解法，其針對標準指派模型的特殊形式(方形矩陣)，基于匈牙利數學家Konig提出的獨立零元素定理，只采用矩陣變換等操作就能求出模型最優解，但研發初期，其解算流程基本是基于人工操作，隨著計算機語言對矩陣變換等操作的編譯，使得HA擁有計算速度快、解算結果穩定等優勢[8-9]。2002年，柳毅等[10]利用HA研究了攻擊機與目標機的分配問題，并提出一對多不平衡分配問題的解法，但并未提出多對一不平衡分配問題的解法。2013年，谷穩[11]基于進化HA研究了無人機目標分配問題，并考慮了不平衡目標分配情況，但并未建立統一的效率矩陣。2015年，李元左等[12]利用HA解算了炮兵火力分配模型，但并未解決一對多或是多對一的不平衡分配問題。以上基于HA研究目標分配問題的文獻都未曾將HA與智能優化算法進行對比分析，無法體現二者的優劣勢。

本文在充分對比分析HA與常用智能優化算法的基礎上，提出適用于所有目標分配問題的可適應HA，并利用該算法求解了復雜約束條件下的武器-目標分配問題。

1 傳統HA與智能優化算法的比較

1.1 傳統HA

傳統HA是Kuhn通過引用匈牙利數學家Konig關于矩陣中獨立0元素定理：在效率矩陣(也稱代價矩陣)的任意行或列加上或者減去一個常數不會改變最優分配方案的基礎上，提出用于解決指派問題的優化方法[11-12]。HA解決標準指派問題的步驟[13-14]如下：

步驟1構建d×d的效率矩陣。

步驟2用效率矩陣的每一行元素減去該行中的最小元素，再從每列元素中減去該列的最小元素。

步驟3在矩陣中找到某個0，如果其行或列中沒有加星號的0，則將該0標記上星號(簡稱星標0)，直至找遍所有的0.

步驟4如果該列中有帶星號的0，則劃線該列，如果所有的列都被劃線，則最優值已找到，否則轉步驟5.

步驟5找到一個未被劃線的0并標注它(簡稱標注0)。如果包含該標注0的行中沒有星號0，則轉步驟6；否則，劃線此行，并找出包含帶星號0的列。以這種方式繼續，直到沒有未被劃線的0，并保存最小的未劃線值，轉步驟7.

步驟6按照以下過程，構造一系列交替的標注0和星號0，首先令Z0代表步驟5中未被劃線的標注0，再令Z0表示Z0列中星號0(如果有)，最后令Z2表示Z1行中的標注0(始終為1個)，繼續直到標記0(Z0)的列中沒有星號0(Z1)。對標注0標記星標，變為星號0.返回步驟4.

步驟7將最小未劃線值加到每個劃線行的每個元素，并從每個未劃線列的每個元素中減去它。返回步驟5.

1.2 對比與分析

(6)式表示的是m個武器與n個目標的效率矩陣，一般而言，效率矩陣規模越大，則武器-目標分配問題就越復雜。為比較分析不同規模分配問題下HA與智能優化算法的耗時性與穩定性，本文分別選取10×10、20×20、50×50、100×100規模的武器-目標分配問題，其中pij的數值由計算機隨機產生，以求取總效率最低為優化目標函數。目前，GA、粒子群優化(PSO)算法及基于以上兩種算法改進的優化算法被頻繁用于求解武器-目標分配問題，因此，本文選取改進的GA[15]及PSO算法[16]與HA進行對比，運行環境為Windows 7系統、i5-2450M處理器、4GB運行內存的筆記本。

A1A2…An

(6)

式中：Wm表示第m個武器；An表示第n個目標；pij可以為Wi武器對Aj目標的毀傷概率，也可以取毀傷概率與該目標威脅程度的乘積，視目標函數而定。

1.2.1 耗時性對比

對4種不同規模的分配問題分別采用3種算法求解，每種規模下各算法都被運行10次，取其運行時間平均值作為最終耗時，由于PSO算法和GA運行時間與迭代次數相關，本文不采用以迭代次數為終止迭代條件，采用最優值不再更新作為終止迭代條件，運行結果如圖1所示。

圖1 HA、PSO算法、GA運行時間對比

從圖1中可以看出：1)在不同規模分配問題中，HA始終是3種算法中耗時最短的算法，以20×20規模的分配問題為例，HA平均耗時為0.006 s，PSO算法平均耗時為0.830 s，GA耗時1.674 s，相比于PSO算法和GA，HA的平均耗時要小兩個數量級，在實際作戰使用時，可有效縮短最優方案生成時間；2)隨著問題規模的上升，PSO算法和GA的平均耗時都在呈指數式增長，例如，相比于50×50規模的分配問題，求解100×100分配問題時，PSO算法平均耗時增加了5.2倍，GA平均耗時增加了3.1倍，而HA只增加了2.5倍，即使耗時增加了2.5倍，HA求解100×100規模分配問題也只耗時0.348 s，仍然處于可接受范圍內。

1.2.2 穩定性對比

將不同規模武器-目標分配問題下3種算法運行10次求解的最優值進行對比，為直觀分析結果，本文繪制了箱型圖，如圖2所示。圖2(a)表示10×10規模分配問題的最優值，圖2(b)表示20×20規模分配問題的最優值，圖2(c)表示50×50規模分配問題的最優值，圖2(d)表示100×100規模分配問題的最優值。

圖2 不同規模分配問題下的最優值比較

從圖2(a)～圖2(d)中可以看出：1)在不同規模分配問題中，HA始終是3種算法中求解最穩定的算法，其最優值始終收斂于某一個值，這是因為HA是基于矩陣的操作，對某一確定的效率矩陣，其求解結果也是確定的，而對于PSO算法及GA，均為群體智能優化算法，存在一定的隨機性，因此求解結果并不都收斂于某一個值[6]；2)從圖2(a)中可以看出，對于小規模分配問題，PSO算法及GA求解結果大概率都能獲取與HA同樣的結果，但對于大規模分配問題(見圖2(c)及圖2(d))，PSO算法及GA求解的最優值都遠小于HA.

綜上所述，HA的耗時性及穩定性均優于PSO算法及GA.但傳統的HA不能適用于所有類型的分配問題，因此有必要對傳統HA進行適應性改進。

2 可適應HA

傳統HA只能用于求解一對一的分配問題，后續學者通過研究HA的求解過程，提出利用“加邊補零法”使效率矩陣滿足HA的求解條件(效率矩陣必須為方形矩陣)，從而用于求解武器數多于目標數或武器數小于目標數的不平衡目標分配問題，還提出利用“虛擬目標數量法”解決1個武器攻擊多個目標的分配問題[9,11]。但截止目前，很少有學者研究多個武器同時攻擊1個目標的分配問題，也未曾建立適用于所有類型分配問題的統一效率矩陣。

本文在前人研究的基礎上，提出m個武器與n個目標，其中每個武器至多可以攻擊i個目標，每個目標至多可以被j個武器攻擊的統一效率矩陣，矩陣形式如圖3所示。

圖3 可適應HA的統一效率矩陣

圖3中黑色實線矩形框中的矩陣即為統一效率矩陣，當約束條件為每個武器至多可以攻擊2個目標(即y=2)，則i=1、i=2矩陣塊(見圖3中的藍色虛線矩形框)納入統一效率矩陣，當約束條件為每個目標至多可以被2個武器攻擊(即x=2)時，則j=1、j=2矩陣塊(見圖3中紅色虛線矩形框)納入統一效率矩陣，最后采用“加邊補0法”使效率矩陣變為方形矩陣。雖然處理復雜約束條件會導致統一效率矩陣維度變大，但從1.2.1節中的分析可知，HA處理大規模分配問題時耗時依然很小。

3 實例應用

為驗證可適應HA的正確性以及處理復雜約束條件的可行性，本文選取文獻[4]中的航空兵編隊對地攻擊仿真實例數據(見表1)，實例中共設置目標12批，W1武器4個、W2武器4個、W3武器2個，共10個武器。本文實例分以下兩種情形：1)每個目標至多可以被1個武器攻擊；2)每個目標至多可以被2個武器攻擊，分別構建了統一效率矩陣并采用可適應HA進行求解。

表1 文獻[4]中的毀傷概率及目標威脅度數據

當每個目標至多可以被1個武器攻擊時，構建的統一效率矩陣如圖4所示。可適應HA求解結果在圖4中被紅框標記，其中W1武器攻擊T4、T6、T10、T12，W2武器攻擊T1、T3、T5、T8，W3武器攻擊T2、T9，與文獻[4]中的求解結果相一致，驗證了可適應HA的正確性。

圖4 統一效率矩陣及求解結果(實例1)

為進一步比較可適應HA、GA及PSO算法的性能，同時采用3種算法求解以上兩種實例10次，結果如下：

實例1：可適應HA平均求解時間為5.343×10-3s，最優解求解次數10/10；GA平均求解時間為3.031×10-1s，最優解求解次數10/10；PSO算法平均求解時間為1.673×10-1s，最優解求解次數10/10.從以上結果可看出，3種算法都能穩定地求出最優解，但可適應HA的求解時間顯著低于另外兩種算法。當每個目標至多可以被2個武器攻擊時，構建的統一效率矩陣如圖5所示，可適應HA求解結果在圖5中被紅框標記，其中T1目標被2個W2武器同時攻擊，T3目標被2個W3武器同時攻擊，T5目標被2個W1武器同時攻擊，T6目標被2個W1武器同時攻擊，T8目標被2個W2武器同時攻擊，效率矩陣最優值為1.308 6.

圖5 統一效率矩陣及求解結果(實例2)

實例2：可適應HA平均求解時間為8.461×10-3s，最優解求解次數10/10；GA平均求解時間為6.309×10-1s，最優解求解次數9/10；PSO算法平均求解時間為3.732×10-1s，最優解求解次數9/10.從以上結果可看出，可適應HA的求解時間和穩定性都要優于另外兩種算法。

以上仿真實例應用結果表明，可適應HA可用于解決復雜約束條件下的武器-目標分配問題。

4 結論

本文針對傳統HA適用性差的缺陷，提出了可求解所有類型目標分配問題的可適應HA，并通過實例應用得到了以下結論：

1)相比于常見的智能優化算法，可適應HA算法具有求解耗時短、結果穩定的優勢；

2)可適應HA可用于求解復雜約束條件下的武器-目標分配問題。