基于混合粒子群优化的编队防空目标分配❋

王幸运❋❋，陈杰生

（空军工程大学防空反导学院，西安710051）

基于混合粒子群优化的编队防空目标分配❋

王幸运❋❋，陈杰生

（空军工程大学防空反导学院，西安710051）

针对防空作战中的多批次目标分配问题进行了研究。首先，建立了目标分配的约束优化模型；其次，提出了一种混合式粒子群优化算法用于问题的求解；然后，给出了问题求解的详细步骤和粒子群算法的应用规则；最后，基于仿真算法验证了模型的正确性和算法的有效性及计算实时性。

防空作战；目标分配；粒子群优化；约束优化；混沌优化

1 引言

防空作战中的目标分配，是指在多平台防空体系中，确切指明由哪些火力装置对哪些目标在何时采取什么样的射击方案进行射击，以协调各火力单元作战行为的协调指挥过程，也称为火力分配或武器目标分配（Weapon Target Assignment，WTA）。在防空作战中，高效的目标分配算法能够最大程度地提高防空系统的作战效能［1］。

目前，武器目标分配大致可分为静态分配和动态分配两种类型，这两个问题适用范围不同，应针对具体场景和条件进行适当的选取。解决静态目标分配问题的方法很多，如非线性整数规划、启发式搜索算法、动态规划等方法。如文献［2］建立了武器目标分配的指派问题模型；文献［3］建立了防空武器系统的多目标分配决策模型，并基于粒子群优化（Particle Swarm Optimization，PSO）方法进行了求解；文献［4］建立了目标分配的整数规划数学模型，然后采用匈牙利法来求取模型最优解。动态分配的方法也是一个研究热点，可分为集中式和分布式方法。如文献［5］基于构造启发式算法研究了动态武器目标分配问题，文献［6］对合同网协议（Contract Net Protocol，CNP）进行了扩展，构建了基于扩展CNP协同机制的动态武器目标分配（Dynamic Weapon Target Assignment，DWTA）的体系结构。

本文在上述研究的基础上，针对多批次目标分配的问题，建立其约束优化模型，提出一种自适应的混沌优化方法与粒子群算法相结合的混合粒子群算法，对该问题进行求解，最后进行仿真分析。

2 编队防空目标分配模型

2.1 问题的描述及分配原则

假设一个编队通过其侦察预警系统发现有m批空中威胁目标，编队内有k类不同型号的防空武器系统，每种型号的防空武器的资源数为Ci（i＝1，2，…，k），在武器系统的有效作用区域和时间内，每种型号的防空武器的可用资源为CTi，第i种防空武器对第j批目标分配一个火力单元后，对目标的毁伤概率为Pij（j＝1，2，…，m）。给定如下基本假设［7］：

（1）防空武器系统只有在其有效的作用区域和作用时间内才能对目标进行分配，否则不进行分配；

（2）每种防空武器可以对多批目标进行火力单元分配，每批目标可以同时被分配多个火力单元；

（3）每种型号防空武器在作战时间内分配的火力单元总数不能超过该型号武器的资源数；

（4）在面对多批次空中目标时，为获得最大作战效能，每种武器应对其有效的作用区域和作用时间内的可用资源完全分配。

2.2 编队防空目标分配的多目标优化模型

根据上述原则，定义编队防空目标分配的决策变量为xij（i＝1，2，…，k；j＝1，2，…，m）为第i种类型防空武器对第j批目标分配的火力单元数，则决策矩阵为

在定义决策变量的基础上，编队防空目标分配决策即可表述为：对目标进行武器火力单元分配，要求分配后使整个编队防空武器系统的作战效能最大，即使毁伤目标的威胁程度的数学期望达到最大值，同时使得我方资源消耗最小。上述问题可建模为如下的约束优化问题：

式中，Pij意义同上；wj（j＝1，2，…，m）为第j个目标的威胁系数，Ci为第i个武器系统的资源数，CTi为第i个武器系统在其有效作用区域和时间内的可用资源数。

