基于遗传算法的渡船横渡航法寻优模型

孙志宏， 索永峰， 杨神化， 刘武艺

(集美大学 航海学院， 福建 厦门 361021)

渡船既是长江两岸车辆来往、运输物资重要而便捷的交通工具，也是陆上公路运输的水上连接线。尽管长江上已呈现增架桥梁的局面，但渡船在长江干线水域的重要地位依然不能完全取代。[1]鉴于具有类似渡船的复杂内河水域交通流密集，船舶位置灵活多变，给渡船横渡目标水域带来很大的碰撞风险，在很大程度上增加了该水域的交通压力。目前，渡船横渡主要依靠驾驶员根据实时交通状况做出临时反应，对驾驶员的要求较高。本文重点研究复杂水域的渡船横渡路径规划问题，旨在运用遗传算法(Genetic Algorithm，GA)对交通状况进行整体把握，降低航行风险，提前规划出最优路径。目前对航路寻优的研究主要集中在无人机、机器人等领域，水路交通路径优化研究相对较少，主要从路径优化和自动避碰两个方面开展研究。目前，对避碰决策的研究主要有：基于模糊数学的避碰决策研究[2-3]；基于专家系统的避碰决策研究[4-6]；基于动态规划的避碰决策研究。[7]在路径优化方面，马全党等[8]提出多目标规划模型，在此基础上利用GA求解最优路径，采用多目标规划算法操作，综合考虑航路安全性、船舶可操纵性和操船者的主观意识等因素，对油田区水域航路规划有较强的适用性，但因没考虑船舶尺度的问题，该研究不适用于状况复杂的内河水域。田鹤等[9]采用改进的GA对舰艇航线进行规划，利用蚁群搜索策略生成初始种群，其中适应度函数编写时主要从威胁代价和航程代价方面进行构建，但其针对舰艇的航路规划展开，舰艇的操纵性能和对危险的定义有所不同。倪生科等[10]针对在不同会遇态势下的船舶避碰路径规划问题，构建一种基于GA和非线性规划理论的避碰路径规划模型,该模型加入非线性规划理论，以解决GA局部搜索能力较弱的问题，但其研究针对的是单一目标船舶的情况，更适用于开阔水域的船舶会遇。谢玉龙等[11]针对传统GA解决船舶路径规划问题的不足，提出一种改进的GA,在传统GA的基础上增加复原操作、重构操作和录优操作等3种新的遗传；复原和重构操作能避免算法收敛于局部最优解，使算法尽早收敛于全局最优解，录优操作保证种群朝着最优解方向进化。另外，设计插入算子、删除算子和平滑算子来提高种群进化效率和生成路径的现实意义,但其在环境仿真方面仅考虑通航时的碍航物，如岛屿、暗礁等静止物标，未加入目标船舶信息。本文首先建立安全评价模型作为适应度函数的阈值，然后建立GA模型作为安全评价模型的下级指标，在满足阈值的基础上，综合考虑经济性、船舶操纵性和转向个数得出适应值，再进行遗传操作和迭代计算，最终所得适应度函数最优路径即为最终规划所得路径。

1 安全评价模型

1.1 模型简化

交通状况模拟根据镇扬渡船某一时刻的真实交通状况生成交通流，为简化研究，将其他碍航船看作在规定区域内航向、航速固定，根据该船转向点设置的时间间隔进行实时更新，其中碍航船选用镇扬航段两岸港口以直线相连后上下游的来往船舶。将目标水域看作规则区域，根据镇扬所得原始数据，经过坐标转化得到模拟交通流初始的船舶位置、航向和航速。确定安全性指标主要参考本船和他船的位置、航速、航向和船舶尺度,其中船舶数据均借助镇扬段船舶自动识别系统(Automatic Identification System, AIS)和岸基雷达获得。

1.2 航路规划安全性指标

(1)

dCPA和tCPA的值就是对相应的距离函数对时间t求导得到的最小值点。[12]

