基于改进遗传算法的岛礁区航路规划模型

高邈+史国友+李伟峰+王玉闯

摘要：为解决船舶穿过岛礁区时危险度大、航行难、航路规划复杂等问题，提出应用实数路径点编码配合采取精英保留策略的遗传算法。考虑船舶的转向困难性、航程、人为指定经过路径点以及船舶安全性，建立适应度函数评价模型。在电子海图平台上提取障碍物特征多边形顶点坐标，规划出最佳航路。该算法能解决多约束条件下的多目标优化问题。对舟山岛礁区进行实例验证。结果表明，改进后的遗传算法能够解决岛礁区的复杂航路规划问题，且实现简单，收敛速度较快，也不易陷入局部极小值。随着自动控制技术的不断发展，可为船舶在岛礁区的自主航行提供理论支持。

关键词：

遗传算法； 岛礁区； 航路规划； 精英保留

中图分类号： U692.31

文献标志码： A

Shipping route planning model based on improved genetic algorithm

in island and reef areas

GAO Miao， SHI Guoyou， LI Weifeng， WANG Yuchuang

（

a. Navigation College； b. Key Laboratory of Navigation Safety Guarantee， Dalian Maritime

University， Dalian 116026， Liaoning， China）

Abstract：

In order to solve the problems of high risk， difficult navigation and complicated route planning for ships through the island and reef areas， a genetic algorithm is proposed using the real path point coding and the elite reservation strategy. Considering the ship steering difficulty， sailing range， designated path points and ship safety， the fitness function evaluation model is established. Based on the electronic chart system， vertex coordinates of characteristic polygons of obstacles are extracted， and the optimal path is planned. The algorithm can solve the multiobjective optimization issues under multiconstraints. The Zhoushan island and reef area are taken for example. The results show that， the improved genetic algorithm is feasible for the complicated route planning problem of island and reef areas， is of easy implementation and faster convergence， and is not easy to be lost into the local minimum. With the development of automatic control technology， it can provide theoretical support for the autonomous navigation of ships through the island and reef areas.

Key words：

genetic algorithm； island and reef area； shipping route planning； elite reservation

0引言

随着全球贸易的发展，水路运输成为大宗货物运输的主要方式，港口规划建设者考虑到保护环境、节约运输成本以及容纳更多船舶等要求，将很多港口的建设地点逐步向海上延伸，以岛礁区为基础平台建设多个小型港口。[1]以往船舶经过岛礁区时单凭船长经验，手动进行航路规划，而如今船舶在岛礁区航行频率增加，对航海人员保障航行安全是一个巨大的挑战。

有关航路规划的研究主要集中在机器人、无人机以及导弹制导领域。孙树栋等[2]运用遗传算法解决机器人在离散空间的路径寻优问题，但对环境确定性的要求很高，必须将大量的有关联的障碍物全部收纳，但障碍物使用的效率却很低。SUGIHARA等[3]使用二进制编码，统一个体长度，通过随机产生障碍物位置和数目的方式初始化寻优问题，但使用格栅化处理必须把握好规划精度。周明等[45]将遗传算法与模拟退火算法结合在一起提出基于遗传算法的机器人路径规划方法，先采用视觉法产生初始可航路径，再使用遗传算法进一步优化调整路径，但在环境复杂、障碍物数目较多的情况下，建立链接图很困难。安柏义等[6]使用动态规划法对无人机进行航路规划，但其对战场上环境的处理过于简单，因此限制了很多实际上的可行路线。穆晓敏等[7]运用人工势场的方法对无人机航路进行规划，但是收敛速度随着规划空间复杂度的增加而变慢，并且对障碍物的形状要求很高。

