編隊(duì)防空火力分配建模及其優(yōu)化方法研究

阮旻智，李慶民，劉天華

(海軍工程大學(xué) 兵器工程系，湖北 武漢430033)

在編隊(duì)協(xié)同防空作戰(zhàn)中，如何合理地部署我方兵力來迎接空中威脅目標(biāo)，并確切的指出由哪些武器裝備對(duì)哪些目標(biāo)采取什么樣的方式進(jìn)行攻擊，以協(xié)調(diào)各作戰(zhàn)單元作戰(zhàn)行為的協(xié)調(diào)指揮過程［1］，稱為火力分配(WTA).在未來高技術(shù)條件下的局部海戰(zhàn)中，水面艦艇編隊(duì)將會(huì)面臨十分嚴(yán)峻的空中威脅。防空WTA 是編隊(duì)防空指揮決策中最為關(guān)鍵的問題之一，其目的是在現(xiàn)有防空武器裝備的基礎(chǔ)上，選擇最優(yōu)的WTA 方案，使武器系統(tǒng)對(duì)空中來襲的多批目標(biāo)分配給它們射擊最有利的火力單元［2］，最大限度地發(fā)揮編隊(duì)防空武器的整體作戰(zhàn)效能。

防空WTA 問題實(shí)質(zhì)上是一種整數(shù)型非線性組合優(yōu)化決策問題，屬于N-P 難問題［2］。作為指控系統(tǒng)的一項(xiàng)重要輔助決策功能，WTA 與作戰(zhàn)原則、策略、方案等因素密切相關(guān)，存在大量的變量和參量。因此，除了要建立合理的WTA 模型之外，還要在解算的方法上進(jìn)行探討，嘗試一些新算法。如Kuttar提出的序列算法，分支定界法，但這些算法收斂速度很慢;Castanon 提出用非線性網(wǎng)絡(luò)流程求準(zhǔn)最優(yōu)解的算法，但結(jié)果會(huì)產(chǎn)生較大的誤差;Wacholker 提出了一種神經(jīng)網(wǎng)絡(luò)的解法，此方法有時(shí)得不到穩(wěn)定解。近來，人們又引進(jìn)各種啟發(fā)式算法來解決WTA 問題，如采用蟻群算法［3］，基于神經(jīng)網(wǎng)絡(luò)的TSP 算法［4］，改進(jìn)的遺傳算法及采用粒子群算法與遺傳算法相結(jié)合來解決WTA 問題［5］。本文引入一種新的進(jìn)化計(jì)算方法——人工免疫算法，依據(jù)該算法原理，構(gòu)造了有效表達(dá)編隊(duì)防空作戰(zhàn)效能的特種抗體數(shù)據(jù)結(jié)構(gòu)染色體矩陣編碼方案和親和度算法，給出用于產(chǎn)生高效防空WTA 結(jié)果的克隆免疫算子?？寺∶庖咚阕幽軌虮ＷC抗體群的多樣性，通過特殊的編碼方式保證得到全局最優(yōu)方案，并利用二次免疫機(jī)理提高編隊(duì)防空WTA 的反應(yīng)速度。

1 編隊(duì)防空WTA 模型

1.1 問題的描述及分配原則

編隊(duì)防空WTA 是一個(gè)動(dòng)態(tài)分配過程。假設(shè)一個(gè)編隊(duì)通過其偵察預(yù)警系統(tǒng)發(fā)現(xiàn)有m 批空中威脅目標(biāo)，編隊(duì)內(nèi)有k 類不同型號(hào)的防空武器系統(tǒng)，每種型號(hào)的防空武器的資源數(shù)為Ci，i =1，2，…，k，在武器系統(tǒng)的有效作用區(qū)域和時(shí)間內(nèi)，每種型號(hào)的防空武器的可用資源為CTi，第i 種防空武器對(duì)第j 批目標(biāo)分配一個(gè)火力單元后對(duì)目標(biāo)的毀傷概率為Pij，j=1，2，…，m.

編隊(duì)防空WTA 及獲利原則:

