王幸運??，陳杰生

（空軍工程大學防空反導學院，西安710051）

基于混合粒子群優(yōu)化的編隊防空目標分配?

王幸運??，陳杰生

（空軍工程大學防空反導學院，西安710051）

針對防空作戰(zhàn)中的多批次目標分配問題進行了研究。首先，建立了目標分配的約束優(yōu)化模型；其次，提出了一種混合式粒子群優(yōu)化算法用于問題的求解；然后，給出了問題求解的詳細步驟和粒子群算法的應用規(guī)則；最后，基于仿真算法驗證了模型的正確性和算法的有效性及計算實時性。

防空作戰(zhàn)；目標分配；粒子群優(yōu)化；約束優(yōu)化；混沌優(yōu)化

1 引言

防空作戰(zhàn)中的目標分配，是指在多平臺防空體系中，確切指明由哪些火力裝置對哪些目標在何時采取什么樣的射擊方案進行射擊，以協(xié)調(diào)各火力單元作戰(zhàn)行為的協(xié)調(diào)指揮過程，也稱為火力分配或武器目標分配（Weapon Target Assignment，WTA）。在防空作戰(zhàn)中，高效的目標分配算法能夠最大程度地提高防空系統(tǒng)的作戰(zhàn)效能［1］。

目前，武器目標分配大致可分為靜態(tài)分配和動態(tài)分配兩種類型，這兩個問題適用范圍不同，應針對具體場景和條件進行適當?shù)倪x取。解決靜態(tài)目標分配問題的方法很多，如非線性整數(shù)規(guī)劃、啟發(fā)式搜索算法、動態(tài)規(guī)劃等方法。如文獻［2］建立了武器目標分配的指派問題模型；文獻［3］建立了防空武器系統(tǒng)的多目標分配決策模型，并基于粒子群優(yōu)化（Particle Swarm Optimization，PSO）方法進行了求解；文獻［4］建立了目標分配的整數(shù)規(guī)劃數(shù)學模型，然后采用匈牙利法來求取模型最優(yōu)解。動態(tài)分配的方法也是一個研究熱點，可分為集中式和分布式方法。如文獻［5］基于構(gòu)造啟發(fā)式算法研究了動態(tài)武器目標分配問題，文獻［6］對合同網(wǎng)協(xié)議（Contract Net Protocol，CNP）進行了擴展，構(gòu)建了基于擴展CNP協(xié)同機制的動態(tài)武器目標分配（Dynamic Weapon Target Assignment，DWTA）的體系結(jié)構(gòu)。

本文在上述研究的基礎(chǔ)上，針對多批次目標分配的問題，建立其約束優(yōu)化模型，提出一種自適應的混沌優(yōu)化方法與粒子群算法相結(jié)合的混合粒子群算法，對該問題進行求解，最后進行仿真分析。

2 編隊防空目標分配模型

2.1 問題的描述及分配原則

