基于多种群遗传算法的多UUV 任务分配方法

范学满,薛昌友,张会

(海军潜艇学院,山东 青岛,266199)

0 引言

利用搭载传感器载荷的无人水下航行器(unmanned undersea vehicle,UUV)执行对海侦察任务是UUV 典型应用方向之一。单个UUV 在巡航时间、载荷数量以及种类等方面制约了其侦察能力,往往需要多UUV 协同作战。此时,根据任务的复杂度、UUV 数量以及任务完成能力等因素,对任务进行合理地分配,对于提高任务执行效率至关重要[1]。

任务分配是海战场多UUV 协同作战的重要研究内容之一,其目的是在实现各技术、战术指标的前提下,根据目标状态和战场态势,将任务分配给各UUV,使得整个多UUV 系统的整体作战收益最大,付出的代价最小[2]。目前,常用的任务分配算法主要有基于市场机制的分配方法、指派方法和启发式算法等。其中:基于市场机制的方法受市场经济学启发提出,是基于买卖双方的需求与能力,通过竞争与交换完成分配,又细分为拍卖算法和合同网算法等[3];指派方法是基于任务需求和约束条件,依据特定的指派原则确定任务分配方案[4];启发式算法是受大自然运行规律或面向具体问题的经验、规则启发出来的方法,相比另外2 种算法,具有高鲁棒性和求解高度复杂非线性问题的能力,已成为解决任务分配问题的主流方法。遗传算法就是典型的启发式算法[5]。

文献[6]～[9]利用多种群遗传算法求解多目标多约束问题,通过为不同的种群分配不同概率的重组和变异算子,并行实现多样化的搜索结果;通过在各种群内部引入“精英保留”策略,改进遗传算法的全局收敛能力;通过设置种群间的个体迁移操作,实现协同进化。但对于复杂、大规模约束问题仍存在收敛过慢、进化不充分等问题。为了解决上述问题,文中提出一种人机融合的多种群遗传算法用于多UUV 协同侦察任务分配,一方面,针对多UUV 协同任务分配的多约束特性,引入人类先验知识进行种群初始化,提升初代种群的个体质量,加速算法收敛;另外,针对可行性法则处理多约束条件时,存在多代种群极易缺乏甚至没有满足约束个体的问题,引入“遗忘策略”弥补可能出现的进化不彻底问题。并针对多基地、多目标、多约束的多UUV 协同侦察任务分配问题开展上述研究,通过与单种群遗传算法对比,验证了文中算法的有效性和鲁棒性。

1 多UUV 协同侦察任务分配模型

1.1 模型假设

多UUV 协同侦察任务分配问题是一个典型的多约束、多参数的非确定多项式(non-deterministic polynomial,NP)问题,该问题涉及系统结构、单UUV、任务目标和外界环境等多因素,针对不同因素的模型求解策略有较大不同。文中基本假设如下:

1) 任务目标事先确定,环境因素已知且不发生重大变化;

2) UUV 经过目标,任务即完成;

3) 每个侦察任务由单个UUV 即可完成;

4) 目标位置已知且静止,对UUV 不构成威胁;

5) 各UUV 位于不同的基地;

6) 单个UUV 可搭载多种侦察载荷。

1.2 符号描述

1.3 约束条件

由于协同侦察任务的复杂性,可以将任务集合中的任务分为独立任务和协同任务2 类。其中,独立任务是只与其自身约束相关的任务;协同任务是除自身约束外,相互间还存在时间或功能约束的任务。任务自身约束主要包括时间约束和载荷约束等,任务之间的约束主要包括时序约束和使能约束等,另外UUV 自身约束主要包括物资约束和最大工作时间约束等[2]。

1) 侦察次数约束

对任意目标j∈M最多进行一次侦察,避免重复侦察。

2) 重返基地约束

对任意UUVi∈V,若执行侦察任务,需满足从基地出发并返回原基地的要求。

3) 任务时间约束

如果对目标j的侦察任务必须在固定的时间窗口内开始,表示该任务具有时间约束。过早或过晚到达任务点位置,则无法执行侦察,需要等待至满足时间约束方可执行。

4) 任务载荷约束

对目标j进行侦察的UUVi需要满足目标j的任务载荷类型要求,即。

5) 时序约束

如果必须同步或按顺序依次完成对任务目标i和目标j的侦察,表示目标i与目标j之间存在时序约束,记为S equence(i,j)。必须在目标i被侦察之前完成的任务称为目标i的紧前任务,必须在目标i被侦察之后立即执行的任务称为目标i的紧后任务,与目标i具有时序约束的任务构成集合记为Sseq(i)。具有时序约束的任务通常需要遵循严格的执行顺序。例如,假设共7 个待执行的任务,其中任务1 为任务4 的紧前任务,任务7 为任务4 的紧后任务,使用有向图表示任务的执行序列,则图1 为可行解,而图2 为非可行解。