此优化问题可通过整数规划方法求解。已经证明，在大规模情况下，此问题为NP－难问题［7］。为保证在大规模情形下算法的实时性，本文采用一种混合粒子群算法进行求解。下面首先给出混合粒子群算法的基本原理，然后针对此问题进行求解。

3 混合粒子群优化算法

3.1 基本原理

粒子群算法［8］是一种基于迭代的优化算法。系统初始化为一组随机解，通过迭代搜寻全局最优值。在解决优化问题时，每个个体可被相应看成一个潜在解，按照一定规则，通过概率化地调整这些潜在解，不断迭代，最终得到所需要的全局最优解。该模型可被抽象成如下形式：令num表示粒子总数，第i个粒子保存自身当前速度vi＝（vi1，vi2，…viD）和位置xi＝（xi1，xi2，…xiD），并按如下规则对速度和位置进行更新：

其中，d＝1，2，…，D代表搜索空间的维数；vid∈［－vm，vm］，vm为界限，如果超出范围则取边界值；c1、c2称为学习因子，分别代表了个体对于自身认知能力和对社会新息的认知能力；pg＝［pg1，pg2，…，pgD］T为当前的个体极值，即粒子所搜索到的最优位置，gi＝［gi1，gi2，…，giD］T为第i代的全局极值，即整个群体所有粒子所搜索到的最优位置；r1和r2取［0，1］范围内变化的随机数，其作用是增强粒子群运动的随机性，防止过早收敛于局部极值。wi为加权系数，一般采用线性规律递减的权重，也可采用自适应方式进行改变，wi大可对大范围进行探索，有利于跳出局部极小值，wi小可以对小范围进行挖掘，有利于算法收敛。

3.2 不可行解的存活策略

通过求解此类问题可以发现这样一类问题，当最优解处于约束边界附近，边界附近某些不可行解可能优于已找到的可行解，那么找到这些不可行解并将它们加入可行解对于收敛到全局最优解是有益的，因此，采用不可行解的存活策略［9］，保留适量的不可行解，以增加算法的全局搜索能力。

使用这种方法对不可行解进行保留，当前代更新以前，为保持种群的规模恒定，被舍弃的粒子由当前种群中适应度最小的可行解粒子补充。

3.3 全局极值的混沌优化

由于粒子初始化和演化过程的随机性，基本粒子群优化算法具有进化后期收敛慢、局部寻优较差的缺点。本文以粒子群算法为基本算法，提出一种自适应的混沌优化方法来完成粒子的重新初始化，在全局极值邻域一定范围内进一步搜索，在运算量不致明显增大的情况下增强此算法的寻优能力。

混沌优化的基本思想是把混沌变量从混沌空间映射到优化变量的取值范围空间（即解空间），利用混沌的遍历性、随机性和规律性的3种特性进行搜索。混沌优化算法具有易跳出局部极值、全局收敛等优点。

混沌搜索步骤如下：

4 问题求解原理

组合优化问题的求解可通过遍历方法求解，但在问题规模较大时遍历方法是不可行的。采用粒子群优化（PSO）进行组合优化问题的求解是一种直观而且简单的方法，求解速度快，且可保证收敛性。下面针对上述优化问题给出PSO应用方法。

4.1 解的编码方法

应用PSO最重要的步骤是对问题的解进行编码，编码应能够直观地表达问题的解。此问题采用十进制编码方式，较为简单，解的编码方式如图1所示：其中，每m个编码为一组，依次表示第i类防空武器对所有目标所分配的火力单元数，共计k×m个编码为即可表示所有的分配方式。

图1 解的编码方式Fig.1 The codingmethod of solution

4.2 适应度函数的定义

适应度函数即为指标函数，其表示解的优劣程度。粒子群算法中粒子向适应度函数值优的方向移动，因此对于群体中的所有粒子，首先比较粒子的适应度，将适应值优的粒子排名靠前，最后挑选出粒子个体极值和粒子种群的最优解。

