面向對地打擊武器-目標分配問題的遺傳算法變量取值控制技術

王然輝， 王超

(1.61683部隊， 北京 100094；2.火箭軍工程大學， 陜西 西安 710025)

?

面向對地打擊武器-目標分配問題的遺傳算法變量取值控制技術

王然輝1， 王超2

(1.61683部隊， 北京 100094；2.火箭軍工程大學， 陜西 西安 710025)

對地打擊目標與武器類型復雜多樣，其武器- 目標分配問題難度較大，研究不足，而合理的武器- 目標分配方案，可優化資源配置，用最小的代價獲取最大的戰場收益。為此，構建相應數學模型，并針對采用遺傳算法進行解算時收斂速度慢，甚至無法得出可行解等問題，設計了一種變量取值控制方法。該方法通過約束和控制初始種群個體中變量的取值范圍來縮小搜索空間，提高搜索效率；通過改進變異策略擴大變量取值范圍，確保解的質量。仿真結果表明，改進的遺傳算法能有效地解決大規模對地打擊武器- 目標分配問題，且性能較優。

兵器科學與技術； 武器- 目標分配； 毀傷貢獻度； 遺傳算法； 變量取值范圍

0　引言

武器- 目標分配(WTA)是指揮決策中的關鍵問題，根據WTA中的目標是否具有威脅性，可分為廣義的WTA與狹義的WTA[1]。防空武器- 目標分配(AD-WTA)屬于典型的狹義WTA，國內外相關文獻和研究成果很多，不同的算法都有各自的優勢。對地打擊武器- 目標分配(AG-WTA)屬于廣義WTA，由于其時效性要求沒有AD-WTA高，問題比較復雜，相關的研究非常少見。

對地打擊武器- 目標分配是現代戰爭中的重要問題。從美軍近幾場局部戰爭中可發現，贏得戰爭的重要手段是大量打擊和毀傷對方地面目標，以達削弱其作戰力量和癱瘓相關設施的目的，進而快速贏得戰爭。為達成作戰目的，要選用大量的各型武器彈藥打擊各類地面目標。武器和目標的類型及數量眾多，若不能合理分配打擊資源，不僅需要投入過多的武器打擊目標，造成大量的武器資源浪費，還可能延誤戰機，導致作戰目的無法實現。因此，深入研究AG-WTA問題，建立合理的模型，設計高效的算法，是一項十分必要且非常緊迫的任務。

算法研究方面，王小藝等[2]、楊飛等[3]和張蛟等[4]提出了一種針對多約束WTA問題的粒子編碼方案及模型的適應度函數，解決了粒子的整數域初始化問題，提高了粒子群優化算法的迭代效率及尋優能力。王瑋等[5]針對遺傳算法設計了一種滿足約束條件的染色體編碼格式，把求解問題轉化為無約束的組合優化表現形式，為求解問題提供了新的思路。余家祥等[6]結合遺傳算法、模擬退火算法和貪婪算法的優點，綜合運用3種算法求解艦載武器目標分配問題。楊山亮等[7]在遺傳算法的基礎上，通過對初始種群編碼機制的優化和采用精英選擇及動態遺傳算子的改進算法，較好地解決了WTA問題。

AG-WTA與AD-WTA有較大的差別。AD-WTA問題中，用于攔截空中目標的武器類型與數量較少，目標類型與數量也不多；用于攔截單個空中來襲目標的武器數量通常為1～2發；武器對目標毀傷屬于0～1毀傷，無需考慮每發彈藥對目標的累積毀傷效應；其優化原則是武器資源損失最小或敵方剩余目標數最少[8]。而AG-WTA問題中，打擊地面目標的類型與數量很大，使用的武器類型多樣、數量巨大；由于地面目標的復雜性，用于打擊單個地面目標的武器用量也很大；不同武器，甚至不同類型的武器作用于目標時，要考慮累積毀傷效應；其優化原則是以最少的武器消耗達到預期目標毀傷要求。因此，AG-WTA問題的計算規模與解空間都遠大于AD-WTA，現有WTA解決方案難以滿足求解AG-WTA問題需要；且現有的方法存在因求解問題的維數過大而可能導致算法無法搜索到符合約束條件的解或搜索時間過長的問題[9]，在實際作戰籌劃決策中是不允許出現的，因而需設計新的AG-WTA問題解決方案。

