分階段對地打擊武器-目標分配建模與決策

楊奇松,王順宏,王然輝,牛曉潔

(1.火箭軍工程大學 六系,陜西 西安 710025;2.火箭軍工程大學 初級指揮學院,陜西 西安 710025; 3.中國人民解放軍61683部隊,北京 100094)

分階段對地打擊武器-目標分配建模與決策

楊奇松1,王順宏2,王然輝3,牛曉潔2

(1.火箭軍工程大學 六系,陜西 西安 710025;2.火箭軍工程大學 初級指揮學院,陜西 西安 710025; 3.中國人民解放軍61683部隊,北京 100094)

為解決以對地打擊作戰(zhàn)行動為背景的武器-目標分配問題,在合理的假設條件下,建立了分階段對地打擊武器-目標分配的全局模型和局部模型,并設計了粒子群算法結合改進單純形法的模型求解思路。結合具體算例所得出的仿真結果表明,所提出的模型與算法是準確的,能夠有效地得到目標選擇方案和武器分配方案,決策結果與實際作戰(zhàn)思路基本一致,為對地打擊武器-目標分配問題的工程實現(xiàn)提供了參考,具有重要的實際應用價值。

武器-目標分配;粒子群;優(yōu)化;單純形法

當前所研究的WTA問題的背景始終是防空攔截武器-目標分配(Air Defense Weapon-Target Assignment,AD-WTA),以對地打擊作戰(zhàn)行動為背景的研究非常少見[1]。對地打擊武器-目標分配是現(xiàn)代戰(zhàn)爭中的重要問題,從美軍近幾場局部戰(zhàn)爭中可發(fā)現(xiàn),贏得戰(zhàn)爭的重要手段是大量打擊和毀傷敵方地面目標,以達到破壞其重要設施和削弱其作戰(zhàn)力量的目的,進而快速贏得戰(zhàn)爭,在該背景下的武器-目標分配問題稱為對地打擊武器-目標分配問題(Ground Attack Weapon-Target Assignment,GA-WTA)[2]。相比于防空攔截武器-目標分配問題,對地打擊問題可選用的武器彈藥組合較多,目標多樣,這導致其規(guī)模更大,復雜程度更高。若不能合理分配武器彈藥,不僅會造成資源浪費,還有可能貽誤戰(zhàn)機[3-4]。

靜態(tài)對地打擊武器-目標分配問題(GA-SWTA)不考慮武器及目標的時間屬性,即假設作戰(zhàn)雙方都是靜止的,雙方的武器數(shù)量及其他因素均是不發(fā)生變化的。靜態(tài)WTA模型無法解決超飽和攻擊、新目標的攻擊以及確定攻擊時機等問題,具有一定的局限性[5]。而對地打擊作戰(zhàn)行動通常是分階段進行的,武器數(shù)量、毀傷概率等目標相關情況均會發(fā)生動態(tài)變化,使得時間因素對整個作戰(zhàn)進程發(fā)揮作用明顯[6]。因此,針對分階段對地打擊武器-目標分配問題(GA-DWTA),建立合適的模型并尋找合適的算法,是一項十分必要且緊迫的任務。

1 GA-DWTA問題模型

1.1 問題假設

結合精確制導武器打擊地面目標的作戰(zhàn)實際,構建GA-DWTA問題模型,首先作出如下假設:

①離散化考慮時間因素,將整個過程分為若干個階段;

②不考慮防御方反制武器對攻擊方目標實施打擊,武器彈藥的可用數(shù)量不會因受到敵方攻擊而減少;

③武器對目標的毀傷概率為綜合毀傷概率,考慮了武器的突防概率、命中概率和毀傷概率等;

④隨著作戰(zhàn)進程推進,戰(zhàn)場環(huán)境變化由綜合毀傷概率變化體現(xiàn);

⑤某目標若被選為某階段打擊對象,則該階段必須達到該目標的預期毀傷要求,暫不考慮目標修復能力[7]。

1.2 全局分配模型

