孫海文， 謝曉方， 孫濤， 龐威

(1.海軍航空大學(xué) 岸防兵學(xué)院， 山東 煙臺 264001； 2.31102部隊， 江蘇 南京 210000)

0 引言

火力分配是防空作戰(zhàn)中的重要組成部分[1]，它根據(jù)敵我雙方的作戰(zhàn)力量，明確哪些火力單元對哪些目標(biāo)在何時采取何種射擊方案進(jìn)行攔截。

目前，傳統(tǒng)的防空火力優(yōu)化分配模型主要采用毀傷概率越大越好原則[2-3]。當(dāng)處于火力資源相對充足的情況下，也存在很多的火力資源約束條件：文獻(xiàn)[4]限制了攔截同一目標(biāo)的火力單元數(shù)量，并以此對火力優(yōu)化分配進(jìn)行了約束；文獻(xiàn)[5]定義一個毀傷概率均值的概念，即單位火力單元的毀傷概率，將其作為火力優(yōu)化分配模型的原則，利用盡可能少的火力資源達(dá)到最大化的毀傷概率。這些火力優(yōu)化分配模型由于火力資源的約束，往往在有限資源的條件下，利用毀傷概率大的火力單元進(jìn)行目標(biāo)分配[6]，但這忽視了目標(biāo)進(jìn)入火力單元發(fā)射區(qū)的時間，即飛臨時間，當(dāng)這些火力單元分配給更遠(yuǎn)目標(biāo)時將會貽誤戰(zhàn)機(jī)。

此外，防空火力優(yōu)化分配問題是一種整數(shù)型非線性多維組合優(yōu)化決策問題，屬于非確定性(NP)問題[7]，常用求解算法有匈牙利算法[8]、粒子群算法[9-11]、蟻群算法[12]以及遺傳算法[13]等。綜合分析這些方法，主要存在以下兩方面問題：一方面部分方法控制參數(shù)較多，較難調(diào)整出適合的控制參數(shù)來有效地進(jìn)行問題優(yōu)化；另一方面不能有效地平衡全局探索和局部開發(fā)，往往顧此失彼，無法滿足對實(shí)時性及準(zhǔn)確度要求較高的優(yōu)化問題。Yang等[14]提出了一種新的生物啟發(fā)算法，即布谷鳥搜索算法(CSA)，該算法因具有結(jié)構(gòu)簡單、控制參數(shù)少和搜索能力強(qiáng)等優(yōu)點(diǎn)，被廣泛應(yīng)用。文獻(xiàn)[15]提出了基于初始交叉和變異的混合CSA，避免過早收斂，并應(yīng)用于可靠性冗余分配問題。文獻(xiàn)[16]分析了種群規(guī)模對算法性能的影響，提出了采用正交化學(xué)習(xí)的CSA，并對23個基準(zhǔn)問題進(jìn)行了算法測試，結(jié)果表明基于正交化學(xué)習(xí)增強(qiáng)了CSA的探測能力以及收斂性。文獻(xiàn)[17]提出了離散CSA，有效地解決了旅行商問題。文獻(xiàn)[18]提出了一種基于混沌的CSA，有效地提高了CSA的全局探索能力。文獻(xiàn)[19]提出了一種動態(tài)自適應(yīng)CSA，引入Rechenberg的1/5法則和學(xué)習(xí)因子來調(diào)整控制參數(shù)，仿真結(jié)果表明該方法動態(tài)適應(yīng)性強(qiáng)，是一種高效簡便的參數(shù)調(diào)整方法。從這些文獻(xiàn)中可以得到3個主要結(jié)論：1)采用Lévy 飛行[14,20]搜索和偏好隨機(jī)搜索后，都是對每個新解同時修改所有維的值來進(jìn)行比較分析，沒有考慮各維間變化的相互干擾；2)大部分文獻(xiàn)并沒有考慮將多種搜索模型相結(jié)合，提高全局探索能力；3)很少有文獻(xiàn)充分利用種群的規(guī)模和數(shù)量來提高CSA的性能。