針對求解AG-WTA問題，本文首先構建AG-WTA模型，提出一種基于遺傳算法的變量取值控制方法；而后定義貢獻度概念，并以貢獻度約束各型武器打擊每個目標的用量和武器打擊單目標的總用量，縮小變量初始化空間并使變量取值合理化，加快搜索到可行解；之后擴大變量變異范圍，改變變異策略，消除因縮小變量取值范圍可能造成的解空間缺失的問題，并加快算法收斂速度；最后進行算例仿真及對比，驗證提出方法思路的正確性和優越性。

1　AG-WTA問題

1.1AG-WTA過程

AG-WTA主要包括兩個階段。

第一階段：彈目匹配，即針對某具體目標，分析武器的戰斗部毀傷機理、制導方式是否適用，預設陣地發射或防區外投射時射程能否覆蓋目標，目標周圍的環境是否滿足武器的作戰要求等，從而選出適宜打擊該目標的武器類型。

第二階段：分配優化，即綜合考慮各型武器總量約束，將適宜的武器按照效費比最優的方式合理分配給目標，使所有目標達到預期毀傷效果。

1.2AG-WTA問題模型

彈目匹配階段涉及的因素非常多，分析過程非常復雜，但結果只有“適宜”或“不適宜”兩種，無需也無法進行優化。

因此，AG-WTA問題模型主要針對分配優化階段進行設計。首先假設：

1)適宜的武器對目標的毀傷概率為考慮了突防、命中和毀傷等因素的綜合毀傷概率，且同種類型武器對同類目標的綜合毀傷概率相同；

2)不適宜的武器對目標的毀傷概率為0；

3)為降低風險，所有武器平臺均在防區外進行發射，武器的價值消耗不包含武器平臺受損部分；

4)暫不考慮目標打擊的先后順序，以及一個波次的最大投射能力限制。

基于上述假設，簡要描述AG-WTA問題：有N型武器打擊M類地面目標，使得M類目標的毀傷分別達到C1,C2,…,CM. 其中，N型武器數量分別為N1,N2,…,NN，其價值分別為V1,V2,…,VN；M類目標數量分別為M1,M2,…,MM，第i型武器打擊第j類目標的綜合毀傷概率為pij(i=1, 2,…,N;j=1, 2,…,M)。武器- 目標最佳分配目標是以最小武器價值消耗滿足目標毀傷要求，設第i型武器作用于第j類第k個目標的數量為mijk(k=1, 2,…,Mj)，武器消耗價值為V，則AG-WTA問題模型為

(1)

(2)

2　遺傳算法的變量取值控制技術

遺傳算法的基本思想來源于生物的遺傳進化，模擬自然界生物群體優勝劣汰的進化過程，能夠有效地處理多種優化問題[10]，經過算法改進[5-8,11,12]已在WTA問題中得到了廣泛應用[1,9]。生物群體的遺傳進化起始于初始種群，初始種群的優劣直接影響個體進化的速度與方向，若遺傳算法中的初始種群相對接近于最優個體，則將很快進化為最優個體。因此，可以針對遺傳算法設計一種變量取值控制技術，通過控制變量取值范圍使得初始種群個體在可行解空間內產生，從而有效提高解的質量和計算效率。

2.1控制變量取值的意義

AG-WTA問題是NP完全問題，算法搜索空間隨著變量數量的增加或變量取值范圍的擴大呈指數增加。在AG-WTA問題中，變量的個數是確定的、不可改變的，其值為武器類型數與目標數的積；但變量取值范圍是不確定的，因AG-WTA一般不會約束各型武器作用于每個目標的用量，只會限制各型武器的可用數量，則在求解中作為變量取值范圍的武器用量區間是不確定的、可改變的。若變量取值范圍不作控制，即以每類武器的數量作為變量取值范圍上界，則搜索空間內生成的WTA方案的數量極大。

