基于改进遗传算法的船舶路径规划

谢玉龙，王 直

(江苏科技大学 电子信息学院，江苏 镇江 212003)

0 引 言

随着船舶智能化的发展，人们对船舶路径规划和动态避障的要求越来越高。由于海洋环境的复杂性(包括风浪、船舶、危险海域等)，船舶在海上航行可能会出现各种各样的危险，所以路径规划是船舶航行过程的重要环节。船舶路径规划是在一定的障碍环境中，按照一定的性能指标(距离最短、时间最短或者消耗最少等)，为船舶规划出从起点到终点的最优无碰撞路径[1]。

路径规划是近年来的研究热点，比较流行的路径规划方法有：蚁群算法、人工场势法、神经网络、遗传算法等。每一种算法都有各自的优缺点。例如，遗传算法是一种全局寻优算法，具有鲁棒性、适应能力强等优点，而标准遗传算法又存在早熟、陷入局部最优、寻优时间长等问题，输出的最优解有时不能完美地应用到实际中[2]，同时保证不了对路径规划的计算效率和可靠性的要求[3]。为了提高路径规划问题的求解质量和求解效率，文中在传统遗传算法的基础上，提出了一种改进的遗传算法，即在原有遗传算法五元素(选择操作、交叉操作、变异操作、编码解码、适应度评价)的基础上增加了复原操作、重构操作和录优操作。另外，在传统遗传算法基础上增加了新的基本操作，又增加了插入和删除算子来降低寻优时间和减少搜索空间，并在此基础上对生成的路径进行平滑处理[4]。最后通过仿真实验来验证该算法的有效性和可行性。

1 改进型遗传算法

标准遗传算法GA包括以下五个元素：GA={Se,Cr,Mu,Ed,fv}，其中Se为选择操作，Cr为交叉操作，Mu为变异操作，Ed为编码、解码操作，fv为适应度评价。

新的遗传算法加入了新的元素：GA={Se,Cr,Mu,Ri,Rd,Rs,Rc,Rb,Rm,Ed,fv}。

适应度表示：

f(i,t)=f(xi(t))表示第i个个体xi(t)的适应度；

fm(t)=max{f(i,t)}表示t时刻的最优适应度；

fm为计算机中存储的录优适应度。

新增元素的含义如下：

插入操作Ri：初始化种群后，通过插入操作生成连续的可行路径。

删除操作Rd：在保证种群连续性的基础上，删除重复冗余的路径。

复原操作Rs：由于交叉和突变操作有一定的随机性，当交叉和突变失败时，恢复到操作之前的种群状态。

重构操作Rc：当交叉和变异操作出现多次失败时，证明初始化生成种群的质量不高，则重新构造质量不高的种群。

录优操作Rb：当交叉和突变操作成功时，利用较优适应度代替存储的原有适应度，保证种群朝着最优解的方向进化。

平滑操作Rm：使最终生成的最优路径变得平滑，路径的转弯角度尽可能小，这样最优路径在船舶实际航行时具有一定的现实意义。

其中，Ri、Rd是为了生成连续的路径，并使路径朝着目标点方向运动；Rs、Rc是为了促进搜索的遍历性，增加算法的搜索范围，尽可能搜索到全局路径；Rb的作用是取代计算机中存储的录优适应度值，即fm:fm(t)→fm；Rm的作用是使生成的最优路径具有现实意义。

2 遗传算法船舶路径规划

这里障碍船的速度位置信息和个数可以由激光雷达和机器视觉确定；在局部的动态路径规划中，假设船舶的当前速度保持不变，而各障碍船也是以当前速度做匀速直线运动，由于在局部路径规划中，控制周期很小，所以在路径规划过程中，可以把障碍船看作匀速直线运动，那么船舶与障碍船的相遇点就能提前确定，并将该点设为障碍点。

所以，文中船舶的路径规划是在一张障碍物分布和海拔高度都已知的一幅二维地图上进行的，在该地图上寻找一条路径最短，同时又能够避开障碍物的一条平滑航线。为了简化讨论，将船舶看做一个无体积的质点来处理，同时障碍物周围扩展船舶的半径加上船舶能够安全航行的最大距离为d。

2.1 路径编码