1)防空武器系統(tǒng)只有在其有效的作用區(qū)域和作用時(shí)間內(nèi)才能對(duì)目標(biāo)進(jìn)行WTA，否則不進(jìn)行分配。

2)每種防空武器可以對(duì)多批目標(biāo)進(jìn)行火力單元分配，每批目標(biāo)可以同時(shí)被分配多個(gè)火力單元。

3)每種型號(hào)防空武器在作戰(zhàn)時(shí)間內(nèi)分配的火力單元總數(shù)不能超過該型號(hào)武器的資源數(shù)。

4)在面對(duì)多批次空中目標(biāo)時(shí)，為獲得最大作戰(zhàn)效能，每種武器應(yīng)對(duì)其有效的作用區(qū)域和作用時(shí)間內(nèi)的可用資源完全分配。

1.2 防空WTA 數(shù)學(xué)模型

設(shè)有m 批空中威脅目標(biāo)，編隊(duì)內(nèi)有k 類防空武器系統(tǒng)，每種型號(hào)的防空武器的資源數(shù)為Ci，在有效作用區(qū)域和時(shí)間內(nèi)，每種型號(hào)的防空武器的可用資源為CTi，第i 種防空武器對(duì)第j 批目標(biāo)分配一個(gè)火力單元后對(duì)目標(biāo)的毀傷概率為Pij.則WTA 決策矩陣為

式中:xij，i=1，2，…，k，j =1，2，…，m 為第i 種類型防空武器對(duì)第j 批目標(biāo)分配的火力單元數(shù)。

對(duì)目標(biāo)進(jìn)行武器火力單元分配，要求分配后使整個(gè)編隊(duì)防空武器系統(tǒng)的作戰(zhàn)效能最大，即使毀傷目標(biāo)的數(shù)學(xué)期望達(dá)到最大值，則建立的WTA 模型為

式中:ωj，j=1，2，…，m 為第j 個(gè)目標(biāo)的威脅系數(shù);Ci為第i 個(gè)武器系統(tǒng)的資源數(shù);CTi為第i 個(gè)武器系統(tǒng)在其有效作用區(qū)域和時(shí)間內(nèi)的可用資源數(shù)。

2 人工免疫系統(tǒng)原理

人工免疫系統(tǒng)(AIS)是一個(gè)信息處理技術(shù)與計(jì)算方法相結(jié)合的智能系統(tǒng)。它借鑒、利用生物免疫系統(tǒng)的性質(zhì)和機(jī)制發(fā)展用于解決工程和科學(xué)問題的技術(shù)方法。生物免疫系統(tǒng)是一個(gè)高度進(jìn)化的生物系統(tǒng)，它旨在區(qū)分外部有害抗原和自身組織，從而清除病原并保持有機(jī)體的穩(wěn)定［6］，人們從生物免疫系統(tǒng)的運(yùn)行機(jī)制中獲取靈感，開發(fā)面向應(yīng)用的免疫系統(tǒng)計(jì)算模型——AIS.克隆選擇原理(CS)最先由Jerne提出，克隆選擇的主要特征是免疫細(xì)胞在抗原刺激下產(chǎn)生克隆增殖，隨后通過遺傳變異分化為多樣性效應(yīng)細(xì)胞(如抗體細(xì)胞)和記憶細(xì)胞，克隆選擇對(duì)應(yīng)著一個(gè)親合度成熟的過程，即對(duì)抗原親合度較低的個(gè)體在克隆選擇機(jī)制的作用下，經(jīng)歷增殖復(fù)制和變異操作后，其親合度逐步提高而“成熟”的過程。

編隊(duì)防空WTA 過程與AIS［9］有很多相似之處，表1給出了二者之間的對(duì)比。

DeCastro 基于免疫系統(tǒng)的克隆選擇理論提出了克隆選擇算法，核心是比例復(fù)制和比例變異算子，這是一種模擬免疫系統(tǒng)的學(xué)習(xí)過程的進(jìn)化算法。其算法步驟為［6］:

