王順宏， 楊奇松， 王然輝， 趙久奮， 王國(guó)江

(1.火箭軍工程大學(xué)，西安 710025; 2.中國(guó)人民解放軍61683部隊(duì)，北京 100094)

對(duì)地打擊武器-目標(biāo)分配問題的粒子群算法

王順宏1， 楊奇松1， 王然輝2， 趙久奮1， 王國(guó)江2

(1.火箭軍工程大學(xué)，西安 710025; 2.中國(guó)人民解放軍61683部隊(duì)，北京 100094)

對(duì)地打擊武器-目標(biāo)分配問題(BTG-WTA)是現(xiàn)代戰(zhàn)爭(zhēng)中的重要問題；相比于一般武器-目標(biāo)分配問題，其規(guī)模更大，復(fù)雜程度更高。提出使用粒子群算法解決BTG-WTA問題，改進(jìn)了粒子初始化、慣性權(quán)重選擇等關(guān)鍵問題使其適應(yīng)BTG-WTA問題模型，并結(jié)合具體算例進(jìn)行了仿真。仿真結(jié)果表明，粒子群算法比解決WTA問題的經(jīng)典算法速度更快、結(jié)果更優(yōu)，具有更強(qiáng)的實(shí)際應(yīng)用價(jià)值。

武器目標(biāo)分配； 粒子群； 優(yōu)化； 對(duì)地攻擊

0 引言

武器-目標(biāo)分配(Weapon-Target Assignment,WTA)也稱火力分配或者目標(biāo)分配，主要研究平臺(tái)防空體系如何在已知來(lái)襲武器對(duì)己方目標(biāo)威脅等級(jí)、破壞概率、己方防御武器的殺傷概率和受保護(hù)資源的重要程度等因素的條件下，按一定的分配原則、因素和約束條件，設(shè)計(jì)合適的武器分配方案，使得敵方來(lái)襲武器受到最大程度的打擊且使己方受防御資源得到最好的保護(hù)[1]。目前WTA問題的模型研究和算法研究已經(jīng)取得了較多成果，文獻(xiàn)[2]提出了貪心遺傳算法解決WTA問題；文獻(xiàn)[3]提出了模糊多目標(biāo)規(guī)劃方法；此外，還有學(xué)者提出了基于滿意決策的目標(biāo)分配算法、基于遺傳算法的動(dòng)態(tài)武器目標(biāo)分配策略以及基于免疫記憶的蟻群算法等，這都是對(duì)WTA問題有益的探索[4]。

當(dāng)前所研究的WTA問題背景始終是防空攔截武器-目標(biāo)分配，也有許多學(xué)者使用粒子群算法解決該問題，但是以對(duì)地打擊作戰(zhàn)行動(dòng)為背景的研究非常少見。對(duì)地打擊武器-目標(biāo)分配是現(xiàn)代戰(zhàn)爭(zhēng)中的重要問題，從美軍近幾場(chǎng)局部戰(zhàn)爭(zhēng)中可發(fā)現(xiàn)，贏得戰(zhàn)爭(zhēng)的重要手段是大量打擊和毀傷對(duì)方地面目標(biāo)，以達(dá)到削弱其作戰(zhàn)力量和癱瘓相關(guān)設(shè)施的目的，進(jìn)而快速贏得戰(zhàn)爭(zhēng)。在該背景下的武器-目標(biāo)分配問題稱為BTG-WTA問題。與其他WTA問題相關(guān)文獻(xiàn)本質(zhì)區(qū)別在于問題的背景與模型不同,相比于防空攔截武器-目標(biāo)分配問題，對(duì)地打擊問題可選用的武器彈藥組合較多，目標(biāo)多樣，導(dǎo)致其規(guī)模更大、復(fù)雜程度更高。若不能合理分配武器彈藥，不僅會(huì)造成資源浪費(fèi)，還有可能造成戰(zhàn)機(jī)貽誤。針對(duì)對(duì)地打擊武器-目標(biāo)分配問題建立合理的模型，設(shè)計(jì)高效的算法，是一項(xiàng)十分必要且緊迫的任務(wù)[5-9]。

