基于弹性网格的改进遗传算法在无人艇路径规划中的研究

余文曌， 佘航宇， 欧阳子路

(1. 武汉理工大学 a. 交通学院; b. 物流工程学院，武汉 430063; 2. 上海交通大学 a. 海洋工程国家重点实验室； b. 海洋智能装备与系统教育部重点实验室， 上海 200240)

随着时代发展，无人艇技术已得到深入发展。无人艇不仅可用于民用领域，比如海上搜救、垃圾清理和环境监测等方面，还可用于军事上的海上巡逻、侦查、监视和扫雷等方面，具有十分广泛的应用领域。[1]同时，无人艇路径规划对于舰船实现自动化航行和航线优化具有重要意义，要求在复杂的海洋环境中，根据已知的地理信息数据，寻找出一条从起点到终点的最安全且航程最短的航线。[2]目前已有多种算法被应用于路径规划，例如粒子群算法[3]、神经网络算法[4]和人工势场法。[5]其中遗传算法较为灵活，使用相对广泛，已被应用于众多无人设备的路径规划。

遗传算法现已在路径规划方面得到一定的运行效果。但是标准遗传算法搜索空间一般较大，存在过多多余搜索、导致收敛速度慢和运行时间长等缺陷。例如，文献[6]和文献[7]所提的基于栅格地图的改进遗传算法中，当栅格密度较大时，搜索空间达数百数千栅格，有较多冗余搜索，影响算法搜索收敛速度。本文在原有遗传算法的基础上加入弹性网格概念，采用简单独立坐标编码，通过动态变换地图网格密度，减小算法搜索空间；同时，加入自适应变异算子，以加速收敛速度。

1 环境模型的建立

在路径规划中，需先对环境信息进行描述。由于复杂的海面环境导致算法不能直接被利用，采用坐标法建立海平面二维模型，并将复杂的海面地理信息进行简化，把障碍物适当扩大安全距离，转化成简单的封闭几何图形(见图1)。图1a)地图位于印度尼西亚附近海域，由部分岛礁组成中心经度为123°38′，纬度为01°57′；图1b)地图在坐标平面内以黑色部分表示障碍物，(0，0)为起始点，(40，40)为目标点。

2 遗传算法的改进及实现方法

2.1 路径编码

对于个体路径采用十进制横、纵坐标简单独立编码，其具体结构为

Xi(xi1→xi2→…→xik→…→xij)

Yi(yi1→yi2→…→yik→…→yij)

(1)

式(1)中：Xi为第i条路径全部横坐标编码；Yi为该路径全部纵坐标编码。示例路径见图2，可表示为

X1(0,6,10,12,19,21,25,27,29,35,40)

Y1(0,7,11,14,21,22,23,23,25,33,40)

(2)

式(2)中：B为路径转向点。

2.2 适应度函数

在全局路径规划过程中需选取合适的适应度函数，即将目标函数作为评价群体中路径优劣的标准和依据。[6]适应度函数的建立应综合考虑安全性与经济性，需满足以下条件：与障碍物无干涉、路径长度尽可能短和各转向角要尽可能小。这里综合考虑3个条件作为适应度函数的评价标准。

2.2.1路径长度

(3)

式(3)中：len为个体路径总长度；m为权重因子，用以调整路径长度评价在总体适应度评价中的权重大小；L为起始点到目标点直线近似距离。

2.2.2路径转角

(4)

式(4)中：n为权重因子用以调整路径转角评价在总体适应度评价中的权重大小；aveangle为路径平均转角；θ为无人艇最大舵角，取35°。

2.2.3路径安全性

fit3=(1-0.1×interdots)×k

(5)

式(5)中：interdots为与障碍物有干涉路径段个数；k为适应度权重调整因数；综合适应度为Fit=fit3×(fit1+fit2)，即综合适应度函数为

(1-0.1×interdots)×k

(6)

2.3 算法基本操作

2.3.1选择操作

传统遗传算法采用轮盘赌方法[7]，根据个体适应度大小选择优秀个体，为生成子代参与交叉变异操作。然而，交叉变异操作可能导致优秀个体流失。本文采用在父代与交叉变异后的个体之间同时进行选择操作，从而获得子代个体，以确保优秀个体能进化到下一代。

2.3.2交叉操作

采用单点交叉法对个体进行交叉[8]，以一定的概率选择路径A中某单个路径点，将该点之后所有路径与路径B中相应路径点交换，形成新的个体路径。

2.3.3变异操作

