舰船科学技术  2022, Vol. 44 Issue (22): 69-75    DOI: 10.3404/j.issn.1672-7649.2022.22.013   PDF    
基于改进灰狼算法的UUV集群任务分配研究
杨芳, 陈彦勇, 张云佳, 李健萍, 普俊韬     
中国船舶集团有限公司第七〇五研究所,云南 昆明 650118
摘要: UUV集群任务分配问题与狼群攻击围捕目标的问题十分相似,本文尝试将狼群行为理论和灰狼算法引入到UUV集群任务分配问题中。针对传统灰狼算法未考虑全局与局部搜索的协调配合以及未考虑位置更新的权重问题进行改进,本文提出改进收敛因子以余弦规律减小和引入动态权重的改进灰狼算法。为了验证方法的可行性和优越性,进行侦察和攻击目标任务分配仿真,并针对同一场景分别采用灰狼算法(GWO)、遗传算法(GA)以及改进灰狼算法(IGWO)进行仿真。结果表明,IGWO算法比GA算法和GWO能够更好对UUV集群侦察目标任务分配的问题进行求解,并能够减小资源浪费,提高工作效率。
关键词: UUV     狼群理论     改进灰狼算法     任务分配     集群侦察    
Research on task allocation of multi-UUV based on improved grey wolf optimizer
YANG Fang, CHEN Yan-yong, ZHANG Yun-jia, LI Jian-ping, PU Jun-tao     
The 705 Research Institute of CSSC, Kunming 650101, China
Abstract: The problem of UUV swarm task assignment is very similar to the problem of wolves attacking and rounding up targets. This paper attempts to introduce the wolf pack behavior theory and gray wolf algorithm into the UUV swarm task assignment problem for the first time. In order to improve the traditional gray wolf algorithm which does not consider the coordination of global and local search and does not consider the weight of position update, this paper proposes an improved gray wolf algorithm that reduces the convergence factor by cosine law and introduces dynamic weights. Feasibility and superiority, carry out reconnaissance and attack target task assignment simulation, and use gray wolf algorithm (GWO), genetic algorithm (GA) and improved gray wolf algorithm (IGWO) to simulate the same scene, result shows that IGWO algorithm is better than GA. The algorithm and GWO can better solve the problem of UUV cluster reconnaissance target task assignment, also reduce the waste of resources and improve work efficiency.
Key words: UUV     wolf pack theory     improved grey wolf algorithm     swarm reconnaissance     task allocation    
0 引 言

UUV集群攻击目标问题是指对UUV集群系统下达一个具体侦察或探测任务时,在一定的约束条件下(如UUV总数守恒、目标依赖关系匹配等),UUV集群的主控台根据具体分配任务的复杂度、各UUV的位置和UUV数量对任务进行分配,使得系统的总目标最优或者系统的某个指标最优,从而提高执行任务效率。

目前UUV集群系统使用的任务分配方法主要有市场机制法和图论法等。近年来,专家学者开始研究生物群体智能,并映射到集群控制研究中,提出了群智能算法。例如多目标猫群优化、灰狼算法[1]、多目标蚁群优化[2]、多目标人工蜂群算法等。吕洪莉[3]针对多区域海底地形勘察问题提出一种基于多个蚁群的多目标优化算法,该算法解决了多UUV从不同位置出发对多区域进行侦察和探测的任务分配问题。Mirjalili等[1]在2014年提出了一种新型群体智能化优化算法,灰狼算法(grey wolf optimizer,GWO)。GWO通过模拟灰狼群体捕食行为,基于狼群群体写作的机制来达到优化的目的。GWO算法结构简单、需调节的参数少,容易实现,但传统灰狼算法并未考虑全局与局部搜索的协调配合以及未考虑位置更新的权重问题。张阳等[4]采用指数规律收敛因子减小策略来提高灰狼算法的求解精度。游达章等[5]将灰狼优化算法中的线性收敛因子转变为非线性收敛因子,并将粒子群与灰狼优化算法结合,将改进算法运用到机器人路径规划中。林梅金等[6]提出了一种基于反余弦函数收敛因子变化和变异策略的新型灰狼优化算法。以上文献都针对灰狼算法中的收敛因子进行了非线性改进,但是没有考虑GWO算法后期搜索多样性的缺失,算法陷入局部最优的问题。本文针对以上2个问题对GWO进行改进,提出改进收敛因子以余弦规律减小和引入动态权重的改进灰狼算法,并基于改进灰狼算法设计UUV集群攻击目标的方法。