綜上所述，本文提出了一種新的火力分配模型，即在傳統(tǒng)模型上設(shè)置聯(lián)合毀傷概率門限，同時加入目標(biāo)飛臨時間參數(shù)，在滿足毀傷概率門限的前提下，選擇目標(biāo)威脅度大、飛臨時間短、火力單元數(shù)量少的分配組合。在此基礎(chǔ)上，提出了一種多種群并行CSA(MPCSA)，該算法引入了多個種群同時對解空間進(jìn)行協(xié)同搜索，通過移民算子進(jìn)行信息相互，各種群采用不同的控制參數(shù)取值和搜索模型；在此基礎(chǔ)上，引入柯西變異算子構(gòu)建新的全局搜索模型，能有效提高算法的全局探索能力；采用貪婪方式對全局探索到的解逐維進(jìn)行更新，保留改善的解并進(jìn)行種群更新，從而提高局部開發(fā)能力。最后，通過仿真分析，驗(yàn)證了所建模型的優(yōu)勢以及MPCSA求解火力優(yōu)化分配問題的有效性和優(yōu)越性。

1 防空火力優(yōu)化分配模型

防空火力優(yōu)化分配應(yīng)遵循的主要原則：1)優(yōu)先對威脅度大的目標(biāo)進(jìn)行攔截[7]；2)充分利用火力單元對不同目標(biāo)的毀傷程度，在滿足毀傷門限要求的條件下，用盡可能少的火力單元進(jìn)行攔截；3)兼顧攔截時機(jī)，優(yōu)先攔截飛臨時間短的目標(biāo)。針對這些原則，本文在傳統(tǒng)防空火力分配模型的基礎(chǔ)上進(jìn)行了改進(jìn)。

假設(shè)某一次編隊防空作戰(zhàn)中，m個空襲目標(biāo)編號為Tj(j=1,2,…,m)，n個火力單元的編號為Fi(i=1,2,…,n)。令xij為決策變量，若第i個火力單元被分配攔截第j個目標(biāo)，則xij=1，否則xij=0；令pij為第i個火力單元對第j個目標(biāo)的毀傷概率。設(shè)Pj為所分配火力對第j個目標(biāo)的聯(lián)合毀傷概率，則

(1)

目標(biāo)j到攔截該目標(biāo)火力單元的飛臨時間之和為

(2)

式中：tij為第j個目標(biāo)到第i個火力單元的飛臨時間。

引入預(yù)先毀傷概率閥值和飛臨時間的火力- 目標(biāo)分配模型：

(3)

(4)

(5)

從(3)式中發(fā)現(xiàn)目標(biāo)函數(shù)Vmax與第j個目標(biāo)的威脅度Wj呈正相關(guān)，而與j(xij)呈負(fù)相關(guān)。這個模型表明火力分配在控制火力數(shù)量的情況下，選擇飛臨時間之和小的火力單元，分配給威脅度大的目標(biāo)。(4)式保證各來襲目標(biāo)分配的火力單元聯(lián)合毀傷概率都達(dá)到預(yù)期毀傷概率門限如果火力- 目標(biāo)分配方案中則該目標(biāo)的分配無效。毀傷概率門限是根據(jù)戰(zhàn)場態(tài)勢由指揮員或指揮系統(tǒng)確定。(5)式表示一個火力單元至多只能分配給一個目標(biāo)。

2 求解防空火力優(yōu)化分配的MPCSA

CSA是一種新的啟發(fā)式算法[21]，其靈感來自于布谷鳥類動物在巢鳥產(chǎn)卵時的占巢寄生行為，即寄生性布谷鳥會將卵放置到宿主巢穴中。CSA利用發(fā)現(xiàn)概率融合了全局隨機(jī)探索和局部隨機(jī)開發(fā)。布谷鳥全局探索采用Lévy飛行模型將有效地對解空間進(jìn)行最優(yōu)解的探索。經(jīng)全局探索得到更新解，根據(jù)發(fā)現(xiàn)概率pa(即各宿主發(fā)現(xiàn)陌生鳥卵的概率)，選取其中一部分進(jìn)行局部開發(fā)。全局探索和局部開發(fā)相結(jié)合將有效地提高算法的收斂速度，具體2種搜索方式如下：

1)基于Lévy飛行的全局探索：

(6)

