基于遗传算法的开敞水域帆船航线规划

杜胜， 刘轶华， 陈茜， 闫化然

(上海海事大学商船学院， 上海 201306)

0 引 言

随着经济发展和人民生活水平的提高，帆船运动在中国逐步发展起来，越来越多的人可以接触和体验到帆船运动。然而，驾驶帆船的技能和经验通常要经过长时间的训练才能获得，这阻碍了帆船运动在中国的普及。为促进帆船运动的推广，让更多的人体验帆船运动的乐趣，有必要降低帆船运动的入门门槛，减少对经验的依赖。在确保安全的前提下，实现帆船在开敞水域的航线自动规划，不仅能使帆船运动员达到良好的竞技状态，取得较好的训练效果，还能培养和巩固帆船爱好者的兴趣。

帆船的动力来自于风，而海面的风场是变化且不均匀的，因此帆船的航线规划非常复杂。邢惠丽等[1-2]提出了基于分区段优化和进化规划的帆船航行路径优化方法，以及利用全局搜索优化的进化规划方法；葛艳等[3-4]提出一种基于模糊综合评价和动态规划理论的帆船直航训练最优路径动态规划方法，利用动态规划原理分阶段进行航向决策；FOSSEN[5]和FLAY等[6]通过船体和帆的流体动力学分析计算帆船的航行速度，但由于帆船在海面航行时受到多种因素的影响，用流体动力学分析的方法所计算出的帆船航速不太准确。以往关于帆船航线规划的研究主要集中在近岸短距离绕标竞赛的情况下，对开敞水域帆船航线规划的研究较少。本文基于相关领域的研究成果进一步研究开敞水域的帆船航线规划。帆船航线规划本质上是一种路径规划，在问题规模较小时用分支定界法、动态规划法[7]等能得到最优解，在问题规模较大时可以使用进化算法[8-9]进行求解。遗传算法是进化算法的一种经典方法，来源于达尔文的进化论、魏茨曼的物种选择学说和孟德尔的群体遗传学说，是模拟自然界遗传和进化[10]并引用随机统计理论而形成的一种迭代式算法，具有坚实的生物学基础[11]。该算法是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，不受问题性质的限制，可有效地处理传统优化算法难以解决的问题[12-13]。因此，本文采用遗传算法进行开敞水域的帆船航线规划。

1 模型建立

1.1 基本假设

受海浪、海风及海流等环境因素的影响，海上航行环境具有模糊性和不定性的特点[1-2]。考虑到帆船运动的特点，同时为了提高求解效率，本模型作以下假设：

(1)浪和流对帆船的影响较小，可以忽略不计；(2)无航道宽度、航行水域范围和碍航物的限制；(3)帆船严格按照既定的航向航行，不会偏航；(4)不考虑运动员的操帆技能和团队协作水平；(5)不考虑后退的航行路径。

1.2 坐标系

离岸帆船驾驶通常是通过卫星导航用大地坐标进行定位的，同时需要借助于纸质海图或电子海图。为方便计算，本文基于海图建立平面直角坐标系，将大地坐标转换为平面直角坐标。

因为航海用海图比例尺较大，坐标转换时纬度渐长率可以忽略不计，所以大地坐标转化为平面直角坐标的公式为

(a,b)=f(α,β)

(1)

式中:(α,β)为海图中某点的大地坐标，(a,b)为其对应的平面直角坐标；f表示(a,b)与(α,β)之间的映射关系。式(1)可以表示为

(2)

即海图图幅范围内任意两点的经度之差与纬度之差的比值与这两点在平面直角坐标系中的纵坐标之差与横坐标之差的比值相等。式(2)中，(α0,β0)为海图中任意一点的大地坐标，(a0,b0)为其对应的平面直角坐标。

1.3 风场数字化

在海上通常不能精确测量每个位置的风矢量数据，只能获得气象船或气象浮标等(统称气象站)站点的风矢量数据。表1列有与航线规划有关的关键位置点的地理坐标及其相应的平面直角坐标，以及气象站的风矢量数据。

表1 与航线规划有关的关键位置点初始数据

海面上一般没有遮蔽物，风场变化较为均匀，因此可以使用插值的方法得到整个风场的风矢量数据。通过查询风场的风矢量数据可以获得海图图幅范围内任意一点的风矢量数据。

插值的方法多种多样，本文采用反距离加权插值法。找到距离待插值点最近的气象站，根据区域大小对这些气象站数据进行插值[14]，公式如下：

式中：zj为平面直角坐标(xj,yj)处的风速值；dj是点(x,y)与点(xj,yj)之间的水平距离，j=1,2，…，k；p是一个大于0的常数，称为加权幂指数，本文中取p=1。可以使用Surfer、ArcGIS等辅助软件完成该插值过程。