狼群围捕猎物的行为具有自主认知、严密分工、分布式、协作性,化整为零和聚零为整的灵活战术,以及对环境的适应性等优点,改进灰狼优化算法能够以较大的概率快速找到最优解,其并行性可以在同一时间从多个点出发进行搜索,点与点之间互不影响,从而提高其效率。本文将狼群行为理论和灰狼算法引入到UUV集群任务分配问题中,基于狼群行为机制对UUV集群攻击目标问题进行数学建模,包括约束条件,攻击目标收益、攻击目标代价以及总代价函数,设计基于改进灰狼算法的UUV集群任务分配的方法。为了验证方法的可行性和优越性,进行集群侦察和攻击目标2种仿真,并针对同一侦察场景分别采用了GWO,GA和IGWO算法进行仿真。

1 UUV集群任务分配问题建模

狼群围捕猎物行为机制包括游动搜索、接近包围和围捕攻击,以及行为更新等智能行为。狼群围捕猎物的行为机制借鉴到UUV集群侦察与攻击多目标任务分配问题中,本文基于狼群围捕猎物的行为机制对UUV集群任务分配问题进行研究。

选用一个五元组描述UUV集群任务分配:

$ \{ P,U,T,C,S\} {\text{。}}$ (1)

式中: $P$ 为目标集合; $U$ 为UUV集合;T为约束条件;C为目标函数集合;S为任务环境。

建立的约束条件有:

$ \sum\limits_{i = 1}^N {num({P_i})} = M {\text{,}}$ (2)
$ num({P_i}) \geqslant \min num({P_r}),{P_r} \in P {\text{,}}$ (3)
$ Pfinal = \left\{ {{P_2},{P_1}, \cdots ,{P_j},{P_i}, \cdots ,{P_n}} \right\} {\text{。}}$ (4)

式中: $num({P_i})$ 为参与目标 ${P_i}$ 的UUV数量; $\min num({P_r})$ 为探测 ${P_r}$ 所需的最少UUV数; $Pfinal$ 为分配目标清单。

建立的目标收益函数如下:

$ benefit = dense + sp \times \left(value \times \sum\limits_{i = 1}^k {hur{t_i}} \right) {\text{。}}$ (5)

式中: $dense$ 为目标的密度; $sp$ 为预估成功的概率; $value$ 为目标的价值; $\displaystyle\sum\limits_{i = 1}^k {hur{t_i}}$ 为该目标的k个UUV的伤害总和; $benefit$ 为攻击目标收益值。

$ damage = {d_1} + {d_2} + {d_3} + {d_4} {\text{。}}$ (6)

式中: ${d_1}$ 为UUV非对抗损失; ${d_2}$ 为UUV的对抗损失; ${d_3}$ 为UUV航程消耗,简单起见,用UUV当前与目标之间的欧式距离定量表示如下:

$ {d_3} = \sqrt {{{({x_{UUV}} - {x_P})}^2} + {{({y_{UUV}} - {y_P})}^2}} {\text{。}}$ (7)

式中: $({x_{UUV}},{y_{UUV}})$ 为UUV的位置坐标; $({x_p},{y_p})$ 为目标的位置坐标; ${d_4}$ 为能量资源消耗。

基于狼群行为机制的UUV集群攻击目标分配模型的目标函数可以定义为:

$ price = damage - benefit {\text{。}}$ (8)

式中,目标收益 $ price $ 为总代价。

2 基于灰狼算法的UUV集群攻击目标算法 2.1 改进灰狼算法

1)灰狼算法

