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

張進，郭浩，陳統(tǒng)

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

0 引言

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

(1)

(2)

(3)

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

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

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

(4)

(5)

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

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

1 傳統(tǒng)HA與智能優(yōu)化算法的比較

1.1 傳統(tǒng)HA

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

步驟1構(gòu)建d×d的效率矩陣。

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

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

步驟4如果該列中有帶星號的0，則劃線該列，如果所有的列都被劃線，則最優(yōu)值已找到，否則轉(zhuǎn)步驟5.

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

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

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

1.2 對比與分析

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

A1A2…An

(6)

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

1.2.1 耗時性對比

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

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

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

1.2.2 穩(wěn)定性對比

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

圖2 不同規(guī)模分配問題下的最優(yōu)值比較

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

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

2 可適應HA

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

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

圖3 可適應HA的統(tǒng)一效率矩陣

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

3 實例應用

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

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

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

圖4 統(tǒng)一效率矩陣及求解結(jié)果(實例1)

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

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

圖5 統(tǒng)一效率矩陣及求解結(jié)果(實例2)

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

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

4 結(jié)論

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

1)相比于常見的智能優(yōu)化算法，可適應HA算法具有求解耗時短、結(jié)果穩(wěn)定的優(yōu)勢；

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