在實際作戰(zhàn)中,各階段作戰(zhàn)任務相同,必須以任務為基礎,合理地選擇目標。例如,為了創(chuàng)造攻擊敵方重要資產(chǎn)要地的條件,早期的攻擊目標可能以敵方的預警和防御設施為主?；?.1節(jié)的假設,簡要描述GA-DWTA問題模型如下。

令時間階段的數(shù)量為T,有N種類型的武器彈藥打擊M個目標,N型武器價值分別為Vw,1,Vw,2,…,Vw,N;在第t階段,第i型武器分配給第j類目標的數(shù)量為mij(t),武器i對目標j的綜合毀傷概率為Pij(t);在按照第t-1階段的分配方案交戰(zhàn)之后,第t階段開始之前,武器i的剩余數(shù)量為WS(t)={WS,i(t),i=1,2,…,N},目標的毀傷級別為TC(t)={TC,j(t),j=1,2,…,M},那么可定義各目標在第t階段的狀態(tài)TS(t)為

(1)

為了在模型中體現(xiàn)目標選擇的過程,令整個模型的優(yōu)化變量為目標選擇方案TD={TD,j,j=1,2,…,M },其取值范圍為[1,T],且為整數(shù)。TD,j=t代表第t階段對目標j進行打擊。但TD并不存在于具體的模型之中,而是通過T階段優(yōu)化結束之后剩余武器數(shù)量WS(T+1)和目標的狀態(tài)TS(T+1)來影響約束條件和優(yōu)化結果。

在產(chǎn)生目標選擇方案TD之后,令整個T階段的優(yōu)化目標為:在第T階段打擊結束之后,武器消耗價值最少,且所有目標均達到了戰(zhàn)前要求的毀傷級別。令武器總的消耗價值為V,則可用數(shù)學模型描述為

(2)

(3)

式中:WS,i(1)代表分配之前各型武器的數(shù)量,是已知量;時間屬性為T+1的各項參數(shù)代表的是第T階段交戰(zhàn)之后的結果,是在目標選擇方案TD確定的情況下,對各階段的局部分配模型求解后得到的,局部分配模型見下節(jié),全局分配模型與局部分配模型的關系如圖1所示。

全局優(yōu)化的結果是在給定目標選擇方案TD的情況下產(chǎn)生的。每一個目標選擇方案都會對應一個最優(yōu)的武器-目標分配方案,使得武器消耗價值最少。因此,minV為衡量目標分配方案優(yōu)劣的標準,以使得武器總的消耗價值最小的目標選擇方案為最優(yōu)目標選擇方案,此為全局優(yōu)化目標。

1.3 局部分配模型

在整個模型中,TD為全局優(yōu)化變量。在依據(jù)一定規(guī)則產(chǎn)生TD之后,便可從第1到第T分階段優(yōu)化,求出當前TD對應的武器總消耗價值。

由于各種武器平臺出動能力受具體硬件條件限制,每個階段各型武器的用量都存在上限要求,用Sp(t)={Sp,i(t),i=1,2,…,N}表示各武器在t階段的最大用量。

依據(jù)當前TD的值,便可得知t階段需要對哪些目標實施打擊。如果TD,j滿足:

TD,j=t

(4)

則目標j在本階段被確定為打擊對象。令有M(t)個目標滿足式(4)的條件,第t階段武器消耗價值為V(t);為保證子問題的最優(yōu)性,以武器消耗價值最少為各階段的優(yōu)化目標,則問題可以描述為

(5)

(6)

式中:mij(t)≥0,且為整數(shù)。為了滿足全局優(yōu)化目標,對于階段選擇的目標,必須在本階段使其毀傷級別達到規(guī)定毀傷級別,故增加了第2個約束條件,滿足:

(7)

經(jīng)過對上述模型進行求解,得出t階段最優(yōu)分配方案mij(t)。根據(jù)式(1)和t階段的剩余武器數(shù)量WS(t),得出第t+1階段的TS(t+1)和WS(t+1)。

