吳洪坤

(江蘇自動(dòng)化研究所,江蘇 連云港 222061)

現(xiàn)代局部熱戰(zhàn)中,空襲和防空對抗相當(dāng)程度上影響著戰(zhàn)爭的進(jìn)程和勝負(fù)。防空系統(tǒng)在面臨大規(guī)模梯次配置的空襲編隊(duì)時(shí),必須充分利用各火力單元的彈藥資源,盡可能攔截更多更重要的目標(biāo),以實(shí)現(xiàn)作戰(zhàn)效能最大化,在此過程中,武器-目標(biāo)分配是指揮控制決策的關(guān)鍵環(huán)節(jié)。武器-目標(biāo)分配(Weapon Target Assignment, WTA)又稱火力分配,是指在一定的條件約束下,根據(jù)作戰(zhàn)目的、武器性能、目標(biāo)參數(shù)等因素,合理配置武器資源,優(yōu)化火力打擊體系。

從模型研究的角度,根據(jù)是否考慮時(shí)間因素,通常分為靜態(tài)武器-目標(biāo)分配模型(Static Weapon Target Assignment, SWTA)和動(dòng)態(tài)武器-目標(biāo)分配模型(Dynamic Weapon Target Assignment, DWTA)。靜態(tài)WTA模型強(qiáng)調(diào)在單個(gè)階段內(nèi)一次性求解分配方案,不考慮時(shí)間因素,僅將毀傷概率和目標(biāo)威脅等因素作為優(yōu)化對象,這樣一來雖然可以提高求解效率,但模型過于簡單,實(shí)用性受限。動(dòng)態(tài)WTA模型則將分配過程分成多個(gè)階段執(zhí)行,在靜態(tài)模型的基礎(chǔ)上增加考慮時(shí)間約束和打擊次序?qū)Ψ峙浣Y(jié)果的影響,從而使模型更貼近實(shí)際,合理性更強(qiáng),但約束條件增多給求解計(jì)算造成困難。

從算法研究的角度,WTA是典型的非線性組合優(yōu)化問題,隨著武器與目標(biāo)數(shù)量的增加,解空間將呈指數(shù)式擴(kuò)大,給求解帶來困難。目前主要有兩類求解方法,一類是基于枚舉的精確算法,如窮舉法、隱枚舉法、割平面法、分支定界法等。這類算法精確度高、穩(wěn)定性好,但計(jì)算效率偏低,很難用于多約束復(fù)雜問題。另一類是基于啟發(fā)式策略的智能優(yōu)化算法,如遺傳算法、粒子群算法、蟻群算法、模擬退火算法等。這類算法可以在不進(jìn)行全枚舉的情況下搜索到理想的解,但穩(wěn)定性較差,容易出現(xiàn)重復(fù)迭代導(dǎo)致收斂慢,或過早收斂卻陷入局部最優(yōu)的情況。

當(dāng)前針對SWTA的研究較多,針對DWTA的研究較少,并且大多都采用啟發(fā)式算法進(jìn)行求解,很難滿足實(shí)際戰(zhàn)場中實(shí)時(shí)性和準(zhǔn)確性的要求。本文在傳統(tǒng)的多級WTA模型的基礎(chǔ)上進(jìn)行改進(jìn),并結(jié)合KM算法對問題進(jìn)行求解,為防空作戰(zhàn)中的動(dòng)態(tài)WTA問題給出了一種可行的解決方法。

1 動(dòng)態(tài)WTA問題建模

1.1 目標(biāo)函數(shù)

動(dòng)態(tài)分配問題可視作個(gè)階段的靜態(tài)分配問題,每個(gè)階段用序號進(jìn)行區(qū)分。在第個(gè)階段,假設(shè)有個(gè)武器構(gòu)成武器集合={,,…,},有個(gè)目標(biāo)構(gòu)成目標(biāo)集合={,,…,},有目標(biāo)函數(shù):

(1)

目標(biāo)函數(shù)中()表示第個(gè)階段分配方案的作戰(zhàn)收益值;()∈(0,1)表示第個(gè)階段目標(biāo)的威脅系數(shù);()表示第個(gè)階段武器對目標(biāo)的整體攔截概率;()是布爾量,用于判定武器是否分配給目標(biāo),是則()=1,否則()=0;約束條件表示,武器與目標(biāo)之間采用“一對一”的分配方式。

1.2 時(shí)間因素

動(dòng)態(tài)武器-目標(biāo)分配中需要考慮的時(shí)間因素主要包括武器射擊周期和目標(biāo)來襲時(shí)間。