1 BTG-WTA問題模型

BTG-WTA問題模型的假設(shè)如下:

1) 武器對(duì)目標(biāo)的毀傷概率為綜合毀傷概率，考慮了武器的突防概率、命中概率和毀傷概率等；

2) 同類武器對(duì)同類目標(biāo)的綜合毀傷概率相同。

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

2 基本粒子群算法

粒子群優(yōu)化(Particle Swarm Optimization,PSO)算法是近年發(fā)展起來(lái)的一種新的進(jìn)化算法(Evolutionary Algorithm,EA)，與遺傳算法相似，它也是從隨機(jī)解出發(fā)，通過迭代尋找最優(yōu)解，通過適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)。但是粒子群算法比遺傳算法規(guī)則更為簡(jiǎn)單，收斂速度更快；且沒有遺傳算法的“交叉”和“變異”操作，通過追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)解。粒子群算法的研究依然處于初期，雖然在實(shí)際應(yīng)用中證明是有效的，但是問題依然很多，還沒有關(guān)于其收斂性和收斂速度等方面的數(shù)學(xué)證明，其理論和數(shù)學(xué)基礎(chǔ)的研究還不夠[10]。

PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過迭代找到最優(yōu)解。在每一次迭代中，粒子通過兩個(gè)“極值”來(lái)更新自己。第一個(gè)是粒子本身所找到的最優(yōu)解，即個(gè)體極值pbest；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，即全局極值gbest。在找到這兩個(gè)極值之后，便

可根據(jù)下式更新粒子的速度和位置。

式中：vk為當(dāng)前粒子的速度；ω是慣性權(quán)重;xk是當(dāng)前粒子的位置;pbest,gbest如前定義;r1,r2是介于(0，1)之間的隨機(jī)數(shù)[11];c1,c2為學(xué)習(xí)因子，通常c1=c2= 2。每一維粒子的速度都會(huì)被限定在固定的范圍之內(nèi)，如果某一維粒子更新后的速度vk+1超過用戶設(shè)定的最大速度vmax，則該維速度被限定為vmax；反之，如果小于設(shè)定的最小速度vmin，則vk+1取值vmin，通常vmin=-vmax。

3 解BTG-WTA問題的粒子群算法

3.1 粒子的結(jié)構(gòu)和表示形式

為便于BTG-WTA問題的求解，首先要設(shè)計(jì)解的表示形式與粒子的結(jié)構(gòu)。為使模型求解的過程更加清晰，用矩陣X=(xijk)N×M×Mj表示粒子位置，為與位置對(duì)應(yīng)，粒子的速度用V=(vijk)N×M×Mj表示；xijk代表第i種武器對(duì)第j類第k個(gè)目標(biāo)分配xijk個(gè)武器，xijk與第1章中mijk表達(dá)的意義一致，需滿足式(2)所示條件，那么矩陣X便可以表示粒子的位置。每個(gè)粒子作為整個(gè)種群的一部分，在每次尋優(yōu)過程中應(yīng)該攜帶該粒子的當(dāng)前位置信息以及歷史尋優(yōu)信息，該信息通過粒子結(jié)構(gòu)來(lái)體現(xiàn)，如圖1所示。

圖1 粒子結(jié)構(gòu)Fig.1 Particle structure

3.2 慣性權(quán)重系數(shù)的選擇

慣性權(quán)重系數(shù)ω可以有效調(diào)整算法的搜索范圍，這對(duì)于搜索空間巨大且容易陷入局部極值的BTG-WTA問題至關(guān)重要。權(quán)重系數(shù)ω越大，算法的全局搜索能力越強(qiáng)；反之，局部搜索能力較強(qiáng)，搜索精度較高。權(quán)重系數(shù)ω一般是在算法開始前即設(shè)定ω的遞減規(guī)律，但無(wú)法根據(jù)粒子位置的更新規(guī)律進(jìn)行自主調(diào)節(jié)[12]。為適應(yīng)BTG-WTA模型求解，本文以10次迭代為一個(gè)階段，設(shè)定權(quán)重系數(shù)根據(jù)粒子位置及最優(yōu)值的變化規(guī)律進(jìn)行自主更新，流程如圖2所示。