表1 AIS 與編隊(duì)防空WTA 比較Tab.1 Comparison between immune system and fleet anti-aircraft firepower allocation

1)產(chǎn)生一個(gè)初始群體;

2)基于親和度度量確定群體中的n 個(gè)最佳個(gè)體;

3)對(duì)群體中的這n 個(gè)最佳個(gè)體進(jìn)行克隆(復(fù)制)，并使其發(fā)生變異，從而形成下一代群體;

4)從群體中選出一些最好個(gè)體加入記憶集合，并用記憶集合中的一些個(gè)體替換群體中的一些個(gè)體;

5)將群體中的d 個(gè)低親和度的抗體予以替換，從而維持抗體的多樣性;

6)返回步驟2)循環(huán)計(jì)算，直到滿足結(jié)束條件。

與其它算法(如遺傳算法、蟻群算法、進(jìn)化策略等)相比，免疫算法有如下的特點(diǎn)［7-8］:

1)它在記憶單元基礎(chǔ)上運(yùn)行，確保了快速收斂于全局最優(yōu)解;

2)它有計(jì)算親和性的程序，反映了真實(shí)的免疫系統(tǒng)的多樣性;

3)它通過促進(jìn)或抑制抗體的產(chǎn)生，體現(xiàn)了免疫反應(yīng)的自我調(diào)節(jié)功能。

上述特點(diǎn)使得免疫算法有不同于其它算法的附加優(yōu)化步驟:計(jì)算親和性、計(jì)算期望值、構(gòu)造記憶單元。因此免疫算法有以下優(yōu)點(diǎn):

1)保存了多樣性:因?yàn)槊庖咚惴ǖ奶攸c(diǎn)即多樣性和自我調(diào)節(jié)功能，所以使用這一方法能夠獲得許多優(yōu)化問題的最優(yōu)解;

2)記憶訓(xùn)練應(yīng)用免疫算法，通過重復(fù)的優(yōu)化過程，能夠很快的得到最優(yōu)解。因?yàn)閷?duì)于曾經(jīng)出現(xiàn)過的抗原，免疫算法產(chǎn)生相應(yīng)抗體的速度比以前更快。雖然遺傳算法和免疫算法一樣，都是模擬自然進(jìn)化過程的優(yōu)化模型，但是在記憶訓(xùn)練和不同抗體的產(chǎn)生方面，兩者有本質(zhì)區(qū)別。

3 基于人工免疫的防空WTA 模型

3.1 有關(guān)定義

抗原:將空中來襲目標(biāo)的態(tài)勢(shì)表述為抗原。

抗體:將編隊(duì)防空武器的一種WTA 方案表述為抗體。

親和力函數(shù):將目標(biāo)毀傷概率的數(shù)學(xué)期望作為本模型中的親和力函數(shù)。

3.2 抗體編碼

抗體編碼采用一種等價(jià)形式表示，具體到本文的優(yōu)化模型，則按照每個(gè)火力單元分配給不同批次目標(biāo)進(jìn)行編碼，抗體編碼矩陣的維數(shù)不再由目標(biāo)批數(shù)決定，而由編隊(duì)防空武器系統(tǒng)在作戰(zhàn)過程中可用于分配的火力單元總數(shù)確定。

解空間的等價(jià)形式為第i 個(gè)武器系統(tǒng)的第j 個(gè)火力單元分配的目標(biāo)為Mij，即待優(yōu)化的參數(shù)為Mij=(M11，M12，…，M1k，M21，…，M2k，…，Mm1，Mm2，…，Mmk)，通過這種方法可以將分配模型中的約束條件直接從抗體編碼中體現(xiàn)出來。

編碼說明，碼位長度由編隊(duì)內(nèi)防空武器系統(tǒng)在作戰(zhàn)過程中可分配的資源總數(shù)決定;若第i 個(gè)武器系統(tǒng)的可用資源數(shù)為ki，則該武器系統(tǒng)所占的碼位長度為ki;如第2 個(gè)武器系統(tǒng)的可用資源數(shù)5，則該武器系統(tǒng)在抗體編碼中所占的碼位長度為5;抗體編碼中的數(shù)字表示該碼位的火力單元所分配的目標(biāo)代號(hào)。

