基于数据驱动的遗传算法的无人艇路径规划研究

辛峻峰, 张永波, 伯佳更, 赵博文, 范世缘

【摘要】 遗传算法（GA）是无人艇路径规划系统中的一种有效方法，为了克服该算法易陷入局部最优早熟和收敛速度慢等缺陷，在不增加算法复杂度的前提下，基于数据驱动线性动态交叉策略提出了一种能够在最短时间内自适应动态调整控制参数的改进遗传算法（LCPGA）。与传统的遗传算法相比，LCPGA增加了种群多样性，能更有效地避免陷入局部最优，并提高了路径规划的精度、稳健性和收敛速度。仿真实验和无人艇现场试验验证了该算法具有更优良的性能，该算法可为无人艇路径规划提供一定的应用价值。

【关键词】 路径规划  ;  改进遗传算法  ;  无人艇  ;  自适应    

引用格式 辛峻峰, 张永波, 伯佳更, 赵博文, 范世缘.基于数据驱动的遗传算法的无人艇路径规划研究. 智能科学与技术学报[J], 2019, 1(2):  171-180 

 Study on path planning of unmanned surface vessel based on data-driven genetic algorithm     

XIN Junfeng, ZHANG Yongbo, BO Jiageng, ZHAO Bowen, FAN Shiyuan

Abstract  The genetic algorithm (GA) is an effective method for the path planning system of unmanned surface vessel (USV),but it is easy to fall into local optimal precocity and converges slowly.For this,without increasing the complexity of the algorithm,a data-driven linear changing parameters genetic algorithm (LCPGA) was proposed,which can adjust adaptively control parameters in the shortest time.Compared with the traditional genetic algorithm,the LCPGA increases the diversity of the population,avoids falling into local optimum more effectively,and improves the accuracy,robustness and convergence speed of path planning.Then simulation experiments and field tests verify the more excellent performance of the LCPGA.This algorithm can be helpful in path planning for unmanned surface vessel.

Keywords：  path planning ;  improved genetic algorithm ;  unmanned surface vessel ;  self-adaption

Citation XIN Junfeng.Study on path planning of unmanned surface vessel based on data-driven genetic algorithm. Chinese Journal of Intelligent Science and Technology[J], 2019, 1(2):  171-180

1 引言

水面无人艇^[1,2]（unmanned surface vessel， USV）是一种无人操作的水面舰艇，主要用于执行危险或不适于有人船只执行的任务，具有体积小、速度快、智能化和自动化程度高等特点，可用于水文气象探测、环境监测和海上搜救等。

人工智能就是让机器能够像人一样学习、思考并理解，即用计算机模拟人的智能，它涵盖认知与推理（包含各种物理常识和社会常识）、计算机视觉、自然语言理解与交互（包含听觉）、机器学习等广泛的学科领域。人机协同的混合增强智能是新一代人工智能的典型特征，当AI进入新的时代——后深度学习时代，各国都将处于同一起跑线上，谁能跑到最前面并引领AI的发展，完全取决于其创新能力，特别是原始创新能力^[3,4]，而USV 的主要配备系统包括运动控制系统、传感器系统、通信系统和武装系统。运动控制系统分为导航定位子系统、路径规划子系统和航迹跟踪子系统，其中路径规划子系统的路径规划算法是USV 研究的核心问题之一，代表无人艇的智能化水平。算法在智能控制中起着至关重要的作用，如基于 UWB 定位技术的多移动机器人编队控制算法能够使多机器人系统达成速度一致性，并且能够按照给定轨迹实现编队队形^[5]。20 世纪中后期Holland和Bagley^[6,7,8,9]提出的遗传算法直接对结构对象进行操作，不存在求导和函数连续性的限定，具有内在的隐并行性和更好的全局寻优能力，且该算法采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应调整搜索方向，不需要确定的规则，求解速度快、质量高，更适用于欠驱动无人艇的路径规划。但传统遗传算法存在收敛速度慢和种群早熟等问题。

针对上述缺点，本文在文献[6]的基础上不增加算法复杂度，提出了一种数据驱动线性遍历控制参数的遗传算法，继而通过蒙特·卡罗实验和现场试验对比改进算法与传统遗传算法，验证改进算法的优良性能。

2 遗传算法

2.1 传统遗传算法

