坦克分队WTA问题的改进人工蜂群算法

常天庆， 陈军伟， 张 雷， 杨国振

(装甲兵工程学院控制工程系， 北京 100072)

坦克分队WTA问题的改进人工蜂群算法

常天庆， 陈军伟， 张 雷， 杨国振

(装甲兵工程学院控制工程系， 北京 100072)

针对目前智能算法初期收敛速度难以满足坦克分队武器-目标分配(Weapon-Target Assignment, WTA)要求的问题，提出了一种改进人工蜂群算法。该算法结合NEH启发式算法和随机方法对种群进行初始化，利用变邻域搜索和模拟退火方法改进了采蜜蜂算法，并简化了跟随蜂算法，提出了一种全局最优限制算法。最后，结合不同规模的WTA问题，给出了该算法参数的确定方法。仿真结果表明：改进人工蜂群算法相比于其他算法在初始种群质量和算法初期收敛速度方面具有明显优势，特别适合求解坦克分队WTA问题。

人工蜂群算法；NEH启发式算法；模拟退火算法；WTA；坦克分队

武器-目标分配(Weapon-Target Assignment, WTA)问题在军事上又称作火力分配问题，研究的是在作战过程中明确指出由我方哪些武器对敌方哪些目标采取何种方案进行射击，从而实现作战目的[1]。WTA问题属于典型的NP-hard问题[2]，解空间为(n+1)m(n、m分别为参与战斗的武器、目标数量)。采用枚举法、分支定界法、割平面法、动态规划法等传统算法求解WTA问题，虽然可以得到最优解，但当武器-目标规模较大时，其解算代价是不能接受的。近年来的研究[3-5]已经证明：智能算法可以更快求解NP-hard问题，并得到满意解。其中，粒子群算法(Particle Swarm Optimization, PSO)[6]、遗传算法(Genetic Algorithm, GA)[7]、蚁群算法(Ant Colony Optimization, ACO)[8]均在解WTA问题上取得了一定效果。但由于智能算法在运行初期正反馈信息缺乏，其普遍存在初期收敛速度慢、易陷入局部最优解的问题[9]。

射击反应时间是坦克射击的重要指标，一般的要求是炮手从发现目标到击发的反应时间不超过10 s[10]，如果将WTA加入坦克射击过程中，其求解WTA时间增加1 s，射击反应时间至少增加10%。另外，地面战场作战态势瞬息万变，及时输出一个可行的次优解要比花费长时间寻找满意解更符合坦克分队作战需求。因此，坦克分队WTA问题的求解算法首先需要提高的性能就是算法运行初期收敛速度，同时还要避免陷入局部最优解。

人工蜂群算法(Artificial Bee Colony, ABC)是由Ereiyes大学的Karaboga[11]提出的群智能优化算法。与其他优化算法相比，ABC算法具有多种群协同寻优的特点，可以在更小的种群和时间成本内得到优秀的结果[12-13]。ABC算法独有的“采蜜蜂、跟随蜂”2层寻优机制提高了算法运行初期收敛速度，其“侦察蜂”机制减小了陷入局部最优解的概率[14]。然而，由于ABC算法出现时间较短，其在应用时还存在如下问题[15-17]：1) ABC算法最早提出是用于求解连续多峰函数最值的问题，其位置更新公式不适用于WTA等离散问题；2) 在邻域搜索方面不具备区域搜索能力，仅根据位置更新公式产生单个新解；3) 在接近全局最优解时，由于种群相似度大，搜索速度变慢，仅依靠“侦察蜂”机制难以保证搜索效率。

针对上述问题，笔者提出一种改进ABC算法，并通过与其他算法的仿真对比验证该算法在解决坦克分队WTA问题上的优势。

1 坦克分队WTA问题描述

红蓝双方装甲分队处于会战某时刻，此时红方有m个战术单位，称为武器集W={Wi}，i=1,2,…,m。蓝方装甲分队有n个战术单位，称为目标集T={Tj}，j=1,2,…,n。红方目标是使打击效果最大化，建立坦克分队WTA模型如下[18]：

(1)

(2)

(3)

式中：tj∈[0,1]，为目标j对武器集W的威胁程度；pij∈[0,1]，为武器i对目标j的命中概率；xij={0,1}，xij=1表示Wi对Tj进行打击，否则xij=0。由于一个武器同一时刻只能打击一个目标，因此设置约束条件(2)；由于射击武器数量不能超过武器总数m，因此设置约束条件(3)。