在灰狼算法中,存在社会等级,头狼 $\alpha $ 、从狼 $\beta $ 以及普通狼 $\delta $ 最后还包括底层狼 $\omega $ ,每匹狼代表的含义是一个候选解, $\alpha $ $\,\beta$ $\delta $ 分别代表最优解、次优解和第三优解。算法在运行过程中, $\alpha $ $\,\beta$ $\delta $ 负责定位目标的位置,引导其他狼来进行追踪、围捕和攻击行为,最终成功捕获目标。

灰狼通过以下公式逐渐包围猎物:

$ \vec D = \left| {\vec C \cdot {{\vec X }_p}(t) - \vec X (t)} \right| {\text{,}}$ (9)
$ \vec X (t + 1) = {\vec X _p}(t) - \vec A \cdot \vec D {\text{。}}$ (10)

式中:t为当前迭代次数; $\vec A $ $\vec C $ 为系数向量; ${\vec X _p}(t)$ $\vec X (t)$ 分别为目标与狼的位置。 $\vec A $ $\vec C $ 的计算方式如下:

$ \vec A = 2\vec \alpha \cdot \vec {{r_1}} - \vec \alpha ,\vec C = 2 \cdot \vec {{r_2}} {\text{。}}$ (11)

式中: $\alpha $ 为收敛因子,随着迭代次数增大该收敛因子将线性从2减小到0; ${r_1}$ ${r_2}$ $\left[ {0,1} \right]$ 之间随机分布。

其他狼 ${X_i}$ 根据 $\alpha $ $\ \beta $ $\delta $ 的位置 ${X_\alpha }$ ${X_\beta }$ ${X_\delta }$ 更新自己的位置:

$ {\vec D _\alpha } = \left| {{{\vec C }_1} \cdot {{\vec X }_\alpha } - \vec X } \right|,{\vec D _\beta } = \left| {{{\vec C }_2} \cdot {{\vec X }_\beta } - \vec X } \right|,{\vec D _\delta } = \left| {{{\vec C }_3} \cdot {{\vec X }_\delta } - \vec X } \right| {\text{,}} $ (12)
$ {\vec X _1} = {\vec X _\alpha } - {\vec A _1} \cdot ({\vec D _\alpha }),{\vec X _2} = {\vec X _\beta } - {\vec A _2} \cdot ({\vec D _\beta }),{\vec X _3} = {\vec X _\delta } - {\vec A _3} \cdot ({\vec D _\delta }) {\text{,}}$ (13)
$ \vec X (t + 1) = \frac{{{{\vec X }_1} + {{\vec X }_2} + {{\vec X }_3}}}{3}{\text{。}} $ (14)

式中: ${\vec D _\alpha }$ ${\vec D _\beta }$ ${\vec D _\delta }$ 分别为其他狼与 $\alpha $ $\ \beta $ $\delta $ 之间的距离; ${\vec X _\alpha }$ ${\vec X _\beta }$ ${\vec X _\delta }$ 分别为 $\alpha $ $\ \beta $ $\delta $ 当前的位置; ${\vec C _1}$ ${\vec C _2}$ ${\vec C _3}$ 为随机向量; $\vec X $ 为其他狼当前的位置向量。

2)改进灰狼算法

群体智能算法在迭代过程中均有全局搜索和局部搜索2种搜索方式,全局和局部搜索需要较好的协调,否则算法会陷入局部最优或收敛性能降低。全局搜索能力强能够使保持算法种群的多样性从而避免算法陷入局部最优,局部搜索能力强可以确保精确的进行局部搜索,加速算法的收敛。GWO作为群智能算法之一也要均衡两者,其中收敛因子就是与全局和局部搜索相关的值,GWO中 $\alpha $ 是线性减小,可以用等式(15)表示,这种线性变化不能够完全体现出优化搜索的实际过程。

在GWO算法中,狼群个体主要跟随最优解 $\alpha $ 狼来更新自己的位置。在搜索后期,基于保存最优个体的策略,狼群将会大量聚集在 $\alpha $ 狼左右,这样会导致搜索多样性的缺失。尤其当 $\alpha $ 狼陷入局部最优解时,整个算法也将会陷入局部最优,导致算法精度下降。