2) 基于發(fā)現(xiàn)概率pa和偏好隨機(jī)游走的局部開發(fā)：

(7)

在過去的幾十年里，優(yōu)化問題的復(fù)雜性越來越高，進(jìn)化算法也日益增多，Wolpert等[22]證明了沒有哪種算法能適用于所有的優(yōu)化問題。因此，針對不同的問題，需要設(shè)計不同的方法進(jìn)行解決。本文改進(jìn)了全局和局部搜索模式，并引入了多種群并行搜索的思想，以此來提高CSA的尋優(yōu)能力。根據(jù)新思路提出新的全局探索模型，根據(jù)火力優(yōu)化分配的特點(diǎn)，采用貪婪方式逐維進(jìn)行尋優(yōu)；在確定搜索模型的基礎(chǔ)上，另一個新的思路是多種群并行搜索，即建立多個種群，各種群分別采用不同的控制參數(shù)取值和搜索模型進(jìn)行同步搜索，通過移民算子進(jìn)行種群間的相互交流，這種搜索模式兼顧了多種搜索模型的特點(diǎn)，降低了對控制參數(shù)的依賴性，增強(qiáng)了全局探索的能力，提高了收斂速度。

2.1 新全局探索模型

盡管Lévy 飛行模型中步長變化的大小能很好地探索全局空間，但為了進(jìn)一步提高全局探索能力，需要一個更好地探索方式進(jìn)行空間探索。柯西變異算子具有更廣泛的分布范圍，能更快地跳出局部區(qū)域[23]。利用柯西變異算子產(chǎn)生一個柯西分布隨機(jī)數(shù)δ，將這個隨機(jī)數(shù)代入全局探索公式中，產(chǎn)生一個新解。

柯西密度函數(shù)為

(8)

式中：g為尺度參數(shù)，通常取值為1.

柯西分布函數(shù)為

(9)

式中：y∈[0,1]。

根據(jù)(9)式，可得

δ=tan (π(y-0.5)).

(10)

根據(jù)(10)式，可產(chǎn)生一個0～1分布的柯西分布隨機(jī)數(shù)。根據(jù)(6)式可得新的全局探索公式為

(11)

2.2 逐維局部開發(fā)模型

在CSA中，盡管偏好隨機(jī)游走能有效地提高算法尋優(yōu)能力，但火力分配模型屬于多維目標(biāo)函數(shù)，各維變量之間存在相互干擾，該搜索模型對解向量采用整體更新策略，從而影響了算法的收斂速度和解的質(zhì)量。

針對上述問題，引入貪婪式逐維更新的思路。在每一代更新中，從第1維變量開始，更新該維的值，保持其他維的值不變，將其與其他維的值組合成一個新解，并與舊解進(jìn)行比較。若改善當(dāng)前的解，則保留新解，否則放棄當(dāng)前維的更新值，進(jìn)入下一維的操作?；谪澙肥街鹁S更新模式，將有效避免整體更新中各維之間的相互干擾，使得各維共同沿著優(yōu)質(zhì)解的方向變化，從而有效地提高局部開發(fā)能力。

2.3 多種群并行搜索

影響CSA尋優(yōu)能力的因素主要有下列3個方面：

1)由于搜索模型自身結(jié)構(gòu)的限制，單一的搜索模型將很難進(jìn)一步提高搜索能力。

2)算法中存在控制參數(shù)，例如步長控制因子α和縮放因子r，控制參數(shù)不同的取值，將影響步長大小及變化尺度，進(jìn)而可能導(dǎo)致不同的計算結(jié)果。至此，許多學(xué)者對控制參數(shù)的改進(jìn)進(jìn)行了探索，提出了自適應(yīng)參數(shù)控制。但是，控制參數(shù)的設(shè)定往往是結(jié)合實(shí)際問題進(jìn)行多次探索總結(jié)出來的，算法的性能在很大程度上受到控制參數(shù)設(shè)定的影響。

3)種群規(guī)模對算法尋優(yōu)能力也存在較大影響。當(dāng)種群規(guī)模較小時，群體多樣性程度低，個體間競爭性較弱，隨著迭代搜索的進(jìn)行，群體會很快趨于單一化，并終止尋優(yōu)；當(dāng)種群規(guī)模較大時，將造成計算量的增加，影響計算效率。