(2)

具体可表述为

(3)

(4)

对于任意路线，该路线转向点处船位、船速、航向、船长和船宽，以及模拟交通流中碍航船船位、船速、航向、船长和船宽均已知，可求出任意路径每个转向点与每条碍航船的dCPA和tCPAi值。

适应度函数中的dCPA值不能直接采用上述方法求取，在内河流域，渡船频繁变换方向，无法得知本船舶是否到达最短会遇的节点。运用一个转向点到下一转向点的时间ti与tCPAi比较的方式来确定是否到达最短会遇节点。若已知任意路径上各转向点的位置坐标，同时认为一转向点到下一转向点的速度恒定，就可利用相应公式计算出一转向点到下一转向点的时间ti。若ti

(5)

(6)

得到实际最近会遇距离为

(7)

实际最近会遇距离见图1。

为判别船舶是否有碰撞风险，此处引入安全会遇距离(Safe Distance of Approach,SDAmin),SDAmin是最近安全会遇距离最小值[13-14]，SDAmin也可称为船舶临界碰撞会遇距离，对于该参数的求取，在考虑本船和目标船尺度与相对航向的基础上，将船舶会遇局面分为本船过目标船艏部、本船过目标船艉部和本船与目标船接近相向或同向等3种情况[15]进行求解。

图1 最近会遇距离

在计算该指标时为保证船舶通航安全，有

(8)

仿真试验中添加判断:若真实最小会遇距离

设θ为锐角，本船过目标船艏部时，分析本船与目标船航向的夹角α满足

SDAmin=

(9)

式(9)中：Lt为目标船船长；Lo为本船船长;Bt为目标船船宽;Bo为本船船宽;α为本船与目标船航向夹角;P为目标船全球定位系统(Global Positioning System, GPS)的定位精度,m。

2 基于GA内河横渡模型

2.1 产生初始种群

建立模型时，对河流宽度和港口宽度进行限定，河流宽度为WR,港口宽度为WP，生成一定规模的种群，每个种群都有固定转向点，但鉴于最终目的为实现横渡河流，另加艏艉点，艏艉点在两岸且位于港口范围内。转向点设置为三维向量的形式为

M=(xij,yij,vij)

(10)

式(10)中：xij和yij为第i条路径，第个转向点的位置;vij为在此点的速度。以任意一边港口的中点为O′点，并以该边的河岸做x轴，以过O′点垂直x轴并指向另一河岸为y轴(见图2)。

图2 转向点向量示意

(11)

2.2 适应度函数

适应度函数对于GA程序而言至关重要，本文在构建适应度函数时加入时间指标、转向角和转向点个数。适应度函数为

fit=αTime+βGB+γAC

(12)

式(12)中：fit为个体适应值；Time为时间指标；GB为转向角互补角；nAC为转向点个数；α为时间指标权重；β为转向角指标权重；γ为转向点数权重。

对种群初始化时生成种群，计算安全性指标，执行遗传操作。航行路径经济最优，可等价为时间最短，时间指标求取方式为

(13)

式(13)中：nvars为第j条路径转向点数。

转向角是船舶路径规划中的重要指标，希望船舶在航行中没有大幅度转向，从而保证其安全航行。本文在仿真实现时采用常规的观点，认为：转向角越小，船舶越稳定、安全；限定转向角越小，航线越优。每条路径都预设转向点，每个转向点都对应一个转向角，其转向角的刻画利用与其互补的角A(见图3)。

图3中：r为航线的转向角，A为航路夹角，A越大，则r越小。此外，用cosA描述A的大小，在(0,π)内单调递减，因此在设计航路时期望cosA越小，路径越优。

图3 航路夹角示意

(14)

(15)

(16)

因此，综合时间指标、转向角、转向点个数最优路径为

(17)

式(17)中：各指标进行算术相加均经过z-score归一化。

(18)

2.3 遗传操作