圖2 慣性系數(shù)更新規(guī)律Fig.2 Law of inertia weight succession

3.3 適應(yīng)度函數(shù)

由于BTG-WTA問題所含的約束條件較多，尋求一定數(shù)量可行解的過程較慢，因此直接解決此問題效率必定不高。本文將約束條件處理成罰函數(shù)的形式，以加快整個(gè)算法的尋優(yōu)進(jìn)程。引入懲罰因子W，其為量級(jí)較大的正整數(shù)；引入懲罰程度K1和K2，分別代表對(duì)式(2)中第一和第二個(gè)約束條件的懲罰程度，即可計(jì)算出[13]

式中:

在算法優(yōu)化的過程中，需要根據(jù)解的優(yōu)劣來(lái)控制優(yōu)化的方向，解的優(yōu)劣由適應(yīng)度函數(shù)進(jìn)行評(píng)價(jià)。本文設(shè)適應(yīng)度函數(shù)為

式中，X代表一個(gè)完整的分配方案。在優(yōu)化過程中，獲取每一次的分配方案之后，便可根據(jù)式(5)～式(7)計(jì)算出懲罰程度，然后利用式(8)計(jì)算該粒子的適應(yīng)度。

3.4 初始化粒子速度范圍

由粒子群算法優(yōu)化的基本步驟可知，粒子的位置根據(jù)粒子的速度進(jìn)行更新。因此，粒子更新的速度必須受到一定的限制，其大小必須與粒子位置的量級(jí)相適應(yīng)，這直接影響了算法尋優(yōu)的速度與精度。結(jié)合BTG-WTA問題的模型，X中的每一個(gè)xi jk均是由武器的數(shù)量和目標(biāo)的數(shù)量決定的，其具體數(shù)值必然根據(jù)所有武器平均于每個(gè)目標(biāo)上的數(shù)量上下浮動(dòng)，本文利用式(9)決定粒子速度的范圍，取得了較好的效果。

式中:[·]代表不大于·的最大整數(shù)。

3.5 放寬約束條件產(chǎn)生初始種群

在模型有解的條件下，適當(dāng)放寬武器數(shù)量約束后的模型最優(yōu)解與原模型一致。在有約束的情況下，放寬約束條件可以大大加快可行解的生成速度。將約束條件處理成罰函數(shù)之后，初始解的產(chǎn)生不再受約束條件的限制，但放寬武器數(shù)量約束依然可以發(fā)揮較強(qiáng)作用。本文按照式(10)更加寬松的武器數(shù)量，利用粒子群算法迭代n1次產(chǎn)生的各粒子最優(yōu)位置為初始種群，這樣的約束使得初始解的搜索范圍更廣，以更多的方向往最優(yōu)解接近，從而避免被嚴(yán)格的約束所阻隔，降低了后續(xù)尋優(yōu)中陷入局部最優(yōu)解的概率[14]。

初始解的優(yōu)劣將直接影響算法的效率和最終結(jié)果，因此初始解X0在隨機(jī)產(chǎn)生的過程中必須具有一定的方向性，要盡可能滿足約束且往最優(yōu)解的方向靠攏。本文采用式(10)所示算法對(duì)初始解和速度加以控制。

式中：ω1，ω2為[0,1]區(qū)間內(nèi)的隨機(jī)數(shù)；α為[0.5,1]區(qū)間內(nèi)的隨機(jī)數(shù)。按照式(11)依次對(duì)每一個(gè)xijk和vijk賦初值，形成完整的初始解X0和V0。

3.6 模型求解

3.1～3.5節(jié)解決了粒子群算法求解BTG-WTA模型的關(guān)鍵問題，綜上所述，本文解決BTG-WTA問題的算法流程如圖 3所示。

圖3 改進(jìn)PSO算法解算流程Fig.3 Resolving process of the improved PSO

