火力分配多目标优化的IBACO算法

肖中晖，寇英信，李战武，徐 安

（空军工程大学航空航天工程学院，西安 710038）

火力分配多目标优化的IBACO算法

肖中晖，寇英信，李战武，徐 安

（空军工程大学航空航天工程学院，西安 710038）

应用蚁群优化算法（Ant Colony Optimization）求解多目标优化问题已经引起广泛关注，多目标火力分配问题的目标是求出一个合适的武器目标分配方案，使满足决策需要。建立了多目标火力分配的数学模型，提出一种基于指标的蚁群优化算法Indicator-Based Ant Colony Optimization），给出了算法的具体步骤。IBACO的核心思想是利用二元性能指标来引导人工蚂蚁进行搜索，由于该算法中的信息素是根据指标的值来更新的，通过奖励信息素可以强化最优解。仿真实验证明了该算法的有效性，在解决火力分配问题上，所提算法和蚁群优化算法相比具有较好的收敛性。

火力分配，二元指标优化，多目标蚁群优化

0 引言

火力分配问题，也称武器目标分配（Weapon Target Assignment，WTA）问题，是一个典型的优化问题，需将武器根据目标进行合理分配，从而达到作战意图。应用智能算法求解火力分配单目标优化问题目前有很多研究，如蚁群算法［2］、遗传算法［3］、混合算法［4］等。

相对于单目标优化火力分配而言，多目标优化能够同时综合考虑并优化多个目标，使其同时达到综合的最优值，更符合决策者的需求。在实际问题中，由于多个目标之间存在冲突，多目标优化问题往往不存在一个最优解而应存在一个解的集合，当考虑所有目标时，在这个集合中的解优于其他解，这个解的集合称为Pareto解集或者非支配解。

文献［1］提出一种基于指标的进化算法，但指标被用来排除最差解，而不是强化最优解；文献［2］对多个目标定义信息素更新规则，并不能直接反映解的好坏；文献［7］采用基于分解的多目标进化算法，并设计了不可行解修复方法，但该算法收敛速度低，只对小规模的火力分配案例进行测试。

针对以上问题，提出一种采用二元性能指标的蚁群优化算法，利用这些指标对每个Pareto近似解给出一个反映解的好坏的值，重新定义路径上的信息素，从而引导蚂蚁搜索。传统的基于指标的方法往往排除最差解，而在本文提出的方法中，指标被用来强化最优解。

1 多目标火力分配优化问题

1.1 火力分配问题描述

假设使用m个武器攻击n个目标，且m≥n，武器i攻击j目标的毁伤概率为表示武器的有效性，表示导弹命中概率；毁伤j目标的收益为，设允许多个武器攻击同一个目标，使用武器i攻击j目标后目标生存概率为，所有攻击结束后，j目标的毁伤概率为表示将武器i分配给目标j的数目，如果导弹i打击目标j，那么xij=1；如果导弹i没有打击目标j，那么xij=0。获得的总收益为。火力分配的优化问题的目标函数通常是打击敌方获得的总收益最大。

1.2 多目标优化数学模型

提出让所使用武器成本最小作为第2个目标函数。假设i型武器的成本为ci，则攻击总成本为。因此，多目标火力分配优化问题可定义为：

2 二元性能指标

定义1 二元性能指标

表示该二元指标服从Pareto规则。

文献［1］提出基于指标的进化算法（Indicator-Based Evolutionary Algorithm，IBEA），利用性能指标将适应度值最差的个体删除，剩余个体的适应度值更新。在IBEA中，测试了两种指标：epsilon指标Iε和hypervolume指标IHD，本文只测试指标 Iε。表示使x1支配x2所需移动的最小值。当x1支配x2时，Iε为负值。

3 IBACO算法描述

IBACO算法的基本思想是利用基于指标的方法引导蚂蚁进行搜索找到Pareto近似解，在该算法中只有Pareto解能够释放信息素。在算法的每个循环中，每个蚂蚁构建一个解，一旦构建过程结束，进行适应度分配并采用二元指标更新Pareto解集，信息素根据适应度值更新。当达到最大循环数时，算法终止。

3.1 解的构建