针对这些问题,本文提出改进收敛因子减小规律和引入动态权重的方式改进传统灰狼算法(improve grey wolf optimizer,IGWO)。

1)收敛因子以余弦规律减小的策略

本文提出一种让 $\alpha $ 收敛因子做余弦规律减小的方式,如下式:

$ \alpha = 2 \times (1 - t/T) {\text{,}}$ (15)
$ \alpha = \left\{ \begin{gathered} {\alpha _f} + ({\alpha _i} - {\alpha _f}) \times \frac{{1 + {{\left| {\cos ((t - 1){\text{π}} /(T - 1))} \right|}^n}}}{2},t \leqslant \frac{1}{2}T {\text{,}} \\ {\alpha _f} + ({\alpha _i} - {\alpha _f}) \times \frac{{1 - {{\left| {\cos ((t - 1){\text{π}} /(T - 1))} \right|}^n}}}{2},\frac{1}{2}T < t \leqslant T {\text{。}} \\ \end{gathered} \right. $ (16)

式中: ${\alpha _f}$ ${\alpha _i}$ 为收敛因子的最终和初始值,和GWO一样, ${\alpha _f}$ ${\alpha _i}$ 为0和2, $t$ $T$ 分别为当前和总迭代次数, $n$ 为递减参数,取值0~1,本文取0.6。 $\alpha $ 收敛因子做余弦规律减小的变化如图1所示。

图 1 收敛因子变化图 Fig. 1 Change of convergence factor

原始的收敛因子在迭代过程中线性减小,改进后的因子图像是一条余弦规律减小的曲线,在初期减小的速率较慢,收敛因子可以长时间保持在较大值,从而提高搜索效率,后期收敛因子减小的速率较快,可以提高算法的精度,从而有效地平衡了GWO算法的全局与局部搜索的更离。

2)引入自适应移步方法与改进适应度值的动态比例权重策略

受差分进化算法与文献[7]的启发,引入了自适应移步方法与改进适应度值的动态比例权重策略。文献[7]提出了一种基于适应度值的比例权重表达式可能会出现分母为0的情况,所以在文献[7]的基础上,对其他狼更新位置的公式继续改进,在学习率的公式中再引入一个极小的常数 $\ \rho $ ,取为 ${10^{ - 15}}$ ,表达式变为式(19),再将自适应移步方法引入到式(14)中,其他狼更新位置的最终公式变为式(20)。

$\begin{split} {W_1} &= \frac{{\left| {{X_1}} \right|}}{{\left| {{X_1}} \right| + \left| {{X_2}} \right| + \left| {{X_3}} \right| + \rho }}, {W_2} = \frac{{\left| {{X_2}} \right|}}{{\left| {{X_1}} \right| + \left| {{X_2}} \right| + \left| {{X_3}} \right| + \rho }},\\ {W_3} &= \frac{{\left| {{X_3}} \right|}}{{\left| {{X_1}} \right| + \left| {{X_2}} \right| + \left| {{X_3}} \right| + \rho }}{\text{。}} \end{split}$ (17)
$ X(t + 1) = \frac{{{X_1} \cdot {W_1} + {X_2} \cdot {W_2} + {X_3} \cdot {W_3}}}{3}\left(1 - \dfrac{t}{T}\right) + {X_1}\frac{t}{T} {\text{。}}$ (18)

式中: ${W_1}$ ${W_2}$ ${W_3}$ 表示的是其他狼对 $\alpha $ $\ \beta $ $\delta $ 狼的学习率,引入这种比例权重可以提高算法的收敛速度。

3)改进灰狼算法步骤

结合所有的改进策略,本文提出的改进灰狼算法流程图如图2所示。

图 2 改进灰狼算法流程图 Fig. 2 Flow chart of IGWO
2.2 基于改进灰狼算法的UUV集群攻击目标方法

