復(fù)合打擊下具有多次攔截時機(jī)的火力分配問題

馮超， 景小寧

空軍工程大學(xué) 航空航天工程學(xué)院， 西安 710038

復(fù)合打擊下具有多次攔截時機(jī)的火力分配問題

馮超， 景小寧*

空軍工程大學(xué) 航空航天工程學(xué)院， 西安 710038

針對傳統(tǒng)火力分配模型容易造成資源浪費(fèi)的問題，將火力單元以組為單位，以最大化殺傷概率為目標(biāo)，構(gòu)建一種具有多次攔截時機(jī)的動態(tài)火力分配模型；考慮到組內(nèi)火力單元復(fù)合打擊的情況，使用Kuhn-Munkres算法，優(yōu)先將目標(biāo)分配給復(fù)合打擊效果大的目標(biāo)；在此基礎(chǔ)之上，設(shè)計(jì)了一種基于遺傳算法(GA)的Anytime算法，引入了元級控制，提出一種任意時刻算法停機(jī)時刻的判定方法；仿真實(shí)驗(yàn)驗(yàn)證了模型優(yōu)越性以及算法的合理性，對火力分配任意時刻算法使用元級控制可以有效提高解的效用。

火力分配； 復(fù)合打擊； Anytime算法； 元級控制； 多次攔截時機(jī)

火力分配，作為作戰(zhàn)決策中的一個重要環(huán)節(jié)，是指通過合理的分配手段，將有限的武器資源分配給相應(yīng)的目標(biāo)，以最大化對敵方的殺傷效果[1]。模型與算法是目前研究火力分配問題中的兩大熱點(diǎn)。

模型研究的重點(diǎn)主要是動態(tài)火力分配模型的構(gòu)建。動態(tài)火力分配相對于靜態(tài)火力分配需要考慮離散時間段武器目標(biāo)的分配[2]。文獻(xiàn)[3]提出一種分階段動態(tài)火力分配模型，將動態(tài)火力分配分為一個個階段，利用動態(tài)規(guī)劃的思想處理每個階段目標(biāo)的分配問題，雖然建立了一般意義上的動態(tài)火力分配模型，但是并沒有提出合適的方法求解動態(tài)模型；文獻(xiàn)[4]將火力分配過程視為馬爾可夫模型，并利用馬爾可夫決策過程進(jìn)行研究，但是所建立的模型約束過多，在目標(biāo)個數(shù)較大的情況下，計(jì)算量大且效率低，不具有實(shí)戰(zhàn)價(jià)值。針對動態(tài)火力分配問題，本文將火力單元分組，以組為單位進(jìn)行分配，考慮到目標(biāo)到達(dá)不同火力單元具有時間差的特點(diǎn)，建立了一種考慮多次攔截時機(jī)的動態(tài)火力分配模型，具有一定的實(shí)戰(zhàn)價(jià)值。一般情況下，關(guān)于火力分配的文獻(xiàn)[5-10]大多認(rèn)為火力打擊行動之間是相互獨(dú)立的，并沒有考慮到復(fù)合打擊的問題，而本文在同組火力單位中將考慮復(fù)合打擊的情況。

對算法的研究，動態(tài)火力分配問題是一個多參數(shù)、多約束的NP-完全問題[11]，具有復(fù)雜度高、計(jì)算量大的特點(diǎn)，使用單純型法、分解算法以及隱枚舉法等傳統(tǒng)求解模型不能滿足實(shí)際需求；近年也涌現(xiàn)出了許多智能算法，例如：遺傳算法(Genetic Algorithm, GA)[12]、蟻群算法[13]、粒子群算法[14]、多目標(biāo)進(jìn)化算法[15]等；文獻(xiàn)[16]便提出使用Anytime算法求解動態(tài)火力分配模型。本文根據(jù)建立的具有多次攔截時機(jī)火力分配模型，設(shè)計(jì)一種多次攔截時刻的改進(jìn)遺傳算法(Modified Genetic Algorithm at Multiple Interception Opportunities, MIO-MGA)。最后，對MIO-MGA算法引入元級控制(Meta-level Control)，并且設(shè)計(jì)了一種算法停機(jī)時刻的判定方法。

1 火力分配模型

防空作戰(zhàn)火力分配的主要原則是：優(yōu)先打擊殺傷概率大的目標(biāo)，盡量減少己方武器消耗，使得全局達(dá)到最優(yōu)分配。在實(shí)際防空作戰(zhàn)中，敵方目標(biāo)進(jìn)入我方火力覆蓋區(qū)域是有時間差的?？紤]這一特點(diǎn)，本文將我方作戰(zhàn)的火力單元以組為單位進(jìn)行劃分，使用不同火力單元組對同一目標(biāo)進(jìn)行多次打擊。不僅可以充分提高我方對敵機(jī)整體的打擊效果，并且能夠減少我方武器消耗，還為每個火力單元贏得了寶貴的準(zhǔn)備時間，使整體達(dá)到了最優(yōu)的分配；在火力單元組內(nèi)，模型考慮了不同武器攻擊時復(fù)合打擊的問題，求解出火力單元組內(nèi)復(fù)合打擊條件下的最大毀傷效果。