2 改进ABC算法

2.1 基本ABC算法

ABC算法是模拟自然蜂群采蜜行为的一种群智能算法。该算法定义了食物源、采蜜蜂、跟随蜂、侦察蜂4个组件，以及搜索、招募、放弃蜜源3个行为。每一个食物源有且只有一个采蜜蜂，食物源的位置代表优化问题的一个可行解，每个食物源的蜂蜜量代表相关解的质量，称为收益度。算法开始时，所有蜜蜂均为侦察蜂，采用完全随机的方式寻找食物源，即问题的解；寻找到食物源后，所有侦察蜂返回蜂巢，根据所持有食物源的收益度遵循一定概率成为采蜜蜂或跟随蜂；采蜜蜂回到原食物源附近继续寻找新食物源，跟随蜂选择在蜂巢等待；当采蜜蜂完成新食物源的寻找后回到蜂巢，跟随蜂根据采蜜蜂所持新食物源的收益度遵循一定概率接受招募，在新食物源附近进一步寻找食物源；如果采蜜蜂和跟随蜂经过一定次数寻找后未能找到收益度更高的食物源，则放弃当前食物源并成为侦察蜂，依然采用完全随机的方式搜索食物源。

2.2 改进ABC算法流程

改进ABC算法沿用了标准ABC算法主流程，对其中的子算法进行了改进，其流程如图1所示。改进ABC算法具体步骤如下：

图1 改进ABC算法总体流程

1) 进行参数初始化，包括设定种群规模N，最大迭代次数M，蜂群控制参数L、L2,全局阈值Lmax，最优解阈值Bmax和初始搜索范围S；

2) 采用NEH启发式算法[19]进行采蜜蜂的种群初始化，运用随机方法进行跟随蜂的种群初始化，采蜜蜂与跟随蜂的数量相等；

3) 采蜜蜂采用基于变邻域与模拟退火(Simulated Annealing, SA)[20]的算法进行邻域搜索；

4) 采用简化的跟随蜂算法保持种群中的最优个体；

5) 采用基于遗传算子的全局最优限制算法协调2种蜂群中最优个体的数量，防止因种群相似度过大而陷入早熟；

6) 判断是否满足算法终止条件，若满足，则输出最优解，否则返回步骤3)。

与标准ABC算法相同，侦察蜂算法嵌入采蜜蜂算法和跟随蜂算法中。当采蜜蜂或跟随蜂的控制参数L、L2达到阈值Lmax时，则采蜜蜂或跟随蜂放弃食物源并转变为侦察蜂，以全随机的方式寻找新的食物源。

2.3 种群编码方法

食物源(分配方案)可编码为N个m维向量所组成的矩阵形式：X=(xuv)N×m。其中：u=1,2,…,N，N为食物源数量，也是采蜜蜂数量；v为武器的编号；xuv是区间[0,n]内的整数，xuv=j(j≠0)表示在分配方案u中，编号为v的武器射击编号为j的目标，xuv=0表示武器v没有射击目标。

2.4 NEH启发式算法和随机方法相结合的种群初始化

初始种群的多样性特征和个体解的质量对后期算法寻优效果具有重要影响。标准ABC算法采用全随机的方法生成初始化种群，这种方法简单易行、离散度高，有利于全局寻优，但初始种群质量较差，限制了算法初期的收敛速度。为此，本文采用NEH启发式算法和随机方法相结合(简称“混合法”)进行种群初始化。

NEH启发式算法是为解决流水线车间调度问题所提出的一种启发式算法[21]，本文基于NEH基本方法并加以改进，对采蜜蜂进行种群初始化，具体步骤如下：

1) 将所有n个目标按照威胁程度递减的顺序进行排列；

2) 选择威胁程度最大的目标jtmax，并计算武器单独打击目标产生的收益Qi=tj·pij,i=1,2,…,m，选择其中收益最大的武器和目标进行匹配；

3) 更新武器集、目标集，将步骤2)中选择的武器、目标从集合中去除，令m=m-1,n=n-1；

4) 判断m·n是否为0，若否，返回步骤2)，否则初始化结束，输出WTA分配结果。