3.3 親和度計(jì)算

本文抗原與抗體之間親和力，可以直接采用目標(biāo)函數(shù)表示，即抗原與抗體之間親和力

3.4 新抗體的產(chǎn)生

新的抗體的產(chǎn)生通常與遺傳算法差別不大，主要包括選擇算子、交叉算子和變異算子。對(duì)群體中的抗體按照各自的生存力進(jìn)行選擇，選擇下來的抗體再按一定的概率進(jìn)行隨機(jī)配對(duì)交叉，然后以一定的變異概率進(jìn)行變異產(chǎn)生下一代的新抗體。

以本文算法編碼為例，所用算子變換如下:

交叉算子:

交叉前

1 3 4 1 2 5 5 4 3 … … …2 3 5 1 2 2 3 3 4 2 4 … … …1 5

交叉后

2 3 3 1 2 5 5 4 3 … … …2 3 5 1 2 1 3 4 4 2 4 … … …1 5

變異算子:

變異前

5 1 2 1 3 4 4 2 4 … … …1 5

變異后

3 2 3 1 3 4 4 2 4 … … …1 5

3.5 算法實(shí)現(xiàn)步驟

1)初始化抗體群Ab，隨機(jī)產(chǎn)生N 個(gè)抗體，生成初始群體;

2)對(duì)Ab 中的抗體按照親和力由大至小按降序排列，從中選取前M 個(gè)抗體按照克隆免疫算子進(jìn)行克隆，得到規(guī)模為Nc 的抗體群Abc;

3)對(duì)抗體群Abc 中的抗體按照親和力由大至小按降序排列，進(jìn)行刪除操作，從中選取前E 個(gè)抗體，得到規(guī)模為Ne 的抗體群Abe;

4)合并抗體群Ab 和Abe，選出親和力最高且互不相同的N 個(gè)抗體組成抗體群Abp;

5)隨機(jī)產(chǎn)生規(guī)模為Nr 的抗體群Abr，選出親和力最高的Ns 個(gè)抗體組成抗體群Abs;

6)用Abs 代替Abe 中親和力最低的Ns 個(gè)抗體，形成規(guī)模為N 的抗體群Ab;

7)判斷是否滿足終止條件，不滿足則轉(zhuǎn)至步驟2)繼續(xù)執(zhí)行，滿足則結(jié)束計(jì)算。

在限定條件比較多的編隊(duì)防空WTA 中，步驟6)顯得非常重要。它成為產(chǎn)生抗體多樣性的主要原因，因?yàn)檫^多的限制條件使得交叉和變異較難產(chǎn)生合理的抗體。

4 仿真計(jì)算及結(jié)果分析

4.1 作戰(zhàn)想定及仿真結(jié)果

假設(shè)有10 批空中威脅目標(biāo)從不同的方位襲來，編隊(duì)內(nèi)共有7 種不同類型的防空武器，每種武器在規(guī)定的作戰(zhàn)時(shí)間內(nèi)可用資源數(shù)分別為C=［4，5，4，5，4，5，4］，武器系統(tǒng)對(duì)每批目標(biāo)的毀傷概率以及目標(biāo)的威脅系數(shù)矩陣，如表2所示。

表2 武器系統(tǒng)毀傷概率與目標(biāo)威脅系數(shù)Tab.2 Weapon's damage probability and targets'threat degree

首先確定WTA 優(yōu)化參數(shù)，初始化抗體群為100個(gè)，克隆免疫算子的交叉概率為0.5，變異概率為0.5，算法迭代次數(shù)200.

仿真計(jì)算所得到的最優(yōu)WTA 矩陣為

