Task Assignment Method for Multiple UUVs Based on Multi-population Genetic Algorithm
-
摘要: 多无人水下航行器(UUVs)协同侦察任务分配方案的优劣关系到作战效能甚至任务成败。文中针对传统遗传算法存在过早收敛、效率不高等问题, 提出一种人机融合的多种群遗传算法, 用于多基地、多目标、多约束的多UUV协同侦察任务分配。该算法通过引入多种群对解空间进行协同搜索, 可更好地平衡全局寻优和局部搜索能力, 突破经典遗传算法仅靠单种群进行寻优的性能瓶颈; 另外, 以人类先验知识作为启发信息辅助种群进行初始化, 提高算法收敛效率; 引入“遗忘策略”, 缓解可能出现的进化不完全问题。基于典型想定进行仿真实验, 结果表明, 提出的多种群遗传算法具有较强的鲁棒性和较高的寻优效率, 可以得到高品质的协同任务分配方案。Abstract: The quality of task assignment schemes for multiple unmanned undersea vehicles(UUVs) during cooperative reconnaissance is key to the operational effectiveness or even the success of missions. A multi-population genetic algorithm based on man-machine fusion was proposed for task allocation of multi-base, multi-target, and multi-constraint cooperative reconnaissance to solve the problems of premature convergence and low efficiency of traditional genetic algorithms. The algorithm can better balance global optimization and local search and break through the performance bottleneck of the classical genetic algorithm, which relies only on a single population for optimization, by introducing multiple populations to search the solution space cooperatively. In addition, human prior knowledge was used as heuristic information to assist population initialization in improving the convergence efficiency of the algorithm, and a forgetting strategy was introduced to alleviate possible incomplete evolution. The results of the simulation based on typical scenarios show that the proposed multi-population genetic algorithm is robust, has high optimization efficiency, and can generate high-quality collaborative task allocation schemes..
-
0. 引言
利用搭载传感器载荷的无人水下航行器(un- manned 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 符号描述
假设共
$ {N_m} $ 个待侦察目标,$ {N_v} $ 个可使用的UUV,$ {n_r} $ 种侦察载荷。记待侦察任务目标集合
$M=\left\{ {1,\;2,\; \cdots ,\;{N_m}} \right\}$ ; UUV集合$V=\left\{ {1,\;2,\; \cdots ,\;{N_v}} \right\}$ ; 侦察载荷类型集合$ R=\left\{ {1,\;2,\; \cdots ,\;{N_r}} \right\} $ ; 任务收益矩阵${\boldsymbol{C}}={\left[ {{C_{ij}}} \right]_{{N_v} \times {N_m}}}$ ,$ {C_{ij}} $ 为UUVi完成对目标j侦察可获得的收益; 任务分配结果矩阵$ {\boldsymbol{Y}}={\left[ {{y_{ij}}} \right]_{{N_v} \times {N_m}}} $ ,$ {y_{ij}} $ =1 or 0,$ {y_{ij}} $ =1表示将目标j分配给UUVi进行侦察, 反之亦然。记
$ R_i^v=\left\{ {1,\;2,\; \cdots ,\;{N_{{r_i}}}} \right\} $ 表示UUVi搭载的侦察载荷类型集合,$ R_i^v \subseteq R $ , i=$ 1,\;2,\; \cdots ,\;{N_v} $ 。$ R_j^m=\{ 1,\; 2,\; \cdots ,\; {N_{{r_j}}}\} $ 为侦察目标 j 可用的任务载荷类型,$ R_j^m \subseteq R $ , j=$ 1,\;2,\; \cdots ,\;{N_m} $ 。记
$ {t_j} $ 为侦察目标j所需的时间,$ t_j^E $ 、$ t_j^L $ 分别为开始侦察j所需的最早和最晚时间。1.3 约束条件
由于协同侦察任务的复杂性, 可以将任务集合中的任务分为独立任务和协同任务2类。其中, 独立任务是只与其自身约束相关的任务; 协同任务是除自身约束外, 相互间还存在时间或功能约束的任务。任务自身约束主要包括时间约束和载荷约束等, 任务之间的约束主要包括时序约束和使能约束等, 另外UUV自身约束主要包括物资约束和最大工作时间约束等[2]。
1) 侦察次数约束
对任意目标
$ j \in M $ 最多进行一次侦察, 避免重复侦察。2) 重返基地约束
对任意UUV
$ i \in V $ , 若执行侦察任务, 需满足从基地出发并返回原基地的要求。3) 任务时间约束
如果对目标j的侦察任务必须在固定的时间窗口[
$ t_j^E $ ,$ t_j^L $ ]内开始, 表示该任务具有时间约束。过早或过晚到达任务点位置, 则无法执行侦察, 需要等待至满足时间约束方可执行。4) 任务载荷约束
对目标j进行侦察的UUV i需要满足目标j的任务载荷类型要求, 即
$ R_j^m \subseteq R_i^v $ 。5) 时序约束
如果必须同步或按顺序依次完成对任务目标i和目标j的侦察, 表示目标i与目标j之间存在时序约束, 记为
$ Sequence\left( {i,j} \right) $ 。必须在目标i被侦察之前完成的任务称为目标i的紧前任务, 必须在目标i被侦察之后立即执行的任务称为目标i的紧后任务, 与目标i具有时序约束的任务构成集合记为$ {S^{{\text{seq}}}}\left( i \right) $ 。具有时序约束的任务通常需要遵循严格的执行顺序。例如, 假设共7个待执行的任务, 其中任务1为任务4的紧前任务, 任务7为任务4的紧后任务, 使用有向图表示任务的执行序列, 则图1为可行解, 而图2为非可行解。
图 1 满足时序约束的可行解有向图Figure 1. Directed graph of feasible solutions satisfying temporal constraints
图 2 违反时序约束的非可行解有向图Figure 2. Directed graph of infeasible solutions violating temporal constraints6) 使能约束
如果任务i不完成, 则任务j无法完成, 即任务j的完成依赖于任务i的实现, 表示任务i对任务j具有使能约束, 记为
$ Enable\left( {i,j} \right) $ , 对任务j具有使能约束的任务集合记为$ {S^{{\text{ena}}}}\left( j \right) $ 。使能约束与时序约束相似, 但比时序约束的要求宽松。例如, 假设共7个待执行的任务, 其中任务1对任务4具有使能约束, 任务4对任务7具有使能约束, 则图1和图2均为满足使能约束的可行解, 可见只要目标任务在其使能任务之后完成即符合要求。7) 航程约束
对任意UUV
$ i \in V $ , 执行任务的总航程不能超过其最大航程。1.4 目标函数
多UUV协同侦察任务分配的目的是将任务分配给具体的UUV执行, 保证每个任务只分配给一个UUV, 为了使多UUV系统的整体侦察效能最佳, 需要满足以下4个目标。
1) 任务收益最大化
各UUV完成侦察任务后, 整体收益(Reward)为最大, 即
$$ Reward{\text=}\sum\nolimits_{i=1}^{{n_v}} {Reward({S_i})} $$ (1) 式中:
$ {S_i} $ 为分配给UUV i的任务子集;$ Reward({S_i}) $ 为UUV i完成任务集$ {S_i} $ 所得的收益。2) 任务代价最小化
各UUV完成侦察任务后, 整体代价(Cost)为最小, 即
$$ Cost=\sum\nolimits_{i=1}^{{n_v}} {Cost({S_i})} $$ (2) 式中,
$ Cost({S_i}) $ 为UUV i完成任务集$ {S_i} $ 所付出的代价, 此处代价是主要指航行距离。3) 任务完成时间最小化
各UUV协同完成侦察任务的时间(Time)为最小, 即让各UUV完成任务的最长时间最小化, 即
$$Time=\max \left\{ {Time\left( {{S_1}} \right),\;Time\left( {{S_2}} \right),\; \cdot \cdot \cdot ,\;Time\left( {{S_{{n_v}}}} \right)} \right\} $$ (3) 式中,
$ Time({S_i}) $ 为UUV i完成任务集$ {S_i} $ 所花费的时间。4) 任务负载均衡化
各UUV的任务负载(Load)趋于均衡, 文中用各UUV任务分配数的标准差表征任务负载
$$ Load=\sqrt {\frac{1}{{{N_v}}}\sum\nolimits_{i=1}^{{n_v}} {\left( {\left| {{S_i}} \right| - \frac{1}{{{N_v}}}\sum\nolimits_{i=1}^{{n_v}} {\left| {{S_i}} \right|} } \right)} } $$ (4) 式中,
$ \left| {{S_i}} \right| $ 为分配给UUV i的任务数。这是一个多目标优化问题, 需要根据指挥人员的决策意图确定各个指标的相对权重, 通过加权求和转化为单目标优化问题。综合考虑上述优化目标, 将多UUV系统的整体效能定义为
$$ U={w_1} \cdot Reward - {w_2} \cdot Cost - {w_3} \cdot Time - {w_4} \cdot Load $$ (5) 式中,
$ {w_i} $ 为大于等于0的实数, 表示第i项优化目标的权重, i=1, 2, 3, 4。1.5 任务分配模型
定义决策变量
$ x_{ij}^k $ , 其中i, j=$ 1,\;2,\; \cdots ,\;{N_m} $ ; k=$ 1,\; 2,\; \cdots ,\;{N_v} $ , 满足$$x_{ij}^k{\rm{ = }}\left\{ \begin{array}{l} \begin{array}{*{20}{c}} {1,}&{{\rm{UUV}}\,k}从目标i航行到j执行任务 \end{array}\\ \begin{array}{*{20}{c}} {0,}&{{\rm{UUV}}\,k}不从目标i航行到j执行任务 \end{array} \end{array} \right. $$ (6) 综上可得, 多UUV协同侦察的任务分配方案需满足式(7)~式(13)的约束, 使−U最小化, 从而求得多UUV协同侦察任务分配方案。
侦察次数约束
$$ \left\{ \begin{gathered} \sum\limits_{i=1}^{{N_m}} {\sum\limits_{k=1}^{{N_v}} {x_{ij}^k} } \leqslant 1,\;\forall j \in M \\ \sum\limits_{j=1}^{{N_m}} {\sum\limits_{k=1}^{{N_v}} {x_{ij}^k} } \leqslant 1,\;\forall i \in M \\ \end{gathered} \right. $$ (7) 重返基地约束
$$ \sum\limits_{j=1}^{{N_m}} {x_{0j}^k} {\text=}\sum\limits_{i=1}^{{N_m}} {x_{i0}^k} =1,\;\forall k \in V $$ (8) 式中, 0代表UUV的出发基地。
任务时间约束
$$ \begin{array}{*{20}{c}} {t_j^E \leqslant t_j^S \leqslant t_j^L,}&{\forall j \in M} \end{array} $$ (9) 任务载荷约束
$$ \begin{array}{*{20}{c}} {R_j^m \subseteq R_i^v,}&{\forall i \in V,\;\;\;j \in M} \end{array} $$ (10) 任务使能约束
$$ {Enforce\left( {S equence\left( {i,j} \right)} \right),}\quad{\forall j \in M,\;\;i \in {S^{{\text{seq}}}}\left( j \right)} $$ (11) 任务时序约束
$$ \begin{array}{*{20}{c}} {Enforce\left( {Enable\left( {i,j} \right)} \right),}&{\forall j \in M,\;i \in {S^{{\text{ena}}}}\left( j \right)} \end{array} $$ (12) 最大航程约束
$$ \sum\limits_{i=0}^{{N_m}} {\sum\limits_{j=0}^{{N_m}} {{d_{ij}} \cdot x_{ij}^k} } \leqslant {L^k},\;\forall k \in V $$ (13) 通过求解min −U可确定各UUV的侦察任务序列
$$ {M_i}=\left\{ {m_1^i,\;m_2^i,\; \cdots ,\;m_{{n_i}}^i} \right\},\;i \in V $$ (14) 式中,
$ {n_i} $ 为UUVi需要执行的任务个数。2. 基于多种群遗传算法的任务分配方法
基于“不把鸡蛋放在同一篮子”的集成学习思想[10], 选择多种群协同进化遗传算法求解多UUV协同侦察任务分配问题。通过种群迁移, 使得种群间能够共享优秀基因, 实现高质量自进化; 借助移民算子协同进化, 促进了种群间的信息交换, 达到协同进化目的; 通过精英保留操作保存各种群每个进化代中的最优个体, 并作为判断算法收敛的依据, 提高全局收敛能力; 通过“人机融合”提升初代种群质量, 加速算法收敛; 引入“遗忘策略”弥补可能出现的进化不彻底问题。
2.1 编码策略
常用的遗传编码策略有格雷码、实整数编码、排列编码等, 文中采用排列编码。一个种群由多条染色体构成, 可用二维矩阵表示
$$ {\boldsymbol{Chrom}}=\left[ {\begin{array}{*{20}{c}} {{g_{1,\;1}}}&{{g_{1,\;2}}}& \cdots &{{g_{1,\;Lind}}} \\ {{g_{2,\;1}}}&{{g_{2,\;2}}}& \cdots &{{g_{2,\;Lind}}} \\ \vdots & \vdots & \vdots & \vdots \\ {{g_{Nind,\;1}}}&{{g_{Nind,\;2}}}& \cdots &{{g_{Nind,\;Lind}}} \end{array}} \right] $$ (15) 式中: Nind为种群的规模, 即种群的个体数; Lind为种群个体的染色体长度,
$ Lind={N_m} + {N_v} - 1 $ 。Chrom中每行对应一条染色体, 个体染色体采用“排列编码”方式, 每条染色体对应1~Lind的一种全排列, 第i条染色体对应如下行向量
$$ {{\boldsymbol{Chrom}}_i}=\left( {{g_{i,\;1}},\;{g_{i,\;2}},\; \cdots ,\;{g_{i,\;Lind}}} \right),\;i=1,\;2,\; \cdots ,\;Nind $$ (16) 式中,
$ {g_{i,\;j}} \in \left\{ {1,\;2,\;3, \cdots ,\;{N_m} + {N_v} - 1} \right\} $ 且$ {{g_{i,j}} \ne {g_{i,j}},}\;{j \ne k} $ 。其中, 1, 2, ···,$ {N_m} $ 对应任务目标的编号;$ {N_m} + 1 $ ,$ {N_m} + 2 $ , ···,$ {N_m} + {N_v} - 1 $ 为各分割点标记, 用于分割染色体得到各UUV的任务序列。例如, 当目标数
$ {N_m} $ =13, UUV数目$ {N_v} $ =3时, 图3给出了一条染色体结构实例。如图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]。其中, 罚函数法的思想是通过在目标函数中引入惩罚项将约束优化问题转化为无约束优化问题进行逼近求解; 可行性法则是通过计算每个个体违反约束的程度, 引导种群向满足约束的方向进化。罚函数法虽然简便, 但对于多约束条件问题容易找不到可行解, 因此文中选择可行性法则。利用可行性法则进行处理, 每个种群对应一个违反约束程度矩阵, 记为
$$ {\boldsymbol{CV}}=\left[ {\begin{array}{*{20}{c}} {c{v_{1,\;1}}}&{c{v_{1,\;2}}}& \cdots &{c{v_{1,\;{N_2}}}} \\ {c{v_{2,\;1}}}&{c{v_{2,\;2}}}& \cdots &{c{v_{2,\;{N_2}}}} \\ \vdots & \vdots & \vdots & \vdots \\ {c{v_{Nind,\;1}}}&{c{v_{Nind,\;2}}}& \cdots &{c{v_{Nind,\;{N_2}}}} \end{array}} \right] $$ (17) 式中: Nind为种群的规模;
$ {N_2} $ 为约束条件个数, 2.3节中的7个约束, 其中前2个约束通过编码策略可得到满足, 因此只需要考虑后5个约束, 即$ {N_2} $ =5。CV中每一行对应种群的一个个体, 每一列对应一个约束,
$ c{v_{ij}} \in \left\{ {0,\;1} \right\} $ 当取值为0时表示满足约束, 反之表示违反约束。2.4 局部遗传算子
遗传算子主要包括局部遗传算子和全局遗传算子。其中: 局部遗传算子是指子种群内部染色体之间交互信息的遗传操作; 全局遗传算子是指不同子种群之间信息交互的遗传操作。局部遗传算子主要包括选择、交叉和变异等操作[11]。文中使用二进制锦标赛选择算子。
2.5 全局遗传算子
全局遗传算子主要包括移民算子、精英保留算子[6]和遗忘策略。
1) 移民算子
移民算子是用源种群的最优个体代替目标种群的最劣个体, 通过种群间信息交换实现协同进化目的。
2) 精英保留算子
精英保留算子是选出各种群中的最优个体, 并将其放入精英种群加以保存, 保证各种群的最优个体不被破坏。
同时, 精英种群与最大进化代数一起作为判断算法终止的依据。设置进化停滞判断阈值TrappedValue、进化停滞计数器最大上限值MaxTrappedCount和最大进化代数MaxGen。当相邻两代精英个体的适应度之差小于TrappedValue, 则判定进化陷入停滞; 若连续MaxTrappedCount代陷入进化停滞, 则终止进化; 在没有因停滞而终止的情况下, 当进化代数达到MaxGen时则终止进化。
3) 遗忘策略
利用CV矩阵判断种群中是否有满足约束条件的个体, 当没有或仅有极少数个体满足约束条件时, 说明此次进化没有达到预期效果。针对这种情况, 当某一代的满足约束个体少于MinNum时, 进化记录器将不对这一代种群进行记录, 同时进化代数−1, 这意味着后面需要多进化一代作为补偿, 从而使优化结果更加充分。MinNum为超参数, 文中取
${\text{MinNum}}$ =1。2.6 多种群遗传算法流程
综合种群初始化、个体评价、局部遗传算子和全局遗传算子等操作, 可得多种群遗传算法的执行流程如图4所示。
首先, 进行多种群进化参数的初始化, 主要包括各种群的规模、交叉概率、变异概率以及与终止进化相关的判断阈值等参数; 然后, 各个种群独立进行选择、重组、变异, 得到各种群的子代, 并将父代和子代个体合并; 随后, 对所有种群的所有个体进行统一的适应度评价, 并完成移民、约束条件判断、精英保留等全局操作; 最后, 若满足停止条件则停止, 否则继续执行。
3. 仿真实验
3.1 想定设计
假设共有4个可用的UUV和15个待侦察的目标, 随机分布在50 n mile × 50 n mile的正方形任务海域里, 以正方形的中心为原点构建直角坐标系, UUV和目标位置可用横纵坐标表示, 如图5所示。
1) 任务载荷约束
共有4种任务载荷, 其中UUV 2、UUV 3和UUV 4均搭载了4种载荷, UUV 1搭载了除载荷2之外的另外3种载荷。15个侦察目标对任务载荷的需求如图6所示。
由图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列取值表示由UUV i侦察目标j可获得的任务收益; ×表示UUV无法执行对相应目标的侦察。
表 1 任务收益矩阵Table 1. Task benefit matrixUUV 目标 1 2 3 4 5 6 7 8 1 7 9 15 11 12 11 15 5 2 7 9 13 10 13 7 14 13 3 15 13 10 5 12 8 11 11 4 8 7 15 7 5 9 8 11 UUV 目标 9 10 11 12 13 14 15 1 10 × 6 13 13 × 10 2 9 11 15 7 15 5 6 3 14 6 7 7 6 11 10 4 14 15 13 14 15 12 5 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 多种群协同进化算法任务分配结果示意图Figure 7. Task assignment results of multi-population coevolution algorithm该任务分配方案中, 各UUV的任务收益、航行距离、任务完成时间(考虑返程)和任务个数等信息如表2所示。
表 2 多种群协同进化算法各UUV任务信息表Table 2. Information table of UUV tasks for multiple population coevolution algorithmUUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 35 65.78 2 306.05 4 2 35 111.16 2 077.41 4 3 48 54.01 2 006.8 4 4 21 68.91 1 776.93 3 合计 139 299.86 8167.19 15 由图7和表2可知, 优化所得的任务分配方案中, UUV的任务负载较为均衡, 航行轨迹没有往复, 符合节省能源的要求, 经验证该方案满足所有约束条件。另外, 由于任务2、5、4空间距离较远并存在时序约束, 优化结果将它们分配给航速最快的2号UUV执行, 在满足约束的同时可以兼顾任务完成时间, 凸显了算法的优势。
优化过程运行到123代时算法提前终止, 用时29.92 s, 最优目标函数值为2 467.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 随机初始化多种群协同进化算法实验结果示意图Figure 8. Experimental results of multi-population coevolution algorithm with random initialization该任务分配方案对应的任务信息如表3所示。
表 3 随机初始化多种群协同进化算法信息表Table 3. Information table for multi-population coevolution algorithm with random initializationUUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 21 52.10 1 311.62 3 2 46 108.45 2 585.34 4 3 51 92.31 2 438.96 4 4 41 76.35 2 302.25 4 合计 159 329.21 8 638.17 15 优化过程共运行167代, 用时32.61 s, 最优目标函数值为2 755.98。
3) 未设置遗忘策略多种群实验结果
不使用遗忘策略时, 多种群协同进化算法的任务分配结果如图9所示, 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。
图 9 无遗忘策略多种群协同进化算法实验结果示意图Figure 9. Experimental results of multi-population coevolution algorithm without forgetting strategy该任务分配方案对应的任务信息如表4所示。
表 4 无遗忘策略多种群协同进化算法信息表Table 4. Information table for multi-population coevolution algorithm without forgetting strategyUUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 32 68.87 1 969.77 3 2 47 108.45 2 585.34 4 3 55 56.61 2 371.04 5 4 37 68.66 2 413.66 3 合计 171 302.60 9 339.81 15 优化过程共运行200代, 用时36.65 s, 最优目标函数值为2 717.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 单种群遗传算法任务分配结果示意图Figure 10. Task assignment results of single population genetic algorithm该任务分配方案对应的任务信息如表5所示。
表 5 单种群遗传算法各UUV任务信息表Table 5. Information table of UUV tasks for single population genetic algorithmUUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 20 52.10 1 311.62 3 2 49 108.45 2 585.34 4 3 49 92.29 2 398.75 4 4 44 83.37 2 534.01 4 合计 162 336.21 8829.72 15 优化过程共运行200代, 用时41.01 s, 最优目标函数值为2 759.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 多种群协同进化算法任务分配结果示意图Figure 11. Task assignment results of multi-population coevolution algorithm4. 结束语
为了提升多目标、多基地、多约束条件下多UUV协同侦察任务分配的方案质量, 针对经典单种群遗传算法过早收敛、效率不高等问题, 提出一种人机融合的多种群协同进化算法。一方面, 引入人类直觉、经验构造较优的初始染色体, 作为启发信息引导种群尽快找到全局最优解; 另外, 利用多种群并行、协同搜索, 提升算法鲁棒性和全局寻优能力。在典型场景下进行仿真对比实验, 实验结果表明: 多种群协同进化算法能够提升协同任务分配的鲁棒性, 能够提升任务分配方案的质量。后续将在此基础上, 研究任务变更、UUV个体故障等突发情况下的动态协同任务分配。
-
图 1 满足时序约束的可行解有向图
Figure 1. Directed graph of feasible solutions satisfying temporal constraints
图 2 违反时序约束的非可行解有向图
Figure 2. Directed graph of infeasible solutions violating temporal constraints
图 7 多种群协同进化算法任务分配结果示意图
Figure 7. Task assignment results of multi-population coevolution algorithm
图 8 随机初始化多种群协同进化算法实验结果示意图
Figure 8. Experimental results of multi-population coevolution algorithm with random initialization
图 9 无遗忘策略多种群协同进化算法实验结果示意图
Figure 9. Experimental results of multi-population coevolution algorithm without forgetting strategy
图 10 单种群遗传算法任务分配结果示意图
Figure 10. Task assignment results of single population genetic algorithm
图 11 多种群协同进化算法任务分配结果示意图
Figure 11. Task assignment results of multi-population coevolution algorithm
表 1 任务收益矩阵
Table 1. Task benefit matrix
UUV 目标 1 2 3 4 5 6 7 8 1 7 9 15 11 12 11 15 5 2 7 9 13 10 13 7 14 13 3 15 13 10 5 12 8 11 11 4 8 7 15 7 5 9 8 11 UUV 目标 9 10 11 12 13 14 15 1 10 × 6 13 13 × 10 2 9 11 15 7 15 5 6 3 14 6 7 7 6 11 10 4 14 15 13 14 15 12 5 
下载: 导出CSV
表 2 多种群协同进化算法各UUV任务信息表
Table 2. Information table of UUV tasks for multiple population coevolution algorithm
UUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 35 65.78 2 306.05 4 2 35 111.16 2 077.41 4 3 48 54.01 2 006.8 4 4 21 68.91 1 776.93 3 合计 139 299.86 8167.19 15
下载: 导出CSV
表 3 随机初始化多种群协同进化算法信息表
Table 3. Information table for multi-population coevolution algorithm with random initialization
UUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 21 52.10 1 311.62 3 2 46 108.45 2 585.34 4 3 51 92.31 2 438.96 4 4 41 76.35 2 302.25 4 合计 159 329.21 8 638.17 15
下载: 导出CSV
表 4 无遗忘策略多种群协同进化算法信息表
Table 4. Information table for multi-population coevolution algorithm without forgetting strategy
UUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 32 68.87 1 969.77 3 2 47 108.45 2 585.34 4 3 55 56.61 2 371.04 5 4 37 68.66 2 413.66 3 合计 171 302.60 9 339.81 15
下载: 导出CSV
表 5 单种群遗传算法各UUV任务信息表
Table 5. Information table of UUV tasks for single population genetic algorithm
UUV
编号任务
收益航行距离
/(n mile)完成时间
/min任务
个数1 20 52.10 1 311.62 3 2 49 108.45 2 585.34 4 3 49 92.29 2 398.75 4 4 44 83.37 2 534.01 4 合计 162 336.21 8829.72 15
下载: 导出CSV
-
[1] 严浙平, 刘祥玲. 多UUV协调控制技术研究现状及发展趋势[J]. 水下无人系统学报, 2019, 27(3): 226-231. doi: 10.11993/j.issn.2096-3920.2019.03.001Yan Zhe-ping, Liu Xiang-ling. Research Status and Development Trend of Multi-UUV Coordinated Control Technology: A Review[J]. Journal of Unmanned Undersea Systems, 2019, 27(3): 226-231. doi: 10.11993/j.issn.2096-3920.2019.03.001 [2] 董晓明, 范慧丽, 龚俊斌, 等. 海上无人装备体系概览[M]. 哈尔滨: 哈尔滨工程大学出版社, 2020: 460-473. [3] 轩孟丽. 无人机编队的任务规划[D]. 西安: 西安电子科技大学, 2020. [4] 叶航航, 李泽仁, 刘浩, 等. 一种基于指派模型的导弹-目标分配算法[C]//2018中国自动化大会(CAC2018)论文集. 西安: 中国自动化学会, 2018: 564-569. [5] 孙凡, 邹强, 彭英武. 基于GA的水下预置反舰导弹区域封锁部署优化[J]. 水下无人系统学报, 2021, 29(2): 238-242.Sun Fan, Zou Qiang, Peng Ying-wu. Optimization of Regional Blockade Deployment of Underwater Preset Anti-ship Missiles Based on GA[J]. Journal of Unmanned Undersea Systems, 2021, 29(2): 238-242. [6] 董浩, 李烨. 基于多种群遗传算法的虚拟机优化部署研究[J]. 控制工程, 2020, 182(2): 131-137. doi: 10.14107/j.cnki.kzgc.170671Dong Hao, Li Ye. Research on Optimization of Virtual Machine Deployment Based on Multi Population Genetic Algorithm[J]. Control Engineering of China, 2020, 182(2): 131-137. doi: 10.14107/j.cnki.kzgc.170671 [7] 刘胜, 于海强. 基于改进遗传算法的多目标FJSP问题研究[J]. 控制工程, 2016, 23(6): 816-822. doi: 10.14107/j.cnki.kzgc.150184Liu Sheng, Yu Hai-qiang. Research on Multi-objective FJSP Problem Based on Improved Genetic Algorithm[J]. Control Engineering of China, 2016, 23(6): 816-822. doi: 10.14107/j.cnki.kzgc.150184 [8] Bai X, Yan W, Ge S S, et al. An Integrated Multi-population Genetic Algorithm for Multi-vehicle Task Assignment in a Drift Field[J]. Information Sciences, 2018, 44(4): 1-29. [9] 陈娟, 荆昊, 方宇杰. 基于多种群协同进化算法的混合交通流信号优化[J]. 上海大学学报(自然科学版), 2020, 156(6): 153-166.Chen Juan, Jing Hao, Fang Yu-jie. Mixed Traffic Flow Signal Optimization Based on Multi-population Coevolutionary Algorithm[J]. Journal of Shanghai University (Natural Science), 2020, 156(6): 153-166. [10] 张习习, 顾幸生. 基于集成学习概率神经网络的电机轴承故障诊断[J]. 华东理工大学学报(自然科学版), 2020, 46(1): 77-85. doi: 10.14135/j.cnki.1006-3080.20181206001Zhang Xi-xi, Gu Xing-sheng. Motor Bearing Fault Diagnosis Method Based on Integrated Learning Probabilistic Neural Network[J]. Journal of East China University of Science and Technology, 2020, 46(1): 77-85. doi: 10.14135/j.cnki.1006-3080.20181206001 [11] 焦儒旺, 曾三友, 李晰, 等. 基于学习的动态多目标方法求解约束优化问题[J]. 武汉大学学报(理学版), 2017, 63(2): 177-183. doi: 10.14188/j.1671-8836.2017.02.012Jiao Ru-wang, Zeng San-you, Li Xi, et al. Constrained Optimization by Solving Equivalent Dynamic Constrained Multi-Objective Based on Learning[J]. Journal of Wuhan University (Natural Science Edition), 2017, 63(2): 177-183. doi: 10.14188/j.1671-8836.2017.02.012 [12] Jazzbin, Yuan Q X. Geatpy: the Genetic and Evolutionary Algorithm Toolbox for Python with High Performance in python[EB/OL].(2021-04-04)[2021-07-02]. http://www.geatpy.com/. 期刊类型引用(2)
1. 吴思聪，吴曦. 基于NSGA-Ⅲ的UUV集群打击任务分配模型. 水下无人系统学报. 2023(03): 474-480 . 
本站查看2. 邓辅秦，黄焕钊，谭朝恩，付兰慧，张建民，林天麟. 结合遗传算法和滚动调度的多机器人任务分配算法. 计算机应用. 2023(12): 3833-3839 . 
百度学术其他类型引用(4)
-
下载:
百度学术
点击查看大图
计量
- 文章访问数: 517
- HTML全文浏览量: 122
- PDF下载量: 87
- 被引次数: 6