1.1 模型的建立

根據(jù)實(shí)際防空作戰(zhàn)中，目標(biāo)到達(dá)不同火力單元攻擊范圍有時間差的特點(diǎn)，可以使用不同火力單元對同一目標(biāo)進(jìn)行多次打擊。假如通過某種約束，使打擊相同目標(biāo)的火力單元在不同時刻進(jìn)行打擊，則火力單元具有多次攔截時機(jī)。如圖1所示，目標(biāo)從右向左通過火力單元A與B。在t1時刻，火力單元A可以對目標(biāo)進(jìn)行攻擊。如果沒有擊落目標(biāo)，那么在t2時刻目標(biāo)進(jìn)入火力單元B的攻擊范圍，火力單元B也可以攻擊目標(biāo)。如果時間間隔足夠長，火力單元A完成裝彈，那么在時刻t2，火力單元A還可以對目標(biāo)進(jìn)行第二次打擊。如果設(shè)置合適的時間間隔，可以使火力單元多次打擊目標(biāo)，不僅節(jié)約彈藥，更為火力單元贏得寶貴的裝填彈藥的時間。

圖1 火力單元多次攔截時機(jī)示意圖 Fig.1 Schematic diagram of fire unit at multiple interception opportunities

圖2 火力單元組示意圖Fig.2 Schematic diagram of fire unit group

(1)

若目標(biāo)Nj的價(jià)值為vj，則本文建立的考慮多次攔截時機(jī)的火力分配模型為

(2)

約束如下：

1) 決策變量為0-1整數(shù)，即xij={0,1}。

1.2 毀傷效果計(jì)算

本文考慮火力單元組內(nèi)復(fù)合打擊的情況。在實(shí)際作戰(zhàn)中，復(fù)合打擊被廣泛使用，對同一目標(biāo)同時使用兩種或兩種以上武器進(jìn)行打擊，造成的殺傷效果遠(yuǎn)遠(yuǎn)高于分別使用武器進(jìn)行攻擊。例如，在打擊堅(jiān)固防御工事下的有生力量時，可以首先使用穿甲彈藥對工事進(jìn)行破壞，在打開一個缺口后，投放航爆彈鉆入工事進(jìn)行內(nèi)部打擊，造成預(yù)定的殺傷效果。這兩種武器就存在復(fù)合打擊的情況。為簡化模型，本文將同一火力單元組內(nèi)不同的火力單元各自視作一種武器，只分析兩種不同火力單元之間復(fù)合打擊的情況，對多種火力單元的復(fù)合打擊不做分析。

uj(ailj)=-lb(1-pilj)

(3)

uj(ailj,aikj)=uj(ailj)+uj(aikj)

(4)

uj(ailj,aikj)>uj(ailj)+uj(aikj)

(5)

這里僅考慮復(fù)合打擊效果大于各自獨(dú)立打擊的情況，即復(fù)合打擊正相關(guān)的情況。記復(fù)合打擊效率為γ(ailj,aikj)，則有

uj(ailj,aikj)=(1+γ(ailj,aikj))(uj(ailj)+

uj(aikj))

(6)

1) 若火力單元組內(nèi)火力單元個數(shù)為偶數(shù)

圖3 火力單元組復(fù)合打擊拓?fù)浣Y(jié)構(gòu) Fig.3 Topology description of fire unit group in composite strikes

假如Λ?E(G)，?eλ1,eλ2∈Λ，且eλ1與eλ2都沒有相同端點(diǎn)(λ1≠λ2)，則Λ為圖G中的一個對集，而Λ中任意一邊的兩個端點(diǎn)稱為在對集Λ里相配。假如圖G中每一個節(jié)點(diǎn)都被Λ許配，則Λ被稱為完美對集?；魻?Hall)定律表明，二分圖G中，若X與Y是圖G中節(jié)點(diǎn)集合的劃分，則G中存在把X中節(jié)點(diǎn)皆許配的對集的充要條件是，?S?X，|N(S)|≥|S|，N(S)為S中節(jié)點(diǎn)的鄰集。進(jìn)一步可知，假如G為d(d>0)次正則二分圖，則G一定存在完美對集。

根據(jù)假設(shè)，加權(quán)無向圖G=(M(G),E(G))描述火力單元在復(fù)合打擊條件下的拓?fù)浣Y(jié)構(gòu)滿足存在完美對集條件，可以使用Kuhn-Munkres算法求解完美對集，進(jìn)而求解全局打擊效果最大的打擊方案。為方便計(jì)算，需要引入可行節(jié)點(diǎn)標(biāo)號與相等子圖的概念。