图1 满足时序约束的可行解有向图Fig.1 Directed graph of feasible solutions satisfying temporal constraints

图2 违反时序约束的非可行解有向图Fig.2 Directed graph of infeasible solutions violating temporal constraints

6) 使能约束

如果任务i不完成,则任务j无法完成,即任务j的完成依赖于任务i的实现,表示任务i对任务j具有使能约束,记为Enable(i,j),对任务j具有使能约束的任务集合记为Sena(j)。使能约束与时序约束相似,但比时序约束的要求宽松。例如,假设共7 个待执行的任务,其中任务1 对任务4 具有使能约束,任务4 对任务7 具有使能约束,则图1和图2 均为满足使能约束的可行解,可见只要目标任务在其使能任务之后完成即符合要求。

7) 航程约束

对任意UUVi∈V,执行任务的总航程不能超过其最大航程。

1.4 目标函数

多UUV 协同侦察任务分配的目的是将任务分配给具体的UUV 执行,保证每个任务只分配给一个UUV,为了使多UUV 系统的整体侦察效能最佳,需要满足以下4 个目标。

1) 任务收益最大化

各UUV 完成侦察任务后,整体收益(Reward)为最大,即

式中:Si为分配给UUVi的任务子集;Reward(Si)为UUVi完成任务集Si所得的收益。

2) 任务代价最小化

各UUV 完成侦察任务后,整体代价(Cost)为最小,即

式中,Cost(Si) 为 UUVi完成任务集Si所付出的代价,此处代价是主要指航行距离。

3) 任务完成时间最小化

各UUV 协同完成侦察任务的时间(Time)为最小,即让各UUV 完成任务的最长时间最小化,即

式中,Time(Si)为UUVi完成任务集Si所花费的时间。

4) 任务负载均衡化

各UUV 的任务负载(Load)趋于均衡,文中用各UUV 任务分配数的标准差表征任务负载

式中,|Si|为分配给UUVi的任务数。

这是一个多目标优化问题,需要根据指挥人员的决策意图确定各个指标的相对权重,通过加权求和转化为单目标优化问题。综合考虑上述优化目标,将多UUV 系统的整体效能定义为

式中,wi为大于等于0 的实数,表示第i项优化目标的权重,i=1,2,3,4。

1.5 任务分配模型

综上可得,多UUV 协同侦察的任务分配方案需满足式(7)～式(13)的约束,使-U最小化,从而求得多UUV 协同侦察任务分配方案。

侦察次数约束

重返基地约束

式中,0 代表UUV 的出发基地。

任务时间约束

任务载荷约束

任务使能约束

任务时序约束

最大航程约束

通过求解min -U可确定各UUV 的侦察任务序列

式中,ni为UUVi需要执行的任务个数。

2 基于多种群遗传算法的任务分配方法

基于“不把鸡蛋放在同一篮子”的集成学习思想[10],选择多种群协同进化遗传算法求解多UUV协同侦察任务分配问题。通过种群迁移,使得种群间能够共享优秀基因,实现高质量自进化;借助移民算子协同进化,促进了种群间的信息交换,达到协同进化目的;通过精英保留操作保存各种群每个进化代中的最优个体,并作为判断算法收敛的依据,提高全局收敛能力;通过“人机融合”提升初代种群质量,加速算法收敛;引入“遗忘策略”弥补可能出现的进化不彻底问题。

2.1 编码策略

常用的遗传编码策略有格雷码、实整数编码、排列编码等,文中采用排列编码。一个种群由多条染色体构成,可用二维矩阵表示

式中:Nind为种群的规模,即种群的个体数;Lind为种群个体的染色体长度,Lind=Nm+Nv-1。

Chrom中每行对应一条染色体,个体染色体采用“排列编码”方式,每条染色体对应1～Lind的一种全排列,第i条染色体对应如下行向量

式中,gi,j∈{1,2,3,···,Nm+Nv-1}且gi,j≠gi,j,j≠k。其中,1,2,···,Nm对应任务目标的编号;Nm+1,Nm+2,···,Nm+Nv-1为各分割点标记,用于分割染色体得到各UUV 的任务序列。

例如,当目标数Nm=13,UUV数目Nv=3 时,图3 给出了一条染色体结构实例。

图3 UUV 协同任务分配方案Fig.3 Allocation scheme of collaborative task for UUV

