基于改进布谷鸟算法的目标分配问题

李宜芮，张云志，王 刚，王晶晶

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

0 引言

在防空作战过程中，武器-目标分配（WTA）问题是作战指挥决策的关键环节，其解空间大小随着防御武器数目及来袭目标数目的增加呈指数级增长，是一个多参数、多约束的NP完全问题，许多学者将智能算法引入目标分配优化中，取得了不少研究成果［1-3］，但传统的算法存在耗时长、收敛慢、寻优效果差的缺陷，在复杂多变的防空作战环境中，无法满足作战决策的实时、动态需求。如何运用高效的目标分配算法最大程度地提高防空系统的作战效能，解决目标分配中存在的实时性难题，适应现代防空快速的作战节奏，成为WTA问题的重点。

受多种群并行计算思想［4-5］的启发，基于全局搜索能力强的布谷鸟算法［6］的基础上，建立种群协同进化机制，制定种群交流策略，实现种群间的信息交流共享，加快算法的收敛速度；在并行种群中加入免疫机制，增加了种群的局部寻优能力，同时提高了算法的精确性和收敛速度，通过将其应用到目标分配问题，验证了算法的可行性和有效性。

1 基本布谷鸟算法

标准布谷鸟算法的主要思想是通过Le'vy飞行路径产生候选鸟窝以及采用精英保留策略更新当前鸟窝位置，最终使鸟窝位置能够达到或接近全局最优解［7］。

首先，在寻窝过程中，设定3个理想状态：

1）对于每个布谷鸟而言，一次产卵一个，采用随机方式选择寄生鸟巢；

2）对于被布谷鸟寄生的鸟巢，符合一定条件的鸟巢将会保留到下一代；

3）布谷鸟可以用来寄生的鸟巢的数目是固定的，同时宿主发现外来鸟蛋的概率为pa。

因此，在这3个理想状态的基础上，布谷鸟寻找鸟窝的路径和位置更新公式如下：

2 改进布谷鸟算法

标准布谷鸟算法参数少，收敛速度对参数不敏感，不易陷入局部最优，全局搜索能力强，但收敛速度较慢，缺少进化活力。因此，针对布谷鸟算法的收敛速度和进化活力问题，提出改进的布谷鸟算法。

改进布谷鸟算法采用种群协同进化机制，在种群中采用不同的搜索策略进行全局搜索和局部搜索，通过种群间的信息交流，加快算法求解的收敛速度，在局部搜索中采用免疫机制，进行个体变异操作，增加算法的进化活力，最后达到算法的快速收敛和解的精准性。

2.1 种群协同进化机制

基本思想：采用多个种群同时进化的方法，每个种群采用不同的搜索机制沿着不同的方向进化，让种群的进化各有侧重，并通过种群交互策略使得种群协同进化，快速搜索到全局最优解，缩短算法运行时间，同时保证解的精准性。

2.1.1 种群设置

基于种群协同进化的思想，构建两个种群协同进化结构，由精英种群（α_pop）和开发种群（β_pop）组成。在开发种群中通过布谷鸟算法进行全局搜索，发现整个种群中的优质解；在精英种群中采用局部收敛速度较快的免疫机制，对精英个体进行变异操作，加强了算法的局部搜索能力，发掘最优个体的能力。

多种群协同进化机制使得算法的搜索方式具有多样性和针对性。如表1所示。

表1 种群设置

2.1.2 种群进化

如图1所示，精英种群指导开发种群向其进化，因此，设置初始开发种群规模设定为3N/4，随着算法的进行，开发种群中的个体慢慢向精英种群进化，种群规模越来越小，通过式（3）对种群的规模进行自适应调整，使精英种群的规模得到补充，提高算法的收敛速度。

2.1.3 种群交互

在种群协同进化模型中涉及到种群间信息交流，精英种群通过利用精英个体与开发种群的个体进行信息交流，引导开发种群的进化方向，加快开发种群的收敛速度。在种群交流策略中运用简单的自适应交流算子β，进行种群交流。假设精英个体（鸟窝）的位置为，则按照交流策略更新鸟窝：

