多機空戰(zhàn)指揮引導不平衡目標分配方法研究

高陽陽，余敏建，楊杰

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

0 引 言

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

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

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

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

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

1 目標分配模型

1.1 目標分配的概念

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

(1) 平衡目標分配方式

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

圖1 平衡目標分配方式

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

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

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

圖2 不平衡目標分配方式

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

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

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

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

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

根據(jù)以上假設(shè)，在多機空戰(zhàn)的指揮引導目標分配中，只需要考慮空戰(zhàn)中的敵我戰(zhàn)機數(shù)量，由此進行指揮引導目標分配建模。假設(shè)空戰(zhàn)中有敵機m架，我機n架，我機只能同時對一架敵機進行攻擊，我方戰(zhàn)機組成機群W={Wi,i=1,2,…,n}，敵方目標機組成機群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)指揮引導目標分配問題的模型可以描述為

(1)

(2)

(3)

滿足

(4)

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

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

2.1 匈牙利算法

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

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

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

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

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

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

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

2.2 進化匈牙利算法

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

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

將第一行和第二行交換：

將第二列和第四列交換：

算法流程為

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

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

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

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

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

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

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

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

當前的評價矩陣為

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

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

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

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

當前的評價矩陣為

我方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)化為平衡目標分配問題，在此對敵我戰(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)的行進行“補邊”，原則是不影響正常的目標分配。修改后的評價矩陣為

結(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號。

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

結(jié)果矩陣為

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

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

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

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

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

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

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

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

評價矩陣由電腦隨機產(chǎn)生，評價矩陣中的元素值的大小在0到1之間并且滿足約束條件。進化代數(shù)設(shè)置為100至1 000代，每隔100代記錄一次數(shù)據(jù)，采用改進的進化匈牙利算法處理目標分配問題，結(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é)果表明了算法具有較好的時效性和可靠性，能滿足多維條件下的目標分配處理。

4 結(jié) 論

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

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