为了用蚁群优化算法求解火力分配问题，火力分配问题可以表示为二分图G=（V，U，E）。V表示n个目标，U表示m个武器，E是连接目标节点和武器节点的边。二分图的多个边组成的一条路径，表示火力分配的一种分配方案，构建火力分配问题的解就是求二分图的路径。

图1 WTA问题二分图

在构建解的过程中，每个蚂蚁从可分配的武器目标集合Cand中构建各自的武器目标分配方案Sant，一旦选择了一个武器或者目标，集合Cand必须更新。

构建解的步骤如下：

步骤1：初始化，蚂蚁随机选择初始点。

步骤2：下一节点的选择。蚂蚁由武器i以概率Pij转移到目标j，在火力分配问题中，存在每个目标允许分配的武器限制的问题，所以蚂蚁在由武器i转移到目标j时需要检查目标j已分配武器数目是否已达到限制。若已达到限制，蚂蚁在该目标点不能移向武器点，只能移向目标点，否则随机移向另一个点。此外，蚂蚁位于一个已被分配的武器点上时，只能移向未被分配的武器点。这两条规则分别对应于模型的两个约束。

概率Pij定义为：

其中：α、β是决定信息素因子ij与启发信息因子ηij相对重要程度的参数。与真实蚂蚁不同，人造蚂蚁在分配武器给不同目标时，纳入启发信息。

步骤3：更新Cand，根据约束条件删除已被分配的武器和已到达分配武器数目限制的目标，回到步骤2，当Cand=0时终止。

3.2 启发信息

多目标优化的启发信息是单目标优化启发信息的聚合，考虑打击敌方获得的总收益最大和使用武器的成本最小为目标函数，那么启发信息可定义为打击敌方收益与成本的比：

3.3 适应度分配

适应度分配是指利用二元性能指标将得到的解根据各自的性能进行排序，也就是说，最优解的适应度值越大。在IBACO中，适应度分配只在Pareto中进行，表明其关于其他解的关系。为评价解x1在整个种群的性能，学者们提出不同的适应度分配方法。其中一个方法就是将剩余种群的性能指标求和。

为了强调支配解对非支配解的影响，采用另一种适应度分配方法：

其中：κ是比例缩放因子。

3.4 信息素更新规则

当Pareto解集中的蚂蚁选择一个武器或目标点以后，通过信息素更新规则来更新武器i到目标j路径上的信息素。

其中ρ为信息素挥发系数，且0＜ρ＜1。

如果解Sant支配解Sant，指标的值为负，当给指标分配负值时，适应度值越大。因此，支配解的适应度值比被支配解的适应度值大。为了引导蚂蚁搜寻，IBACO算法中，信息素只奖励Pareto解集中的解。在信息素更新过程中，根据分配的适应度值，最优解的信息素最高，被蚂蚁选择的概率将会更大。

算法流程如下：

步骤1 初始化信息素init；

步骤2 对每个蚂蚁从ant=1到NbAnts构建一个解Sant；

步骤3 计算解的适应度值；

步骤4 更新Pareto解集P，筛选非支配解；

步骤5 更新信息素；

步骤6 当最大循环数达到时终止，否则回到步骤2。

4 仿真分析

假设有12个武器和10个目标，对每个目标分配的最大武器数a取3。模型的参数设定为如下：

表1 目标价值uj取值

表2 武器的有效性qij取值

表3 武器命中概率ρk取值

表4 武器成本ci取值

4.1 Pareto前沿

图2 Pareto前沿

图2所示用改进的IBACO算法求解多目标火力分配模型得到的解集和真实的Pareto解，该算法求得的解包含了Pareto解，表明了算法求解Pareto解的有效性。每个Pareto解对应的函数值以及分配方案如表5所示。

4.2 算法收敛性分析

求解多目标火力分配问题就是找到近似最优解，在实际应用中，根据作战指挥以及作战需求从中选出实时的方案，因此，算法的收敛性应满足实际需求。图3和图4分别为两种算法单独求解f1和f2的收敛情况。本文提出的算法与ACO相比，指标改进了适应度分配规则，提高了支配解路径上的信息素浓度，最优解的信息素浓度最高，蚂蚁选择最优解的概率越大，从而提高了搜索的效率，因此，能更快得到单个目标函数的最优解。

