高陽陽，余敏建，楊杰

(空軍工程大學(xué) 空管領(lǐng)航學(xué)院，西安 710051)

0 引 言

在多機協(xié)同對抗的網(wǎng)絡(luò)化現(xiàn)代空戰(zhàn)中，對敵我戰(zhàn)機的引導(dǎo)配批是多機空戰(zhàn)指揮引導(dǎo)的重要環(huán)節(jié)，合理科學(xué)地進行引導(dǎo)配批能更好地發(fā)揮多機空戰(zhàn)的整體效能。

從理論角度，對敵我戰(zhàn)機的引導(dǎo)配批問題屬于目標(biāo)分配問題。目前，對于目標(biāo)分配問題國內(nèi)外進行了相關(guān)的研究。在國外，J.C.F.Cabrera等[1]、S.Moon等[2]研究了對美國空軍無人機協(xié)同作戰(zhàn)目標(biāo)分配問題；Aleksandar Jevtic等[3]研究了無人機協(xié)同控制與任務(wù)分配問題。在國內(nèi)，Lee Z J等[4]在武器目標(biāo)分配方面展開了研究；肖金科等[5]采用人工免疫算法解決了大規(guī)模區(qū)域反導(dǎo)目標(biāo)分配問題；崔亞妮等[6]提出了一種多無人機時敏任務(wù)動態(tài)分配算法，實現(xiàn)戰(zhàn)場環(huán)境下多架無人機對多個時敏目標(biāo)的打擊；王然輝等[7]采用遺傳算法解決了對地打擊武器—目標(biāo)分配問題；夏維等[8]采用改進型多目標(biāo)粒子群優(yōu)化算法解決了武器—目標(biāo)分配問題；宋遐淦等[9]采用改進的模擬退火遺傳算法解決了協(xié)同空戰(zhàn)目標(biāo)分配問題。

但以上算法存在如下問題：不平衡目標(biāo)分配問題中經(jīng)常會遇到加入戰(zhàn)場和退出戰(zhàn)場等情況，采用上述方法處理動態(tài)不平衡目標(biāo)分配問題時，難以保證算法的時效性，且搜索效率低，容易出現(xiàn)早熟收斂現(xiàn)象。

匈牙利算法是目前公認的一種能有效解決目標(biāo)分配的算法，在解決小規(guī)模目標(biāo)分配問題時具有運算速度快、可靠性好等特點。然而大量的數(shù)據(jù)試驗表明，匈牙利算法在處理某些特殊的數(shù)據(jù)時會不收斂而無法找到最優(yōu)解，且耗時、不穩(wěn)定，當(dāng)目標(biāo)分配問題的矩陣規(guī)模較大時，通常會出現(xiàn)不收斂的情況。

基于多機空戰(zhàn)的實際考慮，本文將多機空戰(zhàn)的指揮引導(dǎo)配批問題，分為小規(guī)模配批問題和大規(guī)模配批問題，分別采用匈牙利算法和進化匈牙利算法進行目標(biāo)分配，并進行仿真分析，以期為解決多機空戰(zhàn)指揮引導(dǎo)不平衡目標(biāo)分配問題拓展研究思路。

1 目標(biāo)分配模型

1.1 目標(biāo)分配的概念

考慮戰(zhàn)機數(shù)量，目標(biāo)分配有兩種方式，一種是平衡目標(biāo)分配方式，另一種是不平衡目標(biāo)分配方式[10]。

(1) 平衡目標(biāo)分配方式

平衡目標(biāo)分配方式是指空戰(zhàn)中，敵我雙方兵力一致，且戰(zhàn)機能力相當(dāng)時，根據(jù)戰(zhàn)場態(tài)勢，將敵我戰(zhàn)機以“一對一”進行分配的方式，能夠有效確保作戰(zhàn)兵力使用的效率，防止火力浪費。如圖1所示。

圖1 平衡目標(biāo)分配方式

空戰(zhàn)中，雙方戰(zhàn)機在執(zhí)行作戰(zhàn)任務(wù)中導(dǎo)致的戰(zhàn)損，或者是戰(zhàn)術(shù)性的加入或退出戰(zhàn)場，都會導(dǎo)致空戰(zhàn)態(tài)勢發(fā)生變化。為了緊跟戰(zhàn)場態(tài)勢，確保掌握戰(zhàn)場主動，必須對之前的目標(biāo)分配結(jié)果做出及時調(diào)整，應(yīng)根據(jù)新的戰(zhàn)場態(tài)勢進行再次分配。由于作戰(zhàn)力量發(fā)生了改變，平衡目標(biāo)分配方式不再適用于新的戰(zhàn)場態(tài)勢，由此轉(zhuǎn)為不平衡目標(biāo)分配方式。由此可見，平衡目標(biāo)分配方式通常為最初的分配方式。