至此,可依據(jù)上述信息變化更新Pij(t+1),并進行下一階段的優(yōu)化。在第T階段優(yōu)化結束之后,由WS(T+1)計算各型武器消耗量,依據(jù)式(2)計算出TD對應的最優(yōu)解,并以此最優(yōu)解作為評價當前全局優(yōu)化變量TD的標準。

2 GA-DWTA問題求解

建立了分配問題的全局模型和局部模型之后,需要選擇合適的算法解算模型。由模型的介紹可以看出,本問題不僅涉及到目標選擇方案的優(yōu)化,而且在其中嵌套著武器分配方案的優(yōu)化。因此全局模型和局部模型需要選擇不同的算法進行解決。

2.1GA-DWTA問題的求解流程

目標選擇方案TD的優(yōu)劣由minV衡量,minV在模型解算過程中作為全局優(yōu)化變量TD的適應值參與運算。為了不因局部模型最優(yōu)解的波動而對最終結果產(chǎn)生影響,必須使minV最大程度地接近該目標選擇方案下的最優(yōu)解,非智能算法是較為合適的選擇。對比全局與局部模型可以看出,在找到局部模型最優(yōu)解的情況下,minV對應的武器分配方案必然包含第t階段minV(t)所對應的分配方案,該問題具有最優(yōu)子結構性質,全局模型的最優(yōu)解與局部模型的最優(yōu)解保持了一致性。

模型求解過程中優(yōu)化套優(yōu)化,且靜態(tài)GA-WTA問題本身計算規(guī)模和解空間巨大,所以外層算法的效率是需要解決的關鍵問題。鑒于粒子群算法實現(xiàn)容易、精度高、收斂快的優(yōu)點,使用粒子群算法進行目標選擇方案的優(yōu)化。在確定了全局模型和局部模型的算法之后,便可以得到求解整個問題的流程,如圖2所示。

2.2 基于粒子群算法解算全局模型

粒子群算法的任務在于有指向性地對各階段目標選擇方案進行遍歷,盡可能找到最優(yōu)的目標選擇方案。本文對于粒子群算法的基本原理不再闡述,詳見文獻[8]。就具體模型而言,粒子群算法依然需要解決幾個關鍵問題。

1)粒子的表示形式。

對于GA-DWTA問題而言,目標選擇方案TD即為粒子的位置,粒子的速度用vTD={vTD,j,j=1,2,…,M}表示。每個粒子作為整個種群的一部分,在每次尋優(yōu)過程中應該攜帶該粒子的當前位置信息以及歷史尋優(yōu)信息,因此在解算的過程中采用圖3所示的粒子表示形式。

2)適應度函數(shù)的建立。

為提高粒子群算法對問題的求解效率,采用罰函數(shù)的形式對約束條件進行處理,由式(8)計算出對約束條件的懲罰程度:

(8)

(9)

(10)

在獲取懲罰因子的基礎上,可設適應度函數(shù)為

(11)

式中:W為懲罰因子,通常設定為量級較大的正整數(shù)。

3)粒子的速度。

GA-DWTA問題模型離散化考慮時間因素,但一般情況下,時間階段數(shù)量T不會過大?？紤]到T為整數(shù)且量級不高,不需要在速度問題上增加算法的復雜程度,因此本節(jié)將粒子的速度范圍直接設定為vmax=-vmin=2。如果粒子速度經(jīng)過更新之后不滿足整數(shù)條件,那么對其向下取整,即vk+1=[vk+1],然后將其同vmax和vmin比較,確定更新之后的速度。

4)產(chǎn)生初始種群。

產(chǎn)生初始種群的本質在于確定各個目標的打擊階段,隨機產(chǎn)生(0,1)之間隨機數(shù)rTD之后,如果TD,j滿足:

(12)

式中:t∈[1,T],且為整數(shù)。

那么TD,j=t,目標選擇方案TD即粒子的位置,便可以確定。至此,便可以按照粒子群算法的求解步驟進行解算。

2.3 改進單純形法解算局部模型