假設(shè)一個編隊通過其偵察預警系統(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）。給定如下基本假設(shè)［7］：

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

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

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

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

2.2 編隊防空目標分配的多目標優(yōu)化模型

根據(jù)上述原則，定義編隊防空目標分配的決策變量為xij（i＝1，2，…，k；j＝1，2，…，m）為第i種類型防空武器對第j批目標分配的火力單元數(shù)，則決策矩陣為

在定義決策變量的基礎(chǔ)上，編隊防空目標分配決策即可表述為：對目標進行武器火力單元分配，要求分配后使整個編隊防空武器系統(tǒng)的作戰(zhàn)效能最大，即使毀傷目標的威脅程度的數(shù)學期望達到最大值，同時使得我方資源消耗最小。上述問題可建模為如下的約束優(yōu)化問題：

式中，Pij意義同上；wj（j＝1，2，…，m）為第j個目標的威脅系數(shù)，Ci為第i個武器系統(tǒng)的資源數(shù)，CTi為第i個武器系統(tǒng)在其有效作用區(qū)域和時間內(nèi)的可用資源數(shù)。

此優(yōu)化問題可通過整數(shù)規(guī)劃方法求解。已經(jīng)證明，在大規(guī)模情況下，此問題為NP－難問題［7］。為保證在大規(guī)模情形下算法的實時性，本文采用一種混合粒子群算法進行求解。下面首先給出混合粒子群算法的基本原理，然后針對此問題進行求解。

3 混合粒子群優(yōu)化算法

3.1 基本原理

粒子群算法［8］是一種基于迭代的優(yōu)化算法。系統(tǒng)初始化為一組隨機解，通過迭代搜尋全局最優(yōu)值。在解決優(yōu)化問題時，每個個體可被相應看成一個潛在解，按照一定規(guī)則，通過概率化地調(diào)整這些潛在解，不斷迭代，最終得到所需要的全局最優(yōu)解。該模型可被抽象成如下形式：令num表示粒子總數(shù)，第i個粒子保存自身當前速度vi＝（vi1，vi2，…viD）和位置xi＝（xi1，xi2，…xiD），并按如下規(guī)則對速度和位置進行更新：

其中，d＝1，2，…，D代表搜索空間的維數(shù)；vid∈［－vm，vm］，vm為界限，如果超出范圍則取邊界值；c1、c2稱為學習因子，分別代表了個體對于自身認知能力和對社會新息的認知能力；pg＝［pg1，pg2，…，pgD］T為當前的個體極值，即粒子所搜索到的最優(yōu)位置，gi＝［gi1，gi2，…，giD］T為第i代的全局極值，即整個群體所有粒子所搜索到的最優(yōu)位置；r1和r2?。?，1］范圍內(nèi)變化的隨機數(shù)，其作用是增強粒子群運動的隨機性，防止過早收斂于局部極值。wi為加權(quán)系數(shù)，一般采用線性規(guī)律遞減的權(quán)重，也可采用自適應方式進行改變，wi大可對大范圍進行探索，有利于跳出局部極小值，wi小可以對小范圍進行挖掘，有利于算法收斂。

3.2 不可行解的存活策略

通過求解此類問題可以發(fā)現(xiàn)這樣一類問題，當最優(yōu)解處于約束邊界附近，邊界附近某些不可行解可能優(yōu)于已找到的可行解，那么找到這些不可行解并將它們加入可行解對于收斂到全局最優(yōu)解是有益的，因此，采用不可行解的存活策略［9］，保留適量的不可行解，以增加算法的全局搜索能力。

使用這種方法對不可行解進行保留，當前代更新以前，為保持種群的規(guī)模恒定，被舍棄的粒子由當前種群中適應度最小的可行解粒子補充。

3.3 全局極值的混沌優(yōu)化

由于粒子初始化和演化過程的隨機性，基本粒子群優(yōu)化算法具有進化后期收斂慢、局部尋優(yōu)較差的缺點。本文以粒子群算法為基本算法，提出一種自適應的混沌優(yōu)化方法來完成粒子的重新初始化，在全局極值鄰域一定范圍內(nèi)進一步搜索，在運算量不致明顯增大的情況下增強此算法的尋優(yōu)能力。

混沌優(yōu)化的基本思想是把混沌變量從混沌空間映射到優(yōu)化變量的取值范圍空間（即解空間），利用混沌的遍歷性、隨機性和規(guī)律性的3種特性進行搜索?；煦鐑?yōu)化算法具有易跳出局部極值、全局收斂等優(yōu)點。

混沌搜索步驟如下：

4 問題求解原理

組合優(yōu)化問題的求解可通過遍歷方法求解，但在問題規(guī)模較大時遍歷方法是不可行的。采用粒子群優(yōu)化（PSO）進行組合優(yōu)化問題的求解是一種直觀而且簡單的方法，求解速度快，且可保證收斂性。下面針對上述優(yōu)化問題給出PSO應用方法。

4.1 解的編碼方法

應用PSO最重要的步驟是對問題的解進行編碼，編碼應能夠直觀地表達問題的解。此問題采用十進制編碼方式，較為簡單，解的編碼方式如圖1所示：其中，每m個編碼為一組，依次表示第i類防空武器對所有目標所分配的火力單元數(shù)，共計k×m個編碼為即可表示所有的分配方式。

圖1 解的編碼方式Fig.1 The codingmethod of solution

4.2 適應度函數(shù)的定義

適應度函數(shù)即為指標函數(shù)，其表示解的優(yōu)劣程度。粒子群算法中粒子向適應度函數(shù)值優(yōu)的方向移動，因此對于群體中的所有粒子，首先比較粒子的適應度，將適應值優(yōu)的粒子排名靠前，最后挑選出粒子個體極值和粒子種群的最優(yōu)解。

4.3 初始種群生成方法

各基因位的取值采用十進制編碼，各基因位按均勻分布隨機生成，應保證取值范圍不超過有效作用區(qū)域和時間內(nèi)的可用資源數(shù)CTi。

4.4 基于自適應混沌優(yōu)化的混合粒子群算法