本文使用的粒子群算法步驟可以描述為：

1) 放寬武器數(shù)量約束，設(shè)置相應(yīng)適應(yīng)度函數(shù)F(X)，初始化群體；

2) 利用粒子群算法迭代n1次(算法關(guān)鍵問題與后續(xù)過程一致)，以各粒子的最優(yōu)位置為初始種群；

3) 還原約束條件，調(diào)整適應(yīng)度函數(shù)；

4) 計(jì)算每個(gè)粒子的適應(yīng)度F(X)，更新pbest和gbest；

5) 按照式(3)和式(4)更新粒子的位置和速度；

6) 檢驗(yàn)是否滿足結(jié)束條件(設(shè)定迭代次數(shù)n2)，如果滿足，則停止迭代輸出最優(yōu)解，否則，轉(zhuǎn)至步驟4)。

4 仿真算例

為了驗(yàn)證本文改進(jìn)粒子群算法解決BTG-WTA問題的有效性，使用算法對(duì)4個(gè)不同規(guī)模的案例進(jìn)行解算，并與改進(jìn)的遺傳算法[15]計(jì)算結(jié)果進(jìn)行比較。有5類武器彈藥D1，D2，…，D5，對(duì)地面6類目標(biāo)B1，B2，…，B6進(jìn)行打擊，不同案例的武器信息如表1所示，目標(biāo)信息以及對(duì)每類每個(gè)目標(biāo)的要求毀傷級(jí)別如表2所示，武器對(duì)目標(biāo)的毀傷概率信息如表3所示。

各案例的問題規(guī)模如表4所示。設(shè)置粒子群算法的粒子數(shù)為100，產(chǎn)生初始種群的迭代次數(shù)n1為1000，終止條件設(shè)迭代次數(shù)n2為30 000；權(quán)重系數(shù)最大值ωmax取值1.2，最小值ωmin取值0.1，初始值ω0取值0.9。分別使用改進(jìn)遺傳算法和本文所述粒子群算法對(duì)各案例進(jìn)行解算，兩種算法各測(cè)試100次后取測(cè)試過程中的最優(yōu)解。為使解算結(jié)果更為直觀，繪制了如圖4和圖5所示的時(shí)間和武器消耗價(jià)值與變量個(gè)數(shù)的關(guān)系折線圖。

表1 武器信息

表2 目標(biāo)信息

表3 毀傷概率信息

表4 問題規(guī)模

圖4 解算時(shí)間與變量個(gè)數(shù)的關(guān)系Fig.4 Resolving time vs number of variables

由圖4、圖5粒子群算法的計(jì)算結(jié)果可以看出，沒有出現(xiàn)量級(jí)較大的武器消耗價(jià)值，這證明所得解均是滿足約束條件的。由圖4和圖5可以看出，與改進(jìn)遺傳算法的計(jì)算結(jié)果相比較，粒子群算法收斂更快，結(jié)果更優(yōu)；隨著問題規(guī)模的增加，粒子群算法效率和結(jié)果的優(yōu)勢(shì)更加明顯。而且，粒子群算法解算上述不同規(guī)模的問題時(shí)，參數(shù)設(shè)置都是一樣的，只需根據(jù)實(shí)際任務(wù)需要，適當(dāng)改變算法的迭代次數(shù)以調(diào)整模型解算時(shí)間，這使得整個(gè)模型解算過程操作簡(jiǎn)便，更加適應(yīng)工程實(shí)際的需要。

圖5 武器消耗價(jià)值與變量個(gè)數(shù)的關(guān)系Fig.5 Consumption value vs number of variables

5 結(jié)束語(yǔ)

對(duì)地打擊武器-目標(biāo)分配是現(xiàn)代戰(zhàn)爭(zhēng)中的重要問題，本文嘗試用改進(jìn)粒子群算法對(duì)其進(jìn)行解算，為該類型的WTA問題研究提供了一種新的思路。從本文仿真結(jié)果看，本文算法易于實(shí)現(xiàn)、效率更高并且結(jié)果更優(yōu)，這使得其更加適應(yīng)現(xiàn)代戰(zhàn)爭(zhēng)中對(duì)地打擊武器-目標(biāo)分配問題的巨大規(guī)模，以及信息化條件下快速?zèng)Q策的需要,但由于對(duì)地打擊問題模型與算法的探索還處于初期階段，更多細(xì)致工作有待進(jìn)一步開展。