通过这种方法可以得到一个可行解，将其插入采蜜蜂群中，其他采蜜蜂和跟随蜂采用全随机的方该进行种群初始化。

这样的种群初始化方法可以有效提高初始种群质量和算法运行初期的收敛速度，但由于初始化后某一个体收益度远超种群平均收益度，该个体很快占据优势比例，降低了全局最优解的搜索能力，导致算法陷入早熟。为此，笔者将通过改进的采蜜蜂算法和全局最优限制算法予以解决。

2.5 基于变邻域与模拟退火的采蜜蜂算法

采蜜蜂负责在食物源附近搜索优秀解，传统的搜索方法是在m维的编码中随机选择一个位置，在可行域内随机生成新的编码值。这种固定域的搜索方法忽视了算法在不同迭代次数时对搜索宽度的不同需求。本文采用一种搜索范围随迭代过程变化的变邻域搜索算法，参数初始化时给定了一个搜索范围S，则更新搜索邻域的公式为

s.t.S≥Slimit。

式中：C为算法迭代次数；Cmax为设定的算法最大迭代次数；ceil表示对括号内的内容向上取整。为确保算法运行后期变邻域依然可以起到搜索新食物源的作用，设置约束条件S≥Slimit，Slimit的数值需要根据求解问题中目标的数量n来确定，一般取Slimit=n/4。与固定邻域的食物源搜索方法相比，变邻域的搜索范围在初始值S的基础上随迭代次数的增加而不断变小。这种方法既提高了算法运行初期的搜索宽度，又加快了算法运行后期的寻优速度。

在采蜜蜂搜索过程中，将蜂群分为2部分：1) 采用SA算法对蜂群中具有最优收益度的解进行深度搜索，SA算法的搜索邻域依然采用变邻域的方法；2) 对其他采蜜蜂所拥有的解仅采用变邻域的方法进行搜索。新编码搜索更新方法如下：

模拟退火算法的引入不但提高了优秀解的局部搜索能力，而且其概率突跳特性可以有效降低算法早熟的概率，突跳概率为

P=exp[-(fit(E2)-fit(E1))]，

式中：fit(E1)、fit(E2)分别为采蜜蜂E1和E2的收益度。

基于变邻域与模拟退火的采蜜蜂算法流程如图2所示，采用数组L作为蜂群控制参数，记录各个采蜜蜂连续未更新的代数。个体更新后，L中的对应值归0；否则，对应值加1。当采蜜蜂在L中的对应值达到全局阈值Lmax时，采蜜蜂转变为侦察蜂，侦察蜂随机寻找新的食物源替换当前个体。SA算法中：Tstart为初始温度；Tend为终止温度；T为温度；K为退火系数。

图2 基于变邻域与模拟退火的采蜜蜂算法流程

2.6 简化的跟随蜂算法

在标准ABC算法中，跟随蜂会根据采蜜蜂所持信息采用轮盘赌的方法进行选择，持有高收益度食物源的采蜜蜂被选中的概率较大；反之，被选中的概率较小。跟随蜂在选中采蜜蜂后，会在采蜜蜂持有解的基础上进行搜索，产生一个新解，分别与采蜜蜂持有解和自身解进行比较，保留较优秀的解。与其他群智能优化算法相比，这种二次搜索的方法相当于在总体上提高了蜂群1倍的搜索量，跟随蜂可以在采蜜蜂的基础上更深度地搜索优秀解。

在基于变邻域与SA的采蜜蜂算法中，变邻域搜索增加了采蜜蜂群优秀解的搜索广度，SA算法增加了采蜜蜂群优秀解的搜索深度。此时，由于跟随蜂在采蜜蜂基础上进行深度搜索时只产生一个新解，因此对最优解收益度的提高效果有限。如果仍然在跟随蜂中采用基于变邻域和SA的搜索方法，不仅增加了算法复杂度，还会使算法陷入早熟。

因此，本文对标准ABC算法中的跟随蜂算法进行了简化：首先跟随蜂采用轮盘赌的方法进行选择；而后仅根据贪婪法进行更新，不再进行二次搜索。比较跟随蜂与采蜜蜂所拥有可行解的收益度，保留其中收益度大的解。另外，在跟随蜂群中采用数组L2记录各跟随蜂连续未更新的代数，跟随蜂更新后，L2中的对应值归0；否则，对应值加1。当跟随蜂在L2中的对应值达到全局阈值Lmax时，跟随蜂转变为侦察蜂，侦察蜂随机寻找新的食物源替换当前个体。