记插值完成后风场的风速值构成矩阵为M。局部风速值及帆船在风场中的航线见图1。图1中：数字代表邻近位置点的风速值；曲线为风速的等值线；*代表帆船在风场中的转向点位置，转向点之间的有向线段代表航线。

图1 风场局部风速值及帆船在风场中的航线示意图

1.4 目标函数

以整个航程的航行时间Ti为目标函数，建立以帆船在规划航线上用时最短为目标的优化模型，即

(5)

式中：tj表示帆船从前一转向点A航行到后一转向点B所用的时间。由于点A与B之间的风场是变化且不均匀的，所以很难直接求出帆船在这段航线

上用的时间。本文采用积分的思想来进行计算：假定在航段l0内的风场是均匀的，用l0起点位置处帆船的航速代替帆船在该航段内的平均船速，通过调用风速值矩阵M获得该位置的风向和风速；把从点A到B的航向θ1代入式(7)和(8)计算出该船速v；把每个航段l0上所用的时间累积起来近似为tj。本文取l0=0.5 n mile，则从点A到B的航行时间公式[10]如下：

(6)

式中：n为两个转向点之间的距离与l0的比值；vi=fvθ(M(aij,bij))，(aij,bij)为风场内任意一点的平面直角坐标，M(aij,bij)为该点的风矢量数据，fvθ表示视风速的计算。

式中：v和θ分别表示视风速的大小和方向；v1和θ1分别表示船速大小和航行方向；v2和θ2分别表示真风速大小和方向。

图2 真风速、船速和视风速的矢量关系

2 算 法

2.1 初始解生成

2.2 初始解优化

由于随机生成的转向点是杂乱的(图3a)，若将这些转向点从起点随意连接到终点，则路线的有效性会很低(图3b)。为获得初始可行解，在随机生成初始路线后增加转向点排序操作，提高搜寻效率，使发现最优解的可能性尽可能提高，有效避免帆船航线规划问题的复杂性所带来的搜寻时间过长的问题。具体做法是将从起点到转向点的向量在从起点到终点的向量上的投影按从小到大的顺序排列(图3c)。具体计算公式如下：

A=(ad-as,bd-bs)

(9)

(10)

bj=|A0|·|Bj|cosθj

(11)

式中：A表示从起点到终点的向量；A0表示从起点到终点的单位向量；Bj表示从起点到第j个转向点的向量；θj表示A与Bj的夹角；bj表示Bj在A上的投影大小。

a)随机生成的转向点位置b)转向点排序前的航线

c)从起点到各转向点的向量d)转向点排序后的航线

图3算法随机生成的转向点排序前后航线对比

当初始可行解生成之后，用遗传算法对其进行优化，实现帆船航线的寻优。

2.3 染色体编码与解码

帆船航线规划包括规划每个转向点的位置，以及它们的连接顺序。染色体编码需要包含转向点顺序的信息。由于本文所使用海图的横向幅值和纵向幅值均不会超过1 500 pixel，因此转向点坐标值不超过1 500。由于210<1 500<211，编码采用11位二进制数即可。

(12)

2.4 评价函数

(13)

图4编码前后的染色体

2.5 选择、交叉和变异操作

2.6 终止规则

一般情况下，可以选择最大迭代次数作为进化规划算法的终止条件。如果最大迭代次数比较大，则相应的计算时间比较长；如果设置的最大迭代次数较小则会导致种群过早成熟，无法保证得到全局最优解。一般可以通过试探的方法找到比较合适的最大迭代次数，从而减少计算时间。最后，将生成的转向点连接成线，也就生成了帆船的最优航线。

图5 染色体单点交叉示意图

图6 染色体变异前后示意图

3 模型验证

3.1 案例参数

某型28英尺(1英尺=0.304 8 m)帆船[15]是一款易于操控的龙骨型赛船，在近岸航行中性能优异，是行业内知名度较高的一种船型，因此选择该类型帆船作为算法案例更具有代表性。通过实船测试获得该帆船的航速表。因为表中数据较多，所以将帆船航速以航速图的形式展现出来，见图7。假定仿真过程中帆船能时刻保持在帆船航速表中所记录的状态。

图7 不同风速条件下帆船航速随迎风角的变化

中国东海某海域(27°10′～29°10′N，122°20′～125°20′E)较为开敞，水深条件好，没有岛屿和其他碍航物，因此选择该海域作为仿真海域。

获取关键位置点的坐标以及某日该海域的风场资料，经过数字化处理后的初始数据见表2。

表2 某海域关键位置点初始数据