传统遗传算法（流程如图 1所示）的计算步骤如下^{[10,11,12,13,14,15,16]}。

① 根据实际问题，确定实际问题的参数值，并确定所选用的编码方式；

② 在论域空间U上定义一个适应度函数f(x)；

③ 给定种群规模N、交叉概率P_c和变异概率P_m等参数；

④ 随机产生U中的N个染色体组成初始种群，置代数计数器g=1；

⑤ 计算S中每个染色体的适应度f(x)；

⑥ 根据遗传算法的方法（即选择、交叉、变异）生成下一代群体；

⑦ 如果生成的新群体满足某个性能指标，或者满足已经设定的代数规定，结束操作；否则返回第⑥步，重新进行选择、交叉、变异的操作。

利用传统遗传算法求解实际问题时，第③步的控制参数主要是凭经验给定的：种群大小N为20～100，交叉概率 P_c为 0.60～0.90，变异概率 P_m为0.001～0.01^[9]。

2.2 改进的遗传算法

借鉴 Ratnaweera^{[14,15,16,17,18,19]}的研究成果对传统遗传算法进行优化，对步骤③控制参数的选取改进如下。

首先设定P_c和P_m的选取范围分别为0.9～0.1和0.001～0.1，继而使用式（1）逐步迭代线性更新P_c和P_m，随着迭代次数的增加，P_c从0.9线性递减到0.1，同时P_m从0.001线性递增到0.1。最终遍历更新获取全局最优值。

其中，P_ce、P_cs分别是 P_c的终值和初值，P_me、P_ms分别为P_m的终值和初值；gen是由0以1的步长逐渐递增的迭代次数；MAXGEN 是最大迭代次数。改进过程如图2所示。

理论上的改进使遗传算法具备了以下两个更优异的性能：

① 交叉概率P_c和变异概率P_m两个控制参数不再需要人为设定，避免了初始参数选择的盲目性；

② 随着待规划点矩阵维数的增加，交叉概率和变异概率两个参数的自适应线性变化组合在搜索初期使种群尽可能地扩大搜索空间以获取更多的信息便于自身做出相应的调整，从而增加群体的多样性，尽可能摆脱局部极值的干扰，提高传统遗传算法向全局最优点收敛的能力，提高算法的计算效率以及路径规划的稳健性。

3 仿真实验

本节设置了5种工况，即分别随机选取10、20、30、40、50个待规划点，全面科学地对比改进算法与传统算法的性能。

3.1 对比方案一（路径规划长度和计算精度）

参数选定如下：传统遗传算法种群大小N设置为100，交叉概率P_c设置为0.9，变异概率P_m设置为0.1；改进遗传算法种群大小N同样设置为100，交叉概率P_c和变异概率P_m不需要设置（见表1）。

选定参数后分别进行蒙特·卡罗仿真实验获取两种算法的路径规划性能，实验结果如图3所示。

从图3中可见：5种工况下，直线在纵轴上的位置和散点的离散程度都很相似，并不能清晰地展示两种算法的差异，进而分别单独对比两种算法规划结果的均值（如图4所示）和方差（如图5所示）。从图4中可以看出：两条曲线几乎重合，这说明传统算法和改进算法在5种工况下的规划路径长度相差不大，即待规划点数不同，不会影响两种算法规划路径的长度。

为了对比两种算法的稳健性，继续对比计算结果的离散情况（如图5所示），其方差如式（2）所示。

3.2.1 计算时间对比

图6是5种工况下两种算法路径规划过程所消耗时间的对比结果，可以看出，实线明显高于虚线且间隙较大，说明改进算法的路径优化用时更短。

进一步用量化结果探究两种算法的差异，见表3。

由表3可以看出：改进算法在寻找最优解的过程中比传统方法节省了13.04%～20.874%的时间，而且随着待规划点数的增加，相对误差逐步增大，说明待规划点数越多，改进算法节省的时间越多，优势越明显。

注：相对误差=（改进算法-传统算法）/传统算法。

3.2.2 收敛速度对比

图7所示为传统算法和改进算法单次计算的优化过程，随着迭代次数的增加，路径长度减小，曲线趋于水平并保持不变时即为找到最优解，该水平线对应的数值越小，寻优效果越好，找到最优解的最小迭代次数越小，收敛速度越快。