假設有N型武器，其數量分別為N1,N2,…,NN；M類目標，其數量分別為M1,M2,…,MM. 若以各型武器的數量作為變量取值范圍上界，則第i型武器打擊第j類目標的武器用量mij的取值范圍為

mij∈[0,Ni],mij為整數。

(3)

由(3)式可知，第i型武器打擊第j類目標時，變量mij有Ni+1個可能取值。

對于第j類目標，N型武器打擊該類第k個目標時，有N個變量，將其看作一個向量，則在這N個變量取值范圍構成的搜索空間內，可生成的向量數量njk為

(4)

當N型武器打擊第j類的所有目標時，有N×Mj個變量，則變量取值范圍構成的搜索空間可生成的向量數量nj為

(5)

(6)

式中：向量數量n值，即為當N型武器打擊M類全部目標時，所有可能的WTA方案數量。

從(6)式可以看出，隨著變量取值范圍增大，AG-WTA方案數量n值迅速增大。但AG-WTA問題的可行解數量為定值，只占全部分配方案數量的很少一部分，且絕大部分的可行解集中分布在搜索空間的某一區域，其分布區域和數量不受變量取值范圍的影響。因此，若能急劇縮小搜索空間，并使搜索空間包含可行解所在的空間，就可確保快速搜索到可行解。

例如，有49發同種類型武器打擊10個同類目標，若以武器總量作為變量取值上界，則N1=49，M1=10，根據(6)式可解算分配方案數量n(1)為

(7)

若控制變量取值范圍，令其變量上界取值為9，則N1=9，M1=10，根據(6)式可解算分配方案數量n(2)為

n(2)=(N1+1)M1=1010.

(8)

由(7)式和(8)式解算的分配方案數量n(1)和n(2)，可得無變量取值范圍控制與有變量取值范圍控制搜索空間內的分配方案數量之比α為

(9)

可見，在減小變量取值范圍上界后，搜索空間急劇縮小，搜索空間內的分配方案數量也急劇減少，且縮小后的變量取值范圍總體是合理的，其變量取值范圍構成的搜索空間能夠包含絕大部分可行解空間，表明變量取值范圍的合理控制能確保快速搜索到可行解。

2.2基于毀傷貢獻度確定取值范圍

變量取值控制方法是通過對變量取值范圍進行一系列操作來提高搜索效率，即在遺傳算法初始化過程中縮小算法搜索空間，以縮短解算時間；在變異過程中放大變量取值范圍，確保有合理的解算結果。對于遺傳算法求解AG-WTA問題，變量為各型武器作用于每個目標的數量，變量取值范圍是各型武器可能作用于每個目標的數量區間。變量取值控制由三部分構成：一是約束各型武器作用于每個目標的最大數量；二是約束作用于每個目標的武器總量；三是擴大變量變異區間并改變變異策略。

對于同一個目標，要達到預期的毀傷效果通常會使用n枚武器進行打擊，對于同一種武器而言，每枚武器會貢獻不同的毀傷值，可稱之為毀傷貢獻度，用u表示。若第i型武器打擊第j類目標的毀傷概率為pij，則第n發的毀傷貢獻度為

(10)

(11)

顯而易見，對于同一目標，在選擇武器時，單位價值毀傷貢獻度越大的武器越適宜。

2.2.1約束各型武器作用于每個目標的數量

(12)

因此，第i型武器打擊第j類目標的武器用量區間上界值tij為

tij=n-1.

(13)

2.2.2約束作用于每個目標的武器總數量