如图3 所示,该染色体对应一个任务分配方案:UUV 1 的任务执行序列为0→2→5→7→12→0;UUV 2 的任务执行序列为0→1→6→10→9→4→0;UUV 3 的任务执行序列为0→8→13→11→3→0。0 代表UUV 各自的出发基地。

2.2 种群初始化

与经典遗传算法不同的是,种群初始化除了完成进化代数、种群规模、交叉概率及重组概率等超参数的设置外,还引入人类的先验知识,构造出2 条左右比较优秀的染色体,作为协同进化的基准,提升初代种群的个体质量,引导算法更快、更好地收敛。

2.3 适应度函数与约束处理

适应度函数用于评价个体的优劣程度。多种群遗传算法将个体适应度大小作为进化迭代的依据,适应度越大,个体越接近最优解。由于文中目标函数为极大型,因此取式(5)作为适应度函数。

常用的处理约束条件的方法有罚函数法和可行性法则[11]。其中,罚函数法的思想是通过在目标函数中引入惩罚项将约束优化问题转化为无约束优化问题进行逼近求解;可行性法则是通过计算每个个体违反约束的程度,引导种群向满足约束的方向进化。罚函数法虽然简便,但对于多约束条件问题容易找不到可行解,因此文中选择可行性法则。利用可行性法则进行处理,每个种群对应一个违反约束程度矩阵,记为

式中:Nind为种群的规模;N2为约束条件个数,2.3节中的7 个约束,其中前2 个约束通过编码策略可得到满足,因此只需要考虑后5 个约束,即N2=5。

CV中每一行对应种群的一个个体,每一列对应一个约束,cvij∈{0,1}当取值为0 时表示满足约束,反之表示违反约束。

2.4 局部遗传算子

遗传算子主要包括局部遗传算子和全局遗传算子。其中:局部遗传算子是指子种群内部染色体之间交互信息的遗传操作;全局遗传算子是指不同子种群之间信息交互的遗传操作。局部遗传算子主要包括选择、交叉和变异等操作[11]。文中使用二进制锦标赛选择算子。

2.5 全局遗传算子

全局遗传算子主要包括移民算子、精英保留算子[6]和遗忘策略。

1) 移民算子

移民算子是用源种群的最优个体代替目标种群的最劣个体,通过种群间信息交换实现协同进化目的。

2) 精英保留算子

精英保留算子是选出各种群中的最优个体,并将其放入精英种群加以保存,保证各种群的最优个体不被破坏。

同时,精英种群与最大进化代数一起作为判断算法终止的依据。设置进化停滞判断阈值TrappedValue、进化停滞计数器最大上限值MaxTrappedCount 和最大进化代数MaxGen。当相邻两代精英个体的适应度之差小于TrappedValue,则判定进化陷入停滞;若连续MaxTrappedCount 代陷入进化停滞,则终止进化;在没有因停滞而终止的情况下,当进化代数达到MaxGen 时则终止进化。

3) 遗忘策略

利用CV矩阵判断种群中是否有满足约束条件的个体,当没有或仅有极少数个体满足约束条件时,说明此次进化没有达到预期效果。针对这种情况,当某一代的满足约束个体少于MinNum时,进化记录器将不对这一代种群进行记录,同时进化代数-1,这意味着后面需要多进化一代作为补偿,从而使优化结果更加充分。MinNum 为超参数,文中取 M inNum=1。

2.6 多种群遗传算法流程

综合种群初始化、个体评价、局部遗传算子和全局遗传算子等操作,可得多种群遗传算法的执行流程如图4 所示。

图4 多种群遗传算法流程图Fig.4 Flow chart of multi-population genetic algorithm

首先,进行多种群进化参数的初始化,主要包括各种群的规模、交叉概率、变异概率以及与终止进化相关的判断阈值等参数;然后,各个种群独立进行选择、重组、变异,得到各种群的子代,并将父代和子代个体合并;随后,对所有种群的所有个体进行统一的适应度评价,并完成移民、约束条件判断、精英保留等全局操作;最后,若满足停止条件则停止,否则继续执行。

3 仿真实验

3.1 想定设计

假设共有4 个可用的UUV 和15 个待侦察的目标,随机分布在50 n mile × 50 n mile 的正方形任务海域里,以正方形的中心为原点构建直角坐标系,UUV 和目标位置可用横纵坐标表示,如图5 所示。

图5 目标和UUV 初始态势分布图Fig.5 Initial distribution of targets and UUVs

1) 任务载荷约束