分析GA-DWTA的局部模型可以看出,除了第2個約束條件和整數(shù)約束,目標函數(shù)和第1個約束條件均為線性的。如果將第2個約束條件線性化,便可在不考慮整數(shù)約束的條件下,將模型轉化為符合式(13)形式的線性規(guī)劃模型,求其非整數(shù)解。

(13)

式中:A,b和C分別為線性規(guī)劃模型的約束矩陣、右端向量和價值向量。將式(7)代入式(6)的第2個約束條件,可得:

(14)

上式兩端同時取對數(shù),可得:

(15)

j=1,2,…,M(t)

那么,可以得到不考慮整數(shù)約束的線性規(guī)劃模型:

(16)

(17)

本文使用單純形法求解上述線性規(guī)劃模型,其求解過程不再贅述[9]。單純形法求出了模型的非整數(shù)解之后,關鍵是在非整數(shù)解周圍尋找滿足約束條件的整數(shù)最優(yōu)解。

如果采用分支定界法,將能夠保證找到模型的全局最優(yōu)解,但由于問題維數(shù)限制,使得整個求解過程不斷進行分支、定界、減支,大大降低了算法的求解效率。本文以遞歸的思想對非整數(shù)解進行處理,如圖4所示。

①依據(jù)非整數(shù)解的小數(shù)部分進行排序。

通過對非整數(shù)解小數(shù)部分數(shù)值大小的比較,按從大到小的順序對GA-DWTA問題局部模型的非整數(shù)解進行排序為mq,l,排序編號q=1,2,…,M(t)N,其滿足如下條件:

(18)

式中:l與i,j之間的關系代表了mq,l與mij之間的對應關系。

②對非整數(shù)解取整并更新約束條件。

按照q取值從小到大的順序,依次對mq,l向上取整,即mq,l=[mq,l]+1。假設取到w+1時,mq,l(q=1,2,…,w+1)所對應的mij使得所耗費武器的數(shù)量超出了其數(shù)量約束,即:

(19)

③單純形法求解更新約束后的模型。

在對模型的武器數(shù)量約束和毀傷級別約束進行更新之后,再用一次單純形法求解其非整數(shù)解。對非整數(shù)解的處理依然按照①和②進行,至此完成一次循環(huán),直到所有mij的整數(shù)值確定,整個處理過程結束。

但需要特別說明的是,實際分配過程中,武器彈藥相對充裕,以上處理流程可保證找到滿足約束條件的整數(shù)解;如果設置的武器數(shù)量及目標毀傷要求等約束條件使得局部分配模型本身無解,以上處理流程亦無法得到整數(shù)解,即部分mij的整數(shù)值無法確定。

3 仿真實驗

表1 武器信息

表2 目標信息

假設武器對目標的毀傷概率隨著作戰(zhàn)進程的推進發(fā)生如下改變:

①預警探測類目標不隨作戰(zhàn)進程的推進而發(fā)生改變;

②每毀傷一個預警探測類目標會使得任意武器毀傷防空反導類型和其他類型目標的概率增加0.1;

③每毀傷一個防空反導類目標會使得任意武器毀傷其他類型目標的概率增加0.05。

在對各目標實施打擊之前,即所有目標均未被毀傷的情況下,武器對目標的毀傷概率如表3所示,本文稱之為初始毀傷概率。

設置粒子群算法的粒子個數(shù)為100,取迭代次數(shù)為200。在本節(jié)設置的仿真條件下,最優(yōu)解并不是唯一的,每個目標的打擊階段不是絕對固定的,計算得出的所有最優(yōu)解如表4所示。

本文算法亦可得出其具體分配方案,如圖5～圖10所示。

表3 初始毀傷概率

表4 最優(yōu)解對應目標選擇方案

將算法運行100次,統(tǒng)計每次結果Rn中各類型目標的打擊階段,并計算打擊階段平均值Pa,如圖11所示。

由圖11可以看出,各類型目標打擊階段的平均值存在波動,但是圖中反映出一種大的趨勢:偵察預警類目標在防空反導類目標之前進行打擊,其他類型目標在防空反導類目標之后進行打擊。這與對地面目標實施打擊的作戰(zhàn)思路基本保持了一致。