(2) 不平衡目標(biāo)分配方式

在實際作戰(zhàn)中，平衡目標(biāo)分配方式只是一種比較理想的情況，通常情況下，雙方戰(zhàn)機數(shù)量是不相等的。在我方探測到敵方來襲兵力時，為了確保戰(zhàn)爭的勝利，在不浪費物資的前提下通常會派出較敵方更多的戰(zhàn)機，以求在兵力上進行壓制，取得作戰(zhàn)優(yōu)勢。例如，我機數(shù)量n大于敵機數(shù)量m，這就會出現(xiàn)多架我機同時打擊一架敵機的情況，或者是在經(jīng)過敵我空中交火后形成的剩余戰(zhàn)機數(shù)量不等的情況，這時應(yīng)進行不平衡目標(biāo)分配，如圖2所示。

圖2 不平衡目標(biāo)分配方式

1.2 多機空戰(zhàn)指揮引導(dǎo)目標(biāo)分配模型

通常情況下，對多機空戰(zhàn)目標(biāo)分配需要綜合考慮戰(zhàn)機機型、戰(zhàn)機掛載導(dǎo)彈數(shù)量、掛載導(dǎo)彈性能以及戰(zhàn)機的電子干擾等能力。本文主要是針對三代機的多機空戰(zhàn)指揮引導(dǎo)問題進行研究，考慮到三代機性能和導(dǎo)彈掛載能力的差別相對于戰(zhàn)機數(shù)量的差異對空戰(zhàn)的影響很??；此外，在實際空戰(zhàn)中，我方在探明來襲敵機的情況下，通常會派遣綜合性能高于敵方戰(zhàn)機的我機進行空戰(zhàn)。因此，本文對多機空戰(zhàn)指揮引導(dǎo)問題進行簡化處理，做出如下假設(shè)：

①空戰(zhàn)中我方戰(zhàn)機機動性能優(yōu)于敵機；

②敵我戰(zhàn)機的電子干擾能力相當(dāng)，即不考慮敵我戰(zhàn)機的電子對抗；

③考慮到三代機不具備多目標(biāo)攻擊能力，假設(shè)敵我戰(zhàn)機掛載導(dǎo)彈數(shù)量滿足作戰(zhàn)任務(wù)需求，且對目標(biāo)實施攻擊只需要一枚導(dǎo)彈，即在對所分配的目標(biāo)實施攻擊后剩余導(dǎo)彈可用來攻擊下一次分配的目標(biāo)。

根據(jù)以上假設(shè)，在多機空戰(zhàn)的指揮引導(dǎo)目標(biāo)分配中，只需要考慮空戰(zhàn)中的敵我戰(zhàn)機數(shù)量，由此進行指揮引導(dǎo)目標(biāo)分配建模。假設(shè)空戰(zhàn)中有敵機m架，我機n架，我機只能同時對一架敵機進行攻擊，我方戰(zhàn)機組成機群W={Wi,i=1,2,…,n}，敵方目標(biāo)機組成機群D={Dj,j=1,2,…,m}，其中Wi表示我方第i架戰(zhàn)機，Dj表示敵方第j架戰(zhàn)機，為了取得空戰(zhàn)勝利，通常在兵力使用時應(yīng)對敵方兵力構(gòu)成優(yōu)勢，因此，應(yīng)滿足n≥m，則多機空戰(zhàn)指揮引導(dǎo)目標(biāo)分配問題的模型可以描述為

(1)

(2)

(3)

滿足

(4)

式中：C=(Cij)n×m表示評價矩陣，Cij為第i架我機對第j架敵機構(gòu)成的空戰(zhàn)指揮引導(dǎo)優(yōu)勢值數(shù)值；X=(Xij)n×m表示目標(biāo)分配的解矩陣，Xij值為1時，表示已經(jīng)把第j架敵機分配給我方的第i架戰(zhàn)機，Xij值為0時，表示未把第j架敵機分配給第i架我機；Z為目標(biāo)函數(shù)，表示我方機群總的指揮引導(dǎo)優(yōu)勢值，反應(yīng)我方機群總的空戰(zhàn)態(tài)勢優(yōu)勢，給出分配解X以使總指揮引導(dǎo)優(yōu)勢值Z最大。約束條件(2)和(3)分別表示我方一架戰(zhàn)機只能攻擊一架敵機和一架敵機可以同時被我方兩架戰(zhàn)機攻擊，體現(xiàn)了多機空戰(zhàn)指揮引導(dǎo)目標(biāo)分配的特點。