武器射擊周期是指武器從射擊第一個(gè)目標(biāo)到射擊第二個(gè)目標(biāo)的時(shí)間間隔,即=+。服務(wù)時(shí)間是指武器射擊第一個(gè)目標(biāo)的時(shí)間,包括導(dǎo)彈發(fā)射間隔總耗時(shí),攔截導(dǎo)彈從發(fā)射到與目標(biāo)相遇的飛行時(shí)間,即=+。轉(zhuǎn)火準(zhǔn)備時(shí)間是指武器轉(zhuǎn)火射擊第二個(gè)目標(biāo)所需要的準(zhǔn)備時(shí)間。

目標(biāo)來襲時(shí)間指的是目標(biāo)飛臨發(fā)射區(qū)遠(yuǎn)界的時(shí)間和飛臨發(fā)射區(qū)近界的時(shí)間。

1.3 資源約束

武器平臺載彈量有限,為了保證打擊效果并且提高資源利用率,本文通過設(shè)定攔截概率閾值的方式來約束武器平臺發(fā)射的導(dǎo)彈數(shù)量。

假設(shè)武器的載彈量為,第個(gè)階段武器對目標(biāo)發(fā)射()枚導(dǎo)彈,單發(fā)導(dǎo)彈對目標(biāo)的毀傷概率為(),則對的總體攔截概率:

()=1-[1-()]()

(2)

定義攔截概率閾值(),武器對目標(biāo)的攔截概率不得低于閾值,即()≥(),從而得到關(guān)于()的約束條件:

(3)

的設(shè)定取決于的威脅系數(shù),對于威脅系數(shù)高的目標(biāo),攔截概率閾值設(shè)定的更高,對于<01的目標(biāo)則不進(jìn)行攔截。如表1。

表1 威脅系數(shù)與攔截概率閾值對應(yīng)表

在此約束條加下,若武器的剩余彈藥無法滿足對來襲目標(biāo)實(shí)現(xiàn)高于攔截概率閾值的攔截打擊,則不考慮將分配給。若的彈藥全部用完,則將其從火力單元序列中移出。

1.4 改進(jìn)多級分配模型

多級分配模型是動(dòng)態(tài)WTA研究中的常用模型。傳統(tǒng)的多級分配模型通常采用“射擊-觀察-射擊”的模式,每個(gè)階段的分配決策以上一階段的交戰(zhàn)結(jié)果(來襲目標(biāo)生存或被擊毀)作為新的初始條件,防御方對未被擊毀的目標(biāo)進(jìn)行新一輪的分配,時(shí)間窗口圖如圖1所示。圖中白色框表示武器的射擊周期,灰色框表示防空系統(tǒng)等待階段1的交戰(zhàn)結(jié)果判定以及進(jìn)行階段2發(fā)射準(zhǔn)備的時(shí)間。傳統(tǒng)的多級分配模型中,武器對不同目標(biāo)的射擊周期不存在重疊。

圖1 傳統(tǒng)多級分配模型時(shí)間窗口圖

當(dāng)來襲目標(biāo)數(shù)量多且時(shí)間緊迫時(shí),防空系統(tǒng)為了等待判定交戰(zhàn)結(jié)果往往會(huì)耗費(fèi)許多時(shí)間,這在實(shí)際作戰(zhàn)中對防御方非常不利。因此,本文對多級分配模型進(jìn)行改進(jìn)。區(qū)別于傳統(tǒng)模型中僅有生存和擊毀兩種狀態(tài),改進(jìn)的多級分配模型將來襲目標(biāo)分為:未分配、已分配未交戰(zhàn)、已交戰(zhàn)被摧毀和突破攔截等四種狀態(tài)。防空系統(tǒng)不再等待上一階段的交戰(zhàn)結(jié)果判定,而是以固定的時(shí)間間隔連續(xù)進(jìn)行分配輪次的求解,此時(shí)的時(shí)間窗口圖如圖2所示。

圖2 改進(jìn)多級分配模型時(shí)間窗口圖

由于目標(biāo)數(shù)量過多,防空系統(tǒng)必須命令武器平臺提前準(zhǔn)備轉(zhuǎn)火射擊,以應(yīng)對新目標(biāo)。此時(shí)武器的射擊周期存在重疊,武器發(fā)射的導(dǎo)彈與上一個(gè)目標(biāo)還未交戰(zhàn)便進(jìn)行對下一個(gè)目標(biāo)的轉(zhuǎn)火準(zhǔn)備。此時(shí)武器若想實(shí)現(xiàn)轉(zhuǎn)火攔截,需要滿足約束條件:

≤+≤

(4)

若+>,則攔截失敗;若+<,則武器轉(zhuǎn)火準(zhǔn)備過于提前,待機(jī)過久而浪費(fèi)時(shí)間。

2 動(dòng)態(tài)WTA問題求解

2.1 KM算法基本原理

