編隊防空火力分配建模及其優化方法研究

阮旻智，李慶民，劉天華

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

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

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

1 編隊防空WTA 模型

1.1 問題的描述及分配原則

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

編隊防空WTA 及獲利原則:

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

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

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

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

1.2 防空WTA 數學模型

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

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

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

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

2 人工免疫系統原理

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

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

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

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

1)產生一個初始群體;

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

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

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

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

6)返回步驟2)循環計算，直到滿足結束條件。

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

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

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

3)它通過促進或抑制抗體的產生，體現了免疫反應的自我調節功能。

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

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

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

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

3.1 有關定義

抗原:將空中來襲目標的態勢表述為抗原。

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

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

3.2 抗體編碼

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

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

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

3.3 親和度計算

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

3.4 新抗體的產生

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

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

交叉算子:

交叉前

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 算法實現步驟

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

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

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

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

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

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

7)判斷是否滿足終止條件，不滿足則轉至步驟2)繼續執行，滿足則結束計算。

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

4 仿真計算及結果分析

4.1 作戰想定及仿真結果

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

表2 武器系統毀傷概率與目標威脅系數Tab.2 Weapon's damage probability and targets'threat degree

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

仿真計算所得到的最優WTA 矩陣為

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

4.2 與其它啟發式算法的性能比較

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

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

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

5 方案庫構建

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

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

6 結語

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

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

References)

［1］王紅軍，時進發，遲忠先.編隊抗導調度的免疫算法與仿真［J］.系統仿真學報，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］王小藝，劉載文，候朝楨，等.防空武器多目標優化分配建模與決策［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］王小藝，侯朝楨，原菊梅，等.防空火力分配建模及優化方法研究［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.