4.3 初始种群生成方法

各基因位的取值采用十进制编码，各基因位按均匀分布随机生成，应保证取值范围不超过有效作用区域和时间内的可用资源数CTi。

4.4 基于自适应混沌优化的混合粒子群算法

混沌优化方法分两个阶段进行：首先，在整个空间内按混沌变量的变化规律依次考察经过的各点，接受较好点作为当前最优点；其次，一定步数后认为当前最优点已在实际最优点附近，然后以当前最优点为中心，附加一混沌小扰动，进行细搜索寻找最优点。将混沌优化算法引入到粒子群算法中，有助于解决粒子群算法的不足，以便快速搜寻到最优解。

基于自适应混沌优化的混合粒子群算法求解步骤如下：

Step1：设计最大进化代数，依据上面方法初始化粒子群体的位置和速度，初始化其他所需要确定的参数；

Step2：计算每个粒子的适应度；

Step3：比较每个粒子的适应度，对于满足条件的粒子，运用不可行解的保留策略，对个体的历史最优位置和全局历史最优位置进行更新；

Step4：判断每个粒子是否陷入停滞，若停滞则进入混沌搜索过程；否则，直接进入Step 5；

Step5：根据式（3）计算每个粒子的新位置和新速度，并移动粒子到新的位置上；

Step6：若满足预先设定的收敛准则，则停止计算；否则，转入Step 2。

5 仿真实例

战场想定如下：我方编队成员k类防空目标，各类防空武器的资源数Ci均设为5，在武器系统有效作用范围内的可用资源CTi随机设定，取为［1，5］之间服从均匀分布的随机数；敌方目标共计m次批，每一批目标的威胁因子随机生成，取为［0，1］之间服从均匀分布的随机数；我对敌目标的杀伤概率Pij随机生成，取为［0，1］之间服从均匀分布的随机数。

设定粒子个数为30个，最大迭代次数为1000，当连续50次收益函数无改进时退出，依次对如下6种场景进行仿真分析。在Matlab 2009a环境下，每种情况运行30次统计平均结果如表1所示（计算机性能为Pentium 42.8GHz，2GB内存）。

表1 PSO算法运行结果统计值Table 1 The statistical value of PSO algorithm operation results

可以看出，本文所提算法能够很好地解决编队防空目标分配问题，满足计算的实时性要求。从结果可以看出，当可用资源相对于目标批次较多时，可对每个目标分配更多的资源，因而杀伤概率较高。所得解满足武器目标分配需求，能达到较高的作战效能。

6 结论

本文建立了针对多批次目标分配的约束优化模型，并给出了基于混合粒子群算法的求解步骤，仿真结果表明了算法的有效性和计算实时性。文中混合粒子群算法的提出，为解决目标分配问题提供了一个新的有效途径。应当指出，在具体应用中关于目标威胁程度的量化是基础性的问题［10］，将直接影响到目标分配的结果。另外，当目标批次较多时，目标分配决策依据应在降低敌方威胁程度的基础上，还应考虑我方的资源消耗，防止前期由于分配过多而导致的后果。此时目标分配成为一个多目标优化问题，这是下一步的研究方向。

［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］陈晨，陈杰，张娟.防空火控系统火力分配的多目标优化研究［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］王小艺，刘载文，侯朝桢.防空武器多目标优化分配建模与决策［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］吴鹤，王静宇，蔡少荣.防空导弹作战单元目标分配建模研究［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］唐苏妍，梅珊，朱一凡.基于扩展合同网协议的分布式武器目标分配方法［J］.系统工程与电子技术，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］阮旻智，李庆民，刘天华.编队防空火力分配建模及其优化方法研究［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］徐安，赵思宏，寇英信.基于混合粒子群优化的多目标决策新方法［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年获硕士学位，现为博士研究生，主要研究方向为联合防空作战指挥；

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—），男，河南正阳人，教授、博士生导师，主要研究方向为联合防空作战指挥。

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