武器類型不同、毀傷概率各異，但存在多型武器都適用于打擊同一目標的情況，對于這種情況，在遺傳算法的種群初始化中，就會給各型適用武器都隨機賦予打擊該目標的武器用量數值，且數值為0的可能性小，從而可能會出現作用于該目標的武器數量過多，導致在后續的優化中要消耗大量的時間將作用于該目標的武器數量降到合理的范圍。顯然，打擊某個j類目標的武器總量，不應大于對j類目標毀傷概率最小(min(pij)，i=1, 2,…,N)的武器的取值上界。設有N型武器適用于打擊第j類目標，則作用于該類每個目標的武器總數量最大值Tj為

Tj=max (tij),i=1,2,…,N.

(14)

作用于目標的武器總數量最大值確定后，在算法程序中需對N型武器作用于該目標的數量m1j,m2j, …,mNj進行處理，使得滿足：

(15)

2.3通過定向變異放大變量取值范圍

通過對各型武器作用于每個目標的數量和作用于每個目標的武器總數量進行約束，種群中個體變量可取值范圍變小，這種變量取值范圍約束總體是合理的。但當某型武器對某類目標的毀傷概率較小時，約束后作用于該類單個目標的該型武器數量可能不足以使其達到要求的毀傷程度，導致約束的變量取值范圍內無可行解。假設第i型武器打擊第j類目標，根據(12)式和(13)式可得第i型武器對每個第j類目標的武器最大用量tij，則其對第j類目標的最大毀傷程度βij為

βij=1-(1-pij)tij.

(16)

由(10)式和(12)式可得：當0

(1-pij)tijpij<αj≤(1-pij)tij-1pij,

(17)

即

(18)

聯立(16)式和(18)式又可得

(19)

因此，

(20)

在變異操作過程中擴大變量范圍，使變異過程中變量可取各型武器實有數量內的任意數值，確保搜索到可行解。變量取值范圍的擴大增加了搜索空間，使得搜索可行解的時間變長，為避免該情況，采取動態定向變異。設某類目標要求的毀傷程度為alf0，種群個體中該類目標的實際毀傷程度為alf，若屬于該類目標的一個變量值為pop(i,j)，變量對應的某型武器實有數量為bound，則在變異過程中對其的操作流程如圖1所示。

圖1　遺傳算法變異操作流程圖Fig.1　Flow chart of mutation operation of genetic algorithm

2.4基于變量取值控制技術的遺傳算法流程

變量取值范圍控制方法應用于遺傳算法求解AG-WTA問題的流程：

1) 約束各型武器作用于每個目標的數量。以武器的貢獻度約束各型武器作用于每個目標的數量，控制初始種群變量取值范圍。

2) 產生初始種群。在設定的變量取值范圍內初始化種群。

3) 約束武器作用于每個目標的總數量。以作用于某個目標用量最大的單型武器使用數量max(tij)，作為所有武器作用于該目標的最大用量，約束武器總數量Tj.

4) 控制初始種群變量值。計算種群個體中N型武器打擊同一目標的用量總和T1j. 若Tj 0，mij=mij-1. 若T0j

5) 計算種群個體適應值，并進行復制和交叉操作。

6) 進行定向變異操，流程如圖1所示。

7) 迭代終止。判斷是否滿足迭代次數要求，判斷是否滿足目標毀傷要求，若兩個要求都滿足，迭代終止；否則，轉入步驟5.

2.5可行性分析

變量控制技術包括兩個環節：在初始化階段適當約束變量取值范圍，壓縮搜索空間，提高搜索效率；在變異迭代過程中，根據需要定向微調武器用量，確保解的質量，避免早熟。

由于對地打擊某一目標可以是多型武器的優化組合，使得綜合毀傷值達到預期毀傷要求，因此在種群初始化過程中，根據預期毀傷要求和每型武器的毀傷貢獻度，適當約束作用于某個目標的單型武器數量和所有武器總量，可有效地縮小搜索空間，提高索搜效率。

變異過程中，根據現有武器對目標的綜合毀傷值與預期毀傷要求之差來隨機確定增加或減少武器用量。此時，武器用量不再受毀傷貢獻度約束。若大于0，表示武器用量偏大，則隨機減少某型武器數量；若小于0，表示武器用量偏小，則隨機增加某型武器用量。從而確保每個目標均達到預期毀傷要求，即解可行；且盡量降低總的武器消耗價值，即解更優。