2 基于匈牙利算法的多目標(biāo)任務(wù)分配

2.1 匈牙利算法

匈牙利算法是由庫恩(W.W.Kuhn)在1955年提出的，是一種關(guān)于指派問題的求解方法。匈牙利算法引用了匈牙利數(shù)學(xué)家康尼格(Dénes K?nig)的一個關(guān)于矩陣中獨立0元素個數(shù)的定理：矩陣中獨立0元素的個數(shù)等于能夠覆蓋所有0元素的最少直線數(shù)[11]。

盡管具有多目標(biāo)攻擊能力的四代機、五代機的研制進度加快，也有部分四代機裝備部隊，但是我國現(xiàn)階段空戰(zhàn)的主戰(zhàn)飛機仍然是不具備多目標(biāo)攻擊的三代機。在實際空戰(zhàn)中，為了達到作戰(zhàn)目的，保證作戰(zhàn)效果，我方通常采取大于或等于敵方戰(zhàn)機數(shù)量的兵力進行作戰(zhàn)。在這種情況下的多機協(xié)同攻擊多目標(biāo)的任務(wù)分配即是一種典型的組合優(yōu)化問題，也是一種單對單的目標(biāo)分配問題，適合采用匈牙利算法進行計算和求解。在一般的匈牙利算法目標(biāo)分配模型中，主要通過對評價矩陣的計算處理得到分配結(jié)果[12]。匈牙利算法的一般實施步驟如下：

第一步：對空戰(zhàn)敵我戰(zhàn)機進行隨機編號；

第二步：以敵機的屬性和敵我空戰(zhàn)態(tài)勢為主要依據(jù)進行態(tài)勢評估，構(gòu)建評價矩陣；

第三步：對評價矩陣進行線性變換，使各行各列中出現(xiàn)0元素為止(每行每列分別減去該行該列中的最小元素)；

第四步：由調(diào)整后的評價矩陣得到最優(yōu)分配結(jié)果。

評價矩陣中的元素值是當(dāng)前態(tài)勢下我機相對于敵機的指揮引導(dǎo)優(yōu)勢值，評價矩陣的行號和列號分別代表我機和敵機的戰(zhàn)機編號，例如：第一行第一列處的元素是我機“1號”對敵機“1號”的指揮引導(dǎo)優(yōu)勢值，第一行數(shù)據(jù)就是我方“1號”戰(zhàn)機分別對于敵方所有戰(zhàn)機的指揮引導(dǎo)優(yōu)勢值，其他數(shù)據(jù)定義也是如此。

2.2 進化匈牙利算法

進化匈牙利算法[13]是由J.H.Holland提出的，采用進化算法可以有效地解決目標(biāo)分配問題，但計算速度隨著維數(shù)的增長顯著下降，無法較好地滿足戰(zhàn)場實時性的要求。

不平衡目標(biāo)分配問題可以變換為平衡目標(biāo)分配問題進行解決，因此對基于三代機的多機空戰(zhàn)指揮引導(dǎo)目標(biāo)分配問題可以看作是“單對單”的分配方式，即在目標(biāo)分配的解矩陣中表現(xiàn)為每行每列均只有一個“1”，“1”代表對應(yīng)戰(zhàn)機號進行目標(biāo)分配，“0”代表對應(yīng)戰(zhàn)機號未進行分配。本文采取將匈牙利算法和進化匈牙利相結(jié)合的方式進行大規(guī)模目標(biāo)分配的處理，算法初始種群由兩部分組成，一部分是由匈牙利算法求解得到的解矩陣，該解矩陣對應(yīng)的目標(biāo)分配方案通常不是最優(yōu)，因此再隨機生成0-1矩陣替換解矩陣中的部分行和列，由此組合后的矩陣作為初始種群，通過交叉、復(fù)制及變異等操作得到最終的分配結(jié)果，既可確保分配結(jié)果的最優(yōu)又可確保算法收斂的時效性。算法使用的變異算子是隨機的交換結(jié)果矩陣的兩行或兩列，如下所示：

將第一行和第二行交換：

將第二列和第四列交換：

算法流程為