KM(Kuhn-Munkras)算法是一種在多項(xiàng)式時(shí)間內(nèi)查找有權(quán)二部圖最優(yōu)匹配的算法,其在匈牙利算法的基礎(chǔ)上引入了可行頂標(biāo)以及相等子圖等概念,以實(shí)現(xiàn)二部圖最優(yōu)匹配的求解。

將WTA問題用有權(quán)二部圖進(jìn)行刻畫,如圖1所示。=(,,,),武器集合和目標(biāo)集合是頂點(diǎn)集合,顯然二者互不相交,且集合內(nèi)部元素之間不存在分配關(guān)系;是邊集合,與間的連線表示與可能存在的分配關(guān)系;是邊權(quán)值集合,表示的權(quán)值,是判斷是否將分配給的主要依據(jù)。如此一來只要合理設(shè)置邊權(quán)值就可以將WTA問題轉(zhuǎn)化為有權(quán)二部圖求解最優(yōu)匹配的問題。

圖3 WTA的有權(quán)二部圖模型

定義:=(,,,)是有權(quán)完備二部圖,設(shè)頂點(diǎn)的頂標(biāo)為,頂點(diǎn)的頂標(biāo)為,若子圖中的所有邊都滿足+=,則稱為的相等子圖,若存在原圖的完備匹配,則該完備匹配便是原圖的最優(yōu)匹配。

KM算法主要步驟為:

step1:初始化各個(gè)頂點(diǎn)的可行頂標(biāo)值;

step2:找出相等子圖并使用匈牙利算法搜索最大匹配;

step3:判斷最大匹配是否為原圖的完備匹配,若是則該匹配便是所求的最優(yōu)匹配,若不是則修改可行頂標(biāo)值。

step4:重復(fù)step2～3直至找到最優(yōu)匹配。

2.2 剩余彈藥資源判定系數(shù)

約束條件規(guī)定武器的剩余彈藥對來襲目標(biāo)的總體攔截概率要高于閾值。如果要在分配計(jì)算之前遍歷所有武器,判斷其剩余彈藥量是否滿足要求,顯然會(huì)增加求解耗時(shí)。因此本文定義判定剩余彈藥資源的系數(shù):

=[1-(1-)-]+1

(5)

式中方括號表示取整函數(shù),表示武器的剩余導(dǎo)彈枚數(shù)。當(dāng)武器剩余彈藥量對目標(biāo)的總體攔截概率大于時(shí),=1;小于時(shí),=0。

2.3 目標(biāo)威脅系數(shù)vj的變化

隨著時(shí)間和分配輪次的推移,系統(tǒng)會(huì)接收到數(shù)個(gè)階段以前的交戰(zhàn)結(jié)果,在此過程中目標(biāo)的威脅會(huì)發(fā)生變化。

當(dāng)目標(biāo)未被分配時(shí),威脅系數(shù)不變;

當(dāng)目標(biāo)已被分配未交戰(zhàn)時(shí),認(rèn)為目標(biāo)的威脅系數(shù)降低,本文中用公式(6)來計(jì)算:

(+1)=()×[1-()]

(6)

當(dāng)目標(biāo)已被分配已交戰(zhàn)且目標(biāo)被摧毀,則將其威脅系數(shù)置0;

當(dāng)目標(biāo)已被分配已交戰(zhàn)但目標(biāo)突破攔截,則重置其威脅系數(shù)并再次加入分配輪次。

2.4 匹配度ωij

匹配度也是有權(quán)二部圖的邊權(quán)值,邊權(quán)值的加和是KM算法求解依據(jù),為了契合目標(biāo)函數(shù)與分配模型,定義:

=×(×)

(7)

定義匹配度矩陣=[]×,用來統(tǒng)一表示武器對應(yīng)目標(biāo)的匹配度,如圖4。

圖4 匹配度矩陣Ω

將匹配度矩陣代入KM算法進(jìn)行求解即可求得目標(biāo)分配結(jié)果。

每個(gè)階段目標(biāo)分配結(jié)果求出之后,若武器對目標(biāo)的單發(fā)射擊攔截概率滿足大于等于攔截概率閾值則輸出攻擊次數(shù)()=1,若不滿足,則根據(jù)式(3)計(jì)算()的值并輸出。然后根據(jù)()和()求出(),并代入目標(biāo)函數(shù)中得到分配方案的作戰(zhàn)收益值。

3 仿真實(shí)驗(yàn)與分析

為驗(yàn)證算法和模型的有效性,分別設(shè)置靜態(tài)WTA和動(dòng)態(tài)WTA仿真示例進(jìn)行實(shí)驗(yàn)分析。實(shí)驗(yàn)環(huán)境為Windows10系統(tǒng)、i7-9750H處理器、16G運(yùn)行內(nèi)存。

3.1 靜態(tài)分配實(shí)驗(yàn)