经过计算，海图图幅范围为1 000 pixel×1 356 pixel。采用插值法计算出整个海域的风矢量数据，生成风场矩阵M，见图8。图8中：箭头方向表示风向；箭头的长短和灰度表示风力大小，右侧是箭头灰度的风力比色卡。

图8风场示意图

3.2 仿真结果及分析

由于本次航行直线距离为149.6 n mile，航程相对较短，设置转向点数目(基因数目)C为15，种群数目(染色体数目)N为70，最大迭代次数为400。

运行程序后首先生成70个初始解，见图9a。显然，未经排序的初始种群合理性很低。从排序后的种群(图9b)可以看出，初始种群的合理性大大提高。

经过选择、交叉、变异等操作和迭代400次之后，得到如图9c所示的种群适应度。从图9c可以看出，迭代约350次时，种群适应度已经逐渐稳定，说明此时种群已经收敛。

4 结束语

仿真结果表明，基于遗传算法的开敞水域帆船航线规划是可行的：既能根据气象资料快速、准确地生成帆船的航线，提高航线选择的效率，又能减少帆船运动对航行经验的过度依赖，降低帆船运动的入门门槛，有利于帆船运动的普及。本文的算法仅考虑了对帆船运动影响最大的因素——风的影响，没有考虑其他次要因素的影响，存在一定的局限性，因此该算法需要通过实践检验后再进行修正和完善。

a)未经排序的初始种群

b)排序后的初始种群

c)种群适应度变化曲线

d)适应度最大的5条帆船航线图9 航线规划模拟仿真过程及结果

参考文献：

[1] 邢惠丽, 胡西厚, 葛艳. 帆船比赛航行路径优化与仿真[J]. 计算机工程与应用, 2010, 46(27): 245-248. DOI: 10.3778/j.issn.1002-8331.2010.27.069.

[2] 邢惠丽, 胡西厚, 葛艳. 基于分区段优化方法的帆船绕标航行路径动态仿真[J]. 青岛大学学报(工程技术版), 2009, 24(4): 58-61. DOI: 10.13306/j.1006-9798.2009.04.008.

[3] 葛艳, 孟庆春, 魏振钢, 等. 帆船直线航行比赛最优路径动态规划方法研究[J]. 控制与决策, 2005, 20(12): 1360-1364. DOI: 10.13195/j.cd.2005.12.42.gey.008.

[4] 葛艳, 孟庆春, 李纪平, 等. 基于模糊综合评价的帆船行驶最优路径规划方法[J]. 中国航海, 2005(1): 63-67.

[5] FOSSEN T I. Handbook of marine craft hydrodynamics and motion control[M]. Hoboken: John Wiley & Sons, 2011: 15-80. DOI: 10.1002/9781119994138.

[6] FLAY R G J, VULETICH I J. Development of a wind tunnel test facility for yacht aerodynamic studies[J]. Journal of Wind Engineering & Industrial Aerodynamics, 1995, 58(3): 231-258.

[7] LAI Xuejia, MASSEY J L, MURPHY S. Markov ciphers and differential cryptanalysis[M]//Advances in Cryptology-EUROCRYPT 1991. Heidelberg: Springer, 1991:17-38.

[8] 朱霞, 陈仁文, 徐栋霞, 等. 基于改进粒子群的焊点检测路径规划方法[J]. 仪器仪表学报, 2014, 35(11): 2484-2493.

[9] VELAGIC J, VUKIC Z, OMERDIC E. Adaptive fuzzy ship autopilot for track-keeping[J]. Control Engineering Practice, 2003, 11(4): 443. DOI: 10.1016/S0967-0661(02)00009-6.

[10] 《现代数学手册》编纂委员会. 现代数学手册(计算机数学卷)[M]. 武汉: 华中科技大学出版社, 2001: 679-686.

[11] 周昕, 凌兴宏. 遗传算法理论及技术研究综述[J]. 计算机与信息技术, 2010(4): 37-39, 43.

[12] BUCKLAND M. 游戏编程中的人工智能技术[M]. 吴祖曾, 沙鹰, 译. 北京: 清华大学出版社, 2006: 62-81.

[13] 王倩, 许劲松, 徐建云. 无人帆船循迹航行的控制研究[J]. 船舶工程, 2015, 37(9): 63-67.

[14] HENDERSON N, PENA L. The inverse distance weighted interpolation applied to a particular form of the path tubes method: theory and computation for advection in incompressible flow[J].Applied Mathematics and Computation, 2017, 304: 114-135.

[15] 上海珐伊玻璃钢船艇有限公司. 单体帆船(FAREAST 28R): 303958507S[P]. 2016-12-07.