图7的5个分图中，浅蓝色线全部位于深蓝色线下方，说明同样条件下改进算法规划路径的收敛速度更快，且最大稳态相对误差高达61.538%（见表4）。

综上，本节验证了改进算法无论是在消耗时间还是收敛速度的计算效率上都具有明显优势。

注：相对误差=（改进算法-传统算法）/传统算法。

4 现场试验

本节将使用无人艇实船海上路径规划数据验证上文的分析结论。

4.1 试验设备

4.1.1 试验船型

本次海上实测使用的是实验室自主研发的新型智能五体无人艇，它配备一整套完整的电气控制系统，主要包括电源模块、检测单元、输出控制单元、存储单元、时间单元、通信和人机接口。其中，存储单元可实时存储无人舰艇 GPS 位置、航行日志、状态信息等；通信单元使用Wi-Fi通信和GPRS通信等多种可选通信方式，通信距离为5 km，传输速率为1～100 Mbit/s，实船如图8所示。

4.1.2 试验数据采集仪器——多功能传感器

传感器采用英国 AIRMAR 多参数传感器，如图9所示。

4.1.3 试验数据采集系统

数据采集使用惯性导航模块和GPS-BD模块完成（如图10和图11所示）。

 4.2 数据采集  

试验海域位于青岛市奥帆中心附近，通过惯性导航模块和GPS-BD模块采集待规划点。试验当天海况见表5，试验现场如图12所示。

4.3 实验对比

本节设置了3种工况，即随机选取10个、25个和35个待规划点，分别验证改进算法的性能优势。其中两种算法的参数选取方案为：传统遗传算法种群大小取100，交叉概率P_c设为0.9，变异概率P_m设为0.1；改进遗传算法种群大小取100，交叉概率P_c和变异概率P_m不需要设置。

4.3.1 对比方案一（10个待规划点）

选取10个待规划点，坐标见表6。

 图 13 中，深蓝色线位于浅蓝色线的上方且深蓝色线出现的折点明显比浅蓝色线多，说明改进算法规划的路径更短且迭代次数更少、收敛速度更快。

待规划点为 10 个时，传统算法和改进算法规划路径的轨迹如图14所示。

从统计结果（见表 7）可以更清晰地看出，改进算法规划的路径比传统算法规划的路径短2.631%，消耗时间少15.16%，验证了前文的研究结果。

注：相对误差=（改进算法-传统算法）/传统算法。

4.3.2 对比方案二（25个待规划点）

选取的25个待规划点的坐标见表8。

图 15 中，浅蓝色线位于深蓝色线的下方且浅蓝色线达到水平明显比深蓝色线早得多，说明改进算法规划的路径更短且收敛时的迭代次数更少、收敛速度更快。

待规划点为 25 个时，传统算法和改进算法规划路径的轨迹如图16所示。

从统计结果（见表 9）可更清晰地看出，改进算法规划的路径比传统算法规划的路径短6.557%，消耗时间少12.779%。

注：相对误差=（改进算法-传统算法）/传统算法。

4.3.3 对比方案三（35个待规划点）

选取的35个待规划点的坐标见表10。

图 17 中，浅蓝色线位于深蓝色线的下方且浅蓝色线达到水平明显比深蓝色线早得多，说明改进算法规划的路径更短且收敛时的迭代次数更少、收敛速度更快。

待规划点为 35 个时，传统算法和改进算法规划路径的轨迹如图18所示。

从统计结果（见表11）可更清晰地看出，改进算法规划的路径比传统算法规划的路径短16.867%，消耗时间短7.635%。

综上，本节试验验证了改进算法不但规划的路径短而且计算效率更高。

5 结束语

本文针对传统遗传算法易早熟和全局收敛慢等不足，基于数据驱动控制参数线性动态遍历策略对其进行了改进，并通过蒙特·卡罗实验和现场试验验证了改进算法的优势：① 改进算法能在很大程度上避免早熟现象，且全局规划的路径更短，精度、稳健性更高，收敛速度更快；② 待规划点数越多，改进算法的坐标分布特征提取效率越高，优势越明显；③ 改进算法的控制参数自适应选定，操作更便捷，智能化程度更高，通用性和实用性更好，更适用于欠驱动无人艇的路径规划。