由初始化函数生成渡船航行路径，经求适应度函数求取每条路径的适应值，借助每条路径相应参数和求得的每条路径适应值进行相应的遗传操作。

2.3.1选择算子

选择操作经对比轮盘赌等常用选择算子，最终采用两人竞赛选择方法，采用该方法时，每代最优个体适应度曲线波动范围更广，收敛速度更快。两人竞赛选择方法，即每次随机选出两个个体，选出适应值较大的个体作为新个体进行保留，直到填满初始种群数量为止。

2.3.2交叉算子

交叉操作采用相似交叉的方式。两个父代航线是基于适应度函数随机选择的，交叉点位置也是通过随机产生的方法决定的，采取以节点为单位的方式进行交叉操作。采用顺序交叉方式产生新个体，设个体交叉概率为Pc，最大种群规模为Psize，则进行交叉的个体数为

Ncross=Psize×Pc

(19)

2.3.3变异算子

为增加种群的多样性和保证较好的收敛性，在执行变异操作时，以小概率进行变异操作，变异概率为Pm，根据群体规模和变异概率计算出变异个体个数为

NVar=Psize×Pm

(20)

2.3.4精华模型

为避免子代退化，改善种群的多样性，引进精华模型和精英操作。引入精华模型对之前精英操作所得最优个体进行比较更新，确保最优个体能一直保留。

式(17)和式(18)中：Pc和Pm的取值通过其对每代最优个体适应值的影响进行验证，验证结果见图4。由图4可知：当Pc取值为0.9、Pm取值为0.1时，每代最优个体的适应值曲线波动范围更广，收敛速度更快。

a) 交叉算子

b) 变异算子

3 计算机仿真实现

利用GA进行渡船横渡路径寻优仿真，其实现过程选取镇扬渡船航段两岸渡口的连线作为参照，通过模型简化转化为规则图形区域，然后通过等比放缩转化为规则简单图形区域。2018年12月10日09：00时镇扬段实时交通状况见表1，其中，以渡口两岸的连线为参照，沿上下游分别垂直于内河走向做连线的平行线，以截取距离渡口500 m范围内的船舶。船长和船宽用于计算SDAmin，渡船长76 m,宽14 m。

转向点个数根据实际需要和当时的交通状况设置，在进行仿真试验时，通过咨询镇扬渡船项目专家，认为该航段转向点个数应在1～5个，超过5个的路径显然是不合理的。借助适应度函数对初始路径进行筛选，将各指标数值经标准化之后加入权重，其中α、β和γ通过专家调研法取值分别为0.5、0.4和0.1，迭代所得最优路径见图5。

表1 船舶数据

图5 仿真实现最优路径

最终所得最优路径为有3个转向点的路径，其转向位置如图5所示：(x,y)为转向点处的位置；v为到达下一转向点应采取的速度，箭头为试验时该处的交通流的初始状态；(x,y)、v和c分别为其他船舶位置、航速、航向，在仿真过程，该交通流会随转向点更新船位。仿真验证导出每个转向时间节点处其他碍航船更新的船位、航速和航向，将其与本船真实dCPAmin和SDAmin比较，其中dCPAmin=194.4,SDAmin=79.9。因此，所有真实dCPA满足

(22)

式(21)中：n为碍航船的数量，证明规划所得路径能保证航行的安全性，对于其他指标，由该航线船长对路径转向位置和采取的航速进行分析，认为路径相对较优，可用于实际航行。

4 结束语

基于遗传算法建立渡船横渡航线规划模型，结合渡船横渡内河水域的实际需要，建立将dCPA加入船舶尺度中来建立安全评价指标的模式。通过仿真可知：构建的航法模型规划所得路径满足船舶航行安全性的要求；适应度函数兼顾经济性、转向角和转向角个数，综合所得路径航行时间较短，航线相对平滑，转向次数尽可能少，符合实际驾驶要求。因此，构建的渡船横渡航法模型对实际渡船横渡航线规划有较强的指导价值。