2.7 基于遗传算子的全局最优限制算法

种群相似度过大容易造成算法陷入局部最优解，虽然算法已经引入了全局阈值Lmax对种群个体进行控制，但由于本文改进了种群初始化方法以及采蜜蜂搜索方法，算法运行初期最优解收益度大大超过种群平均个体收益度，最优解会迅速占据优势比例，限制算法的全局搜索能力。为解决这一问题，笔者提出了一种基于遗传算子的全局最优限制算法，用于减少2种群中最优解的重复度。以采蜜蜂为例，其全局最优限制算法流程如图3所示。

图3 采蜜蜂全局最优限制算法流程

算法设计了控制阈值Bmax，目的是限制蜂群中最优解的数量。当蜂群中的最优解数量Bnum超过阈值Bmax时，从种群中任选2个最优解，如果2个最优解的收益度相等，任意选择其中一个变成侦察蜂随机搜索食物源并替代原有解；否则，借用遗传算子中的交叉操作(cross)，通过最优解的交叉合并产生2个子代解。如果2个子代解的收益度值较当前群体最优值发生改变，则保留2个子代解；否则，任意选择一个变成侦察蜂随机搜索食物源并替代原有解。交叉算子(cross)的具体流程如图4所示。

图4 交叉算子(cross)流程

在交叉算子中，随机生成指示参数I1、I2、I3、I4,E1与E2交换指示参数所截取出的序列，并去掉重复部分，可以获得新解Elfinal与E2final。经过cross操作后，蜂群中的最优解数量可以限制在阈值Bmax之内。为提高优秀蜂群的搜索能力，采用SA算法对其他未进行交叉算子操作的解进行优化。为兼顾搜索效率，SA算法中邻域产生法采用单次交叉法[22]。

3 仿真分析

3.1 仿真环境

改进ABC算法运行环境如表1所示。

表1 改进ABC算法运行环境

3.2 种群初始化方法验证

WTA问题还没有公认的标准算例，但文献[23]中所使用的算例最具代表性，也是被比较最多的算例。因此，为验证采用混合法进行种群初始化的优势，分别采用混合法和全随机法对文献[23]中的算例进行100次仿真计算，对每次迭代后的平均最优解进行比较，结果如图5所示。

图5 混合法和全随机法种群初始化的各代平均最优解

通过图5可以看出：采用混合法进行种群初始化可以有效提高初始种群的质量和算法运行初期的收敛速度，但降低了全局最优解的搜索能力，致使算法陷入早熟。

3.3 全局最优限制算法验证

全局最优限制算法可以在保留最优解的情况下限制蜂群中最优解的数量，增加了种群多样性，提高了算法的全局搜索能力。采用该算法对文献[23]中的算例进行100次仿真计算，图6为采用全局最优限制算法前后各代平均最优解对比。可以看出：采用了基于遗传算子的全局最优限制算法后，平均最优解的质量得到了提高。

3.4 参数确定

为充分验证改进ABC算法在WTA问题上的有效性，选取了3个不同规模的WTA算例，分别为5打3(算例1)、11打7(算例2)、17打10(算例3)。3个算例的武器-目标命中概率如表2所示，目标威胁程度如表3所示。

图6 采用全局最优限制算法前后各代平均最优解对比

表2 武器-目标命中概率

表3 目标威胁程度

改进ABC算法的控制参数为：种群规模N、各蜂群规模Ns、最大迭代次数M、全局阈值Lmax、最优解阈值Bmax、初始搜索范围S。首先综合考虑算法优化效果和收敛时间可以确定各参数的取值范围，具体如表4所示。

而后通过算例具体确定全局阈值Lmax与最优解阈值Bmax的取值。由于2种参数独立，可先在不加入全局最优限制算法的条件下确定Lmax的取值。利用3种不同规模的WTA算例，分别对Lmax取[5,10]内的整数值各进行100次仿真运算，比较平均最优解(Average Optimal, AO)、平均均值(Average Mean, AM)、平均最差解(Average Worst, AW)，结果如表5所示。可以看出：对于算例1，Lmax=6时结果最优；对于算例2，Lmax=7时结果最优；对于算例3，Lmax=8时结果最优。