定義1(可行頂點(diǎn)標(biāo)號)：假如存在映射φ∶M(G)→R，使得?x∈X，y∈Y，φ(x)+φ(y)≥uj(x,y)成立，則稱φ為二分圖G的可行頂點(diǎn)標(biāo)號。令

Eφ={x,y|x,y∈E(G),φ(x)+φ(y)≥

uj(x,y)}

(7)

稱以Eφ為邊集的G的生成子圖為相等子圖，以Gφ表示。

這里給出Kuhn-Munkres算法的具體計(jì)算過程。

步驟1選取初始可行頂點(diǎn)標(biāo)號φ，得到Gφ，確定對集Λ。

步驟2假如X中的頂點(diǎn)被Λ全部許配，停機(jī)并輸出結(jié)果，則圖G中權(quán)最大的完美對集即為Λ；否則，任取Gφ中一未被Λ許配的頂點(diǎn)q，令S={q}，B=?。

步驟3假如NGφ(S)?B(NGφ(S)為Gφ中S的相鄰節(jié)點(diǎn)集合)，轉(zhuǎn)步驟4；假如NGφ(S)=B，令

(8)

(9)

并轉(zhuǎn)步驟2。

2) 若火力單元組內(nèi)火力單元個數(shù)為奇數(shù)

本節(jié)給出求解火力單元組內(nèi)復(fù)合打擊效果的Kuhn-Munkres算法步驟，需要討論算法的時間復(fù)雜度。對于Kuhn-Munkres算法步驟，每個頂點(diǎn)都需要作一次可增廣軌，所以有n個循環(huán)。在每個循環(huán)內(nèi)部，在無法得到一條可增廣軌時(該情況下的時間復(fù)雜度為O(n))，需要新加入一個點(diǎn)κ，然后重新尋找可增廣軌。一次最少加入1個點(diǎn)，所以最多加入n次。每次重新尋找可增廣軌的時間復(fù)雜度為O(n)，更新頂點(diǎn)標(biāo)號需要掃描每一條邊的時間復(fù)雜度為O(n2)，所以迭加起來后的復(fù)雜度為O(n)*O(n)*O(n2)。綜合考慮，標(biāo)準(zhǔn)Kuhn-Munkres算法總時間復(fù)雜度為O(n4)。

若對標(biāo)準(zhǔn)Kuhn-Munkres算法進(jìn)行工程改進(jìn)，可以在每個Y頂點(diǎn)上定義一個函數(shù)slack(·)。當(dāng)計(jì)算增廣軌時，首先令函數(shù)slack(·)為一極大值；在每次尋找增廣軌的過程中，時刻檢查邊e(i,j)，假如相等子圖中沒有此條邊，則令slack(j)等于原值與X(i)+Y(j)-u(i,j)中的較小的一個數(shù)值。通過設(shè)置函數(shù)slack(·)，可以降低修改頂標(biāo)的復(fù)雜度。將標(biāo)準(zhǔn)Kuhn-Munkres算法的時間復(fù)雜度降低到O(n3)。

雖然Kuhn-Munkres算法的時間復(fù)雜度較高，但是在實(shí)際作戰(zhàn)中，己方的火力單元個數(shù)不會很大，并且考慮到式(2)中的約束條件式(3)，使得每個火力單元組內(nèi)的火力單元個數(shù)也不會很大；一般火力單元組內(nèi)的火力單元個數(shù)小于6，而這個復(fù)雜度是可以接受的。

2 帶元級控制的Anytime算法

根據(jù)本文的假設(shè)，進(jìn)入火力單元防區(qū)目標(biāo)的進(jìn)入方向是確定的，但是并沒有確定單批目標(biāo)Nj進(jìn)入防區(qū)的時間。合適的火力分配方案需要在目標(biāo)Nj進(jìn)入火力單元防區(qū)前制定出來，即每個目標(biāo)均有一個截止時間，所用算法應(yīng)使當(dāng)前目標(biāo)分配結(jié)果運(yùn)行的時間少于當(dāng)前目標(biāo)的截止時間，這要求算法能夠?qū)崟r地給出計(jì)算結(jié)果。一般文獻(xiàn)[16,18]求解此類問題時，均使用Anytime算法。在Anytime算法中，解的質(zhì)量與時間成正相關(guān)，計(jì)算時間越長，解的質(zhì)量越好，且算法可以隨時停止并輸出結(jié)果，這個特性對于求解動態(tài)火力模型極其有用。文獻(xiàn)[18]指出，雖然Anytime算法可以確保解的質(zhì)量隨時間增加而增加，但是解的效用不一定會隨時間增加而增加，這時就需要一種元級控制過程來對算法進(jìn)行控制，以便確定算法合適的停機(jī)時刻。