步驟1 對空戰(zhàn)中敵我雙方戰(zhàn)機數(shù)量進行判斷并隨機編號。若敵我雙方戰(zhàn)機數(shù)量都不超過4架，則可以直接使用單純的匈牙利算法進行計算；若戰(zhàn)機數(shù)量大于4架，認為是大規(guī)模目標(biāo)分配問題，采用兩種算法相結(jié)合的方式進行處理。

步驟2 在處理大規(guī)模目標(biāo)分配問題時，首先對評價矩陣采用匈牙利算法來處理，得到對應(yīng)的解矩陣，然后隨機生成若干個對應(yīng)的0-1矩陣，將生成的0-1矩陣和得到的解矩陣一起作為算法的初始種群。

步驟3 計算每個個體在種群中的適應(yīng)度，并進行復(fù)制、變異。復(fù)制：保留父代種群中適應(yīng)度高的優(yōu)良個體并添加到子代種群中，并刪除父代種群中適應(yīng)度差的個體；變異：首先從父代種群中隨機選擇一個個體進行變異處理，即對其中的任意兩行或兩列進行交換后得到新的個體，然后將新的個體添加到子代種群中。

步驟4 首先重復(fù)步驟3，增加進化代數(shù)，直至達到最大進化代數(shù)為止，然后對得到的種群中的個體進行選擇，最優(yōu)的個體即為所要求的解，其對應(yīng)的目標(biāo)分配結(jié)果即是最優(yōu)的分配方案。

2.3 動態(tài)目標(biāo)分配的處理

空戰(zhàn)中，敵我雙方參戰(zhàn)兵力會由于戰(zhàn)機的損傷或退出發(fā)生變化，因此目標(biāo)分配將是動態(tài)進行的過程。敵我雙方空戰(zhàn)的態(tài)勢信息是通過評價矩陣體現(xiàn)的，因此可以通過對評價矩陣的處理來反映戰(zhàn)場形勢的變化。

(1) 戰(zhàn)機退出戰(zhàn)場的情況

當(dāng)戰(zhàn)機退出戰(zhàn)場時，其對應(yīng)的評價矩陣中的行或列應(yīng)該被刪除，但是為了保持評價矩陣的完整性，使評價矩陣能夠用于算法的計算處理，通常需要采用補邊法(將退出戰(zhàn)場的敵機對應(yīng)評價矩陣的行或列元素值改為0)，既確保了評價矩陣的完整性，又確保了改動的元素值不影響正常的目標(biāo)分配。具體方法如下所示：

當(dāng)前的評價矩陣為

我方2號戰(zhàn)機退出戰(zhàn)場后的評價矩陣為

敵方4號戰(zhàn)機退出戰(zhàn)場后的評價矩陣為

(2) 戰(zhàn)機加入戰(zhàn)場的情況

當(dāng)戰(zhàn)機新加入戰(zhàn)場時，戰(zhàn)場中戰(zhàn)機數(shù)量發(fā)生變化，評價矩陣也隨之變化，通過地面信息平臺對新加入的戰(zhàn)機進行態(tài)勢評估后建立新的評價矩陣，此時的評價矩陣的行數(shù)和列數(shù)不相等，采用前述補邊法進行處理。具體方法如下所示：

當(dāng)前的評價矩陣為

我方6號戰(zhàn)機加入戰(zhàn)場后的評價矩陣為

敵方6號戰(zhàn)機加入戰(zhàn)場后的評價矩陣為

3 仿真分析

(1) 戰(zhàn)機數(shù)量增加

空戰(zhàn)中敵我雙方戰(zhàn)機數(shù)量的初始態(tài)勢有三種情況：我機數(shù)量占優(yōu)、敵機數(shù)量占優(yōu)和敵我機數(shù)量相等。但在實際作戰(zhàn)中，為了保證作戰(zhàn)效果，通常不會出現(xiàn)初始情況下我機數(shù)量少于敵機數(shù)量的情況，在我機數(shù)量占優(yōu)的情況下，敵機數(shù)量增加后可以轉(zhuǎn)化為平衡目標(biāo)分配問題，在此對敵我戰(zhàn)機數(shù)量相等的情況進行研究。假設(shè)對應(yīng)的評價矩陣為T4×4

使用匈牙利算法計算處理，得到的結(jié)果矩陣為

對應(yīng)的分配結(jié)果為：我機1號攻擊敵機3號；我機2號攻擊敵機2號；我機3號攻擊敵機1號；我機4號攻擊敵機4號。