針對上述問題，本文提出了多種群并行尋優(yōu)的思想，如圖1所示。

該思想具體內(nèi)容如下：

1)突破了傳統(tǒng)CSA僅靠單一種群和單一搜索模型進(jìn)行尋優(yōu)的框架，引入多種群同時進(jìn)行優(yōu)化搜索；為了增強(qiáng)算法的搜索能力，不同的種群賦予不同的搜索模型以及不同的控制參數(shù)。

2)各種群之間是相互獨(dú)立的，為了實(shí)現(xiàn)多種群并行尋優(yōu)，通過移民算子將各種群聯(lián)系起來；最優(yōu)解的獲取是多個種群并行尋優(yōu)的綜合結(jié)果。移民算子將種群進(jìn)化過程中的最優(yōu)個體定期地引入到其他種群中，替換掉目標(biāo)種群中的最差個體，從而實(shí)現(xiàn)多種群之間的信息交換。

3)設(shè)置精華種群，在進(jìn)化的每代中，篩選出其他種群中的最優(yōu)個體放入精華種群中進(jìn)行保存，為了防止破壞和丟失各種群產(chǎn)生的最優(yōu)個體，精華種群不進(jìn)行搜索更新。

總之，引入多個種群同時對解空間進(jìn)行并行搜索，有效地降低了算法控制參數(shù)設(shè)定不當(dāng)對方案優(yōu)化的影響，抑制了未成熟收斂的發(fā)生，兼顧了算法的全局探索和局部開發(fā)能力的均衡。

2.4 基于MPCSA求解火力優(yōu)化分配

綜合以上分析，基于MPCSA求解防空火力優(yōu)化分配的具體步驟如下：

步驟1初始化種群。同時生成M個種群，每個種群的個體數(shù)量為N. 針對整數(shù)型火力優(yōu)化分配問題，采用的編碼可表示為x=[x1x2…xn]，其中xi為0～m之間的整數(shù)，xi=j表示將第i個火力單元分配給第j個目標(biāo)，xi=0表示第i個火力單元沒有分配給任何一個目標(biāo)。

步驟2適應(yīng)度評估。選擇(3)式作為適應(yīng)度函數(shù)，獲取各初始種群中的最優(yōu)個體，并設(shè)置一個精華種群，分別記錄各種群中最優(yōu)個體的適應(yīng)度值和編碼。

步驟3多種群同時進(jìn)行全局探索。一半種群采用(6)式，另一半種群采用(11)式同時進(jìn)行更新，生成多個新種群。其中，各種群的全局探索公式選取不同的控制參數(shù)取值，在更新過程中計算個體適應(yīng)度值，保留改善的解。

步驟4將步驟3中生成的多種群，同時進(jìn)行局部開發(fā)。根據(jù)發(fā)現(xiàn)概率pa以及(7)式，采用貪婪式逐維搜索模型生成多個新種群，同樣在更新過程中計算個體適應(yīng)度值，保留改善的解。至此，該種群完成一次進(jìn)化。

步驟5更新精華種群。將進(jìn)化后的各種群中的最優(yōu)個體保存到精華種群中。

步驟6設(shè)置移民算子。移民算子每隔一定的進(jìn)化代數(shù)，將各種群進(jìn)化過程中的最優(yōu)個體引入其他種群中，替換掉目標(biāo)種群中的最差個體，從而實(shí)現(xiàn)多種群之間的信息交換。

步驟7提取精華種群中的最優(yōu)個體，判斷是否滿足終止條件(通常終止條件有兩種：一種是達(dá)到規(guī)定的進(jìn)化代數(shù)；另一種是在規(guī)定進(jìn)化代數(shù)內(nèi)最優(yōu)個體適應(yīng)度值不發(fā)生變化)，若滿足，則算法終止；若不滿足，則返回執(zhí)行步驟2～步驟6.

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

為了驗(yàn)證本文所提防空火力分配模型的優(yōu)勢以及MPCSA求解該防空火力優(yōu)化分配的有效性和優(yōu)越性，進(jìn)行仿真實(shí)驗(yàn)比較分析。