2.1 Anytime算法描述

文獻(xiàn)[18]提出一類基于遺傳算法的Anytime算法，命名為MGA(Modified GA)算法。使用該算法求解帶截止時間約束的火力分配問題，可在執(zhí)行過程中隨時處理新的目標(biāo)。

若初始狀態(tài)為：m個火力單元Mi對n個目標(biāo)Nj進(jìn)行攔截，并為每個目標(biāo)設(shè)置一個截止時刻。

具體算法步驟為：

步驟1初始化n個目標(biāo)的截止時刻數(shù)組，并按照時間先后順序排序。

步驟2設(shè)定MIO-MGA算法中基本遺傳算法的遺傳與變異算子，設(shè)定最優(yōu)個數(shù)數(shù)目以及相應(yīng)算法參數(shù)。

步驟4構(gòu)建染色體長度為火力單元組個數(shù)g的染色體種群，并計(jì)算每個火力單元組中最大的復(fù)合打擊效果。其中，與標(biāo)準(zhǔn)遺傳算法類似，染色體中每個基因位即為目標(biāo)序號，染色體的適應(yīng)度函數(shù)使用式(2)計(jì)算。

步驟5使用式(2)中的約束條件式(3)對染色體種群進(jìn)行篩選。

步驟6對每一代的種群進(jìn)行遺傳操作，將非劣解直接保留到下一代，保證解質(zhì)量非減。若算法滿足Anytime算法元級控制停止條件時，即可停機(jī)并輸出結(jié)果，否則轉(zhuǎn)步驟7。

步驟7使用遺傳操作得到的最優(yōu)解中的染色體中當(dāng)前目標(biāo)所對應(yīng)的基因位即為需要分配的火力單元組。

步驟8若目標(biāo)被分配后，更新截止時刻數(shù)組，并重復(fù)步驟2～步驟7，直到所有目標(biāo)被分配完畢。

其中，篩選方法如下：

2.2 元級控制的改進(jìn)

Anytime算法盡管可以保證解的質(zhì)量會隨時間的增加而增加，但是不能保證解的效用也隨時間的增加而增加。如果對Anytime算法增加元級控制方法，則可以在每個目標(biāo)截止時刻之前即時輸出效用最大的解，將算法的整體效用進(jìn)行優(yōu)化，以提高算法的性能。

文獻(xiàn)[16]給出了Anytime算法的一種元級控制方法。但是對于Anytime停機(jī)時刻的判斷方法并不明確，且存在算法在目標(biāo)截止時刻之前尚不能判斷算法停機(jī)時刻的情況。本節(jié)對文獻(xiàn)[16]中的元級控制方法進(jìn)行改進(jìn)，提出一種Anytime算法停機(jī)時刻新的判定方法。

文獻(xiàn)[19-20]通過定義一個與時間相關(guān)的效用函數(shù)來對Anytime算法進(jìn)行元級控制，用來表示一段時間內(nèi)解的效用數(shù)值。如果某時刻的效用函數(shù)達(dá)到最大值，則在當(dāng)前時刻由Anytime算法計(jì)算出的目標(biāo)分配方案就是最合適的。文獻(xiàn)[18]中所給出的效用函數(shù)由3部分組成：算法運(yùn)行時解的質(zhì)量與實(shí)際最優(yōu)解質(zhì)量的比值、未分配目標(biāo)數(shù)量對于解效用的影響以及目標(biāo)分配時間對于效用的影響。這里直接給出文獻(xiàn)[18]中3個指標(biāo)的計(jì)算公式：

1) 解質(zhì)量與實(shí)際最優(yōu)解質(zhì)量比值對于解效用的影響。

2) 未分配目標(biāo)數(shù)量對于解效用的影響。

3) 目標(biāo)分配時間對于解效用的影響。

對于每個目標(biāo)而言，處理目標(biāo)使用時間的長短也會影響解的效用，該影響可使用公式Uc=-(T*-t)-2計(jì)算，T*為最近的一個截止期。

綜合算法運(yùn)行時解的質(zhì)量與實(shí)際最優(yōu)解質(zhì)量的比值、未分配目標(biāo)數(shù)量與目標(biāo)分配時間對于效用的影響，可以得到關(guān)于時間的效用函數(shù)公式為

U(t)=ω1Uμ(t)+ω2Us(t)+ω3Uc(t)

(10)

式中：ω1、ω2和ω3分別為算法運(yùn)行時解的質(zhì)量與實(shí)際最優(yōu)解質(zhì)量的比值、未分配目標(biāo)數(shù)量與目標(biāo)分配時間對于效用影響的權(quán)重，依據(jù)具體模型設(shè)定。