表4 改进ABC算法参数取值范围

在确定参数Lmax后，采用同样的验证方法确定Bmax的取值，结果如表6所示。可以看出：当Bmax=Ns/6时，解算性能最优。

表5 不同Lmax取值下的结果对比

表6 不同Bmax取值下的结果对比

3.5 算法比较

分别采用GA、PSO、ACO、标准ABC以及本文的改进ABC (IABC)算法对算例2进行100次仿真计算，对比5种算法各代的平均最优解，具体结果如图7所示。

图7 5种算法各代平均最优解对比

通过图7可以看出：混合种群初始化方法和SA算法的引入对标准ABC算法初始种群质量和初期收敛速度改善明显；与单独引入混合种群初始化方法(如图5所示)的收敛效果相比，变邻域搜索方法和全局最优限制算法的引入改善了标准ABC算法运行后期的寻优能力。总体来说，虽然改进ABC算法的最优解稍逊于标准ABC算法，但由于该算法在运行初期具有明显优势，因此特别适用于求解坦克分队WTA问题。

4 结论

本文提出了一种改进ABC算法，有效满足了坦克分队WTA对求解算法初期收敛速度的要求。但该算法依然采用有限迭代次数的停止方法，下一步将研究一种新型的算法停止控制方法，以满足坦克分队WTA可以随时输出有效解的要求。

[1] Cai H P, Liu J X, Chen Y W, et al. Survey of the Research on Dynamic Weapon-target Assignment Problem [J]. Journal of System Engineering and Electronics, 2006, 17(3): 559-565.

[2] Lloyd S P, Witsenhausen H S. Weapons Allocation is NP-complete[C]∥Metler W A. Proceedings of the 1986 Summer Computer Simulation Conference. Reno,USA: The Society for Modeling and Simulation International, 1986: 1054-1058.

[3] Athanasios C S, Stavros T P, Ilias P T, et al. A New Hybrid Parallel Genetic Algorithm for the Job-shop Scheduling Problem[J]. International Transactions in Operational Research, 2014, 21(3): 479-499.

[4] Zhu X, Li X P, Wang Q. Objective Increment Based Metaheuristic for Total Flow Time Minimization in No-wait Flow Shops [J]. Journal of Southeast University, 2008, 24(2): 168-173.

[5] 杜鹏祯, 唐振民, 孙研. 一种面向对象的多角色蚁群算法及其TSP问题求解[J]. 控制与决策, 2014, 29(10): 1729-1736.

[6] 曲在滨, 刘彦君,徐晓飞. 用离散粒子群优化算法求解WTA问题[J]. 哈尔滨工业大学学报, 2013, 43(3): 67-69.

[7] Changdar C, Rajat G S M. An Efficient Genetic Algorithm for Multi-objective Solid Travelling Salesman Problem under Fuzziness [J]. Swarm and Evolutionary Computation, 2014, 15: 27-37.

[8] Lee Z J, Lee W L. A Hybrid Search Algorithm of Ant Colony Optimization and Genetic Algorithm Applied to Weapon-Target Assignment Problems [J]. Lecture Notes in Computer Science, 2003, 2690 (1): 278-285.

[9] Zhang J. A Hybrid Lehmer Code Genetic Algorithm and Its Application on Traveling Salesman Problems [D]. Norfolk: Old Dominion University, Doctoral Dissertation, 2011.

[10] 王春忠, 荣明, 张成亮, 等. 坦克嵌入式车场射击训练炮长操纵控制模型[J]. 装甲兵工程学院学报, 2008, 22(6): 19-21.

[11] Karaboga D. An Idea Based on Honey Bee Swarm for Numerical Optimization [R]. Kayseri: Engineering Faculty Computer Engineering Department, Ereiyes University, 2005.

[12] Omkar S, Senthilnath J, Khandelwal R. Artificial Bee Colony (ABC) for Multi-objective Design Optimization of Composite Structures [J]. Applied Soft Computing, 2011, 11(1): 489-499.

[13] Mansouria P, Asadya B, Gupta N. An Approximation Algorithm for Fuzzy Polynomial Interpolation with Artificial Bee Colony Algorithm [J]. Applied Soft Computing, 2013, 13(4): 1997-2002.

