薛 杰,劉高峰,程志鋒,林曉烘
(海軍工程大學(xué),武漢 430000)
由于四面環(huán)海、遠(yuǎn)離大陸、位置突出,島礁機(jī)場、油庫和指揮所等重要設(shè)施極易遭受敵方導(dǎo)彈的精確打擊。面對嚴(yán)重威脅,島礁防空作戰(zhàn)時(shí)應(yīng)樹立“依托礁??兆鲬?zhàn)體系積極防御,區(qū)分遠(yuǎn)中近防御層次系統(tǒng)攔截”的指導(dǎo)思想[1]。近程防空區(qū)作為島礁防空末端屏障,如何有效組織島礁多火力單元攔截來襲導(dǎo)彈目標(biāo)流是島礁近程防空作戰(zhàn)的一個(gè)典型武器目標(biāo)分配(Weapon Target Assignment,WTA)問題。
在WTA建模研究方面,文獻(xiàn)[2]建立了針對近海機(jī)動(dòng)目標(biāo)的無人艇編隊(duì)WTA模型;文獻(xiàn)[3]建立了有多次攔截時(shí)機(jī),可減少火力浪費(fèi)的防空WTA模型;文獻(xiàn)[4]構(gòu)建了雙方動(dòng)態(tài)博弈攻防對抗的WTA模型。這些研究都是針對不同作戰(zhàn)場景展開的,建立的WTA模型考慮的因素也各有不同。在WTA算法研究方面,武器目標(biāo)分配是NP完全問題,解空間的大小隨著武器和目標(biāo)數(shù)量增加而呈指數(shù)級增加,傳統(tǒng)算法如動(dòng)態(tài)規(guī)劃、分支定界法等難以處理高維度WTA問題。智能優(yōu)化算法由于收斂速度快、尋優(yōu)精度高,成為求解WTA問題的主流方法。學(xué)者們對遺傳算法[5-6]、差分進(jìn)化算法[7-8]、粒子群算法[9-10]等進(jìn)行了不同的改進(jìn),但這些算法在平衡全局和局部收斂能力方面仍有所不足。文獻(xiàn)[11]提出了一種新的群智能算法——麻雀搜索算法(Sparrow Search Algorithm,SSA),與其他算法相比,SSA具有收斂速度快的特點(diǎn),已被應(yīng)用于航跡規(guī)劃[12]、圖像處理[13]等領(lǐng)域。
針對島礁近程防空作戰(zhàn)場景,本文建立島礁防空多火力單元武器目標(biāo)分配(M-WTA)模型,設(shè)計(jì)了一種求解所建模型的混合麻雀搜索算法(Hybrid Sparrow Search Algorithm,HSSA),并對模型和算法進(jìn)行了仿真對比分析。
島礁近程防空作戰(zhàn)中的WTA主要研究如何合理運(yùn)用島礁各火力單元打擊敵方來襲目標(biāo),使敵對我造成的損失最小,是島礁防空作戰(zhàn)指揮控制的核心問題。多數(shù)學(xué)者基于目標(biāo)威脅總期望值最小的WTA模型進(jìn)行算法及模型的改進(jìn)研究,該常規(guī)模型為
(1)
式中:m為防御方火力單元數(shù)量;n為來襲目標(biāo)數(shù)量;pi j表示火力單元i對目標(biāo)j的毀傷概率(i=1,2,…,m,j=1,2,…,n);vj表示目標(biāo)j的威脅值;xi j為決策變量,xi j=1,表示分配火力單元i攻擊目標(biāo)j,xi j=0,表示不分配火力單元i攻擊目標(biāo)j;Wi表示火力單元i可用彈藥數(shù)量;Tj表示攔截目標(biāo)j的火力單元數(shù)量上限。
實(shí)際島礁防空作戰(zhàn)中,由于發(fā)射時(shí)間和航路、速度等因素的不同,來襲導(dǎo)彈目標(biāo)到達(dá)島礁防御陣地的時(shí)間存在差異,同一時(shí)段先后到來的導(dǎo)彈目標(biāo)形成一個(gè)目標(biāo)流。常規(guī)模型沒有考慮到同一時(shí)間段內(nèi)的來襲目標(biāo)抵達(dá)陣地存在先后次序,默認(rèn)這些目標(biāo)是同時(shí)到達(dá)的,而且未考慮火力單元轉(zhuǎn)移火力攔截情形,無法直接給出火力單元轉(zhuǎn)移火力攔截的WTA方案。應(yīng)用常規(guī)模型求解島礁防空WTA問題,生成的WTA方案難以符合島礁防空實(shí)際,可能造成對導(dǎo)彈目標(biāo)的漏防,防空作戰(zhàn)效能難以保證。
假設(shè)防御方用1個(gè)可以轉(zhuǎn)移火力攔截的火力單元攔截2個(gè)先后到來的導(dǎo)彈目標(biāo),先到目標(biāo)威脅值低于后到目標(biāo),兩者抵達(dá)的時(shí)間間隔小于火力單元轉(zhuǎn)移火力時(shí)間。按照常規(guī)模型,在對2個(gè)目標(biāo)毀傷概率相同的情況下,解算的WTA方案是直接分配火力給后到的目標(biāo),然而很顯然,最優(yōu)的方案應(yīng)該是先攔截先到目標(biāo),再轉(zhuǎn)火攔截后到目標(biāo)。出現(xiàn)不合理分配結(jié)果問題的原因有3點(diǎn):1)目標(biāo)函數(shù)的威脅值vj是一個(gè)常數(shù),無法反映目標(biāo)到達(dá)時(shí)間先后對目標(biāo)威脅程度的影響;2)沒有火力單元轉(zhuǎn)移火力時(shí)間的約束條件,無法判定火力單元轉(zhuǎn)移火力攔截的可能性和次序;3)模型對應(yīng)的WTA方案需要進(jìn)行二維編碼和尋優(yōu),增大了求解難度。對此,需要針對島礁防空作戰(zhàn)的實(shí)際情況,設(shè)計(jì)島礁防空WTA模型和求解算法。
島礁防空是一類特殊的要地防空問題,縱深受限、面積狹小,機(jī)場、油庫等重要設(shè)施較為集中。因此,島礁火力單元通常進(jìn)行線式交叉部署。島礁防空作戰(zhàn)殺傷區(qū)(火力單元不低于某一概率殺傷目標(biāo)的區(qū)域)如圖1所示。其中:C1表示防空火力單元?dú)麉^(qū)遠(yuǎn)界,對應(yīng)武器目標(biāo)分配始線;C2表示防空火力單元?dú)麉^(qū)近界,對應(yīng)武器目標(biāo)分配終線。
圖1 島礁防空殺傷區(qū)示意圖Fig.1 Diagram of the reef-island air defense zone
根據(jù)上文中對不合理分配結(jié)果分析的原因1),定義威脅函數(shù)vj(tj),vj(tj)是對靜態(tài)威脅值vj的修正,表示目標(biāo)j的動(dòng)態(tài)威脅程度。vj(tj)的大小不僅與vj正相關(guān),也與目標(biāo)到達(dá)時(shí)間tj有關(guān),對于相同的vj,tj越大,vj(tj)越小,即
vj(t)=vje-α(tj-t0)
(2)
式中:t0表示導(dǎo)彈目標(biāo)到達(dá)島礁防空武器目標(biāo)分配終線時(shí)距離攻擊地點(diǎn)的時(shí)間,應(yīng)滿足tj≥t0;修正系數(shù)α∈(0,1),其大小根據(jù)島礁防空實(shí)際情況進(jìn)行調(diào)整,以確保多火力單元能對接續(xù)到來的導(dǎo)彈目標(biāo)做出合理分配。
根據(jù)上文中對不合理分配結(jié)果分析的原因2),定義火力單元的轉(zhuǎn)移火力時(shí)間ti,ti表示火力單元i前后2次攔截所需轉(zhuǎn)移火力時(shí)間,只有當(dāng)火力單元攻擊的前后2個(gè)目標(biāo)到達(dá)時(shí)間間隔大于該火力單元的轉(zhuǎn)移火力時(shí)間時(shí),才能對其進(jìn)行分配。顯然,不同火力單元的轉(zhuǎn)移火力時(shí)間不相等,由于來襲目標(biāo)之間到達(dá)時(shí)間間隔不同,其可以轉(zhuǎn)移火力分配的目標(biāo)也就不同,即各火力單元首次攔截時(shí)目標(biāo)可行域相同,轉(zhuǎn)移火力攔截時(shí)目標(biāo)可行域是不同的。由此,在常規(guī)模型的基礎(chǔ)上建立對導(dǎo)彈目標(biāo)流進(jìn)行攔截的、包含一次轉(zhuǎn)移火力攔截的多火力單元武器目標(biāo)分配(M-WTA)模型,目標(biāo)函數(shù)為
(3)
式中:i=1,…,m,j=1,…,n時(shí),(xi j)m×n表示各火力單元首次攔截時(shí)的武器目標(biāo)分配情況;i=m+1,…,2m,j=1,…,n時(shí),(xi j)m×n表示各火力單元一次轉(zhuǎn)移火力攔截時(shí)的武器目標(biāo)分配情況,其中,i=m+r(r=1,…,m),對應(yīng)火力單元r。
模型的約束條件如下。
1)轉(zhuǎn)火約束。
轉(zhuǎn)火約束是根據(jù)上文中對不合理分配結(jié)果分析的原因3)建立的,即
|ti j-t(i+m)k|≥τij≠k,i=1,…,m
(4)
式中:ti j表示被火力單元i攔截的目標(biāo)j的到達(dá)時(shí)間;t(i+m)k表示被火力單元i攔截的目標(biāo)k的到達(dá)時(shí)間;τi表示火力單元i的轉(zhuǎn)移火力時(shí)間。式(4)表示只有目標(biāo)j和目標(biāo)k的到達(dá)時(shí)間差大于等于火力單元i的轉(zhuǎn)移火力時(shí)間時(shí)才可進(jìn)行轉(zhuǎn)移火力分配。
2)資源約束。
(5)
(6)
式(5)表示火力平單元i所攻擊的目標(biāo)總數(shù)不能超過其彈藥存量,式(6)表示目標(biāo)j所受攻擊不能超過最大閾值。
3)其他約束。
(7)
表示參數(shù)必須滿足的數(shù)學(xué)約束。
SSA模擬自然界麻雀種群的覓食和反捕食行為,將種群分為發(fā)現(xiàn)者、加入者和警戒者3種,分別對應(yīng)3種搜索策略迭代尋優(yōu)。發(fā)現(xiàn)者由種群中適應(yīng)度高的部分麻雀組成,為種群提供引導(dǎo)作用;加入者為種群除發(fā)現(xiàn)者外的剩余麻雀,跟隨發(fā)現(xiàn)者進(jìn)行搜索;警戒者為種群隨機(jī)選取的麻雀,如果超過預(yù)警值,則更新對應(yīng)麻雀個(gè)體[11]。
SSA最初用來解決連續(xù)優(yōu)化問題,考慮武器目標(biāo)分配問題是一個(gè)離散組合優(yōu)化問題,以及SSA迭代后期容易陷入局部最優(yōu),提出一種求解M-WTA的混合麻雀搜索算法(HSSA)。
HSSA中種群的每個(gè)個(gè)體對應(yīng)WTA問題的一個(gè)解,采用整數(shù)編碼方式對種群個(gè)體進(jìn)行編碼。在m個(gè)火力單元攔截n個(gè)導(dǎo)彈目標(biāo)的WTA問題中,每個(gè)個(gè)體都是2m維的整數(shù)向量,h表示種群中個(gè)體編號,則個(gè)體h表示如下
Xh=(xh1,xh2,…,xh2m)
(8)
(9)
式中:Xh表示個(gè)體h;xhi表示個(gè)體h對應(yīng)的WTA方案中由火力單元i攔截的目標(biāo)的編號,xhi=0,表示火力單元i不進(jìn)行攔截;Z表示整數(shù)集;P,Q,S,W表示滿足約束條件的值域;i∈P,表示火力單元i首次攔截;i∈Q,表示火力單元(i-m)轉(zhuǎn)火攔截。假設(shè)m=3,n=6,火力單元均滿足轉(zhuǎn)火約束,編碼操作如圖2所示。
圖2 種群個(gè)體編碼Fig.2 Individual coding in population
由圖2可知,WTA方案為{W1:T2→T4,W2:T5→T6,W3:T1→T3},則根據(jù)整數(shù)編碼對應(yīng)的個(gè)體向量為X=(2,5,1,4,6,3)。
群智能算法的適應(yīng)度是評判種群中個(gè)體性能的唯一指標(biāo),SSA適應(yīng)度越高的個(gè)體代表其尋找食物能力越強(qiáng)。M-WTA模型屬于多約束最小優(yōu)化模型,目標(biāo)函數(shù)值越小,對應(yīng)算法中個(gè)體適應(yīng)度越高,通過增加懲罰項(xiàng)可將所建多約束模型轉(zhuǎn)化為無約束模型,則由式(3)~(7)得適應(yīng)度函數(shù)為
minF(X)=F1(X)+M·(G1(X)+G2(X)+G3(X))
(10)
式中:xi或xi+m表示種群某一個(gè)體對應(yīng)WTA方案中,火力單元i所攻擊的目標(biāo)編號;懲罰因子M是常數(shù),為滿足約束條件,一般取較大值,使得懲罰項(xiàng)數(shù)的值數(shù)倍于目標(biāo)函數(shù)值。由式(10)可以看出,懲罰項(xiàng)的目的在于限制非可行解,如果生成解滿足約束條件,個(gè)體適應(yīng)度不會(huì)獲得獎(jiǎng)勵(lì);但是如果違反約束條件,個(gè)體適應(yīng)度將會(huì)受到懲罰。
SSA的3種搜索策略容易使算法在迭代后期陷入局部最優(yōu),因此設(shè)計(jì)以下3種改進(jìn)策略。
1)精英遺傳變異策略。
SSA發(fā)現(xiàn)者策略會(huì)使得生成解隨迭代次數(shù)的增加趨于零,發(fā)現(xiàn)者個(gè)體間缺乏信息交流,算法容易陷入局部最優(yōu)。針對上述問題,引入遺傳算法的交叉和變異算子,即
X′(t+1)=Xr1(t)°B1+Xr2(t)°(1-B1)
(11)
X(t+1)=X′(t+1)°B2+YR1≤Pc
(12)
其中:Xr1(t)和Xr2(t)表示從當(dāng)前發(fā)現(xiàn)者中隨機(jī)選取的個(gè)體編碼方案;B1,B2和Y為1×m的向量,B1中每個(gè)元素隨機(jī)賦值為0或1,B2中隨機(jī)選取某個(gè)元素賦值為0,其余均為1,Y對應(yīng)于B2中值為0的位置根據(jù)可行域隨機(jī)賦值,其余位置均為0;“°”為哈達(dá)瑪積。算法采用多點(diǎn)交叉和單點(diǎn)變異的方式,式(11)表示從當(dāng)前發(fā)現(xiàn)者中隨機(jī)選取父代個(gè)體多點(diǎn)交叉生成子代,式(12)表示隨機(jī)數(shù)R1低于變異概率Pc時(shí)對子代個(gè)體進(jìn)行單點(diǎn)變異。
2)隨機(jī)跟隨進(jìn)化策略。
為提高算法全局收斂能力,設(shè)計(jì)跟隨進(jìn)化和隨機(jī)進(jìn)化策略。若隨機(jī)數(shù)R2 (13) 進(jìn)行位置更新;若R2≥GT,加入者以隨機(jī)生成的一個(gè)解為搜索位置,通過 X(t+1)=γX(t)+(1-γ)·Xbest(t)R2≥GT (14) 進(jìn)行位置更新。式中:β∈(0,1)和γ∈(0,1)均為調(diào)整因子;Xbest(t)為當(dāng)前適應(yīng)度最優(yōu)個(gè)體;GT∈(0,1),為變異閾值;Rand為通過種群初始化方式隨機(jī)生成的一個(gè)解。 3)最優(yōu)搜索替代策略。 SSA警戒者策略通過新個(gè)體隨機(jī)替代種群中部分原有個(gè)體,本質(zhì)上是簡單的隨機(jī)替代,很難有效跳過局部最優(yōu)。提出一種危險(xiǎn)替代選擇策略,選取種群當(dāng)前適應(yīng)度最優(yōu)的個(gè)體進(jìn)行隨機(jī)搜索,通過 X(t+1)=Xbest(t)°B+Z (15) 生成N3個(gè)子代個(gè)體,當(dāng)前最優(yōu)個(gè)體與當(dāng)前所有子代個(gè)體組成備選集合;通過 (16) 基于模運(yùn)算選擇與當(dāng)前最優(yōu)個(gè)體漢明距離最大的前n-1個(gè)個(gè)體為子代,同時(shí)當(dāng)前最優(yōu)個(gè)體Xbest保留至子代。式中:B和Z均為1×m維向量,B中每個(gè)元素隨機(jī)賦值0或1,Z對應(yīng)于B中值為0的位置根據(jù)種群個(gè)體可行域隨機(jī)賦值,其余位置均為0;Dh表示子代個(gè)體h與當(dāng)前最優(yōu)個(gè)體的漢明距離。 HSSA的步驟如下: 1)初始化種群,計(jì)算個(gè)體適應(yīng)度值; 2)根據(jù)適應(yīng)度確定發(fā)現(xiàn)者、加入者位置; 3)根據(jù)式(11),(12)執(zhí)行精英遺傳變異策略; 4)根據(jù)式(13),(14)執(zhí)行隨機(jī)跟隨進(jìn)化策略; 5)根據(jù)式(15),(16)執(zhí)行最優(yōu)搜索替代策略; 6)得到當(dāng)前更新后的子代位置; 7)重復(fù)3)~6),直至達(dá)到最大迭代次數(shù); 8)輸出最佳適應(yīng)度值和對應(yīng)個(gè)體。 HSSA求解M-WTA模型的基本流程如圖3所示。 圖3 求解流程圖Fig.3 Flow chart of calculation 為驗(yàn)證M-WTA模型和HSSA的合理性和有效性,以島礁火力單元反多導(dǎo)彈空襲為背景設(shè)計(jì)仿真實(shí)驗(yàn)。實(shí)驗(yàn)在i5-6300HQ CPU,主頻2.3 GHz,內(nèi)存8 GiB,Matlab2016b環(huán)境下進(jìn)行。算法參數(shù)如下:種群數(shù)量N=40,其中,發(fā)現(xiàn)者N1=8,加入者N2=32,警戒者N3=4,調(diào)整因子β=0.6,γ=0.9,最大迭代次數(shù)Mgen=400,修正系數(shù)α=0.1。 表1 模型仿真結(jié)果Table 1 Results of model simulation 由表1可知,常規(guī)模型生成的WTA方案只對威脅大的T1,T3兩個(gè)目標(biāo)進(jìn)行了攔截,沒有考慮導(dǎo)彈目標(biāo)到達(dá)順序的影響,無法對目標(biāo)進(jìn)行轉(zhuǎn)移火力分配,造成了目標(biāo)T2的漏防;而M-WTA模型生成的WTA方案滿足本想定的約束條件,考慮到了導(dǎo)彈目標(biāo)流先后到達(dá)的順序,并且進(jìn)行了一次轉(zhuǎn)移火力分配,對本想定中的所有目標(biāo)均進(jìn)行了有效攔截,極大地提高了島礁多火力單元的整體防空作戰(zhàn)效能。 算法實(shí)驗(yàn)包含火力單元數(shù)量小于、等于、大于導(dǎo)彈目標(biāo)數(shù)量3種情形,對應(yīng)6個(gè)火力單元分別攔截4,6,8枚來襲導(dǎo)彈目標(biāo)3種想定,火力單元轉(zhuǎn)移火力時(shí)間矩陣τ=[334466],武器目標(biāo)分配時(shí)間線t0=10,毀傷概率pi j=0.45+r(0.95-0.45),目標(biāo)威脅值vj=0.5+r(0.9-0.5),目標(biāo)到達(dá)時(shí)間tj=ceil(t0+10·r),r∈(0,1),為隨機(jī)數(shù)。 選取SSA,HSSA,F(xiàn)WA進(jìn)行性能對比,使用3.1節(jié)的種群初始化方式,適應(yīng)度函數(shù)采用式(14),算法參數(shù)與前文一致,每種算法獨(dú)立運(yùn)行20次。采用置信度為5%的t檢驗(yàn)評估HSSA與其他算法的顯著性差異,結(jié)果以“平均值±標(biāo)準(zhǔn)差”形式表示,“+/≈/-”表示HSSA“優(yōu)于/近似/劣于”所對比算法,黑體部分為最優(yōu)值,“mW-nT”表示該組實(shí)驗(yàn)包含m個(gè)火力單元和n個(gè)導(dǎo)彈目標(biāo)。 表2所示為3種算法的仿真結(jié)果。 表2 算法仿真結(jié)果Table 2 Results of algorithm simulation 由表2可知,根據(jù)t檢驗(yàn)評估結(jié)果,HSSA在3種想定情形下均獲最優(yōu),只有火力單元數(shù)量小于目標(biāo)數(shù)量時(shí),HSSA與FWA的結(jié)果近似相等。 盒圖由5個(gè)數(shù)值點(diǎn)構(gòu)成,分別是最小觀察值、25%分位數(shù)Q1、中位數(shù)、75%分位數(shù)Q3及最大觀察值,可直觀反映原始數(shù)據(jù)分布特征,便于數(shù)據(jù)比較。如圖4所示。 圖4 算法盒圖Fig.4 Boxplots of different algorithms 由圖4可以看出:當(dāng)火力單元數(shù)量大于導(dǎo)彈目標(biāo)數(shù)量時(shí),HSSA和FWA算法最優(yōu)解分布情況近似,2種算法穩(wěn)定性較高;當(dāng)火力單元數(shù)量小于等于導(dǎo)彈目標(biāo)數(shù)量時(shí),HSSA最優(yōu)適應(yīng)度值的中位數(shù)、IQR和最大觀察值3項(xiàng)明顯小于其他算法,異常值少,分布更集中。綜上說明,HSSA尋優(yōu)穩(wěn)定性更好。 圖5所示為算法收斂曲線。 圖5 算法收斂曲線Fig.5 Convergence curves of the algorithms 由圖5可知:當(dāng)火力單元數(shù)量小于目標(biāo)數(shù)量時(shí),HSSA的曲線收斂速度并未明顯優(yōu)于其他算法;當(dāng)火力單元數(shù)量大于等于目標(biāo)數(shù)量時(shí),HSSA曲線比其他算法更快收斂和穩(wěn)定在最小值附近。綜上說明,HSSA比其他算法具有更快收斂速度。 綜合以上結(jié)果可知,HSSA在求解M-WTA模型時(shí),具有優(yōu)異的收斂速度和尋優(yōu)精度。HSSA的種群初始化方式提高了生成解的質(zhì)量,利用精英遺傳變異策略提高了算法局部收斂能力,隨機(jī)跟隨進(jìn)化策略平衡了全局收斂能力,利用最優(yōu)搜索替代策略提高了種群多樣性,通過3種策略的有機(jī)結(jié)合,提高了算法尋優(yōu)的速度和精度。同時(shí)可以看出,HSSA收斂曲線不夠圓滑,這是由于火力單元一次轉(zhuǎn)移火力攔截時(shí)可行解的值域與火力單元首次攔截的目標(biāo)分配情況存在關(guān)聯(lián),導(dǎo)致對火力單元轉(zhuǎn)移火力攔截求解時(shí)的效率略有降低。 本文為提高島礁多火力單元的整體防空作戰(zhàn)效能,建立了對多導(dǎo)彈目標(biāo)流可進(jìn)行一次轉(zhuǎn)移火力分配的多火力單元武器目標(biāo)分配的準(zhǔn)動(dòng)態(tài)模型,設(shè)計(jì)了一種求解多火力單元武器目標(biāo)分配模型的混合麻雀搜索算法,該算法通過3種改進(jìn)的尋優(yōu)策略,極大地提高了全局搜索能力。仿真結(jié)果證明,本文模型和算法可以有效地求解島礁M-WTA問題。但是,由于多火力單元武器目標(biāo)分配模型的部分參數(shù)之間存在耦合信息,導(dǎo)致求解效率降低,下一步工作將繼續(xù)優(yōu)化模型并改進(jìn)求解算法。3.4 算法步驟
4 仿真對比分析
4.1 求解流程
4.2 模型可行性仿真分析
4.3 算法性能對比分析
5 結(jié)束語