基于免疫遗传算法的无人艇任务分配研究∗

胡红波 曹 璐

（1.海装武汉局驻宜昌地区军事代表室 宜昌 443003）

（2.中国船舶重工集团有限公司第七一〇研究所 宜昌 443003）

1 引言

现代战争正朝着透明化、非接触化、无人化的方向发展，随着人工智能技术的进步，无人艇在海上巡逻安防、反水雷以及反潜作战等领域中扮演日益重要的角色［1～2］。无人艇编队协同作战是未来战争的主要发展趋势，作为协同控制关键技术的任务分配，是无人艇协同作战的核心和有效保证。任务分配的主要作用是通过整合无人艇各自的特点，形成“1+1＞2”的总体优势，提高无人艇的战场动态适应能力以及整体作战效能［3～4］。

目前在任务分配求解算法方面已取得了较多的成果，例如基于整数规划模型的算法求解较为简便，但问题规模增大时，求解的难度也变大［5～6］；遗传算法（GA）以生物进化为原型，具有很好的收敛性，但搜索过程中的劣质导致效率低下［7～8］；基于合同网的方法通过互相协商和任务竞争在局部最优的基础上追求全局最优，但问题规模增大导致相互协商次数变多，降低了算法求解的速度［9～10］。

遗传算法在多目标优化时容易出现“早熟”，即收敛于局部极值［11］，为了克服这一缺陷，以提高其全局搜索能力，本文通过将生物免疫机制和遗传算法进行结合，构造一种免疫遗传算法（Immune Ge⁃netic Algorithm，IGA），用于解决多艘无人艇协同任务分配问题，可以有效地提高寻优速度、改善寻优质量。

2 任务分配问题建模

无人艇任务分配是实现无人艇编队协调控制和协同航路规划的前提，主要研究如何从大量目标和无人艇编队之中找到可以最小的代价获得最大任务收益的方案。本文以无人艇损耗最小化、目标价值毁伤最大化以及消耗时间最短建立任务分配模型［12］，并通过加权求和转换为单一目标函数进行求解，各个权值与影响因素的重要程度相关。将各量纲转化为［0，1］集合内的数值，例如令目标的价值V取0～1之间的数值；令Tut=Dut/Dmax，使Tut为第u艘USV与目标t间的距离（到达时间）相对于USV与目标间最远（最长到达时间）距离的百分比。因此，USV任务分配模型为

3 基于IGA的任务分配

3.1 IGA算法流程

生物免疫系统能够进行自我调节，并具有免疫记忆功能，因此抗体多样性增加。IGA将生物免疫原理应用到遗传算法中，通过免疫算子来抑制遗传算法在选择、交叉、变异过程中，因随机操作而带来的个体退化现象，有效地提高上述操作的选择性、目的性，保证种群的多样性并防止未成熟收敛陷入局部最优［13］。

IGA中新抗体的产生依然采用遗传算法中的交叉和变异操作，其结构框图如下图所示。

图1 免疫遗传算法流程图

3.2 抗体适应度计算

无人艇任务分配就是求解目标函数值最大时，USV与目标之间的对应关系，因此通过对任务分配的目标函数进行变化，得到抗体v与抗原之间的结合力 Av：

其中：f(v)为目标函数，Cmin为一个适当地相对较小的数。无人艇任务分配的目的寻求目标函数的最大值，当结合力Av的数值越大，抗体与最优解越接近。

3.3 免疫浓度控制

IGA将免疫系统的浓度控制融入到GA的选择、复制操作中，这样可以保持抗体的多样性。在通常GA采取比例选择的基础上，增加浓度调节因子改进算法的选择操作，实现IGA中抗体的促进和抑制。此时，适应度概率Pf和浓度抑制概率Pd共同组成了个体通过选择之后的再生概率P：

式中，α、β为调节常数，N为抗体总数，ci为抗体浓度。抗体的适应度与选择概率正相关，因此，在保留适应度高的个体的同时，丰富了个体的多样性，有利于早熟现象的改善。

4 仿真验证及分析

4.1 参数设置

在IGA中，有五个参数：群体中所含抗体的数量N、终止代数M、选择概率中适应度概率所占的比例α和交叉概率Pc、变异概率Pm对任务分配问题的求解都有一定的影响。根据在实际问题中的作用效果测试，参数设置如下。

表1 IGA相关参数设置

4.2 仿真验证

仿真场景为3艘无人艇攻击8个不同的目标，假设各目标被确认的概率已知、不同敌方目标的评估值已知、敌方对USV的损伤概率已知、USV与敌方目标的距离已知、USV对敌方目标的杀伤概率已知。IGA具体参数设置如下：种群规模NIND＝40，最大进化代数MAXGEN=400，α=0.6，交叉概率Pc=0.9，变异概率Pm=0.1，经IGA求解得到的目标函数值随迭代次数变化的结果如下图所示。从图中可知，IGA经迭代2次收敛，使无人艇多目标任务分配问题很好地收敛到全局最优。

图2 目标函数值随迭代次数变化图

由IGA计算结果可知，作战效能取最大解（3，2，2，1，1，3，2，1）=0.970时，最终得到的最优分配方案为：目标1和目标6分配给第3艘无人艇，目标2、目标3和目标7分配给第2艘无人艇，目标4、目标5和目标8分配给第1艘无人艇。

4.3 算法有效性分析

从上述仿真算例中可以看出，IGA能够有效地解决USV协同任务分配问题，并反映了无人艇损耗、目标价值毁伤以及消耗时间等因素对任务分配结果的影响。为了分析免疫遗传算法的性能，以10艘无人艇攻击10个目标为例进行仿真对比，结果表明遗传算法与免疫遗传算法均能够有效地处理USV协同任务分配的众多约束条件，解决了USV协同的任务分配问题。从下图可以看出，作战效能目标函数随进化代数变化的曲线均能够收敛到最优值，但IGA的最优值大于GA的最优值，且IGA的收敛速度更快。

图3 IGA与GA目标函数随进化代数变化的曲线

从上图可以看出，遗传算法加入免疫算子后，改进后的遗传算法最优适应度比改进前的最优适应度大，曲线振荡减弱，表明加入免疫算子后，整体收敛速度加快，种群进化时遗传策略保持较好，算法更为稳定，IGA能够快速收敛到全局最优，克服了GA的“早熟现象”缺陷。

5 结语

本文针对无人艇任务分配过程中多参数、多约束条件优化问题，提出了基于免疫遗传算法的任务分配方法。免疫遗传算法通过生物学领域的免疫行为对遗传算法进行改进，很好地保持了种群多样性，从而使算法快速收敛到全局最优解。通过该方法求解无人艇协同任务分配模型，并与遗传算法进行了对比分析，结果表明免疫遗传算法能够快速对多约束条件下的多目标优化问题进行求解，对解决无人艇任务分配优化问题是有效、可行的。