基于UUV集群攻击目标的数学模型,本文提出UUV集群攻击目标的方法。根据现有的信息生成地图,将N个目标信息标记在地图上并初始化UUV;对要攻击目标进行优先级排序;头UUV分配目标;头UUV根据获得的目标优先级列表来向从UUV分配目标,从UUV向头UUV汇报的目标函数值,头UUV进行汇总,得到目标总代价值 $ price $ 矩阵,再利用改进灰狼优化算法向做出响应的从狼分配攻击目标;判断待分配总任务数是否为0。若为0则分配攻击目标工作完成,若不为0,返回进行分配。总流程如图3所示。

图 3 基于改进灰狼算法的UUV集群攻击目标流程图 Fig. 3 Flow chart of research on cluster attack of multi-UUV based on improve grey wolf optimizer
3 仿真 3.1 UUV集群侦察任务分配仿真

仿真试验以UUV集群为仿真对象,选取 $x,y \in [0, 1000{\text{ m}}]$ 的海洋区域为仿真环境,xy分别表示区域的长和宽,在该区域内设置6个任务目标,3个侦察型UUV。仿真试验中3个UUV组成的UUV集群负责侦察6个任务目标,每个任务目标没有特殊性,可被任意一个UUV侦察,为了侦察结果更加准确,每个被侦察目标应该被同一个或多个UUV侦察2次。利用提出的基于改进灰狼算法的UUV集群攻击目标方法进行侦察任务分配,期望最后总侦察代价最小。出于简化,仿真取 $dense = 0$ ,取 $sp = 1$ 即假设攻击会成功,取 $\displaystyle\sum\limits_{i = 1}^k {hur{t_i}} = k$ 。因为仿真环境中没有设置障碍物,所以取 ${d_1} = 0$ ,取 ${d_2} = 0.5$ 。侦察代价用时间表示,单位为min。UUV集群侦察仿真初始分布如图4所示。

图 4 初始分布图 Fig. 4 Initial distribution

3艘侦察型UUV起始位置在图下方呈一字排开坐标分别为 $(500,100)$ $(600,100)$ $(700,100)$ ,6个需要被确认与处理的目标分布在如图的位置。假设UUV的速度为2 m/s,2个被侦察目标之间最大距离约800 m,每个UUV侦察完一个目标后前往下一个目标,所需时间约7 min,设每个目标需要侦察10 min。

依据总代价函数,利用改进灰狼优化算法,得到最终图5的UUV集群侦察目标分配结果。为了更加直观表示分配结果,基于图5得到图6所示的分配结果示意图,再将每个UUV侦察的目标进行汇总得到表1。由表1可知,每个UUV被分配的目标数较为均衡符合预想。

图 5 UUV集群侦察目标分配结果 Fig. 5 Distribution result and convergence curve diagram

图 6 UUV集群侦察目标分配结果示意图 Fig. 6 Distribution result diagram

表 1 UUV集群侦察目标分配情况表 Tab.1 Distribution result
3.2 UUV集群攻击任务分配仿真

设定每个UUV只能攻击一个目标,根据不同目标的价值高低分配的UUV数量也不同。仿真试验选取 $x,y \in [0,1000]$ 的区域为仿真环境,xy分别表示区域的长和宽,在该区域内设置任务目标与UUV。仿真试验中UUV组成的UUV集群负责攻击任务目标,同样的,出于简化,仿真取 $dense = 0$ ,取 $sp = 1$ 即假设攻击会成功,取 $\displaystyle\sum\limits_{i = 1}^k {hur{t_i}} = k$ 。因为仿真环境中没有设置障碍物,所以取 ${d_1} = 0$ ,取 ${d_2} = 0.5$ 。集群攻击初始分布如图7所示。侦察代价用时间表示,单位为min。

图 7 初始分布情景 Fig. 7 Initial distribution

目标1和目标2分别为低价值和高价值目标,3个攻击型UUV放置在 $(600,600)$ 位置,UUV距离两目标的距离相等。图8为情景中UUV集群攻击目标的分配结果与收敛曲线图。

图 8 UUV集群攻击目标分配结果 Fig. 8 Distribution result and convergence curve diagram