有关船舶的航路规划尤其是在特殊的限制性水域进行航路规划的研究相对较少，尚未形成体系，还不够成熟。汪柱等[8]提出基于航路二叉树的航线智能生成算法，弥补了以往航路生成中的不足，提高了航路规划的质量，但其对障碍物二叉树绕行方案的处理并不完善，計算效率过低。王莹等[9]提出了基于改进蚁群算法的航路规划方法，改进了人工绘制航线费时费力、不够精确以及应用范围受限等问题，但蚁群算法的计算成本太高，需要大量数据支持，还容易发生停滞现象。邹春明等[10]提出了基于惩罚粒子群优化（Particle Swarm Optimization， PSO）的群桥水域的多约束航路规划，但其对障碍物的抽象化较为简单，全部转化成纵向间隔相等的圆柱体，简单地将船舶的航路规划问题转换成求多维函数极值问题，但群桥障碍物的特点与航路平滑要求的冲突很容易使求解陷入局部极小值或寻优停滞。endprint

算法选择是航路规划的核心问题，所选用的遗传算法是一种启发式的搜索寻优方法，具有良好的全局寻优能力和多目标并行优化特性。多数优化算法都是单点搜索算法，很容易陷入局部最优解，而遗传算法是一种多点搜索算法，更有可能搜索到全局最优解。遗传算法在整体搜索上不同于变形的贪婪算法，因此在进行优化计算搜索时采用不依赖于梯度问题的振荡搜索[11]。然而，传统的遗传算法存在早熟以及局部搜寻能力差等问题。针对这些问题，采用一种基于精英保留策略的遗传算法，扩大寻优种群数量，在初始化时随机生成路径解决过早成熟的问题，针对交叉算子对单一基因路径同样进行评价，保留优良基因组，缩短寻优时间，对变异算子进行改进，同时引入删除和插入算子，提高局部搜索能力。

1问题描述

我国的岛礁区大致分为两类[12]，一类是由珊瑚虫蜕壳后的遗体所构成的（例如南海岛礁区），另一类是由土石质构成的（例如舟山群岛）。本文以舟山群岛为例，其特点为：（1）航道多，可选择性大，超出人工规划最优能力；（2）航道狭窄、曲折，障碍物多，渔船密度大，需在适应度函数中加入转向角因素；（3）障碍物距离较近，容易产生岸推、岸吸的问题[13]，需在适应度函数中加入安全距离因素；

（4）夜间对船员视觉的影响较大，容易造成船员心理上的恐惧感。

船舶航路规划指在特定的条件下，找到一条从初始点A到终点B的最省时、耗油量最少的安全路径。岛礁区水域的复杂性

对船舶驾驶员的航路规划以及操船能力都是不小的考验[14]。在岛礁区进行航路规划是针对多物标、多障碍物的一个非线性优化问题，要同时处理多个优化目标，在确保航行安全的前提下，追求航程最短，还须考虑船舶实际情况、船舶操纵性能、值班驾驶员航海习惯等。因此，使用遗传算法非常适合解决这类问题。

2数据准备及适应度函数评价模型

2.1数据准备

2.1.1障碍物数据准备

为使用遗传算法计算岛礁区的最优路径，首先需要将航行所涉及的所有障碍物和船舶不可航的浅水区域抽象成多边形，并精确地提取出多边形的顶点坐标。本文基于S57电子海图平台输出多边形的顶点坐标。为便于进行显示和标记，将S57数据通过墨卡托投影变换公式转换成平面直角坐标：

X=Klntanπ2+B21-esinB1+esinBe/2

（1）

Y=K（L-L0）

（2）

K=NB0cosB0

（3）

K=a′2b′1+e2cos2B0cosB0

（4）

式中：X为平面横坐标；Y为平面纵坐标；B0为赤道纬度；L0为本初子午线坐标；B为空间纬度坐标；L为空间经度坐标；a′为地球长半轴；b′为地球短半轴；e为地球第一偏心率；NB0为赤道卯酉圈半径。

基于S57电子海图平台，以舟山群岛中的小五奎山作为研究对象，其被抽象化后的特征多边形顶点见图1。

图1

小五奎山特征多边形顶点

2.1.2安全距离确定

在航路规划时，航路与障碍物之间需保持最小安全距离。为确保

最优解是相对路径最短的，规定一个最小安全距离R，使障碍物顶点到规划路径的最短距离大于等于R。图2为下横梁岛最小安全距离R的确定方式。根据船员正常的航海习惯设定R。一般，在能见度好的情况下，船舶在礁盘的上风方向2～3 n mile处通过[15]。如果船舶在比較狭窄的水域航行，则尽量把定位点设置在水深点处，距离礁盘的最小安全距离不能小于1.5倍船长。