文獻(xiàn)[18]雖然給出了效用函數(shù)的計(jì)算公式，但是并沒有指出何時效用函數(shù)可以達(dá)到最大值，以及如何判斷算法的停機(jī)時刻。要想求得效用函數(shù)的最大值，必須將目標(biāo)截止時刻之前所有時刻的效用函數(shù)值全部求解出來，但是在截止時刻才得到效用函數(shù)值的最大值已經(jīng)失去了實(shí)際意義。為此，本文給出一種Anytime算法在進(jìn)行元級控制時算法停機(jī)時刻的判定方法。

U(k)=ω1Uμ(k)+ω2Us(k)+ω3Uc(k)

(11)

3 仿真與分析

仿真實(shí)驗(yàn)初始設(shè)定如下：假設(shè)我方有火力單元20個，敵方目標(biāo)個數(shù)為10，每個目標(biāo)到第一個火力單元的截止時間服從均勻分布，區(qū)間范圍為[5,30] s；目標(biāo)到達(dá)每個火力單位之間的時間服從均勻分布，區(qū)間范圍為[5,10] s；每個火力單元對目標(biāo)的毀傷概率服從均勻分布，區(qū)間范圍為[0.2,0.8]；火力單元之間的復(fù)合打擊效率除對角線元素為0外，其余元素在區(qū)間[0,0.5]之間服從均勻分布；目標(biāo)價(jià)值在區(qū)間[10,50]之間服從均勻分布；如果一個舊目標(biāo)被分配完成，一個新目標(biāo)將會產(chǎn)生，直至所有目標(biāo)都分配完成，新目標(biāo)的初始條件同上；式(2)的約束條件式(3)中的常數(shù)項(xiàng)C=2，將火力單元分配給10個舊目標(biāo)后實(shí)驗(yàn)結(jié)束；而采用的遺傳算法中種群的染色體個數(shù)為100，交叉和變異的概率為0.8和0.2；實(shí)驗(yàn)引入元級控制，其中影響權(quán)重ω1，ω2和ω3分別設(shè)定為2，2，0.2；進(jìn)行以下實(shí)驗(yàn)：① 在不進(jìn)行元級控制條件下，分別使用MGA算法和本文給出的MIO-MGA算法求解火力分配問題，此時，Anytime算法的截止時間即為當(dāng)前目標(biāo)的截止時間；在進(jìn)行元級控制的條件下(元級控制停止準(zhǔn)則使用本文給出的停機(jī)準(zhǔn)則)，分別使用MGA算法和MIO-MGA算法求解火力分配問題；② 分兩種情況使用本文給出的MIO-MGA算法求解火力分配問題，一種為不進(jìn)行元級控制，即：MIO-MGA算法的停機(jī)時間為當(dāng)前目標(biāo)的截止時間；另一種為使用本文給出的元級控制方法求解；通過求解目標(biāo)適應(yīng)度和效用值兩個實(shí)驗(yàn)對比元級控制的優(yōu)越性；③ 討論在目標(biāo)數(shù)量較大情況下MGA算法和MIO-MGA算法的性能，即分別使用MGA算法和MIO-MGA算法在目標(biāo)數(shù)量較大情況下求解本文給出的火力分配模型。

3.1 Anytime算法性能對比

1) 在不進(jìn)行元級控制的條件下，測試MGA算法與本文提出的MIO-MGA算法求解火力分配問題的性能。圖4給出了10個舊目標(biāo)被處理完成后，每個目標(biāo)被火力單元打擊造成的毀傷效果，即算法中每個目標(biāo)的適應(yīng)度，其中目標(biāo)序號按照先后被處理的順序排列。

從圖4中可以看出，每個目標(biāo)通過MIO-MGA算法計(jì)算出的適應(yīng)度明顯比通過MGA算法得到的適應(yīng)度高，平均高出12.5%。這是因?yàn)?，MIO-MGA算法相比于MGA算法，通過火力單元分組操作、篩選染色體操作降低了計(jì)算的復(fù)雜度，使得算法的計(jì)算時間相對縮短；而MIO-MGA算法的適應(yīng)度隨時間變化是非負(fù)的，在不進(jìn)行元級控制的情況下，對于同一個目標(biāo)，使用MIO-MGA算法可以多次進(jìn)行計(jì)算，所以得到的解的質(zhì)量相對較好。

圖4 兩種算法求解的毀傷效果對比Fig.4 Contrast for damage effect of two algorithms

2) 在使用本文給出的元級控制方法的條件下，測試MGA算法與本文MIO-MGA算法求解火力分配問題的性能。圖5給出了10個舊目標(biāo)被處理完成后，算法處理每個目標(biāo)所用的時間，即算法迭代的次數(shù)，其中目標(biāo)序號按照先后被處理的順序排列。

圖5 不同目標(biāo)的迭代次數(shù)Fig.5 Iterative times of different targets