混沌優(yōu)化方法分兩個階段進行：首先，在整個空間內(nèi)按混沌變量的變化規(guī)律依次考察經(jīng)過的各點，接受較好點作為當前最優(yōu)點；其次，一定步數(shù)后認為當前最優(yōu)點已在實際最優(yōu)點附近，然后以當前最優(yōu)點為中心，附加一混沌小擾動，進行細搜索尋找最優(yōu)點。將混沌優(yōu)化算法引入到粒子群算法中，有助于解決粒子群算法的不足，以便快速搜尋到最優(yōu)解。

基于自適應混沌優(yōu)化的混合粒子群算法求解步驟如下：

Step1：設(shè)計最大進化代數(shù)，依據(jù)上面方法初始化粒子群體的位置和速度，初始化其他所需要確定的參數(shù)；

Step2：計算每個粒子的適應度；

Step3：比較每個粒子的適應度，對于滿足條件的粒子，運用不可行解的保留策略，對個體的歷史最優(yōu)位置和全局歷史最優(yōu)位置進行更新；

Step4：判斷每個粒子是否陷入停滯，若停滯則進入混沌搜索過程；否則，直接進入Step 5；

Step5：根據(jù)式（3）計算每個粒子的新位置和新速度，并移動粒子到新的位置上；

Step6：若滿足預先設(shè)定的收斂準則，則停止計算；否則，轉(zhuǎn)入Step 2。

5 仿真實例

戰(zhàn)場想定如下：我方編隊成員k類防空目標，各類防空武器的資源數(shù)Ci均設(shè)為5，在武器系統(tǒng)有效作用范圍內(nèi)的可用資源CTi隨機設(shè)定，取為［1，5］之間服從均勻分布的隨機數(shù)；敵方目標共計m次批，每一批目標的威脅因子隨機生成，取為［0，1］之間服從均勻分布的隨機數(shù)；我對敵目標的殺傷概率Pij隨機生成，取為［0，1］之間服從均勻分布的隨機數(shù)。

設(shè)定粒子個數(shù)為30個，最大迭代次數(shù)為1000，當連續(xù)50次收益函數(shù)無改進時退出，依次對如下6種場景進行仿真分析。在Matlab 2009a環(huán)境下，每種情況運行30次統(tǒng)計平均結(jié)果如表1所示（計算機性能為Pentium 42.8GHz，2GB內(nèi)存）。

表1 PSO算法運行結(jié)果統(tǒng)計值Table 1 The statistical value of PSO algorithm operation results

可以看出，本文所提算法能夠很好地解決編隊防空目標分配問題，滿足計算的實時性要求。從結(jié)果可以看出，當可用資源相對于目標批次較多時，可對每個目標分配更多的資源，因而殺傷概率較高。所得解滿足武器目標分配需求，能達到較高的作戰(zhàn)效能。

6 結(jié)論

本文建立了針對多批次目標分配的約束優(yōu)化模型，并給出了基于混合粒子群算法的求解步驟，仿真結(jié)果表明了算法的有效性和計算實時性。文中混合粒子群算法的提出，為解決目標分配問題提供了一個新的有效途徑。應當指出，在具體應用中關(guān)于目標威脅程度的量化是基礎(chǔ)性的問題［10］，將直接影響到目標分配的結(jié)果。另外，當目標批次較多時，目標分配決策依據(jù)應在降低敵方威脅程度的基礎(chǔ)上，還應考慮我方的資源消耗，防止前期由于分配過多而導致的后果。此時目標分配成為一個多目標優(yōu)化問題，這是下一步的研究方向。

［1］王冠男，陳火良中，李為民.混編式防空導彈群目標分配模型［J］.電光與控制，2007，14（1）：19－22. WANG Guan-nan，CHEN Lang-zhong，LIWei-min.On objectassignmentmodel ofmixed air-defensemissile group［J］.Electronics Optics＆Control，2007，14（1）：19－22.（in Chinese）

［2］陳晨，陳杰，張娟.防空火控系統(tǒng)火力分配的多目標優(yōu)化研究［J］.火力與指揮控制，2009，34（2）：43－47. CHEN Chen，CHEN Jie，ZHANG Juan.Research on Multiobjective Optimization of Firepower Allotment for Antiaircraft System［J］.Fire Control and Command Control，2009，34（2）：43－47.（in Chinese）

［3］王小藝，劉載文，侯朝楨.防空武器多目標優(yōu)化分配建模與決策［J］.兵工學報，2007，28（2）：228－231. WANG Xiao-yi，LIU Zai-wen，HOU Chao-zhen，etal.Modeling and Decision-Making of Multi-target Optimization Assignment for Aerial DefenseWeapon［J］.Acta Armamentarii，2007，28（2）：228－231.（in Chinese）