由于采用實數編碼的方式，在變異過程中，無論是隨機增加還是減少某型武器的用量時，都只對其中的一型武器加1或減1，而不是隨意變換武器用量取值，通過反復實驗，適當控制變異概率，較好地避免早熟的問題。

3　計算案例

3.1AG-WTA問題實例

針對典型的AG-WTA問題，基于同一背景設置4個不同案例，進行對比分析。

案例背景：總共投入5種不同類型武器，各型武器的價值系數，以及每個案例中的總投入量如表1所示；打擊一定數量的6類地面目標，每個案例中的目標數量如表2所示；已知各型武器對每類目標的毀傷概率如表3所示；要求每個目標的預期毀傷值達到0.9以上，求解最佳的武器分配方案。

表1　各類武器的價值及總量

表2　目標類型及其數量

表3　武器對目標的毀傷概率

3.2AG-WTA問題仿真與分析

針對以上案例，運用Matlab軟件，在相同的軟硬件(Win7 x64，Intel(R) Xeon(R) CPU E3-1240 v3 @3.4 GHz，RAM 16 GB)條件下，分別對文獻[7]的改進遺傳算法和本文提出的解算方法求解AG-WTA問題編程仿真，記錄兩種算法優化的武器消耗價值及解算消耗的時間，其結果如表4所示。

表4　兩種改進算法的解算結果及消耗時間對比

注：表中“變量個數”為“武器類型數量×目標個數”，“-”表示未解算出相應結果。

從表4可以看出，本文采用基于毀傷貢獻度的變量取值控制技術對遺傳算法進行改進，相比文獻[7]改進的遺傳算法，計算結果更優、效率更高，而且隨著變量個數(即武器種類和目標數量)的增加，其效果更明顯。

4　結論

針對AG-WTA這一類特殊問題，本文采取變量控制的方法對遺傳算法進行改進，有兩個方面的優勢：一是合理壓縮搜索空間，大大地提高計算效率；二是改進變異策略，確保了解的質量，有效避免早熟等現象。通過反復實驗和對比分析，該方法針對大規模AG-WTA問題，在解的質量和計算效率方面具有明顯優勢，且規模越大時優勢越明顯。

需要指出的是，本方法在求解AG-WTA問題時具有明顯優勢，不適應于求解AD-WTA問題，針對于其他復雜優化問題是否有效還有待進一步研究。

References)

[1]蔡懷平, 陳英武. 武器- 目標分配(WTA)問題研究進展[J]. 火力與指揮控制，2006，31(12):11-15.

CAI Huai-ping，CHEN Ying-wu. The development of the research on weapon-target assignment (WTA) problem [J]. Fire Control and Command Control, 2006, 31(12):11-15. (in Chinese)