圖5驗(yàn)證了使用MIO-MGA算法可以有效降低計(jì)算復(fù)雜度，減少了目標(biāo)計(jì)算的時間。通過引入元級控制，MIO-MGA算法的運(yùn)行時間明顯減少，而解的效用明顯增加。算法迭代次數(shù)平均減少了17.5%。

3.2 元級控制效果對比

分別測試在有元級控制和沒有元級控制條件下，使用MIO-MGA算法求解本文給出的火力分配模型。

圖6給出了10個舊目標(biāo)被處理完成后，每個目標(biāo)被火力單元打擊造成的毀傷效果。由圖6可以看出，在MIO-MGA算法運(yùn)行過程中，元級控制的引入雖然使解的質(zhì)量差于不使用元級控制的MIO-MGA算法(解質(zhì)量平均下降了23.4%)，但是減少了算法運(yùn)行的時間，使得解的效用得到了綜合提升。

圖7給出了10個舊目標(biāo)被處理完成后，每個目標(biāo)當(dāng)時的解的效用值。

圖7說明雖然引入元級控制會降低解的質(zhì)量，但是通過加入元級控制，減少了運(yùn)行時間，提高了解得效用值。如圖7所示，使用元級控制后的算法解的效用值提高了29.8%。這一點(diǎn)在實(shí)戰(zhàn)中相當(dāng)重要，以往的火力分配模型并沒有考慮到火力單元裝填彈藥修整的時間，引入元級控制，可以節(jié)約出大量時間，使得算法更具有實(shí)際意義。

圖6 有無元級控制下的毀傷效果對比Fig.6 Contrast for damage effect with and without meta-level control

圖7 有無元級控制下不同目標(biāo)的效用值Fig.7 Utility of different targets with and without meta-level control

3.3 目標(biāo)數(shù)量較大情況下的算法性能對比

分別測試MGA算法和MIO-MGA算法在目標(biāo)數(shù)量較大情況下算法求解問題的性能，即測試算法實(shí)際運(yùn)行所用的時間。

這里為消除動態(tài)目標(biāo)飛到火力單元上空存在時間差對算法實(shí)際運(yùn)行時間帶來的影響，所以在這個實(shí)驗(yàn)中引入元級控制，計(jì)算帶元級控制的兩種算法在目標(biāo)數(shù)量較大條件下實(shí)際運(yùn)行的時間。測試平臺使用Intel Core i5處理器，運(yùn)行內(nèi)存為4 GB，基于MATLAB 2010編程實(shí)現(xiàn)。圖8分別給出了兩種算法處理目標(biāo)時所運(yùn)行的總時間。其中，兩種算法的總時間是指算法用于求解火力分配模型所用的時間之和，不包括等待目標(biāo)的時間。

圖8 兩種算法運(yùn)行的總時間Fig.8 Total time of two algorithms

從圖8中可以看出，在目標(biāo)數(shù)量較大的情況下，MIO-MGA算法比MGA算法所用的總時間要少。在處理100個目標(biāo)的時候，MGA算法處理一個目標(biāo)平均的時間只有MIO-MGA算法一半。并且隨目標(biāo)數(shù)量的增加，這種差距會逐漸增大，說明了在目標(biāo)數(shù)量較大的情況下，MIO-MGA算法性能遠(yuǎn)遠(yuǎn)好于MGA算法。

4 結(jié) 論

1) 本文建立了一種考慮多次攔截時機(jī)的動態(tài)火力分配模型，通過分批次打擊敵方目標(biāo)，為每個火力單元贏得了寶貴的準(zhǔn)備時間，具有一定的實(shí)戰(zhàn)價(jià)值，也為動態(tài)火力分配的研究提供了一種新的解決思路。

2) 傳統(tǒng)上動態(tài)火力分配算法在目標(biāo)數(shù)量較大情況下，所耗時間極長，不具備實(shí)際意義。而本文改進(jìn)算法大大減少了算法運(yùn)行時間，對于作戰(zhàn)自主控制有一定的參考價(jià)值。

3) 本文在計(jì)算火力單元復(fù)合毀傷效果時，僅僅考慮兩種不同火力單元復(fù)合打擊的情況，沒有分析多個火力單元直接的復(fù)合打擊效果。而實(shí)際作戰(zhàn)中存在多個火力單元復(fù)合打擊的情況，所以在未來的研究中，可以考慮計(jì)算多個火力單元的毀傷效果。

[1] MEHMET A S, KEMAL L. Approximation the optimal mapping for weapon-target assignment by fuzzy reasoning[J]. Information Science, 2014, 255(1): 30-44.

[2] BAYRAK A E, PLOAT F. Employment of an evolutionary heuristic to solve the target allocation problem efficiently[J]. Information Sciences, 2013, 222(3): 675-695.

[3] HOSEIN P, ATHANS M. Preferential defense strategies, Part 2: The dynamic case: LIDS-P-2003[R]. Massachusetts: Massachusetts Institute of Technology, 1990.