在遗传算法中，编码是生成初始化群体的基础，编码长度是影响算法收敛速度和搜索时间的重要因素[5-6]，因此文中选择一种简化的编码技术。船舶航线可以看作由起点、终点以及一系列中间点组成的一维路径，编码技术如图1所示。起始点即船舶航行的初始位置为O，目标点是船舶要到达的目的地，路径规划的路线就是在起始点和目标点之间，在约束范围内确定中间点时序的坐标，其结构为：(x0,y0)→(x1,y1)…(xi,yi)→(xn,yn)。其中，(x0,y0)是起点坐标，(xi,yi)(i=1,2,…,n-1)是终点坐标，(xi,yi)(i=1,2,…,n-1)是起点和终点之间的一系列中间点，路径的起点和终点是固定的，只需要对中间点进行编码。在大地坐标系xoy中，路径点坐标是二维的，为了降低编码复杂度，对坐标进行变换，新坐标系为XOY[7]。在新的坐标系中，将起点到终点的连线作为X轴，然后在起点和终点之间把X轴平分为X1,X2,…,Xn-1，则在新的坐标系XOY中，路径点就简化为一维的Y轴编码问题。

图1 编 码

2.2 初始化种群

对遗传算法进行最优航线设计时，首先要初始化种群，初始化种群是在全局范围内随机搜索转向点，随机产生航线路径。其中，该路径包括可行路径和不可行路径，这样增加了最优路径的搜索范围和时间。由于前面改变了路径的编码方式，将xoy坐标映射到XOY上，X轴的路经点已经全部确定，即X1,X2,…,Xn，所以只需在Y轴坐标随机产生路经点即可。另外，环境越复杂，转向点越多，产生的航向越复杂，因此就采用变长的编码技术，编码的长度确定了对初始化种群操作的速度和时间。当编码长度过长时，转向点数目会占用太多的资源，因此要设定一个最大的编码长度Nmax，种群中产生的每个个体最大长度m必须满足：2≤m≤Nmax。

初始化种群步骤如下：

(1)随机生成n条染色体，保证开头和结尾在路径上，障碍物栅格不在规划路径上；

(2)对生成的每条染色体进行插入操作；

(3)对完成插入操作后的染色体进行删除操作；

(4)选择所有生成连续路径的染色体。

2.3 适应度函数

适应度函数是影响算法的收敛性和稳定性的重要因素，适应度函数的选择决定了种群的进化方向和进化效率，所以，适应度函数的选择就显得至关重要。船舶的路径规划就是在起点和终点之间找到一条最短的、安全的路径。评价该路径优劣的标准有多种，其中一条安全无碰撞路径是航线的前提，同时还受船舶自身体积的限制，航线应尽可能短，转角尽可能少，转弯角度也要尽可能小。因此，文中对适应度函数的选择考虑三个因素：路径长度、转向个数和转向角度大小[8-9]。

2.3.1 路径安全性评价

路径的安全性是为了保证船舶航线不与障碍物碰撞，即船舶和障碍物保证在安全距离以外。假设船舶到障碍物的距离为d,船舶航行的安全半径为r，路径安全性的评价函数为：

(1)

其中

(2)

即船舶与障碍物之间的距离大于安全距离。

2.3.2 路径总长度L

路径总长度是船舶从起点到终点的路径长度之和。

(3)

其中，d(pi-1pi)是两转向点pi-1,pi之间的距离，另外也引入了惩罚因子ε，即如果两转向点不相邻则对适应度值进行惩罚，惩罚函数如下:

(4)

其中，c=0表示两转向路点不相邻，c=1表示两转向点相邻，所以评价函数可以表示为：

(5)

2.3.3 路径平滑度

船舶航行的时候转弯会消耗极大的能量，并且在海上以大的拐角转向一般不能实现，因此设计航线时要考虑船舶航线的平滑度，并且拐角要尽可能小[10]。假设最大拐角为α/2,路径平滑度可以用平均拐角M来衡量。

(6)

其中，αi(i=2,3,…,n-1)表示两向量(xi-1,yi-1)和(xi,yi)之间的夹角，如图2所示，α为两航路点之间的夹角，当两相邻航路点之间无拐角时α=0。所以M越小，表示路径的平滑度越好，则被选中的概率越大。

图2 转向角

以上三个因素都会影响生成航线的质量，所以，对三个因素加权求和来确定适应度函数。由于加权系数并不是恒定的，而是随着航海环境的变化不断变化的，这种情况各个系数的加权系数就很难确定，因此要尽量减少适应度函数的项数[11]，又要把各个条件融合进适应度函数，所以选择以下适应度函数：

f=S/(M·L)

(7)