2.2适应度函数评价模型

2.2.1船舶操纵能力

考虑到利用遗传算法寻优所找出来的路径有可能在转角处超出船舶的操纵能力，不符合实际的操船避让情况，因此在对路径进行适应度计算时需加入转向角这一评价指标。为防止因转向过大而缩短舵机使用寿命，应避免‘S弯转向，减小船舶在岛礁区航行的操纵难度，将转向角控制在40°以内[1617]，并且鼓励多点逐步转向，避

免大幅度、大角度、单一位置转向。假定所规划的航路存在n个航路点，除去固定设定的初始点和终点，中间包含n-2个航路点，因此就会产生n-2个转向点。如图3所示，根据所得的3个连续航路点坐标，通过式（5）～（7）计算两两之间的距离a，b，c，再求解夹角A。

a=（xi+1-xi-1）2+（yi+1-yi-1）2

（5）

b=（xi+1-xi）2+（yi+1-yi）2

（6）

c=（xi-xi-1）2+（yi-yi-1）2

（7）

sin A=absin B

（8）

夹角A越接近180°，船舶所需要的转向角θi越小。当正弦函数分布在90°～180°之间时，正弦函数值与角度之间呈反比关系，因此利用正弦函数的倒数作为适应度函数来代表船舶的转向角：

F1=n-2k=21sin Ak

（9）

2.2.2值班驾驶员主观意愿

在航行中为满足值班驾驶员的各种意愿和要求，可能需要使航路经过某几个关键的点，从而可能导致航路总里程增加，因此在航路设定时，可依照驾驶员的意向加入必经点，并且提高其权值。假定选定的关键点为

P14，如果航路经过P14，则T（P14）=1，否则为0。式（10）表示航路是否经过值班驾驶员所设定的路径点，如果全部符合则函数值为1，否则为0。

F2=T（Pi）T（Pk）L

（10）

2.2.3航程计算

航程是寻优的关键性指标，一般情况下值班驾驶员当然希望航程越短越好，同时尽量多经过标注点使航路规划时依据点更多，因此利用式（11）将经过的路径点个数与航路总长度的比作为适应度函数进行计算。然而，利用遗传算法在输入数据后进行实际计算时，仅仅是将障碍物抽象成多边形进行计算，各障碍物顶点之间还存在着是否互相连通的问题。有可能计算出的航程非常短，但进行实际验证时会发现路径穿越障碍物的情况。因此，在对航程进行加权计算时引入邻接矩阵。用式（12）进行航程计算时引入邻接判定，如果两节点邻接则=1，否则=10（这使计算出的这条航路的适应度值较小，从而不采纳这条航路）。endprint

F3=nn-1i=1Di

（11）

Di=φ（xi-xi-1）2+（yi-yi-1）2

（12）

3岛礁区航路规划遗传算法编写

3.1实数路径点编码

根据岛礁区障碍物所有顶点坐标的个数与人为选定的必经点的个数之和确定航路规划的最大值，即航路的容量上限。每个基因都代表一条航路，按照从前至后的顺序依次经过编码中的路径点，例如38→2→5→7代表从38经过2，然后经过5，最后到达7的路径。初始路径点和最后一个路径点被锁死，无法进行其他操作。

3.2航路初始化

障碍物的不规则性导致产生很多特征点。因此，在进行初始化时随机产生100个初始种群。由于每个种群编码的容量都是全部障碍物点的个数，而实际船舶不可能经过所有的点，所以设定50%的编码位的数值为零。同时，将固定好的航路分成5个阶段，对每个阶段根据适应度值大小分别进行判断排序。

3.3适应度函数编写

适应度值的计算直接影响算法的计算时间和效率，因此在设计适应度函数时必须切合实际，同时考虑船舶操纵能力、值班驾驶员主观意愿和航程最短这3个重要因素。本文采用加权评分法计算适应度值。这种方法以权值大小体现诸多因素在评价过程中的不同地位和作用。为避免因单位不同而导致适应度值仅由某一项决定，对

Fi（i=1，2，3）进行无量纲化处理：