变异操作在遗传算法中的作用有：

(1) 增强遗传算法的局部搜索能力，与选择和交叉相互配合，可兼顾全局和局部搜所能力；

(2) 保持群体多样性、避免早熟过早收敛，减少选择和交叉操作造成的有用信息流失，保证遗传算法搜索的有效性。[9]

采用自适应变异算子，根据各代路径离散程度，动态调整变异概率。以相应概率选择个体某一路径点，随机搜索坐标点进行替换来作为新个体路径。其自适应调整公式为

Pm=e(-2×varfit)

(7)

式(7)中：varfit为各代适应度总体方差大小，以描述该代路径离散程度。由于在离散程度趋近于0时，路径适应度变化幅度减小，在相同代数里，总体适应度变化幅度较小，所以实现离散度逐渐接近0时，变异概率加速趋近1，以避免陷入局部最优解。同时，在变异概率内采取对与障碍物有干涉路径段两端点采取随机变异和对随机寻找的转向点采取随机变异等多种变异方式。其变异概率自适应调整函数见图3。

2.4 动态变换网格密度

传统遗传算法搜索空间较大，限制了算法的运行效果，且接近最优解时，算法收敛速度降低，相同时间内路径适应度增加不显著。本文采用弹性网格概念，初步采用低密度网格坐标系，减少算法搜索空间；当算法接近当前最优解时，针对各转向点增加局部网格密度，将该点的邻近点构成的方形网格进一步划分，且以该网格为新的变异空间，继续进行算法寻优。例如初级密度网格见图4，次级网格密度见图5，图中曲线为当前路径，图中B点为路径各转向点。

以上述操作为理念，根据实际地图大小及其复杂程度自定义初始，而网格密度以及网格密度升级速度降低算法搜索空间，提升算法搜索速度，加强针对性，以更高效率寻求最优路径。

3 仿真结果与分析

为验证该算法的可行性，运用软件仿真。利用简单海洋环境地图，视无人艇为一质点，起始点坐标为(0,0)，终点坐标为(40,40)。

3.1 自适应变异概率对比分析

为验证自适应调整变异算子的可行性，实现标准遗传算法，先取算法定网格密度，初始种群规模为30个个体，迭代次数为110代，交叉概率为0.9，变异概率为0.2，适应度函数中各变量分别取m=140,L=56,n=20,θ=35,k=0.75，即适应度函数为

(1-0.1×interdots)×0.75

(8)

再取变异概率根据种群情况自适应调整，其余参数均取相同。其适应度成长曲线对比见图6，最终寻优路径对比见图7，其中自适应调整变异概率遗传算法适应度成长较快，最终稳定于5.2左右，收敛效率稍有提高。

3.2 弹性网格概念对比分析

为验证在标准遗传算法中加入弹性网格概念的可行性，变异概率根据种群情况自适应调整，其他数值均与第3.1节所述相同，即适应度函数为

(1-0.1×interdots)×0.75

(9)

为更加直观地了解算法运行结果，另取标准遗传算法定网格密度，其余参数均取相同。适应度成长曲线对比见图8，算法最终寻优结果对比见图9。

其中改进遗传算法于50代左右、80代左右两次增加局部网格密度。由图8和图9可知：改进遗传算法路径适应度在两次增加局部网格密度后进一步升高，最终适应度达到7.6左右，收敛效率有所提高。基本遗传算法在接近最优解时适应度成长速度逐渐降低，适应度值于最优解附近趋于平稳，最终约为5.3。

为进一步验证改进算法可行性，选用较为复杂的真实海洋环境地图对改进算法进行仿真，算法于第50代、第80代左右增加局部网格密度。最终寻优结果见图10。其适应度成长曲线见图11。

由综合仿真结果得，在复杂环境地图下，路径适应度于较少代数内部接近于当前网格密度下的最优路径解，经过两次增加网格密度后路径适应度明显进一步上升，最终达到6.4左右，且所得最终路径显然符合可行路径标准。可知改进算法有一定的可行性和有效性，且较标准遗传算法有较高的收敛效率与较好的寻优效果。

4 结束语

1) 本文在标准遗传算法上做出改进，加入弹性网格概念，通过动态变换网格局部密度，达到减小算法搜索空间，以提高搜索效率的目的；

2) 设计了自适应调整变异概率公式，避免算法出现局部最优解；

3) 利用软件仿真，试验结果表明基于弹性网格的遗传算法在无人艇路径规划方面有一定的可行性及有效性。