若突然增加戰(zhàn)機，則根據(jù)補邊法對評價矩陣進行改動。在此初始條件下，若敵方增加一架戰(zhàn)機，通過分析戰(zhàn)場態(tài)勢，得到新增戰(zhàn)機威脅值后，相應(yīng)的在評價矩陣后加入一列該戰(zhàn)機對我機的威脅值，同時需要在評價矩陣下方加入對應(yīng)的行進行“補邊”，原則是不影響正常的目標(biāo)分配。修改后的評價矩陣為

結(jié)果矩陣為

對應(yīng)的分配結(jié)果為：我機1號攻擊敵機3號；我機2號攻擊敵機2號；我機3號攻擊敵機1號；我機4號攻擊敵機5號；我機5號攻擊敵機4號。

敵方加入后的分配情況如圖3所示。

圖3 敵方加入后的分配情況

從圖3可以看出：分配情況較最初有所變化，且在敵機數(shù)量增加后，在分配中出現(xiàn)漏分配的情況(若沒有我機攻擊敵機4號)，此時指揮員應(yīng)該根據(jù)戰(zhàn)場形勢對我機進行數(shù)量補給，以確保我方在不浪費兵力的情況下占據(jù)優(yōu)勢態(tài)勢。

(2) 戰(zhàn)機數(shù)量減少

以上述初始條件進行研究，假設(shè)對應(yīng)的評價矩陣為T4×4

結(jié)果矩陣為

對應(yīng)的分配結(jié)果為：我機1號攻擊敵機3號；我機2號攻擊敵機2號；我機3號攻擊敵機1號；我機4號攻擊敵機4號。

當(dāng)敵機3號退出戰(zhàn)場，采用補邊法需對第三列進行修改如下：

結(jié)果矩陣為

對應(yīng)的分配結(jié)果為：我機1號攻擊敵機3號；我機2號攻擊敵機2號；我機3號攻擊敵機1號；我機4號攻擊敵機4號。

敵方退出后的分配情況如圖4所示。

圖4 敵方退出后的分配情況

從圖4可以看出：在敵機3號退出戰(zhàn)場后的目標(biāo)分配結(jié)果中，我機1號沒有分配攻擊目標(biāo)，此時可以通過指揮員根據(jù)個人意向選擇1號對任意敵機進行攻擊。

在圖4情況下，可以選擇我機1號協(xié)同2號攻擊敵機2號，再分配情況如圖5所示。

圖5 指揮員個人選擇后的再分配情況

(3) 多維目標(biāo)分配仿真分析

實際空戰(zhàn)中，通常是機群作戰(zhàn)，雙方戰(zhàn)機數(shù)量較大，為了驗證算法在處理多維目標(biāo)分配時的時效性和可靠性，選取48維不同進化代數(shù)的仿真結(jié)果進行分析。

評價矩陣由電腦隨機產(chǎn)生，評價矩陣中的元素值的大小在0到1之間并且滿足約束條件。進化代數(shù)設(shè)置為100至1 000代，每隔100代記錄一次數(shù)據(jù)，采用改進的進化匈牙利算法處理目標(biāo)分配問題，結(jié)果如表1所示。

表1 48維評價矩陣進化代數(shù)數(shù)據(jù)分析表

從表1可以看出：隨著進化代數(shù)從100代到1 000代，評價矩陣總優(yōu)勢值不斷增加。由于在改進的進化匈牙利算法中加入了交叉、變異操作，使種群的多樣性得到增強，進化代數(shù)達到700代后才不斷趨于穩(wěn)定，有效防止了過早收斂現(xiàn)象的發(fā)生。同時，算法運行時間也隨著進化代數(shù)的增加而不斷增加，但是基本都能保持在1 s內(nèi)，能夠滿足戰(zhàn)場實時性要求。該仿真結(jié)果表明了算法具有較好的時效性和可靠性，能滿足多維條件下的目標(biāo)分配處理。

4 結(jié) 論

(1) 分配組數(shù)小于5組為小規(guī)模問題，可以直接用匈牙利算法進行計算，計算時間快且分配結(jié)果準(zhǔn)確。分配組數(shù)大于等于5組時為大規(guī)模配批問題，采用進化匈牙利算法，有效避免了匈牙利算法在處理維數(shù)較大問題時運算時間長和無法收斂的問題，有效確保了目標(biāo)分配方案的整體指揮引導(dǎo)優(yōu)勢。

(2) 本文提出的新的多機空戰(zhàn)不平衡目標(biāo)分配方法具有較好的時效性和可靠性，能滿足多維條件下的目標(biāo)分配處理，滿足實戰(zhàn)需求。