3.1 防空火力分配模型比較分析

假設(shè)在防空作戰(zhàn)中，某一來襲目標(biāo)進(jìn)入我防區(qū)，在敵目標(biāo)來襲方向上的5個火力單元處于空閑狀態(tài)。各火力單元對來襲目標(biāo)的毀傷概率[p11p21p31p41p51]T=[0.824 0.782 0.683 0.810 0.843]T；來襲目標(biāo)威脅度W1=0.17；來襲目標(biāo)到各火力單元發(fā)射區(qū)時間[t11t21t31t41t51]T=[10 s 16 s 11 s 9 s 13 s]T。

分別采用本文所提防空火力分配模型M1、毀傷概率越大越好模型M2以及文獻(xiàn)[11]所提的帶有火力資源約束的分配模型M3進(jìn)行火力優(yōu)化分配。其中模型M1和M3中的毀傷概率門限為0.9. 3種模型的最優(yōu)分配方案、目標(biāo)毀傷概率以及平均飛臨時間如表1所示。

表1 3種模型的最優(yōu)分配方案、目標(biāo)毀傷概率以及平均飛臨時間

由表1中可知：模型M2采用5個火力單元攔截同一目標(biāo)，雖然目標(biāo)的毀傷概率最高，但火力資源浪費(fèi)最嚴(yán)重，且毀傷概率提高幅度較小(數(shù)量級為10-2)；模型M3采用毀傷概率最高的兩個火力單元攔截同一目標(biāo)，在保持較高毀傷概率的同時節(jié)省了火力資源，但來襲目標(biāo)到兩個火力發(fā)射區(qū)的平均飛臨時間較長，因此會貽誤戰(zhàn)機(jī)。本文所提模型M1在滿足目標(biāo)期望毀傷概率的條件下，采用飛臨時間最短的兩個火力單元對目標(biāo)進(jìn)行攔截，極大地節(jié)省了火力資源，并且不會貽誤戰(zhàn)機(jī)。

表2 模型M1的最優(yōu)分配方案

表3 模型M3的最優(yōu)分配方案

由表2和表3可知：模型M3采用毀傷概率最高的火力單元對各來襲目標(biāo)進(jìn)行攔截，雖然節(jié)省了火力資源，但其不考慮飛臨時間，容易貽誤戰(zhàn)機(jī)；模型M1在滿足目標(biāo)期望毀傷概率的條件下，采用飛臨時間最短的火力單元對目標(biāo)進(jìn)行攔截，極大地節(jié)省了火力資源，同時又不會貽誤戰(zhàn)機(jī)，進(jìn)一步證明了M1的優(yōu)勢性，此外，還證明了MPCSA的有效性。

3.2 MPCSA仿真分析

為了驗(yàn)證本文所提算法的實(shí)用性和優(yōu)越性，分別利用粒子群搜索(PSO)算法、自適應(yīng)遺傳算法(DGA)[3]、CSA、改進(jìn)CSA(ICSA)[25]以及MPCSA對8個來襲目標(biāo)和10個空閑火力單元進(jìn)行火力優(yōu)化分配仿真實(shí)驗(yàn)。PSO和DGA的種群規(guī)模均為50；CSA和ICSA的種群規(guī)模均為20；MPCSA的種群規(guī)模為5，種群數(shù)量為10；迭代次數(shù)均為300次。

圖2所示分別為基于PSO算法、DGA、CSA、ICSA以及MPCSA的防空火力分配優(yōu)化過程。從圖2可見：PSO算法很不穩(wěn)定，而且在接近200代時仍然未穩(wěn)定下來，表明適應(yīng)度值還有上升的可能性，其收斂速度較慢；DGA、CSA、ICSA以及MPCSA的收斂速度均有較好表現(xiàn)(100代以內(nèi))，具體收斂性能排序?yàn)镃SA>MPCSA>ICSA>DGA，其中CSA的收斂性能最好。記錄仿真中各算法的最優(yōu)適應(yīng)度值，如表4所示。

