基于改进粒子群算法的多机协同目标分配*

朱德法，单连平，管莹莹

（江苏自动化研究所，江苏连云港222006）

基于改进粒子群算法的多机协同目标分配*

朱德法，单连平，管莹莹

（江苏自动化研究所，江苏连云港222006）

针对多机协同空战目标分配的问题，提出了一种改进的粒子群算法，设计了新的粒子群位置和速度更新过程。充分利用粒子群算法的全局搜索能力以及利用贪婪策略的局部最优搜索能力进行混合搜索，显著地提高了搜索能力。仿真结果表明，改进的粒子群算法能够快速解决多机协同作战的目标分配问题，能够找到逼近全局最优点的解。

粒子群，多机协同，目标分配，贪婪

0　引言

在作战环境日益复杂的现代战争中，作战任务样式多样化，单架飞机所发挥的作战效能极为有限，一般情况下都需要多架飞机相互协同才能完成预定的作战目标。多机协同作战是指两架或两架以上的战斗机相互之间配合、相互协作执行空中战斗任务的方式，以便充分发挥飞机作战能力［1-4］。多机协同目标分配是将一组不同位置、不同价值、不同威胁程度的目标合理地分配给各个飞机，以达到整体作战效能最大、代价最小的目的。目标分配问题是现代战争中一个十分重要的问题，也是多机协同攻击需要解决的难点问题，其解空间随着我机总数和目标总数的增加而呈现指数级增加，使其成为一个多参数、多约束NP问题［5-6］。对于目标分配问题，其求解的方法有隐枚举法、分支定界法、割平面法、动态规划法等传统算法，还有禁忌搜索算法、模拟退火算法、神经网络算法、遗传算法、蚁群算法等智能算法及混合算法。

1　多机协同目标分配问题与模型

在战场态势中，我方有m个战斗机和n个目标，对我机和目标进行分配，假设分配前已知我机对目标的迎击概率，第i个我机迎击第j个目标的概率指标为pij，第j个我方武器平台的重要性为wj，其中每一个我机只能毁伤一个目标，每个目标最多分配Rj战斗机，最终使得迎击目标的效果最优。

根据问题的描述，空战分配问题的数学模型可表示为：

多机协同空战目标分配问题是一个非线性规划问题，优化的目的是对目标的毁伤期望值达到最大。

2　标准粒子群算法

粒子群算法（Particle Swarm Optimization，PSO）由Russell Eberhart和James Kennedy于1995年提出［7-9］，源于对人工生命和鸟群捕食行为的研究。鸟群在飞行过程中会突然改变方向、散开、聚集，其行为不可预测，但其总体总是保持一致性，个体与个体之间也保持着最适宜的距离。所有的粒子都有一个被目标函数决定的适应值，并且知道自己到目前为止发现的最好位置（personal best，记为pbest）和当前的位置，这个可看作是粒子自己的飞行经验。除此之外，每个粒子还知道目前为止整个群体中所有粒子所发现的最好位置（global best，记为gbest）。粒子将根据以下公式来更新自己的速度和位置：

其中，k为迭代次数，c1，c2为学习因子，值为正常数，rand1（），rand2（）是均匀分布于［0，1］上的随机数。

3　改进粒子群算法

3.1粒子表示与编码

多机协同空战的关键在于确定任务由哪个飞机打击哪个目标，采用自然数方式来表达，自然数表达方式与二进制方式相比缩短了编码长度，简化了计算程序。每个粒子的长度等于我机的总数，每个基因表示需要打击的目标。粒子由按目标编号顺序排列的分配编号组成，表示一组可能的分配方案。

例如，对于m取为6，n取为4的一个粒子编码

表示我机1打击第2个目标，我机2打击第1个目标，我机3打击第4个目标，我机4打击第3个目标，我机5打击第2个目标，我机6打击第4个目标。

3.2初始群体与适应度函数

由于粒子群算法操作的需求，必须为粒子群操作准备一个由若干个初始解组成的初始群体，初始群体中的个体通过随机算法产生，初始群体满足模型中约束条件的限制。初始群体通过迁移操作实现粒子的更新。

通过适应度函数用来评价群体中个体的优越性，适应度函数采用目标函数来表示，记录个体对应的目标毁伤期望值。

3.3粒子迁移操作

粒子群算法的实质是每一个粒子根据自己和同伴的飞行经验不断调整位置和速度，从而向最优位置飞行。根据多机协同目标分配的特点，对粒子群算法位置更新公式进行重新定义，假设Xik为粒子i在k时刻的位置，则将其下一时刻的位置为

其中，c1，c2为学习因子，rand1（），rand2（）是均匀分布于［0，1］上的随机数。为粒子向自身最优迁移的距离，为粒子向全局最优迁移的距离。

粒子向自身最优和全局最优迁移的过程如下：

设定Pc1=c1*rand1（），表示个体中信息元素向自身最优进行迁移操作的概率，根据迁移概率Pe进行迁移操作，如果粒子中元素需要向自身最优迁移操作，则将该元素信息赋值到粒子编码对应的元素中。设定Pc2=c2*rand2（），表示个体中信息元素向全局最优进行迁移操作的概率，根据迁移概率Pe进行迁移操作，如果粒子中元素需要向全局最优迁移操作，则将该元素信息赋值到粒子编码对应的元素中。

由此可得，粒子i中第j个元素xij取值为：

其中xpj为粒子i自身最优中第j个元素，xgj为全局最优粒子中第j个元素。

对于粒子中除了保留原有信息的其他元素，则采用贪心策略进行迁移操作。通过粒子所在位置信息可获得我机打击目标的迎击概率，每个分配信息产生的值将对应迎击概率矩阵

因而，对于粒子i则有最优毁伤值