通过简单的自适应交流算子，减少算法计算复杂度，同时将精英个体信息传递给开发种群，调节开发种群中的个体进化方向，使开发种群朝着越来越优秀的趋势发展，加快算法的收敛速度。

2.2 免疫机制

精英种群由开发种群中的精英个体（鸟窝）构成，精英个体与全局最优解之间的相似度要大于整个种群中的其他个体，而且与精英个体有较大相似度的个体也应有较高的适应度［8］。因此，通过免疫机制进行种群的更新和进化，提高算法的局部搜索速度，在精英个体附近寻找最优解，加快算法收敛速度。

采用高斯变异算子对精英种群中个体进行变异操作，提高局部搜索能力和种群进化活力：

高斯变异算子以较高的概率在小邻域范围内产生一个随机数对个体产生干扰形成变异，这种高概率小步长变异使基于高斯变异算法的局部搜索能力更好。

2.3 求解步骤

改进的布谷鸟的算法主要是通过两个种群的并行计算，以及精英种群指导开发种群进行进化，利用布谷鸟算法进行全局寻优，高斯变异加快局部寻优的方法，加快算法的收敛速度，提高算法求解的精准性，其流程如图2所示。

改进布谷鸟算法的求解步骤为：

Step 1：初始化种群，产生n个鸟窝；

Step 2：由式（8）计算每个鸟窝的适应度值，划分成精英种群和开发种群；按照式（3）进行种群规模变化更新；

Step 3：精英种群通过式（4）、式（5）与开发种群中每个个体进行信息交流，指导开发种群进化方向；

Step 4：开发种群利用布谷鸟算法按照式（1）进行全局寻优；精英种群通过高斯变异，按照式（6）、式（7）进行种群更新；

Step 5：将开发种群和精英种群合成新种群，记录最优解，若终止条件不满足，则重复Step 2～Step 4。

3 利用改进布谷鸟算法求解动态WTA问题

3.1WTA问题模型

假设有 n 个来袭目标 T1，T2，…，Tn，分多批次到达目标分配起始线，第j（j=1，2，…，n）目标的综合威胁度为 Vj，阵地有 m 个防空武器系统 W1，W2，…，Wm其中武器系统Wi拥有的火力单元数为ri，同时对来袭目标Tj的杀伤拦截概率为pij，对目标j分配Sj个火力通道。目标分配以充分发挥武器效能，拦截目标期望最大为原则，则WTA问题模型为：

其中，摧毁目标的最低杀伤概率Pij、目标综合威胁度Vj和拦截概率pij以及针对动态目标的防空作战拦截时间、资源、杀伤区等约束条件由上级指挥所或情报中心及武器性能决定，Xij={xij}为射击矩阵，

3.2 初始化问题

初始化问题一直是算法求解中一个关键性问题，影响算法的收敛速度及求解的质量。由于防空作战的实时性、动态性及来袭目标的复杂多变性，造成作战目标分配需要实时、重复循环进行，因此，针对动态WTA问题，设计根据初始化种群规模，利用前次目标分配中适应度值较好的方案作为下次目标分配的初始化种群，提高算法求解的速度，保证防空作战的高实时性需求。

3.3 编码

防空反导作战是多武器对多目标的最优匹配问题，每一个武器可以拦截多个威胁目标，多个武器可以拦截一个威胁目标，由于来袭目标的动态性、复杂性及数量的不确定性，采用十进制编码方式对目标进行编码，鸟窝的每一个位置代表进行拦截的武器系统，同时留有空余位可以随时进行扩展编码，应对来袭目标的动态变化，如图3所示。

4 仿真分析