對(duì)防空武器1:分別將其4 個(gè)火力單元分配給第1，2，6，9 批目標(biāo);對(duì)防空武器2:分配2 個(gè)火力單元給第1，3 批目標(biāo)，分配1 個(gè)火力單元給第10 批目標(biāo);…;對(duì)防空武器7:分別將其4 個(gè)火力單元分配給第1，2，5，8 批目標(biāo)。綜合分配后，整個(gè)編隊(duì)防空武器系統(tǒng)對(duì)空中來襲目標(biāo)的作戰(zhàn)效能為0.991 8.

4.2 與其它啟發(fā)式算法的性能比較

通過仿真，得到免疫算法、遺傳算法、粒子群算法每代抗體群的最大親和度，如圖1所示。免疫算法相比遺傳算法和基本粒子群算法而言，能夠獲得更好的全局最優(yōu)解，算法的穩(wěn)定性較強(qiáng)。

圖1 作戰(zhàn)想定情況下3 種算法親和度演變Fig.1 Evolution of three algorithms'affinity

免疫算法在獲得較好的全局最優(yōu)解和較強(qiáng)的穩(wěn)定性的同時(shí)，是以較長的運(yùn)算時(shí)間為代價(jià)的。就免疫算法和粒子群算法比較而言，粒子群算法在整個(gè)優(yōu)化迭代過程中只需跟蹤粒子的當(dāng)前最優(yōu)位置Pbest和粒子群的全局最優(yōu)位置Pgbest，通過粒子臨近速度匹配、消除不必要的變量、考慮多為搜索以及根據(jù)距離的加速，使得粒子群算法的實(shí)現(xiàn)過程簡(jiǎn)單，算法的收斂速度快等優(yōu)點(diǎn)，但其不足是在迭代過程中易陷入局部最優(yōu)解。而免疫算法需要對(duì)抗原進(jìn)行識(shí)別、產(chǎn)生初始抗體、計(jì)算抗體親和度、產(chǎn)生記憶細(xì)胞池，然后通過促進(jìn)和抑制新抗體的產(chǎn)生來省城親和度較高的抗體群，在該算法的每次迭代過程中都要重復(fù)上述過程，直到達(dá)到算法的終止條件為止。因此，免疫算法的算法結(jié)構(gòu)和實(shí)現(xiàn)過程相對(duì)較為復(fù)雜，計(jì)算時(shí)間相對(duì)較長，但其最為顯著的優(yōu)點(diǎn)是能夠獲得更好的全局最優(yōu)解，算法的穩(wěn)定性較強(qiáng)。

5 方案庫構(gòu)建

雖然上述方法能根據(jù)各種作戰(zhàn)態(tài)勢(shì)給出最優(yōu)的編隊(duì)防空WTA 方案，但是，尋求最優(yōu)解的過程是需要一定時(shí)間的。為了提高對(duì)作戰(zhàn)態(tài)勢(shì)的反應(yīng)速度，可利用AIS 的二次反應(yīng)機(jī)理，免疫系統(tǒng)中二次反應(yīng)的關(guān)鍵是免疫庫的構(gòu)建。在編隊(duì)防空WTA 中，實(shí)現(xiàn)二次快速反應(yīng)的關(guān)鍵即為方案庫的構(gòu)建?？梢詷?gòu)造各種空中威脅目標(biāo)的戰(zhàn)場(chǎng)態(tài)勢(shì)，求解出各種態(tài)勢(shì)下的火力最優(yōu)分配方案，存入到預(yù)案庫中。當(dāng)空中目標(biāo)入侵檢測(cè)系統(tǒng)和態(tài)勢(shì)判決系統(tǒng)工作后，即可確定戰(zhàn)場(chǎng)態(tài)勢(shì)，絕大部分情況下，可以在預(yù)案庫中直接查找到最優(yōu)WTA 預(yù)案。對(duì)一些特殊的情況，再采用解算的方法。基于人工免疫算法的編隊(duì)防空WTA 系統(tǒng)構(gòu)成，如圖2所示。

圖2 基于人工免疫的編隊(duì)防空火力分配系統(tǒng)Fig.2 Fleet anti-air firepower allocation system based on artificial immune

6 結(jié)語