設(shè)置武器與目標(biāo)的數(shù)量為10×10,由于是靜態(tài)分配實(shí)驗(yàn),所以只有一個(gè)分配階段且僅考慮目標(biāo)威脅系數(shù)和武器對目標(biāo)的攔截概率,具體參數(shù)如表2所示。

表2 攔截概率與威脅系數(shù)

令=×,代入KM算法進(jìn)行求解,實(shí)驗(yàn)結(jié)果如表格3所示。分配求解過程耗時(shí)不到0001 s,分配方案總收益值=5900 4,經(jīng)過分支定界法驗(yàn)算可知所求結(jié)果是最優(yōu)解。

表3 靜態(tài)分配實(shí)驗(yàn)結(jié)果

同樣在10×10規(guī)模的WTA問題中,將KM算法分支定界法(B&B)、遺傳算法(GA)和粒子群算法(PSO)進(jìn)行對比,每種算法都進(jìn)行50次重復(fù)實(shí)驗(yàn),對比結(jié)果如表4所示。

表4 算法性能對比

從實(shí)驗(yàn)結(jié)果可知,分支定界法和KM算法作為精確解法,可以穩(wěn)定求得最優(yōu)解,但KM算法搜索增廣路徑的速度遠(yuǎn)遠(yuǎn)快于分支定界法搜索根節(jié)點(diǎn)的速度。遺傳算法和粒子群算法雖然在計(jì)算效率上優(yōu)于枚舉類算法,但求解效果不太穩(wěn)定,容易陷入局部最優(yōu)。

現(xiàn)代空襲目標(biāo)飛行高度低、速度快、暴露時(shí)間較短,留給指控系統(tǒng)分配決策模塊的時(shí)間往往以毫秒計(jì)算。與其他3種算法相比,KM算法的精度和速度都具有明顯優(yōu)勢,能夠更好地適應(yīng)改進(jìn)后多級動(dòng)態(tài)WTA模型的實(shí)時(shí)性和準(zhǔn)確性要求。

3.2 動(dòng)態(tài)分配實(shí)驗(yàn)

假設(shè)我方防空陣地有5臺地空導(dǎo)彈武器,敵方共有20個(gè)目標(biāo)分批次來襲。武器與目標(biāo)的相關(guān)參數(shù)見表5和表6。

表5 攔截概率與威脅系數(shù)

表6 目標(biāo)來襲時(shí)間

由于KM算法對于低維度WTA問題的求解耗時(shí)幾乎可以忽略不計(jì),所以我方防空系統(tǒng)目標(biāo)分配輪次刷新間隔較短,假設(shè)為1 s。武器平臺～的轉(zhuǎn)火準(zhǔn)備時(shí)間分別為:1 s、1 s、2 s、2 s、3 s。

具體的分配求解過程如下:

第0階段:時(shí)刻0 s,此時(shí)防空發(fā)射區(qū)沒有目標(biāo),不進(jìn)行分配計(jì)算。

第1階段:時(shí)刻5 s,飛入發(fā)射區(qū),分配攔截。

第2階段:時(shí)刻6 s,與飛入發(fā)射區(qū),此時(shí)未完成轉(zhuǎn)火準(zhǔn)備,分配攔截,攔截。

第3階段:時(shí)刻7 s,與飛入發(fā)射區(qū),此時(shí)、、未完成轉(zhuǎn)火準(zhǔn)備,分配攔截,攔截。

第4階段:時(shí)刻8 s,與飛入發(fā)射區(qū),此時(shí)未完成轉(zhuǎn)火準(zhǔn)備,分配攔截,攔截。

……

直到第11階段,完成對所有目標(biāo)的分配，具體見表7。

表7 動(dòng)態(tài)分配實(shí)驗(yàn)結(jié)果

根據(jù)實(shí)驗(yàn)結(jié)果可知,改進(jìn)后的多級動(dòng)態(tài)分配模型由于不用等待結(jié)果判定,可以在有限時(shí)間內(nèi)執(zhí)行更多的分配輪次,即使面對數(shù)倍于己的來襲目標(biāo),也可以高效地進(jìn)行分配求解。

4 結(jié)束語

本文以防空作戰(zhàn)WTA為背景,嘗試對傳統(tǒng)的多級分配模型進(jìn)行改進(jìn),通過設(shè)定可疊加的武器射擊周期,并以固定頻率刷新分配求解輪次的方式,使得改進(jìn)后的模型可以用于目標(biāo)較多且時(shí)間緊迫的作戰(zhàn)場景,為解決動(dòng)態(tài)WTA問題給出了一種可行的方案。在算法求解過程中,采用KM算法以滿足改進(jìn)后多級分配模型對算法的實(shí)時(shí)性和準(zhǔn)確性要求。但實(shí)際作戰(zhàn)中需要考慮的因素還有很多,后續(xù)仍需要進(jìn)一步對模型進(jìn)行細(xì)化和改進(jìn)。