2.4 遗传算子

选择算子：采用轮盘赌法进行选择。即计算每条路径的适应度函数的值fi,fi值越大该路径越接近最优。利用轮盘赌法选择出一定的个体，对于父代的优秀个体可以采用精英保留策略，来增加种群的优越性。

交叉算子：交叉操作的方法包括单点交叉、多点交叉、均匀交叉等，文中选择单点交叉的方法，把选择的染色体序号打乱，使染色体能够随机分配，然后把相邻的两个染色体根据交叉概率进行交叉，交叉的时候选择两条染色体的相同基因。如果只有一个基因相同，直接进行交叉；如果有多个基因相同，随机选择一个基因进行交叉[12]。交叉产生的个体长度不能超过Nmax，不能产生回路，如果不符合要求，重新选择交叉点。

插入算子：插入操作是让生成的初始路径变为连续的路径。如果生成的初始路径是连续路径，则选择一条航线的网络节点，然后把节点周围可行网格点插入航线，比较插入之前和之后适应度函数值的大小，若适应度值变高，则用新生成航线代替插入前的航线，否则取消插入操作。

删除算子：删除操作是在保证路径可行的基础上，检查生成航线是否有重复行驶的路经点，如果存在，则删除相同序号航路点之间的冗余序号[13]，也要把相同节点中的一起去掉，使网格点变少，适应度函数值提高。

平滑算子：平滑操作只对可行航线中有拐角的路径进行操作，如图3所示，a,b,c为航路点，原始航线拐角为β，在执行平滑操作时，选择a,b和b,c航路点的中点a'和c'，连接a'c'，做第一次平滑操作时的航线变为aa'→c'c，可以看出转向角明显变小。同理，做第二次平滑操作的航线变为aa''→b'→c''c，按照此方法循环五次可以得到一条平滑的航线a→b'→c。

图3 平滑操作

2.5 终止条件

终止条件的设定遵循以下规则：

(1)强制终止。即当进化代数达到设定的进化代数T时，迭代操作被强制终止。

(2)条件终止。即得到的最优航线的适应度函数的值趋于恒定值时，迭代操作被终止[14-15]。

2.6 算法流程

(1)初始化种群，在已知环境地图上选取N×N个网格点，路径均经过网格点的中心，障碍物网格点除外。

(2)检查生成路径是否连续，如果不连续执行插入使路径连续，在保证路径连续的基础上执行删除操作，删除冗余的路经点。

(3)采用轮盘赌法执行选择操作，计算种群中个体适应度。

(4)检查是否满足终止条件，如果满足执行步骤8，否则执行步骤5。

(5)进行交叉、变异操作，检查交叉是否成功，如果成功进行录优操作，然后执行步骤4。

(6)检查是否达到复原操作的最大次数，如果是执行步骤5，否则执行步骤7。

(7)进行重构操作，跳转到步骤2。

(8)进行平滑操作，输出最优路径。

算法流程如图4所示。

3 仿真结果

船舶航行的环境信息包括在航行区域内的各种障碍物信息(如岛屿，暗礁，禁航区域，沉船等)和海图获得的水的深浅信息。在航行区域内把障碍物信息和航行的浅水区分别用不同规则的多边形表示。为了验证改进算法的可行性和有效性，在Visual Studio C++环境下对算法进行仿真实验。遗传参数设置为：种群大小100，交叉概率和变异概率分别为0.7和0.01。

图4 算法流程

根据不同的海域，选取两种航海环境，分别对传统遗传算法和改进后的遗传算法进行仿真，结果如图5和图6所示。

图5 环境a仿真结果

图6 环境b仿真结果

可以看出，在不同的航海环境中，改进的遗传算法均能找到可行的最优平滑路径。对两种算法进行大量的实验，运行结果如表1、表2所示。从两种环境的运行结果可以看出，改进后遗传算法，无论在路径搜索时间还是路径长度都优于传统遗传算法。

表1 环境a运行结果

表2 环境b运行结果

4 结束语

文中对遗传算法进行扩展和改进，增加了复原操作、重构操作、录优操作，以避免种群陷入局部最优解，使算法尽早收敛于全局最优解。引入插入算子、删除算子和平滑算子，提高种群的进化效率，增加算法的现实意义。将改进后的算法应用于船舶的路径规划，仿真实验证明，改进遗传算法在不同的环境中都能快速收敛于最优解，并且生成路径的标准明显优于传统遗传算法。