[4] 蔡懷平， 劉靖旭， 陳英武. 動態(tài)武器目標(biāo)分配問題的馬爾可夫性[J]. 國防科技大學(xué)學(xué)報(bào)， 2006， 28(3): 124-126.

CAI H P, LIU J X, CHEN Y W. On the Markov characteristic of dynamic weapon target assignment problem[J]. Journal of National University of Defense Technology, 2006, 28(3): 124-126 (in Chinese).

[5] 陳黎， 王中許， 武兆斌， 等. 一種基于先期毀傷準(zhǔn)則的防空火力優(yōu)化分配[J]. 航空學(xué)報(bào)， 2014， 35(9)： 2574-2582.

CHEN L, WANG Z X, WU Z B, et al. A kind of antiaircraft weapon-target optimal assignment under earlier damage principle[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(9): 2574-2582 (in Chinese).

[6] 王少蕾， 陳維義， 顧雪峰. 自適應(yīng)差分進(jìn)化算法求解多平臺多武器-目標(biāo)分配問題[J]. 系統(tǒng)工程與電子技術(shù)， 2013， 35(10)： 2116-2118.

WANG S L, CHEN W Y, GU X F. Solving weapon-target assignment problems based on self-adaptive differential evolution algorithm[J]. Systems Engineering and Electronics, 2013, 35(10): 2116-2118 (in Chinese).

[7] 顧驥， 李相民， 劉立佳， 等. 基于Memetic算法的超視距協(xié)同空戰(zhàn)火力分配[J]. 北京航空航天大學(xué)學(xué)報(bào)， 2014， 40(10): 1424-1426.

GU J, LI X M, LIU L J, et al. Weapon-target assignment based on Memetic optimization algorithm in beyond-visual-range cooperative air combat[J]. Journal of Beijing University of Aeronautics and Astronautics, 2014, 40(10): 1424-1426 (in Chinese).

[8] 賀小亮， 畢義明. 基于模擬退火遺傳算法的編隊(duì)對地攻擊火力分配建模與優(yōu)化[J]. 系統(tǒng)工程與電子技術(shù)， 2014， 36(5): 900-903.

HE X L, BI Y M. Modeling and optimization of formation air-to-ground attack fire distribution based on simulated annealing genetic algorithm[J]. Systems Engineering and Electronics, 2014, 36(5): 900-903 (in Chinese).

[9] 張姣， 王中許， 陳黎， 等. 具有多次攔截時機(jī)的防空火力分配建模及其優(yōu)化方法研究[J]. 兵工學(xué)報(bào)， 2014， 35(10): 1644-1647.

ZHANG J, WANG Z X, CHEN L, et al. Modeling and optimization on antiaircraft weapon-target assignment at multiple interception opportunity[J]. Acta Armamentarii, 2014, 35(10): 1644-1647 (in Chinese).

[10] 張毅， 姜青山， 陳國生. 具有條件風(fēng)險(xiǎn)值的動態(tài)火力分配方法[J]. 系統(tǒng)工程與電子技術(shù)， 2012， 34(2)： 313-316.

ZHANG Y, JIANG Q S, CHEN G S. Dynamic weapon-target assignment with conditional value-at-risk[J]. Systems Engineering and Electronics, 2012, 34(2): 313-316 (in Chinese).

[11] LIOYD S P, WITSENHAUSEN H S. Weapon allocation is NP-complete[C]//Proceedings of the IEEE Summer Simulation Conference. Piscataway, NJ: IEEE Press, 1986: 1054-1058.

[12] LEE Z J, SU S F, LEE C Y. Efficiently solving general weapon-target assignment problem by genetic algorithm with greedy eugenics[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2003, 33(1): 113-121.

[13] 羅德林， 段海濱， 吳順詳， 等. 基于啟發(fā)式蟻群算法的協(xié)同多目標(biāo)攻擊空戰(zhàn)決策研究[J]. 航空學(xué)報(bào)， 2006， 27(6): 1166-1170.

LUO D L, DUAN H B, WU S X, et al. Research on air combat decision-making for cooperative multiple target attack using heuristic ant colony algorithm[J]. Acta Aeronautica et Astronautica Sinica, 2006, 27(6): 1166-1170 (in Chinese).

[14] 李儼， 董玉娜. 基于SA-DPSO混合優(yōu)化算法的協(xié)同空戰(zhàn)火力分配[J]. 航空學(xué)報(bào)， 2010， 31(3)： 626-631.

LI Y, DONG Y N. Weapon-target assignment based on simulated annealing and discrete particle swarm optimization in cooperative air combat[J]. Acta Aeronautica et Astronautica Sinica, 2010, 31(3): 626-631 (in Chinese).

[15] 張瀅， 楊任農(nóng)， 左家亮. 基于分解進(jìn)化多目標(biāo)優(yōu)化算法的火力分配問題[J]. 系統(tǒng)工程與電子技術(shù)， 2014， 36(12)： 2436-2438.

ZHANG Y, YANG R N, ZUO J L. Weapon-target assignment based on decomposition-based evolutionary multi-objective optimization algorithms[J]. Systems Engineering and Electronics, 2014, 36(12): 2436-2438 (in Chinese).

[16] 吳玲， 盧發(fā)興， 賈培發(fā). 動態(tài)武器目標(biāo)分配問題中改進(jìn)遺傳算法的元級控制[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版)， 2008， 48(S2)： 1763-1764.

WU L, LU F X, JIA P F. Meta-level control of the anytime algorithm for the dynamic weapon-target allocation problem[J]. Journal of Tsinghua University (Science & Technology), 2008, 48(S2): 1763-1764 (in Chinese).

[17] 余曉晗, 徐澤水, 劉守生, 等. 復(fù)合打擊下的火力分配方案評估[J]. 系統(tǒng)工程與電子技術(shù), 2014, 36(1): 84-86.

YU X H, XU Z S, LIU S S, et al. Evaluations of fire assignment alternatives in the situation of composite strikes[J]. Systems Engineering and Electronics, 2014, 36(1): 84-86 (in Chinese).

[18] WU L, WANG H Y, LU F X, et al. An anytime algorithm based on modified GA for dynamic weapon-target allocation problem[C]//Proceedings of IEEE World Congress on Computational Intelligence. Piscataway, NJ: IEEE Press, 2008.

[19] ZILBERSTEIN S. Meta-level control of approximate reasoning: A decision theoretic approach[J]. International Symposium on Methodologies for Intelligent System, 1994, 869: 114-123.

[20] HANSEN E A, ZILBERSTEIN S. Monitoring and control of anytime algorithms: A dynamic programming approach[J]. Artificial Intelligence, 2001, 126(1-2): 139-157.

馮超男， 碩士研究生。主要研究方向： 航空兵任務(wù)規(guī)劃與訓(xùn)練效能評估。

Tel.: 029-84787056

E-mail: fengchaoacmi@outlook.com

景小寧女， 博士， 副教授， 碩士生導(dǎo)師。主要研究方向： 航空兵任務(wù)規(guī)劃。

Tel.: 029-84787056

E-mail: jxning157@sina.com

*Correspondingauthor.Tel.：029-84787056E-mail:jxning157@sina.com

Weapontargetassignmentatmultipleinterceptionopportunitiesincompositestrikes

FENGChao,JINGXiaoning*

CollegeofAeronauticsandAstronautics,AirForceEngineeringUniversity,Xi’an710038,China

Adynamicweapontargetassignmentmodelatmultipleinterceptionopportunitiesisconstructedsincethetraditionalweapontargetassignmentmodeliseasytocausewasteofresources.Thefireunitsaregroupedtooptimizethekillprobability.Consideringthecompositestrikesoffireunitsingroups,targetwithbetterstrikeperformanceispreferentiallyassignedbyKuhn-Munkresalgorithm.Ananytimealgorithmbasedongeneticalgorithm(GA)isthendesigned,andmeta-levelcontrolisintroduced.Astoptimingdeterminationmethodofanytimealgorithmisproposed.Simulationexperimentsverifytherationalityofthemodelandalgorithm,andshowthatthealgorithmcanincreaseutilitysignificantly.

weapontargetassignment;compositestrike;anytimealgorithm;meta-levelcontrol;multipleinterceptionopportunity

2015-11-16；Revised2015-12-21；Accepted2016-03-15；Publishedonline2016-03-291455

URL：www.cnki.net/kcms/detail/11.1929.V.20160329.1455.002.html

s：NationalScienceFundforDistinguishedYoungScholars(71501184);AeronauticalScienceFoundationofChina(20155196022)

2015-11-16；退修日期2015-12-21；錄用日期2016-03-15； < class="emphasis_bold">網(wǎng)絡(luò)出版時間

時間：2016-03-291455

www.cnki.net/kcms/detail/11.1929.V.20160329.1455.002.html

國家杰出青年科學(xué)基金 (71501184)； 航空科學(xué)基金 (20155196022)

*

.Tel.：029-84787056E-mailjxning157@sina.com

馮超， 景小寧. 復(fù)合打擊下具有多次攔截時機(jī)的火力分配問題J. 航空學(xué)報(bào)，2016，37(11):3444-3454.FENGC,JINGXN.WeapontargetassignmentatmultipleinterceptionopportunitiesincompositestrikesJ.ActaAeronauticaetAstronauticaSinica,2016,37(11):3444-3454.

http://hkxb.buaa.edu.cnhkxb@buaa.edu.cn

10.7527/S1000-6893.2016.0082

V271.4

A

1000-6893(2016)11-3444-11