共有4 种任务载荷,其中UUV 2、UUV 3 和UUV 4 均搭载了4 种载荷,UUV 1 搭载了除载荷2 之外的另外3 种载荷。15 个侦察目标对任务载荷的需求如图6 所示。

图6 侦察目标对载荷种类需求曲线Fig.6 Demand curve of targets to load types

由图6 可见,目标10 和目标14 需要第2 种任务载荷才能完成侦察,因此不能将目标10 和14 分配给UUV 1 执行。

2) 任务时间约束

对7 号目标添加任务开始时间约束,规定对7 号目标的侦察必须在90～150 min 之间开始。

3) 任务时序约束

对任务2、任务5 和任务4 施加任务时序约束,将任务2 设置为任务5 的紧前任务,将任务4 设置为任务5 的紧后任务。

4) 任务使能约束

对任务3 和任务6 施加使能约束,令任务6 对任务3 具有使能约束,即任务6 必须在任务3 完成后才能开始。

5) 最大航程约束、

设置4 个UUV 的最大航程均为120 n mile。

6) UUV 速度与任务收益矩阵

航速设置方面,2 号UUV 航速为8 kn,其余3 个UUV 的航速均为5 kn。任务收益矩阵如表1所示,表中:第i行第j列取值表示由UUVi侦察目标j可获得的任务收益;×表示UUV 无法执行对相应目标的侦察。

表1 任务收益矩阵Table 1 Task benefit matrix

3.2 算法参数设置

为了验证多种群协同进化算法的可行性,将使用增强精英保留策略的单种群遗传算法作为基线算法。软件方面,使用python 开源进化算法工具箱Geatpy2[12]进行算法开发;硬件配置为:Intel(R)_Core(TM)_i5-1035G1 CPU,主频1.19 GHz,内存8 GB。

1) 多种群协同进化算法主要参数设置

取最大进化代数MaxGen=200;进化停滞判断阈值TrappedValue=10-8;进化停滞计数器最大上限值MaxTrappedCoun=100;种群数量为4,各种群的染色体数量均为150,各种群的交叉概率分别为0.6,0.7,0.8 和0.9,各种群的变异概率分别为0.05,0.1,0.15 和0.2。

另外,利用人类经验构造满足部分约束的染色体引导种群进化。对于任务载荷约束、时序约束、使能约束这类定性约束直观上很容易判断,同时结合目标在图上的分布态势,构造3 条初始化染色体分别为:[7,3,6,16,2,5,4,13,17,1,10,8,18,12,9,11,15,14];[2,5,4,16,7,3,12,6,17,10,13,8,18,9,15,14,1,11];[3,7,6,16,2,5,4,11,17,14,12,9,15,13,18,1,10,8]。上述染色体并不是最优的,甚至可能违反部分约束,但它们均满足任务载荷约束、时序约束和使能约束,以它们做引导可以提高初代种群质量。

2) 单种群遗传算法主要参数设置

单种群遗传算法最大进化代数为200;染色体数量为600;交叉概率为0.7;变异概率为0.1;并采用与多种群协同进化算法相同的初始化和遗忘策略设置。

3.3 实验结果

1) 多种群协同进化算法实验结果

当式(5)中4 个目标函数的权重均为1 时,多种群协同进化算法的任务分配结果如图7 所示,UUV 1 的任务执行序列为0→7→3→13→15→0;UUV 2 的任务执行序列为0→11→2→5→4→0;UUV 3 的任务执行序列为0→14→6→9→12→0;UUV 4 的任务执行序列为0→1→10→8→0。

图7 多种群协同进化算法任务分配结果示意图Fig.7 Task assignment results of multi-population coevolution algorithm

该任务分配方案中,各UUV 的任务收益、航行距离、任务完成时间(考虑返程)和任务个数等信息如表2 所示。

表2 多种群协同进化算法各UUV 任务信息表Table 2 Information table of UUV tasks for multiple population coevolution algorithm

由图7 和表2 可知,优化所得的任务分配方案中,UUV 的任务负载较为均衡,航行轨迹没有往复,符合节省能源的要求,经验证该方案满足所有约束条件。另外,由于任务2、5、4 空间距离较远并存在时序约束,优化结果将它们分配给航速最快的2 号UUV 执行,在满足约束的同时可以兼顾任务完成时间,凸显了算法的优势。

优化过程运行到123 代时算法提前终止,用时29.92 s,最优目标函数值为2467.35。

2) 随机初始化多种群实验结果

采用随机初始化方式生成初代种群时,多种群协同进化算法的任务分配结果如图8 所示,UUV 1 的任务执行序列为0→7→3→8→0;UUV 2 的任务执行序列为0→2→5→4→15→0;UUV 3 的任务执行序列为0→12→9→6→10→0;UUV 4 的任务执行序列为0→1→10→14→13→0。