4 結束語

本文對動態(tài)對地打擊問題進行了初步探索,建立了GA-DWTA問題模型,利用粒子群算法嵌套帶有遞歸思想的單純形法對其進行求解,并結合具體算例進行了實驗。仿真實驗結果表明,本文提出的模型與算法是準確的,能夠有效地得到目標選擇方案和武器分配方案,決策結果與實際作戰(zhàn)思路基本一致,具有重要的實際應用價值,但對地打擊問題模型與算法的探索還處于初期,更多細致工作有待進一步開展。

[1] 蔡懷平,陳英武.武器-目標分配(WTA)問題研究進展[J].火力與指揮控制,2006,32(12):11-15. CAI Huai-ping,CHEN Ying-wu.Development of the research on weapon-target assignment problem[J].Fire Control and Command Control,2006,32(12):11-15.(in Chinese)

[2] 蔡順才,張紹芳,楊磊.從空海一體戰(zhàn)更名看美軍作戰(zhàn)思想演變[J].飛航導彈,2015,4:66-68. CAI Shun-cai,ZHANG Shao-fang,YANG Lei.Change of American combat ideas from air-sea battle concept[J].Aerodynamic Missile Journal,2015,4:66-68.(in Chinese)

[3] AHNER D K,PARSON C R.Optimal methods for interceptor allocation in a weapon-target assignment framework[C]//IIE Annual Conference & Expo 2013.Puerto Rico:Institute of Industrial Engineers-Publisher,2013:2 092-2 094.

[4] LLOYD S P.Weapons allocation is NP-complete[C]//IEEE Summer Conference on Simulation.Reno:IEEE,1986:1 054-1 058.

[5] MA F,NI M,GAO B,et al,An efficient algorithm for the weapon target assignment problem[C]//2015 IEEE International Conference on Information and Automation(ICIA).Lijiang:IEEE,2015:2 093-2 097.

[6] PATRICK A,HOSEIN M A.Some analytical results for the dynamic weapon-target allocation problem:LIDS-P-1944[R].USA:[S.l.],1990.

[7] CULLENBINE C.A Tabu search approach to the weapon assignment model:AFIT/GOR/ENS/00M-08[R].USA:[S.l.],2000.

[8] 劉爽英,韓燮.一種求解武器目標分配問題的量子粒子群算法[J].計算機科學,2013,40(2):235-236. LIU Shuang-ying,HAN Xie.Quantum-behaved particle swarm algorithm on weapon target assignment[J].Computer Science,2013,40(2):235-236.(in Chinese)

[9] 敖特根.單純形法的產(chǎn)生與發(fā)展探析[J].西北大學學報,2012,42(5):861-864. AO Te-gen.Analysis of the formation and development of the simplex method[J].Journal of Northwest University,2012,42(5):861-864.(in Chinese)

Modeling and Decision-making of Ground Attack Weapon-Target Assignment

YANG Qi-song1,WANG Shun-hong2,WANG Ran-hui3,NIU Xiao-jie2

(1.The Sixth Department,Rocket Force University of Engineering,Xi’an 710025,China;2.Primary Command College, Rocket Force University of Engineering,Xi’an 710025,China;2.Unit 61683 of PLA,Beijing 100094,China)

In order to solve the weapon-target assignment problem with the background of ground attack operations,the GA-DWTA global model and local model were established based on reasonable assumptions,and the PSO was combined with the improved simplex method to solve the model.The results of simulated experiment indicate that the model and the algorithm are accurate,and the target options and the weapon assignment scheme can be effectively achieved,and the decision results are consistent with the actual combat thinking.The proposed method provides a reference for the engineering realization of the ground attack weapon-target assignment problem,and it has important application value.

weapon-target assignment;particle swarm;optimization;simplex method

2016-06-11

楊奇松(1993- ),男,博士研究生,研究方向為飛行動力學與制導。E-mail:441048020@qq.com。

O22

A

1004-499X(2017)02-0090-07