图3 第1目标函数与迭代次数的关系

图4 第2目标函数与迭代次数的关系

5 结论

首先，综合考虑攻击的收益和消耗，建立了火力分配的数学模型；其次，提出了一种求解火力分配问题的基于指标的蚁群优化算法——IBACO，该算法利用IBEA算法提出的二元性能指标进行优化，通过指标和适应度分配函数改变路径上信息素的浓度，从而引导蚂蚁搜索；最后，通过火力分配的仿真表明了IBACO求解该问题的有效性以及收敛速度明显优于蚁群优化算法。

本文只研究了静态目标分配问题，下一步将考虑作战时间对模型的影响，研究动态目标分配的模型和求解方法。

表5 Pareto前沿函数值及对应分配方案

［1］ZITZLER E，KVNZLI S.Indicator-based selection in multi-objective search［C］//8th International Conference on Parallel Problem Solving from Nature，2004:832-842.

［2］MCMULLEN M P R.An ant colony optimization approach to addressing a JIT sequencing problem with multiple objectives［J］.Artificial Intelligence in Engineering，2001，15（3）:309-317.

［3］BOGDANOWICZ Z R.Advanced input generating algorithm for effect-based weapon-target pairing optimization［J］.IEEE Transaction on System，Man，and Cybernetics-Part B:Cybernetics，2012，42（1）:276-280.

［4］ LEE Z J，SU S F，LEE C Y.Efficiently solving general weapon-target assignment problem by genetic algorithms with greedy eugenics［J］.IEEE Transaction on System，Man，and Cybernetics-Part B:Cybernetics，2003，33（1）:113-121.

［5］CHAHARSOOGHI S K，AMIR H.KERMANI M.An effective ant colony optimization algorithm（ACO）for multi-objective resource allocation problem （MORAP）［J］.Applied Mathematics and Computation，2008（200）:167-177.

［6］WANG J，GAO X G，ZHU Y W.Solving algorithm for TA optimization model based on ACO-SA ［J］.Journal of Systems Engineering and Electronics，2011，22（4）:628-639.

［7］LI J，CHEN J，XIN B.Solving multi-objective multi-stage weapon target assignment problem via adaptive NSGAII and adaptive MOEA/D:a comparison study［C］//Congress on Evolutionary Computation，IEEE，2015:3132-3139.

［8］张滢，杨任农，左家亮，等.基于分解进化多目标优化算法的火力分配问题［J］.系统工程与电子技术，2014，36（12）:2435-2441.

［9］刘晓，刘忠，侯文姝，等.火力分配多目标规划模型的改进MOPSO 算法 ［J］. 系统工程与电子技术，2013，35（2）:326-330.

［10］王喆.蚁群算法及其在火力分配问题中的应用［J］.火力与指挥控制，2009，34（11）:92-94.

Indicator Based Ant Colony Optimization for Multi-objective WTA Problem

XIAO Zhong-hui,KOU Ying-xin,LI Zhan-wu,XU An
（Engineering College of Aeronautics and Astronautics,Air Force Engineering University,Xi’an 710038，China）

The use of Ant Colony Optimization to solve multi-objective problems is a very active research topic.The Weapon-Target Assignment （WTA） problem aims at seeking for a proper assignment of weapons to targets to meet the decision-making requirements.A mathematic model on weapon-target assignment is formulated at first.Then,an indicator-based ant colony Optimization algorithm called IBACO for the multi-objective weapon-target assignment problem is proposed.The description and the process of IBACO proposed are given.The IBACO algorithm proposes a new idea that uses binary quality indicators to guide the search of artificial ants for that the pheromone information is defined relatively to the indicator values.In this paper,we use the indicator optimization to reinforce the best solutions by rewarding pheromone trails.Simulation results show the effectiveness of the algorithm proposed in the paper as well as better convergence performance compared with ACO.

weapon-target assignment，binary-indicator optimization，multi-objective ant colony optimization

E844；TJ760

A

10.3969/j.issn.1002-0640.2017.07.036

1002-0640（2017）07-0165-05

2016-05-08

2016-06-17

肖中晖（1994- ），男，江苏盐城人，硕士研究生。研究方向：航空武器火力控制原理与技术。