F′i=Fi-Fi，minFi，max-Fi，min

（13）

获得的适应度函数公式为

F=F′2（ω1F′1+ω3F′3）

（14）

3.4选择算子轮盘赌编写

利用轮盘赌编码能使适应度值越大的种群留下来的概率越大。留存概率为

p（i）=F（i）ni=1F（i）

（15）

3.5算法改进核心

3.5.1选择算子精英保留

相对最优航路的可航性极为重要，如果全部随机打破，将会延长寻优时间，故采取精英保留策略，即对每次寻优的最优前5名，不打破其基因序列，直接保留至下一代。

3.5.2交叉算子

交叉在一定的概率Pc下发生，交叉形式分3种：

（1）挑选留存下来的两条路径，搜寻具有相同路径点或邻近路径点的两个种群，在重叠点处（交叉点）进行交叉操作。如

12→2→7→33→21→15→44→3和

19→3→22→33→5→21→23→7，

交叉后产生

19→3→22→33→21→15→44→3和

12→2→7→33→5→21→23→7。

（2）随机挑选两个种群，在随机位上直接进行两两交叉，产生新种群。如

22→12→34→32→1→5→8→23和

54→2→14→16→5→7→8→33，

交叉后产生

54→2→14→32→1→5→8→23和

22→12→34→16→5→7→8→33。

（3）对评价度较高的基因片段采取保留策略，以免打破优良基因。如

19→3→22→33→5→21→23→7和

22→12→34→16→5→7→8→33，

交叉后产生

19→3→22→7→8→33和

22→12→34→16→5→33→5→21→23→7。

3.5.3变异算子

变异在一定的概率Pm下发生，变异方式有4种：

（1）随机选定某一种群的某一数值，对其进行随机更改。如

12→2→7→33→21→15→44→3，变异后产生

12→2→7→2→21→15→44→3。

（2）随机选定某一非零点，然后用零替代。如

54→2→14→16→5→7→8→33，变异后产生

54→2→14→0→5→7→8→33。

（3）隨机选定种群中两个不为零的点进行位置互换。如

22→12→34→16→5→7→8→33，变异后产生

22→7→34→16→5→12→8→33。

（4）随机选定种群中的某一位置插入一个随机的邻接点。如

19→3→22→33→5→21→23→7，变异后产生

19→3→22→24→33→5→21→23→7。

4遗传算法验证

选定舟山群岛附近的一块岛礁区，该区域障碍物繁多，符合试验要求。如图4所示为舟山群岛的部分区域。利用文中给出的遗传算法，采用Visual Studio 2015 C++ 进行编码运算，路径初始点为A（29°58.443 7′N，122°02.992 9′E），终点为B（29°59.098 5′N，122°08.521 4′E），种群规模为150，ω1=0.223，ω3=0.928，Pc在（0.7，0.9）上随机产生，Pm在（0.03，0.05）上随机产生。

利用蚁群算法、模拟退火算法、标准遗传算法和本文改进后的遗传算法各进行两次计算，并将结果进行对比来验证本文算法的高效性和可靠性（见表1）。这些算法都具有随机性。各算法种群数都为150个。

从表1可以得出：蚁群算法平均在经过13.760 5 s， 迭代28.5代后收敛，收敛的适应度平均值为0.009 520 125 7；模拟退火算法平均在经过35.003 2 s， 迭代64.5代后收敛；改进遗传算法平均在经过19.168 6 s， 迭代40代后收敛，收敛的适应度值为0.017 578 231 1。经过对比可以看出：蚁endprint

群算法搜索效率较低，当信息素对蚁群的引导能力不足时很容易出现停滞现象；模拟退火算法频繁地重新加温才能避免陷入局部极小值，但不必要的回温使搜索速度降低，收敛过程太漫长；标准遗传算法局部寻优能力很差，会在局部位置上搜索很久；改进后的遗传算法在搜索效率和收敛速度上都具有一定的优越性。

在实际航行中有船舶采用了图4中利用改进遗传算法得到的路径航行，证明了路径是可行、有效的。图4中的其他路径均有不同程度的缺陷，如路径过长、转向角过大、距离岛礁区过近等。

