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

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

0 引言

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

(1)

(2)

(3)

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

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

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

(4)

(5)

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

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

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

1.1 傳統(tǒng)HA

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

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

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

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

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

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

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

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

1.2 對比與分析

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

A1A2…An

(6)

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

1.2.1 耗時(shí)性對比

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

圖1 HA、PSO算法、GA運(yùn)行時(shí)間對比

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

1.2.2 穩(wěn)定性對比

將不同規(guī)模武器-目標(biāo)分配問題下3種算法運(yùn)行10次求解的最優(yōu)值進(jìn)行對比，為直觀分析結(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)值始終收斂于某一個(gè)值，這是因?yàn)镠A是基于矩陣的操作，對某一確定的效率矩陣，其求解結(jié)果也是確定的，而對于PSO算法及GA，均為群體智能優(yōu)化算法，存在一定的隨機(jī)性，因此求解結(jié)果并不都收斂于某一個(gè)值[6]；2)從圖2(a)中可以看出，對于小規(guī)模分配問題，PSO算法及GA求解結(jié)果大概率都能獲取與HA同樣的結(jié)果，但對于大規(guī)模分配問題(見圖2(c)及圖2(d))，PSO算法及GA求解的最優(yōu)值都遠(yuǎn)小于HA.

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

2 可適應(yīng)HA

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

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

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

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

3 實(shí)例應(yīng)用

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

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

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

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

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

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

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

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

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

4 結(jié)論

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

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

2)可適應(yīng)HA可用于求解復(fù)雜約束條件下的武器-目標(biāo)分配問題。