从而得到针对粒子i所获取的迎击概率增值矩阵

3.4并行粒子群搜索

对群体中所有的粒子进行迁移操作，不断更新粒子自身最优位置和全局最优的位置，通过贪婪策略，减少了不必要的搜索空间，直接向最优结果靠近，这样的搜索效率较高，粒子只需要少量迁移即可得到局部最优解，但会导致粒子进入局部最优解。为避免粒子搜索进入局部最优解，采用多个随机的离散群体代替单一种群进行同时搜索，分别搜索得到各自的最优位置，这样可维持群体的多样性，达到抑制早熟现象的效果。在得到多个离散群体最优解后，将各个群体的最优结果再作为初始群体进行再次搜索，以同样的方法进行粒子的寻优，最终将得到全局最优的搜索结果。

3.5多机协同目标分配算法的实现流程

图1　改进粒子群算法的算法流程图

①初始化参数，建立随机初始群体；②计算每个群体中个体的适应度；③更新每个群中粒子自身最优及全局最优值；④根据粒子群算法对粒子进行下列迁移操作。

粒子中元素以迁移操作概率向自身最优及全局最优迁移。

粒子中其他元素采用贪心策略向局部最优迁移。

更新粒子最优值和全局最优值；⑤保存种群生成的最优结果；⑥将生成的每个种群最优结果作为初始群体，重复②～⑤寻优，输出最优结果。

4　仿真试验与分析

为验证改进型粒子群算法求解最优解及其求解速度，采用参考文献［10-11］中数据，设定m=14，n=14，Rj=1，wj=1并行处理的粒子分群数量为50，每个分群中粒子数量为5，迎击概率数据参考文献［10-11］，见表1所示。采用改进粒子群算法对问题进行仿真，产生最优的分配结果见表2所示。将结果与其他算法［11］进行对比，比较最优解、最优解的平均值、获取最优解的最小时间、获取最优解的最大时间以及获取最优解的平均时间，比较结果数据见表3所示。

表1　我机迎击目标概率数据

表2　目标分配最优分配方案

经过仿真验证，上述条件下的目标最优分配结果数据见表3所示。

表3　算法性能比较

从表3可以看出，本文PSO改进方法能够得到全局最优解，并且最优解的平均值都优于ACS、ACS+信息素递减方法。从时间特性上，可以看出获取最优解的最小时间、获取最优解的最大时间以及获取最优解的平均时间都优于ACS、ACS+信息素递减方法。可见本文改进粒子群算法具有较高的搜索效率，能在较短时间内获取最优结果。

5　结束语

本文结合多机协同目标分配的问题，提出了利用改进粒子群的目标分配方法解决多机协同打击目标分配问题，将粒子群全局最优与贪婪策略局部最优结合起来使用，避免了陷入局部最优的问题，并且加快了收敛速度，方法操作简单，易于实现。仿真结果表明，该方法能够快速给出目标分配的满意解，具有有效性和可行性，为指挥员决策提供了依据。

［1］于雷，任波，鲁艺.自适应蚁群算法的多机协同空战目标分配方法［J］.火力与指挥控制，2008，33（6）:49-51.

［2］范洪达，孙永芹，从海鹏，等.多机协同多目标攻击空空作战系统研究［J］.火力与指挥控制，2009，34（3）:84-87.

［3］魏铁涛，屈香菊.多机协同与多目标分配任务规划方法［J］.北京航空航天大学学报，2009，35（8）:917-920.

［4］朱德法，纪峰波，管莹莹.第四代歼击机空战战术决策研究［J］.指挥控制与仿真，2012，34（1）:41-43.

［5］Lloyd S P，Witsenhausen H S.Weapons Allocation is NP-Complete［C］//Proc.of the IEEE Summer Simulation Conference，Reno，Nevada，1986:1054-1058.

［6］杨啸天，冯金富，冯媛，等.基于遗传粒子群的多传感器目标分配算法［J］.电光与控制，2011，18（3）:5-8.

［7］Kennedy J，Eberhart R C.Particle Swarm Optimization［C］//Proceedings of IEEE International Conference on Neural Networks.Piscataway，USA:IEEE Press，1995:l942-1948.

［8］Shi Y，Eberhart R C.Parameter Selection in Particle Swarm Optimization［M］.Evolutionary Programming VII，Lecture Notes in Computer Science，springer，1998.

［9］Blasil，Del Core G.Particle swarm approach in finding optimum aircraft configuration［J］.Journal of Aircraft，2007，44（2）:679-682.

［10］曹英奇，何张兵.WTA问题的遗传算法研究［J］.控制理论与应用，2001，18（1）:76-79.

［11］袁梅.基于蚁群算法的WTA问题求解［D］.哈尔滨：哈尔滨工业大学，2007，4:42-45.

Multi-fighters Cooperative Target Assignment Based on Improved PSO

ZHU De-fa，SHAN Lian-ping，GUAN Ying-ying
（Jiangsu Automation Research Institute，Lianyungang 222006，China）

According to the problem of multi-fighters cooperative target assignment，an improved particle swarm optimization algorithm is put forward，and the process of updating position and velocity of new particle swarm is designed.The algorithm performance is enhanced observably by taking advantage of the global searching ability of PSO algorithm and the partial searching ability of greedy method.The result of simulation experiment shows that the improved particle swarm optimization can solve the problem of multi-fighters cooperative target assignment quickly，and can g find out the global optimal solution.

particle swarm optimization，multi-fighters cooperative，target assignment，greedy

TP301

A

1002-0640（2015）08-0038-04

2014-06-28

2014-07-17

船舶预研支撑技术基金资助项目（12J3.7.4）

朱德法（1981-），男，江苏盐城人，硕士，高级工程师。研究方向：指挥控制。