[2]王小藝, 劉載文, 侯朝楨, 等. 防空武器多目標優化分配建模與決策[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 defense weapon[J]. Acta Armamentarii, 2007, 28(2):228-231. (in Chinese)

[3]楊飛, 王青, 侯硯澤. 基于整數域改進粒子群優化算法的多平臺武器目標分配[J]. 兵工學報, 2011, 32(7):906-912.

YANG Fei, WANG Qing, HOU Yan-ze. Weapon-target assignment in multi-launcher system based on improved integer field particle swarm optimization algorithm[J]. Acta Armamentarii, 2011, 32(7):906-912. (in Chinese)

[4]張蛟, 王中許, 陳黎, 等. 具有多次攔截時機的防空火力分配建模及其優化方法研究[J]. 兵工學報, 2014, 35(10):1644-1650.

ZHANG Jiao, WANG Zhong-xu, CHEN Li, et al. Modeling and optimization on antiaircraft weapon-target assignment at multiple interception opportunity[J]. Acta Armamentarii, 2014, 35(10):1644-1650. (in Chinese)

[5]王瑋, 程樹昌, 張玉芝. 基于遺傳算法的一類武器目標分配方法研究[J]. 系統工程與電子技術, 2008, 30(9):1708-1711.

WANG Wei, CHENG Shu-chang, ZHANG Yu-zhi. Research on approach for a type of weapon target assignment problem solving by genetic algorithm[J]. Systems Engineering and Electronics, 2008, 30(9):1708-1711. (in Chinese)

[6]余家祥, 王紹華, 程文鑫. 基于改進局部搜索遺傳算法的目標分配決策[J]. 系統工程與電子技術, 2008，30(6):1114-1117.

YU Jia-xiang, WANG Shao-hua, CHENG Wen-xin. Target allocation decision making based on improved genetic algorithms with local search[J]. Systems Engineering and Electronics, 2008, 30(6):1114-1117. (in Chinese)

[7]楊山亮, 黃健, 劉洋, 等. 基于遺傳算法的聯合火力 WTA 問題研究[J]. 計算機仿真, 2012, 29(3):61-63.

YANG Shan-liang, HUANG Jian, LIU Yang, et al. Analysis of weapon target assignment problem in joint fire strike solving by genetic algorithm[J]. Computer Simulation, 2012, 29(3):61-63. (in Chinese)

[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 Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, 2003, 33(1): 113-121.

[9]李勇君, 黃卓, 郭波. 武器- 目標分配問題綜述[J]. 兵工自動化, 2009, 28(11):1-5.

LI Yong-jun, HUANG Zhuo, GUO Bo. Review of weapon-target assignment problem[J]. Ordnance Industry Automation, 2009, 28(11):1-5. (in Chinese)

[10]Aytug H, Khouja M, Vergara F E. Use of genetic algorithms to solve production and operations management problems[J]. International Journal of Production Research, 2003, 41(17): 3955-4009.

[11]李平，李長文. 武器目標協同火力分配建模及算法[J]. 指揮控制與仿真, 2015, 37(2):36-40.

LI Ping, LI Chang-wen. Modeling and algorithm of weapon target cooperative fire assignment[J]. Command Control & Simulation, 2015, 37(2):36-40. (in Chinese)

[12]武從猛, 王公寶. 遺傳- 蟻群算法在目標分配問題中的應用研究[J]. 兵工自動化, 2014, 33(4):8-11.

WU Cong-meng, WANG Gong-bao. Application of genetic ant-colony algorithm in target assignment problem[J]. Ordnance Industry Automation, 2014, 33(4):8-11. (in Chinese)

Variable Value Control Technology of Genetic Algorithm for WTA of Ground Target Attacking

WANG Ran-hui1， WANG Chao2

(1.Unit 61683 of PLA, Beijing 100094, China; 2.Rocket Force University of Engineering, Xi’an 710025, Shaanxi, China)

Research on weapon-target assignment (WTA) of ground target attacking is very difficult due to a wide variety of targets and weapons. A reasonable WTA scheme is developed to optimize the allocation of limited resources, which brings the maximum battlefield gains with minimum costs. For this reason, a mathematical model is established, and the genetic algorithm is used to resolve the optimal result of weapon-target assignment. But the convergence rate of genetic algorithm is slow and can’t even give a feasible solution in solving WTA. A state variable control method is designed to overcome the insufficient of the genetic algorithm. The proposed method can reduce the search space and improve the search efficiency by restraining and controlling the value range of the initial population variables, and ensure the quality of the solution by improving the mutation strategy to expand the value range of the variables. The simulated result shows that the improved genetic algorithm can solve the WTA problem of attacking the ground targets on a large scale effectively.

ordnance science and technology; weapon-target assignment; damage contribution; genetic algorithm; value range of variables

2015-06-09

王然輝(1980—)，男，工程師。E-mail: w_ranhui@163.com

O22.6

A

1000-1093(2016)10-1889-07

10.3969/j.issn.1000-1093.2016.10.016