基于图8得到图9所示的UUV集群攻击目标分配结果示意图,再将结果汇总得到表2。如图9所示,UUV1和UUV2去攻击了目标2,UUV3独自攻击了目标1。在距离相同的条件下,分配攻击高价值目标的UUV较多,分配攻击低价值目标的UUV较少,符合预期目标。

图 9 分配结果示意图 Fig. 9 Distribution result diagram

表 2 UUV集群攻击目标分配情况表 Tab.2 Distribution result
3.3 基于GA、GWO和IGWO的UUV集群任务分配对比仿真

在原来仿真条件基础上,增加目标的数量到12个为原来目标数的2倍,分别采用灰狼算法(GWO)、遗传算法(genetic algorithm,GA)和改进灰狼算法(IGWO)进行仿真。遗传算法是一种高效率,并行性强,全局搜索的优化算法。仿真结果如图10所示,3种算法得到的最优值结果(即完成任务最短时间)分别为61.59,62.07和60.97 min,单次仿真结果不能得出看出哪者更优的结论,接下来进行多次仿真再统计比较3种算法得到的最优解。

图 10 GWO,GA和IGWO集群侦察任务分配对比图 Fig. 10 Distribution result

图10可知,3种算法得到的最优值结果分别为61.591,62.067和60.975 min,单次仿真结果不能得出哪个更优的结论,所以进行多次仿真再统计比较2种算法得到的最优解。为了更加清楚地对比结果,将3种算法得到的分配情况进行汇总得到表3V表示最优值,单位为min,T表示第几次仿真。

表 3 UUV集群侦察目标分配情况对比表 Tab.3 Distribution result

GWO得到的最短时间为61.516 min,GA得到的是62.128 min,IGWO得到的是61.138 min。综上说明,IGWO算法比GWO和GA算法能够更好对UUV集群侦察目标任务分配的问题进行求解,提高多UUV系统的资源利用率和系统的工作效率。

4 结 语

狼群攻击围捕目标行为机制有很多优点,基于狼群理论提出的优化算法寻优效率高。本文将狼群行为理论引入到UUV集群任务分配问题中,解决UUV集群侦察与攻击多任务目标的问题。基于狼群行为机制对UUV集群攻击目标问题进行数学建模,包括约束条件,攻击目标收益、攻击目标代价以及总代价函数;针对传统灰狼算法未考虑全局与局部搜索的协调配合以及未考虑位置更新的权重问题进行改进,提出改进收敛因子以余弦规律减小和引入动态权重的改进灰狼算法设计基于改进灰狼算法的UUV集群任务分配的方法。为了验证方法的可行性和优越性,利用Matlab进行侦察和攻击目标分配仿真,并针对同一场景分别采用GWO、GA和IGWO三种算法对比仿真。结果表明,IGWO算法比GWO和GA算法能够更好对UUV集群侦察目标任务分配的问题进行求解,提高UUV系统的资源利用率和系统的工作效率。

参考文献
[1]
SEYEDALI M, SEYED M M. Grey Wolf Optimizer[J]. Advances in Engineering Software, 2014: 46–61.
[2]
SEYEDALI M. Multi-objective ant lion optimizer: a multi objective optimization algorithm for solving engineering problems[J] Springer, 2016(45) 46–61.
[3]
吕洪莉. 面向多目标优化的多AUVs群体协同任务分配[D]. 哈尔滨: 哈尔滨工程大学, 2012.
[4]
张阳, 周溪召. 求解全局优化问题的改进灰狼算法[J]. 上海理工大学学报, 2021(43): 73-82. DOI:10.13255/j.cnki.jusst.20200331002
[5]
游达章, 等. 一种改进灰狼优化算法的移动机器人路径规划方法[J]. 机床与液压, 2021, 49(11): 1-6.
[6]
林梅金, 等. 改进收敛因子和变异策略的灰狼优化算法[J]. 佛山科学技术学院学报(自然科学版), 2021, 39(3): 1-6. DOI:10.13797/j.cnki.jfosu.1008-0171.2021.0031
[7]
郭振洲, 刘然, 拱长青, 等. 基于灰狼算法的改进研究[J]. 计算机应用研究, 2017(12): 3603-3606.