[14] Gao W, Liu S. A Modified Artificial Bee Colony Algorithm [J]. Computers & Operations Research, 2012, 39(3): 687-697.

[15] Zhang W, Wang N, Yang S. Hybrid Artificial Bee Colony Algorithm for Parameter Estimation of Proton Exchange Membrane Fuel Cell [J]. International Journal of Hydrogen Energy, 2013, 38(14): 5796-5806.

[16] Bullinaria J, AlYahya K. Artificial Bee Colony Training of Neural Networks[EB/OL].(2013-12-06)[2015-05-20]. http://www.cs.bhan.ac.uk/～jxb/PUBS/NICOS13.pdf

[17] Zhang D L, Tang Y G, Guan X P. Optimum Design of Fractional Order PID Controller for an AVR System Using an Improved Artificial Bee Colony Algorithm [J]. 自动化学报, 2014, 40(5): 973-980.

[18] 常天庆, 陈军伟, 郝娜,等. 装甲分队动态武器目标分配中蚁群算法终止控制[J]. 系统工程与电子技术, 2015, 37(2): 343-347.

[19] Nawaz M, Enscore E, Ham I. A Heuristic Algorithm for them-Machinen-job Flow-shop Sequencing Problem [J]. The International Journal of Management Sciences, 1983, 11(1): 91-95.

[20] Kirkpatrick S, Gelatt J C D, Vecchi M P. Optimization by Simulated Annealing [J]. Science, 1983, 4598 (220): 671-680.

[21] Kalczynski P J, Kamburowski J. On the NEH Heuristic for Minimizing the Makespan in Permutation Flowshops [J]. The International Journal of Management Sciences, 2007, 35(1): 53-60.

[22] 王凌, 刘波, 微粒群优化与调度算法[M]. 北京: 清华大学出版社, 2008.

[23] 韩瑞新, 朱红胜, 卢厚清, 等. 舰艇编队防空火力基于改进遗传算法的分配方案[J]. 解放军理工大学学报：自然科学版, 2006, 7(1): 46-50.

(责任编辑: 尚彩娟)

《装甲兵工程学院学报》2016年征订启事

《装甲兵工程学院学报》创刊于1987年，是以反映陆军武器装备工程技术与军事理论为主的综合性学术刊物，双月刊，国内外公开发行，大16开本，每期112页，双月25日出版。2016年定价为15.00元/期，全年90.00元(免邮寄费)。本刊自办发行，无邮发代号，欲订阅者可直接与本刊编辑部联系，编辑部随时办理订阅手续。

订阅者请填写下面的回执，并通过邮寄或E-mail的方式发回本刊编辑部。

《装甲兵工程学院学报》2016年订阅回执

通信地址： 北京市丰台区杜家坎21号《装甲兵工程学院学报》编辑部 邮 编： 100072

联系人： 王老师 联系电话： 010-66719443 E-mail: xuebaozjb@163.com

An Improved Artificial Bee Colony Algorithm for Tank Unit WTA Problem

CHANG Tian-qing, CHEN Jun-wei, ZHANG Lei, YANG Guo-zhen

(Department of Control Engineering, Academy of Armored Force Engineering, Beijing 100072, China)

Aiming at the problem that it is difficult for the current intelligent algorithms to meet the requirement of tank unit Weapon-Target Assignment (WTA) for faster convergence speed on the early stage, an improved Artificial Bee Colony (ABC) algorithm is proposed. This algorithm adopts a combination method of NEH heuristic algorithm and random method for population initialization, uses variable neighborhood search and simulated annealing method for improving employed bees algorithm and simplifying unemployed bees algorithm, and introduces a global optimal limit algorithm. At last, combining different scale of WTA problem, the method used to determine algorithm parameters are given. The simulation results reveal that the improved ABC has a significant advantage on the quality of the initial population and the convergence speed on the early stage over other algorithms, and it is particularly suitable for tank unit WTA problem.

artificial bee colony; NEH heuristic optimization algorithm; simulated annealing algorithm; WTA; tank unit

1672-1497(2015)05-0069-08

2015-07-29

军队科研计划项目

常天庆(1963-)，男，教授，博士。

TP301.6

A

10.3969/j.issn.1672-1497.2015.05.015