基于离散映射的量子粒子群优化算法求解WTA问题

    刘琨　潘翔宇

    摘 要： 针对武器目标分配（WTA）问题及其特点， 提出一种基于离散映射的量子粒子群优化算法。 通过武器系统对目标攻击过程中得到的毁伤收益建立了目标分配模型， 提出一种基于离散映射的编码调整方式， 将连续型粒子位置矢量投影至离散空间上， 避免产生不满足模型约束条件的非法解， 从而提高粒子利用率。 通过仿真对比验证， 论文算法具有较高的收敛速度与稳定性， 表明该方法能有效求解WTA问题。

    关键词： 武器目标分配（WTA）； 量子粒子群优化算法； 离散映射； 编码调整

    中图分类号： TJ760.1； TP18 文献标识码： A文章编号： 1673-5048（2018）03-0037-07

    0 引 言

    武器目标分配（Weapon Target Assignment， WTA）问题是典型的组合优化问题， 旨在求解武器与目标的合理分配组合， 达到己方资源损伤最小化或敌方资源毁伤最大化的目的。 WTA问题本身是一个多参数、 多约束的非确定多项式（Non-Deterministic Polynomial， NP）问题[1]。 目前应用于求解WTA 问题的算法主要有遗传算法[2-3]、 粒子群优化算法[4]等。 但其在解算的过程中不可避免会产生不满足约束条件的非法解， 使粒子的利用率较低， 也会增加算法不必要的时间消耗。

    基于PSO算法实现简单及运算耗时短等优点， 使其在求解WTA优化问题得到广泛应用[4-6]， 文献[4]与[7]均利用粒子群算法分别采用实数整形与二进制矩阵编码及一系列改进措施求解多机协同攻击目标分配问题。 但相关文献的算法分配模型中同时或部分存在以下不足：（1）算法对模型约束条件处理单纯依靠惩罚函数， 无法提高种群粒子利用率； （2）局限于目标个数等于武器个数的目标分配， 缺少对目标个数与武器个数存在差异情况下的相关研究。

    因此， 本文提出目标个数大于武器个数与目标个数小于武器个数两种武器目标分配模型， 同时为提高算法的粒子利用率， 增强算法运算效能， 提出一种基于离散映射的编码调整方式， 将连续型粒子位置矢量投影至离散空间上， 减少算法求解最优解的迭代次数。

    1 武器目标分配模型

    1.1 问题描述

    为便于研究， 对战场环境作以下假设：

    （1） 假定武器对各目标杀伤概率、 目标威胁参数已知。

    1.3 评价函数

    评价函数是对智能搜索算法求解优劣的判定函数， 针对编队对地攻击任务分配问题， 现阶段的研究大多数都以单目标优化模型为求解框架[8-9]。 本文构建了考虑目标剩余价值、 编队攻击损耗的多目标优化模型。 为简化求解难度， 通过线性加权的方法设置合理的权重系数， 将多指标函数转化为单指标评判函数， 其表达式如下：

    2.3 非法解的离散映射处理

    整形实数编码方式易产生不满足目标方案约束条件的非法解， 本文提出一种基于双排序离散映射的编码调整方式， 处理算法迭代运算中产生的非法解， 并对连续性实数编码进行离散化投影至有效解空间上。

    由于约束条件式（7）～（10）规定对每架战机至多能对两个目标实施打击， 因此当2M<n时，

    步骤1 对更新求解后的粒子位置矢量Popold每个维度按照数值大小由左向右依次排序得到Popsort， 并记录下Popold和Popsort间的排序映射关系。

    步骤7 根据之前保存的Popold和Popsort间的排序映射对应关系， 对Popadapt每一维度位置进行逆映射， 即可得到调整后的粒子位置矢量Popnew。

    图2～3针对武器资源数溢出与目标数溢出两种武器目标分配情况， 以具体实例描述了基于排序双映射的离散化编码调整方式的操作流程。 粒子编码经过同比例离散化调整结束后， 连续性武器分配矢量被映射到合法解的离散空间上。 非法解的处理可确保进化后的粒子每一维投影至离散空间， 并保证粒子参与算法下一次迭代时保持原有的搜索方向。 基于排序映射的编码调整方式将提高参与迭代有效解所占种群比例， 大大增强了整个种群的粒子利用率。 相对于利用惩罚函数等传统处理非法解的方式， 本文设计的编码调整过程并未对非法解简单舍弃， 而是对其进行改造， 扩充了有效解的数量与种类。

    3 仿真实验

    仿真实验共设置两组不同规模的武器目标数。 在两组仿真中， 分别对攻击编队携带武器数目大于目标数、 攻击编队携带目标数小于目标数两种情况进行仿真分析。 检验基于离散映射的量子粒子群优化算法（QuantumBehaved Particle Swarm Optimization Algorithm with Discrete Mapping， DMQPSO）， 求解武器目标分配问题。

    通过对比最优适应值变化曲线， 两组不同规模的武器目标数下DMQPSO算法粒子種群均能以最小迭代次数搜索出全局最优解。 SA-GA算法虽然能够最终搜寻到全局最优解， 但算法收敛速度缓慢需要迭代次数较多， 消耗时间较DMQPSO算法时间长；基本QPSO算法和PSO算法在20次迭代内收敛速度较快， 甚至在情况2中， QPSO算法最优适应值短时间内优于DMQPSO算法， 但其在搜索求解过程中易陷入局部最优解。

    针对算例1仿真50次， 表5统计4种算法收敛至最优解的算法时间， 并对比4种算法在搜索时间上的差异。 DMQPSO在搜索至最优解的算法平均耗时上优于SA-GA与PSO算法， 略逊于QPSO算法， 但QPSO算法易陷于局部最优解， 通过搜索时间对比， DMQPSO算法满足对目标分配算法实时性的要求。

    

    （2） 增加编队内战机数量与目标数量。 情况1： 假设有12部待攻击雷达T1， T2， …， T12， 攻击编队为8架战机： F1， F2， …， F8。 每架战机最大武器装配数设置为Wi=2， i=1， 2， 3， …， 8。 各架战机对目标的毁伤概率如表6所示， 被击落概率如表7所示。 情况2： 攻击目标数目不变但减少编队战机数目， 即裁撤编号为6， 7， 8的三架战机， 其余各架战机携带武器数量、 杀伤概率均与情况1相同。 分别利用DMQPSO算法、 SA-GA算法、 QPSO算法、 PSO算法对上述两类情况求解最优目标分配方案， 并对4种算法性能进行对比分析， 迭代次数均设置为300。

    最优适应值变化情况见图6～7， 通过比较可以得出： DMQPSO算法粒子种群均能以最小迭代次数搜索出全局最优解； SA-GA算法由于问题规模增大已不能收敛至全局最优； 基本QPSO与PSO算法收敛速度较快， 但易陷入局部最优。 算法运算初期， 4种算法的搜索性能大致相同， 随着迭代次

    数增加， DMQPSO算法收敛性明显优于其余三种算法。 通过对比观察可以得出， DMQPSO算法在100次迭代内仍能快速搜寻到全局最优解； SA-GA算法由于问题规模增大已不能收敛至全局最优， 且收敛速度缓慢； 基本QPSO算法在50次迭代内有较强的收敛速度， 即在短时间内搜索到的全局最优适应值甚至会高于DMQPSO算法， 但仍会陷入局部最优； PSO算法在收敛性和全局最优解的搜索精度上与DMQPSO算法有较大差距。

    表8中列出最优武器分配方案中， 对分配攻击目标T1， T3， T4， T5， T7， T9， T11的战机均是对其毁伤概率最高的战机且对分配攻击T1， T3， T5目标的战机生存概率均最高， 表9中列出的最优武器分配方案中对分配攻击目标T5， T10， T11的战机均是对其毁伤概率最高的战机， 均满足论文提出的分配最优解判定准则。

    针对算例2仿真20次， 表10对提高运算规模后4种算法的搜索时间进行统计对比。 4种算法在运算规模提高后搜索时间均有所有增长， DMQPSO算法搜索最优解平均耗时明显优于SA-GA算法， 与QPSO与PSO算法相当， 具有良好的实时性。

    4 结 论

    本文针对QPSO算法求解WTA问题中连续型粒子编码方式易产生非法解、 影响算法收敛速度及粒子利用率低等问题， 提出一种新的基于离散映射的方法将非法解进行优化处理， 提高粒子种群利用率。 通过对比仿真， 说明改进后的算法具有较高的精度和较快的收敛速度以及良好稳定性， 具有求解较大规模WTA问题的能力， 算法的可行性、 有效性得到了验证。

    参考文献：

    [1] 刘跃峰， 张安. 有人机/无人机编队协同任务分配方法[J]. 系统工程与电子技术， 2010， 32（3）： 584-588.

    Liu Yuefeng， Zhang An.Cooperative Task Assignment Method of Manned/Unmanned Aerial Vehicle Formation[J]. Systems Engineering and Electronics， 2010， 32（3）： 584-588.（in Chinese）

    [2] 王然辉， 王超. 面向对地打击武器-目标分配问题的遗传算法变量取值控制技术[J]. 兵工学报， 2016， 37（10）： 1889-1895.

    Wang Ranhui， Wang Chao.Variable Value Control Technology of Genetic Algorithm for WTA of Ground Target Attacking[J]. Acta Armamentarii， 2016， 37（10）： 1889-1895.（in Chinese）

    [3] 邓道靖， 马云红， 龚洁， 等. 基于并行GAPSO算法的多无人机协同任务规划[J].电光与控制， 2016， 23（11）： 18-22.

    Deng Daojing， Ma Yunhong， Gong Jie， et al. Cooperative Mission Planning of Multiple UAVs Based on Parallel GAPSO Algorithm[J]. Electronics Optics & Control， 2016， 23（11）： 18-22.（in Chinese）

    [4] 夏维， 刘新学， 范阳涛， 等.基于改进型多目标粒子群优化算法的武器-目标分配[J].兵工学报， 2016， 37（11）： 2085-2092.

    Xia Wei， Liu Xinxue， Fan Yangtao， et al.WeaponTarget Assignment with an Improved MultiObjective Particle Swarm Optimization Algorithm[J]. Acta Armamentarii， 2016， 37（11）： 2085-2092.（in Chinese）

    [5] 王強， 张安， 宋志蛟.UAV 协同任务分配的改进DPSO 算法仿真研究[J].系统仿真学报， 2014， 26（5）： 1149-1155.

    Wang Qiang， Zhang An， Song Zhijiao.Simulation Study on Improved Discrete Particle Swarm Optimization Algorithm for Multiple UAV Cooperation Task Assignment[J].Journal of System Simulation， 2014， 26（5）： 1149-1155.（in Chinese）