[1] 蔡懷平，陳英武．武器-目標(biāo)分配(WTA)問題研究進(jìn)展[J]．火力與指揮控制，2006，32(12):11-15.

[2] 張海兵,徐誠(chéng),李世永.貪心遺傳算法及其在武器目標(biāo)分配問題中的應(yīng)用[J]．彈道學(xué)報(bào)，2007,19(2):40-43.

[3] 陳建虎，呂志明.武器-目標(biāo)分配的模糊多目標(biāo)規(guī)劃[J].武器裝備自動(dòng)化，2007,26(6):3-4.

[4] 李勇君，黃卓，郭波．武器-目標(biāo)分配問題綜述[J]．兵工自動(dòng)化，2009，28(11)：1-4.

[5] MORRIS R D.Weaponeering:conventional weapon system effectiveness[M].Reston:American Institute of Aeronautics and Astronautics,INC,2004.

[6] LOYD S P,WITSENHAUSEN H S.Weapons allocation is NP-complete[C]//Proceedings of the IEEE Summer Computer Simulation Conference,Reno,1986:125-139.

[7] LEE Z J,SU S F,CHOU Y L.Efficiently solving general weapon-target assignment problem by genetic algorithms with greed eugenics[J].IEEE Journal on Systems,Man, and Cybernetics-Bart B Cybernetics,2003,33(1):119-120.

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

[9] CULLENBINE C.A tabu search approach to the weapon assignment model[R].Dayton:AFIT/GOR/ENS/00M-08,2000.

[10] 劉衍民.粒子群算法的研究及應(yīng)用[D].濟(jì)南:山東師范大學(xué),2011.

[11] 高尚,楊靜宇.武器-目標(biāo)分配問題的粒子群優(yōu)化算法[J].系統(tǒng)工程與電子技術(shù),2005,27(7):1250-1252,1259.

[12] 楊飛,王青,侯硯澤.基于整數(shù)域改進(jìn)粒子群優(yōu)化算法的多平臺(tái)武器目標(biāo)分配[J].兵工學(xué)報(bào),2011,32(7):906-912.

[13] 李趙陽(yáng).基于粒子群算法的武器-目標(biāo)分配問題求解[D].長(zhǎng)春:吉林大學(xué),2009.

[14] 劉爽英,韓燮.一種求解武器目標(biāo)分配問題的量子粒子群算法[J].計(jì)算機(jī)科學(xué),2013,40(2):235-236，248.

[15] 喻壽益,鄺溯瓊.嵌套式模糊自適應(yīng)遺傳算法[J].控制工程,2010,17(1):75-79.

ParticleSwarmOptimizationBasedWeapon-TargetAssignmentforAttackingGroundTargets

WANG Shun-hong1, YANG Qi-song1, WANG Ran-hui2, ZHAO Jiu-fen1, WANG Guo-jiang2

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

Weapon-Target Assignment for attacking ground targets (BTG-WTA) is an important issue in modern warfare,which has larger scale and is more complicated than the ordinary weapon-target assignment.Particle Swarm Optimization (PSO) algorithm is used for solution of the BTG-WTA.The key issues,such as particle initialization and inertia weight selection,are improved for adaptable to BTG-WTA model,and simulation is made to an example.The results of simulated experiment indicate that PSO is more efficient than the classical algorithm for BTG-WTA,and thus has great application value.

weapon-target assignment; particle swarm; optimization; ground target attacking

O22

A

1671-637X(2017)03-0036-05

2016-03-21

2016-04-22

王順宏(1975 —),男,甘肅天水人,博士，副教授,碩導(dǎo),研究方向?yàn)閺椀涝O(shè)計(jì)。