阮旻智，李慶民，劉天華

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

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

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

1 編隊防空WTA 模型

1.1 問題的描述及分配原則

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

編隊防空WTA 及獲利原則:

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

2)每種防空武器可以對多批目標進行火力單元分配，每批目標可以同時被分配多個火力單元。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1)保存了多樣性:因為免疫算法的特點即多樣性和自我調(diào)節(jié)功能，所以使用這一方法能夠獲得許多優(yōu)化問題的最優(yōu)解;

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

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

3.1 有關(guān)定義

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

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

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

3.2 抗體編碼

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

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

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

3.3 親和度計算

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

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

新的抗體的產(chǎ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 算法實現(xiàn)步驟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 方案庫構(gòu)建

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

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

6 結(jié)語

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

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

References)

［1］王紅軍，時進發(fā)，遲忠先.編隊抗導調(diào)度的免疫算法與仿真［J］.系統(tǒng)仿真學報，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］蔡懷平，陳英武.武器—目標分配(WAT)問題研究進展［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］高尚.武器—目標分配的蟻群算法［J］.計算機工程與應用，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］王小藝，劉載文，候朝楨，等.防空武器多目標優(yōu)化分配建模與決策［J］.兵工學報，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.