［4］吳鶴，王靜宇，蔡少榮.防空導彈作戰(zhàn)單元目標分配建模研究［J］.彈箭與制導學報，2007，27（3）：298－300. WU He，WANG Jing-yu，CAIShao-rong.Research on Object-distributing Model of Surface-to-air Missile Operational Unit［J］.Journal of Projectiles，Rockets，Missiles and Guidance，2007，27（3）：298－300.（in Chinese）

［5］Xin B，Chen J，Peng Z H，et al.An efficient rule-based constructive heuristic to solve dynamic weapon-target assignment problem［J］.IEEE Transactions on Systems，Man，and Cybernetics-Part A：Systems and Humans，2011，41（3）：598－606.

［6］唐蘇妍，梅珊，朱一凡.基于擴展合同網(wǎng)協(xié)議的分布式武器目標分配方法［J］.系統(tǒng)工程與電子技術(shù)，2011，33（3）：568－574. TANG Su-yan，MEIShan，ZHU Yi-fan.Distributed weapon target assignment algorithm based on extended contract net protocol［J］.Systems Engineering and Electronics，2011，33（3）：568－574.（in Chinese）

［7］阮旻智，李慶民，劉天華.編隊防空火力分配建模及其優(yōu)化方法研究［J］.兵工學報，2010，31（11）：1525－1529. RUANMin-zhi，LIQing-min，LIU Tian-hua.Modeling and Optimization on Fleet Antiaircraft Firepower Allocation［J］.Acta Armamentarii，2010，31（11）：1525－1529.（in Chinese）

［8］Teng P，Lv H G，Huang J.Improved particle swarm optimization algorithm and its application in coordinated air com-batmissile－target assignment［C］//Proceedings of the 7th World Congress on Intelligent Control and Automation. Chongqing：IEEE，2008：2833－2837.

［9］徐安，趙思宏，寇英信.基于混合粒子群優(yōu)化的多目標決策新方法［J］.火力與指揮控制，2010，35（1）：77－80. XU An，ZHAOSi-hong，KOU Ying-xin，etal.ANew Algorithm for Multi-objective Decision based on Hybrid Particle Swarm Optimization［J］.Fire Controland Command Control，2010，35（1）：77－80.（in Chinese）

［10］朱勝偉，周德云，李兆強.基于改進的主成分分析法的目標威脅評估［J］.計算機仿真，2010，27（3）：1－4. ZHU Sheng-wei，ZHOU De-yun，LI Zhao-qiang.Object Threat Evaluation Based On Improved Principal Components Analysis［J］.Computer Simulation，2010，27（3）：1－4.（in Chinese）

王幸運（1977—），女，河北肅寧人，2007年獲碩士學位，現(xiàn)為博士研究生，主要研究方向為聯(lián)合防空作戰(zhàn)指揮；

WANG Xing-yun was born in Suning，Hebei Province，in 1977.She received the M.S.degree in 2007.She is currently working toward the Ph. D.degree.Her research concerns jointair defense operational command.

Email：wangxingy－tg＠126.com

陳杰生（1965—），男，河南正陽人，教授、博士生導師，主要研究方向為聯(lián)合防空作戰(zhàn)指揮。

CHEN Jie-sheng was born in zhengyang，Henan Province，in 1965.He isnow a professor and also the Ph.D.supervisor.His research concerns joint air defense operational command.

W eapon Target Assignment for Air Defense Based on Hybrid Particle Swarm Optim ization

WANG Xing-yun，CHEN Jie-sheng
（Air Defense and AntiMissile Institute，Air Force Engineering University，Xi′an 710051，China）

The problem of targetassignmentofmultiple formations is studied in air defense.Firstly，the restraint optimizationmodel of targetassignment is built.Secondly，amixing particle swarm optimization（PSO）algorithm is put forward to solve the problem.Then，the detailed steps for solving problem are given.Finally，the correctness ofmodel and real time computation ability and the validity of algorithm are verified based on simulation.

air defense；target assignment；particle swarm optimization；constraint optimization；chaos optimization

TP301.6；E926.4

A

1001－893X（2013）02－0122－05

10.3969/j.issn.1001－893x.2013.02.002

2012－04－11；

2012－09－03 Received date：2012－04－11；Revised date：2012－09－03

??通訊作者：wangxingy－tg＠126.com Corresponding author：wangxingy－tg＠126.com