本文將克隆免疫算法應(yīng)用到編隊(duì)防空WTA 優(yōu)化求解中，根據(jù)實(shí)際情況構(gòu)造了有效表達(dá)編隊(duì)防空作戰(zhàn)效能的特種抗體數(shù)據(jù)結(jié)構(gòu)編碼方案和親和度算法，給出用于產(chǎn)生高效防空WTA 結(jié)果的克隆免疫算子，并在傳統(tǒng)免疫算法基礎(chǔ)上對(duì)算法做了一定改進(jìn)，通過實(shí)例分析驗(yàn)證了該算法的正確性和有效性。將改進(jìn)的免疫算法與其它進(jìn)化算法進(jìn)行了比較，在多數(shù)情況下，改進(jìn)的免疫算法相比現(xiàn)有進(jìn)化算法而言，能夠得到更優(yōu)的運(yùn)算結(jié)果。針對(duì)AIS 的二次免疫機(jī)理，構(gòu)建編隊(duì)防空WTA 方案庫，將可進(jìn)一步加快防空WTA 系統(tǒng)的解算速度。

與其它一些進(jìn)化算法相比，免疫算法也有其不足之處。因此，針對(duì)現(xiàn)有一些進(jìn)化算法的優(yōu)點(diǎn)與不足，可以將免疫算法與其他算法有機(jī)結(jié)合，相互之間取長補(bǔ)短，以提高解決實(shí)際問題的能力。這將是進(jìn)化算法在今后被重點(diǎn)研究的方向之一。

References)

［1］王紅軍，時(shí)進(jìn)發(fā)，遲忠先.編隊(duì)抗導(dǎo)調(diào)度的免疫算法與仿真［J］.系統(tǒng)仿真學(xué)報(bào)，2008，20(4):858 -861.WANG Hong-jun，SHI Jin-fa，CHI Zhong-xian.Immune algorithm and simulation of fleet anti-missile job-shop schedule［J］.Journal of System Simulation，2008，20(4):858 -861.(in Chinese)

［2］蔡懷平，陳英武.武器—目標(biāo)分配(WAT)問題研究進(jìn)展［J］.火力與指揮控制，2006，31(12):11 -15.CAI Huai-ping，CHEN Ying-wu.The development of the research on weapon-target(WTA)problem［J］.Fire Control and Command Control，2006，31(12):11 -15.(in Chinese)

［3］高尚.武器—目標(biāo)分配的蟻群算法［J］.計(jì)算機(jī)工程與應(yīng)用，2003，39(3):78 -79.GAO Shang.Ant colony algorithm for weapon-target assignment problem［J］.Computer Engineering and Application，2003，39(3):78 -79.(in Chinese)

［4］王小藝，劉載文，候朝楨，等.防空武器多目標(biāo)優(yōu)化分配建模與決策［J］.兵工學(xué)報(bào)，2007，28(2):228 -231.WANG Xiao-yi，LIU Zai-wen，HOU Chao-zhen，et al.Modeling and decision-making of multi-target optimization assignment for aerial defence weapon［J］.Acta Armamentarii，2007，28(2):228 -231.(in Chinese)

［5］王小藝，侯朝楨，原菊梅，等.防空火力分配建模及優(yōu)化方法研究［J］.控制與決策，2006，21(8):913 -917.WANG Xiao-yi，HOU Chao-zhen，YUAN Ju-mei，et al.Modeling and optimization method on antiaircraft firepower allocation［J］.Control and Decision，2006，21(8):913 -917.(in Chinese)

［6］Timmis J，Neal M.A resource limited artificial immune system for data analysis［J］.Knowledge-Based Systems，2001，14:21 -130.

［7］Lee Z J，Lee W L.A hybrid search algorithm of ant colony optimization and genetic algorithm applied to weapon-target assignment problems［J］.Computer Science，2003，2690，(9):278 -285.

［8］Lee Z J，Su S F，Lee C Y，Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics［J］.IEEE Trans on Systems，Man and Cybernetics，Part B，2003，33(1):113 -121.