由表4可知，各算法的最優(yōu)適應(yīng)度值從大到小排序?yàn)镸PCSA>ICSA>DGA>PSO算法>CSA，適應(yīng)度值越大，代表分配方案越優(yōu)。盡管MPCSA的收斂性能不是最優(yōu)的，但其收斂速度與DGA、ICSA差距較小，且其最優(yōu)適應(yīng)度值最大，表明MPCSA在保證較高收斂速度的同時，具有較優(yōu)的全局探索能力。

為了進(jìn)一步檢驗(yàn)本文所提MPCSA的尋優(yōu)性能，對PSO算法、DGA、CSA、ICSA以及MPCSA分別進(jìn)行了50次仿真。為保證目標(biāo)分配實(shí)時性，需要算法在較短時間內(nèi)尋找到盡量接近最優(yōu)適應(yīng)度次優(yōu)值。設(shè)置各算法參數(shù)，使其進(jìn)行一次仿真的運(yùn)行時間的大約為1.5 s左右。各算法的蒙特卡洛仿真結(jié)果如圖3～圖7所示。

由圖3～圖7對比可見，5種算法均無法保證每次都找到最優(yōu)適應(yīng)度值，這是因?yàn)闉楸ＷC算法具有較快的運(yùn)行速度，各算法參數(shù)設(shè)置限制了算法找到最優(yōu)適應(yīng)度值的能力。進(jìn)一步分析可知，5種算法每次仿真均能找到可行適應(yīng)度值，其中，MPCSA的最優(yōu)適應(yīng)度值波動幅度較小，數(shù)值較穩(wěn)定。為準(zhǔn)確地比較各算法性能，取5種算法關(guān)鍵性能指標(biāo)的統(tǒng)計結(jié)果，如表5所示。

由表5可知，在相同運(yùn)行時間的50次仿真中，MPCSA適應(yīng)度值的均值最大，標(biāo)準(zhǔn)差最小，且適應(yīng)度值大于0.240 0的次數(shù)明顯高于其他算法，表明MPCSA的全局探索性能較優(yōu)越。

表5 5種算法性能指標(biāo)的統(tǒng)計結(jié)果

為了進(jìn)一步說明MPCSA的性能，各算法分別進(jìn)行50次仿真，在保證適應(yīng)度值大于0.240 0的概率不小于70%的條件下，統(tǒng)計各算法的平均運(yùn)算時間，如表6所示。

由表6可見，在保證較高概率搜索到較優(yōu)解的條件下，MPCSA的平均運(yùn)行時間最短，具有較高的尋優(yōu)效率。

表6 5種算法的平均運(yùn)行時間

綜合上述分析可知：PSO算法雖然表現(xiàn)出較好的全局探索能力，但其收斂速度較慢(迭代次數(shù)達(dá)上千次)；DGA、CSA、ICSA以及MPCSA在收斂速度上均有較好的表現(xiàn)，但DGA、CSA以及ICSA在全局探索中容易陷入局部極值，MPCSA能在迭代25次左右搜索到最優(yōu)解，其收斂性較好，且由表5和表6分析可知，MPCSA方法能有效地平衡全局探索和局部開發(fā)，具有較高的尋優(yōu)效率。

4 結(jié)論

在火力資源相對充足的情況下，本文提出了一種結(jié)合毀傷概率門限、飛臨時間以及威脅度的多約束防空火力分配模型；針對該模型的防空火力優(yōu)化分配問題，提出MPCSA. 在多種群并行性尋優(yōu)的思路基礎(chǔ)上，引入柯西變異算子構(gòu)建新的全局探索模型，并采用貪婪方式進(jìn)行逐維局部開發(fā)。通過仿真實(shí)驗(yàn)，得到以下結(jié)論：

1)在火力資源相對充足的情況下，本文所提火力分配模型能在滿足目標(biāo)期望的毀傷概率門限下，結(jié)合飛臨時間和目標(biāo)威脅度信息，利用盡量少的火力單元，盡早地攔截來襲目標(biāo)。在火力資源節(jié)約和把握戰(zhàn)機(jī)兩個方面，其分配結(jié)果優(yōu)于毀傷概率越大越好模型和文獻(xiàn)[11]所提的具有火力資源約束的分配模型。

2)本文所提出的MPCSA能有效地平衡全局探索和局部開發(fā)，在保證較高收斂速度的同時，提高了全局探索能力。