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

范学满; 薛昌友; 张会

doi:10.11993/j.issn.2096-3920.202107001

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

doi: 10.11993/j.issn.2096-3920.202107001

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

基金项目: 中国博士后科学基金项目资助(2021M693939)

详细信息

作者简介:
范学满(1989-), 男, 博士, 助理研究员, 主要研究方向为智能辅助决策

通讯作者:
薛昌友(1969-), 男, 博士, 教授, 主要研究方向为指挥信息系统

中图分类号: U674; E837
计量
- 文章访问数: 512
- HTML全文浏览量: 118
- PDF下载量: 87
- 被引次数: 0
出版历程
- 收稿日期: 2021-07-05
- 修回日期: 2021-09-05
- 网络出版日期: 2022-09-15

Task Assignment Method for Multiple UUVs Based on Multi-population Genetic Algorithm

Naval Submarine Academy, Qingdao 266199, China

摘要

摘要: 多无人水下航行器(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..
- unmanned undersea vehicle(UUV) /
- multi-population genetic algorithm /
- task assignment /
- cooperative reconnaissance

HTML全文

图 1 满足时序约束的可行解有向图

Figure 1. Directed graph of feasible solutions satisfying temporal constraints

下载: 全尺寸图片幻灯片

图 2 违反时序约束的非可行解有向图

Figure 2. Directed graph of infeasible solutions violating temporal constraints

下载: 全尺寸图片幻灯片

图 3 UUV协同任务分配方案

Figure 3. Allocation scheme of collaborative task for UUV

下载: 全尺寸图片幻灯片

图 4 多种群遗传算法流程图

Figure 4. Flow chart of multi-population genetic algorithm

下载: 全尺寸图片幻灯片

图 5 目标和UUV初始态势分布图

Figure 5. Initial distribution of targets and UUVs

下载: 全尺寸图片幻灯片

图 6 侦察目标对载荷种类需求曲线

Figure 6. Demand curve of targets to load types

下载: 全尺寸图片幻灯片

图 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	目标
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	目标
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

参考文献(12)

[1]	严浙平, 刘祥玲. 多UUV协调控制技术研究现状及发展趋势[J]. 水下无人系统学报, 2019, 27(3): 226-231. doi: 10.11993/j.issn.2096-3920.2019.03.001 Yan 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.170671 Dong 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.150184 Liu 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.20181206001 Zhang 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.012 Jiao 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/.