图8 随机初始化多种群协同进化算法实验结果示意图Fig.8 Experimental results of multi-population coevolution algorithm with random initialization

该任务分配方案对应的任务信息如表3 所示。

表3 随机初始化多种群协同进化算法信息表Table 3 Information table for multi-population coevolution algorithm with random initialization

优化过程共运行167 代,用时32.61 s,最优目标函数值为2755.98。

3) 未设置遗忘策略多种群实验结果

不使用遗忘策略时,多种群协同进化算法的任务分配结果如图9 所示,UUV 1 的任务执行序列为0→7→3→8→0;UUV2的任务执行序列为0→2→5→4→15→0;UUV3的任务执行序列为0→14→9→6→11→0;UUV 4 的任务执行序列为0→1→10→12→13→0。

图9 无遗忘策略多种群协同进化算法实验结果示意图Fig.9 Experimental results of multi-population coevolution algorithm without forgetting strategy

该任务分配方案对应的任务信息如表4 所示。

表4 无遗忘策略多种群协同进化算法信息表Table 4 Information table for multi-population coevolution algorithm without forgetting strategy

优化过程共运行200 代,用时36.65 s,最优目标函数值为2717.77。

4) 单种群遗传算法实验结果

当式(5)中4 个目标函数的权重均为1 时,单种群遗传算法的任务分配结果如图10 所示,UUV 1 的任务执行序列为0→7→3→8→0;UUV 2 的任务执行序列为0→2→5→4→15→0;UUV 3 的任务执行序列为0→14→9→6→11→0;UUV 4 的任务执行序列为0→1→10→12→13→0。

图10 单种群遗传算法任务分配结果示意图Fig.10 Task assignment results of single population genetic algorithm

该任务分配方案对应的任务信息如表5 所示。

表5 单种群遗传算法各UUV 任务信息表Table 5 Information table of UUV tasks for single population genetic algorithm

优化过程共运行200 代,用时41.01 s,最优目标函数值为2759.98。

5) 对比分析

对比表2 与表5 中的任务分配方案信息,多种群协同进化算法的寻优结果除了在任务收益方面处于劣势以外,在航向距离、任务完成时间以及最优目标函数值等方面均占有优势,航向距离比单种群遗传算法节省了36.35 n mile,任务完成时间节省279.29 min,所有UUV 的总航行时间节省662.53 min,最优目标函数值改进292.63。另外,得益于并行计算和进化停滞判断策略,多种群协同进化算法的耗时少11.09 s。

对比表2 与表3 中的任务分配方案信息,当引入人类先验知识的多种群协同进化算法,除任务收益外,在航向距离和任务完成时间方面均占有优势,另外进化完成时间也减少约2.67 s。

对比表2 与表4 中的任务分配方案信息,设置遗忘策略多种群协同进化算法,在航向距离和任务完成时间方面均占有优势。另外,由于未设置遗忘策略,虽然进化200 代,但由于其中可能存在多代不含可行解的无效进化,因此并未实现完全进化。

综上所述,通过多种群协同进化,借助并行化计算,可以在提高寻优效率的基础上,取得比单种群遗传算法更好的寻优结果。同时,引入人类先验知识和遗忘策略,可以进一步加速收敛、促进进化。

另外,文中通过加权求和的方式将多目标优化问题转化为单目标优化问题,这样权重组合可以灵活满足不同任务需求,使用偏好的方案优选。例如,将第3 个目标函数权重设置为1,其余3 个目标函数权重设置为0,则对应任务完成时间最小化这一单目标优化问题。利用多种群协同进化算法优化所得的任务分配方案如图11 所示。

图11 多种群协同进化算法任务分配结果示意图Fig.11 Task assignment results of multi-population coevolution algorithm

4 结束语

为了提升多目标、多基地、多约束条件下多UUV 协同侦察任务分配的方案质量,针对经典单种群遗传算法过早收敛、效率不高等问题,提出一种人机融合的多种群协同进化算法。一方面,引入人类直觉、经验构造较优的初始染色体,作为启发信息引导种群尽快找到全局最优解;另外,利用多种群并行、协同搜索,提升算法鲁棒性和全局寻优能力。在典型场景下进行仿真对比实验,实验结果表明:多种群协同进化算法能够提升协同任务分配的鲁棒性,能够提升任务分配方案的质量。后续将在此基础上,研究任务变更、UUV 个体故障等突发情况下的动态协同任务分配。