假设某次防空作战中共有9个来袭目标T1、T2、…、T9，分2批次不同时刻到达，第1批次目标T1～T7在t1时刻来袭，第2批次目标T8～T9在t2时刻来袭，各批次目标均在不同时刻到达目标分配终线，我方阵地部署6种防空武器系统W1、W2、W3、W4、W5、W6，各类武器系统的火力通道数为{2，1，2，1，2，1}，对目标分配最多火力通道数量都为1。假设来袭目标不会临时取消进攻任务并且均进入武器系统的杀伤区，通过上级指挥所或者情报中心得到各来袭目标综合威胁程度及各武器系统对目标的杀伤概率如表2所示。

表2 威胁目标威胁度和武器系统拦截概率

根据目标分配原则及目标来袭的时间约束、资源约束、杀伤约束等条件，按照上述空情对目标进行动态分配，过程如表3所示。

表3 目标动态分配过程

根据算法求解WTA问题的规模，设定初始种群中鸟窝数量为60，迭代次数为100次，利用改进布谷鸟算法与文献［9-10］中的遗传算法、免疫算法在相同的仿真条件下进行计算，仿真结果如表4所示。

表4 目标分配仿真结果

为了验证改进算法的收敛性能和收敛速度，通过多次仿真后得到稳定的结果，如图4所示。

从图4可以看出，在仿真时刻t=4和t=50时刻，由于大批威胁目标的到来，作战效能快速上升，通过算法的优化，目标分配方案快速收敛趋于稳定。当第1批次目标来袭时，利用种群协同进化机制的布谷鸟算法具有较好的收敛性，收敛速度较免疫算法、遗传算法更快，不易陷入局部最优，由于来袭目标的动态变化，遗传算法和免疫算法无法快速收敛，且易陷入局部最优。当第2批目标来袭时，种群的初始化建立在前次寻优的优质个体的基础上，因此，快速收敛，迅速达到稳定状态。

为了进一步验证分析算法的稳定性，利用相同的条件，对3种算法进行100次蒙特卡洛仿真，通过每次与最优解的比较，得到如图5所示仿真结果。

结果显示，免疫算法与遗传算法寻优的稳定性一般，主要是因为其算法的随机性及后期迭代容易陷入局部最优造成的，而改进的布谷鸟算法利用协同进化的思想及布谷鸟算法强大的全局寻优能力和高斯变异强大的局部搜索能力，因此，稳定性较好。仿真实验表明利用本文算法求解动态WTA问题是有效可行的。

5 结论

目标分配是防空作战指挥决策的一个关键部分，其分配的实时性、动态性需求及算法的稳定性问题，严重影响武器系统的作战效能。该算法引入种群协同进化机制，利用种群并行计算的思想，加快算法的收敛速度，显著提高了算法求解效率，较好地完成了武器目标分配的要求，为求解WTA问题的算法提供一种新的思路。

［1］原银忠，韩传久.用遗传算法实现防空导弹体系的目标分配［J］.火力与指挥控制，2008，33（3）：80-83.

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

［3］徐克虎，黄大山，王天召.改进的人工免疫算法求解武器-目标分配问题［J］.系统工程与电子技术，2013，35（10）：2121-2127.

［4］孟安波，李阳，陈育成，等.基于种群替代的量子粒子群算法的含风电网无功优化［J］.电气技术，2014，5（3）：65-69.

［5］邹琳，夏巨谌，胡国安.基于实数编码的多种群并行遗传算法研究 ［J］.小型微型计算机系统，2004，25（6）：982-986.

［6］兰少峰，刘升.布谷鸟搜索算法研究综述［J］.计算机工程与设计，2015，36（4）：1063-1067.

［7］YANG X S.Cuckoo search via levy fights［C］//Nature&Biologically Inspired Computing.World Congress on IEEE，2009：210-214.

［8］伍艳莲，姜海燕，庄嘉祥，等.精英策略个体优势遗传算法研究［J］.计算机工程与应用，2016，52（7）：143-149.

［9］刘洪引，李体方，王立安.基于改进人工免疫算法的火力分配［J］.火力与指挥控制，2014，39（10）：171-174.

［10］梁冠辉，朱元昌，邸彦强.改进遗传算法在防空武器目标分配中的应用研究［J］.军械工程学院学报，2009，21（1）：1-4.