5结束语

为提高船舶频繁进出岛礁区的安全性，以航路规划为切入点，分析岛礁区障碍物和水域环境等特征，建立适应度函数评价模型。基于遗传算法，通过电子海图平台提取障碍物关键点，对进出岛礁区的船舶进行航路规划。该方法能减少以往单凭船长经

验进行人工航路规划的弊端，缓解值班驾驶人员的压力。通过实际数据验证了该方法切实可行，为未来路径规划与自动控制技术相结合，建立岛礁区水域自主航行体系提供理论支持。

参考文献：

[1]

熊海生. 岛礁区通航环境安全评估研究[D]. 大连： 大连海事大学， 2014.

[2]孙树栋， 曲彦宾. 遗传算法在机器人路径规划中的应用研究[J]. 西北工业大学学报， 1998， 16（1）： 7983.

[3]SUGIHARA K， SMITH J. Genetic algorithms for adaptive motion planning of an autonomous mobile robot[C]//IEEE International Symposium on Computational Intelligence in Robotics and Automation， 1997. Proceedings IEEE， 1997： 138143. https：//doi.org/10.1109/cira.1997.613850.

[4]周明， 孫树栋， 彭炎午. 使用遗传算法规划移动机器人路径[J]. 西北工业大学学报， 1998， 16（4）： 580583.

[5]周明， 孙树栋， 彭炎午. 基于遗传模拟退火算法的机器人路径规划[J]. 航空学报， 1998， 19（1）： 118120. DOI： 10.3321/j.issn：10006893.1998.01.026.

[6]安柏义， 曹云峰. 基于动态规划的无人机航路优化问题研究[J]. 计算机测量与控制， 2008， 16（8）： 11771179， 1194. DOI： 10.16526/j.cnki.114762/tp.2008.08.002.

[7]穆晓敏， 姜智超， 包一鸣， 等. 低空突防最优航路规划算法与仿真[J]. 航天控制， 2005， 23（1）： 4550. DOI： 10.3969/j.issn.10063242.2005.01.011.

[8]汪柱， 李树军， 张立华， 等. 基于航路二叉树的航线自动生成方法[J]. 武汉大学学报（信息科学版）， 2010， 35（4）： 407410. DOI： 10.13203/j.whugis2010.04.015.

[9]王莹， 刘维亭. 基于改进蚁群算法的舰船航路规划研究[J]. 现代电子技术， 2010， 33（21）： 186188， 196. DOI： 10.16652/j.issn.1004373x.2010.21.014.

[10]邹春明， 赵俊超， 杨柯， 等. 基于惩罚PSO的群桥水域多约束航路规划[J]. 中国航海， 2016， 39（2）： 6770. DOI： 10.3969/j.issn.10004653.2016.02.016.

[11]刘俊丽， 韩旭. 遗传算法技术浅论[J]. 电脑学习， 2009（5）： 142143. DOI： 10.3969/j.issn.20952163.2009.05.070.

[12]徐建国. 岛礁区航行方法与应急措施[J]. 中国水运， 1997（8）： 2930. DOI： 10.13646/j.cnki.421395/u.1997.08.015.

[13]吕呼平. 浅谈大型船舶在舟山岛礁区航行的方法[C]//中国航海学会优秀论文文摘及学术会议论文目次汇编（1990—1991）. 上海， 1992： 2.

[14]张云鹏， 张吉平. 大型船舶沿岸航行富余水深的研究[J]. 大连海事大学学报， 2014， 40（3）： 3336. DOI： 10.16411/j.cnki.issn10067736.2014.03.017.

[15]栾法敏. 沿岸通航密集区航行风险识别、评估和控制[J]. 中国航海， 2014， 37（3）： 8084. DOI： 10.3969/j.issn.10004653.2014.03.019.

[16]张锡海. 曹妃甸港及其附近水域航路优化的研究[D]. 大连： 大连海事大学， 2007. DOI： 10.7666/d.y1037209.

[17]马全党. 典型水域船舶航路动态规划模型及其应用研究[D]. 武汉： 武汉理工大学， 2012. DOI： 10.7666/d.y2099337.

（编辑赵勉）endprint