基于Maklink图和布谷鸟搜索算法的施工水域路径规划

张波菲　谢新连　何傲

摘要：为提高船舶在复杂施工水域通行的安全性，提出一种基于Maklink图和布谷鸟搜索（cuckoo search， CS）算法的船舶路径规划方法。利用改进的Maklink图构建施工水域环境模型;设置变量参数并用改进的CS算法对模型进行求解，其中采用基于Dijkstra算法得到的最短路径长度作为种群个体的适应度值;采用3个衡量算法性能的指标——优化性能指标、时间性能指标和动态性能指标，对多种算法进行分析比较。结果表明，采用指数型自适应步长和线性自适应发现概率对CS算法进行改进，能提高其在路径规划中的搜索效率和迭代速度，并可以保证求出一定精度内的近似最优解，显示出该算法的优越性。

关键词：船舶避障; 智能交通; 布谷鸟搜索（CS）算法; 性能指标; 施工水域; Maklink图

中图分类号：  U675.73

文献标志码：A

Path planning  in construction waters based on Maklink

graph and cuckoo search algorithm

ZHANG Bofei， XIE Xinlian， HE Ao

（Logistics Research Institute， Dalian Maritime University， Dalian 116026， Liaoning， China）

Abstract：

In order to improve the navigation safety of ships in complex construction waters，  a ship path planning method based on the Maklink graph and the cuckoo search （CS） algorithm is proposed. The construction waters environment model is constructed by the improved Maklink graph; the variable parameters are set and the model is solved by the improved CS algorithm. The shortest path length calculated by the Dijkstra algorithm is used as the fitness value of the population individual. Three performance indexes for measuring the algorithm performance are used to analyze and compare many algorithms， where three performance indexes are the optimization performance index， the time performance index and the dynamic performance index， respectively. The results show that the improvement of the CS algorithm by the exponential adaptive step size and the linear adaptive discovery probability can improve its search efficiency and iteration speed in path planning， and can guarantee to obtain the approximate optimal solution within a certain precision， which shows the superiority of the algorithm.

Key words：

ship obstacle avoidance; intelligent transportation; cuckoo search （CS） algorithm; performance index; construction waters; Maklink graph

0 引 言

随着港口和航道的通航密度迅速增加，船舶呈现大型化、专业化、高速化的发展趋势，海上交通环境越来越复杂。同时，由于需求的增加和沿海城市经济的快速发展，海上和沿海区域的开发利用（如跨海大桥、海底隧道、海上钻井平台、各类水工设施等）越来越频繁，这就对船舶通行安全产生了一定的影响。为提高船舶在施工水域通行的安全性，对通行船舶进行智能诱导，使船舶安全地避开施工区域的障碍物显得尤为重要。

路径规划是船舶智能诱导系统的重要组成部分，其主要目的是在已知船舶准确位置和周围环境信息的情况下，寻找出一条从起点到终点的满足一定要求的航行路径，使船舶在通行过程中能够安全可靠地避开所有障碍物并且使路径尽可能地短。路径规划在机器人领域、航天领域以及船舶避碰领域都有广泛的应用。根据被规划目标对象对环境信息掌握的程度不同，可分为全局路径规划和局部路径规划两种类型。在全局路径规划中，已知全部环境信息，通常采用路线图方法（包括可视图法[1]、Voronoi图法[2]、Maklink图法[3]和随机路线图法等）或者栅格法构建模型，随后采用启发式或智能算法（如蚁群算法[4]（ant colony algorithm， ACA）、遗传算法[5]（genetic algorithm， GA））求解;在局部路径规划方面，由于（基于传感器的）環境信息是未知的，所以通常采用更为简洁且灵活的人工势场法[6]。

在路径规划领域，尽管栅格法应用更为广泛，但相较于Maklink图法来说，存在复杂环境下环境信息存储量大、精度不高、决策效率低的缺点。因此，本文采取Maklink图法构建环境模型。在以往的路径规划研究中，对构建好的Maklink模型求解方法众多，有ACA[4]、GA[5]、人工鱼群算法[7]（artificial fish swarm algorithm， AFSA）、萤火虫算法[8]等，但大多存在无法求得最优解、求解成功率低、计算时间长等缺点。布谷鸟搜索（cuckoo search， CS）算法[9]模拟了布谷鸟寻巢产卵的行为，具有参数少、易于实现、寻优能力强等特点。本文提出的改进的CS算法可以求解出最优解，并且计算时间较短，用于求解路径规划模型有一定的优越性。

1 船舶航行环境建模

1.1 Maklink图

在进行路径规划时，必须对被规划船舶所在的环境空间进行合理的描述，即环境建模。

Maklink图是基于自由空间法的环境建模方法，它首先把环境空间内的障碍物抽象为二维平面内的各种多边形，然后利用图论的知识在这个空间内建立连通图，最后在连通图中完成路径规划。

自由空间法把模型中的障碍物以其顶点表示，对实验环境空间进行如下假设：环境空间内存在

M个障碍物，第i个障碍物Oi有n个顶点，则障碍物Oi可表示为

整个环境可表示为W={B，O1，…，OM}，式中B表示环境边界。构建的施工水域示意图见图1。

随后进行Maklink图的构建，链接线满足4个条件：（1）链接线的两端必须分别为两个多边形障碍物的两个顶点或者其中一个为障碍物顶点而另一个在环境边界上;（2）每个多边形障碍物的每个顶点的外角都被一条或多条链接线分成两个或多个锐角;（3）链接线不能穿越空间内的任何障碍物;（4）每个自由凸区域至少有2条链接线作为边界。

1.2 改进的Maklink图

Maklink图本身也有一定的局限性，为此在研究中结合实际的施工水域通行情况，对Maklink图进行改进。

首先，用Maklink图法画出的航行通道也许并不能满足通行条件，因此利用船宽对链接线的绘制进行限制。在画当前顶点与所有其他障碍物顶点的连线之前，计算出该顶点与其他障碍物的最短距离，它可能是该点与障碍物某一顶点的连线长度（如图2a）或者是该点到障碍物某一边的垂线长度（如图2b）。当最短距离不能满足船舶通行条件时，把该区域设为不可通行区域，构建连通图时不再连接该连线的中点。

其次，当目标区域存在凹多边形时，通常无法画出正确有效的全局连通图。事实上，凹多边形障碍物在海上航行时是时常存在的，尤其存在于复杂的施工水域或者海上捕鱼作业区。在对凹多边形进行连通图构建时，可以把凹多边形划分为多个凸多边形，本文给出一种分解凹多边形的方法：

步骤1 选取凹多边形的一个顶点，连接与该顶点相邻的两个顶点，如果连线没有穿过凹多边形，则该顶点为一个凹顶点，遍历所有的顶点找出所有的凹顶点。

步骤2 选取一个凹顶点，连接该顶点与其他所有不与其相邻的顶点，按线段长度从小到大排列，组成集合A。

步骤3 选取集合A中的第一条线段，检查该线段与凸多边形的顶点产生的两个内角。若2 个内角均小于180°，则保留该连线，进入步骤5; 若某个外角大于180°，则将该连线放入该顶点的候选连线集合B中。

步骤4 检查该顶点的所有候选连线集合B中是否存在外角大于180°的情況。若存在，则返回步骤3;若不存在，则进入步骤5。

步骤5 检查是否已经遍历所有的凹顶点，若是则结束，否则返回步骤2。

通过以上方法画出的连线可以把凹多边形进行分解，随后绘制Maklink图。由于此时分解的凸多边形是相互连接的，用原有步骤无法画出可行的连通图，所以需要适当地缩小凸多边形，使其不再相连。缩小方法为对凸多边形的每条边进行平移，距离选取为船宽的1/10。此时，凸多边形之间有着狭窄的通道，但受不可通行区域的约束，整片多个凸多边形可以近似为整体的凹多边形，如图2c所示。

利用上述方法画出施工水域的全局连通图，如图3所示：点划线是Maklink线，黑实线为通过相邻Maklink线的中点连线得到的无向网格图;在连通图的右下角是一个分解后的凹多边形;链接线的中点5与7，由于船宽限制未进行连接。

2 改进的CS算法

2.1 CS算法简介

CS算法是一种元启发式算法，于2009年由Yang和Deb提出，通过模拟自然界中布谷鸟繁殖行为来实现迭代搜索，即将自己的蛋产在其他鸟类的巢穴并由宿主负责孵化，这种繁殖方式独特且有攻击性。在某些情况下，宿主会发现巢穴中表现异常的蛋，并会将其抛出或者遗弃该巢穴。为便于描述这种行为，Yang和Deb提出3种规则：（1）布谷鸟随机选取一个巢穴产卵，在一个巢穴只产下一个卵;（2）具有最好的卵的巢穴会保留到下一代;（3）巢穴的数量是固定的，布谷鸟的卵被发现的概率是Pa，宿主发现后会抛弃该卵或者抛弃该巢穴，即巢穴以一定概率被取代。

假设CS算法中

[WTHX]X[WTBX]（t）i=（x（t）i1，x（t）i2，…，x（t）in）T表示第i个巢穴在第t代中的位置，n为优化问题的维数即单个解中参数的个数。新一代巢穴位置

[WTHX]X[WTBX]（t+1）i由莱维飞行更新，其公式为

式中：α为优化问题的步长，通常取0.01;⊕为点对点乘法;

[WTHX]L[WTBX]（λ）为服从参数λ（1<λ<3）的莱维分布产生的一个随机搜索向量，经过简化和傅里叶变换后得到的幂次形式的概率密度函数为

为保证最优个体不被替代，对式（2）进行改进：

式中：

[WTHX]γ[WTBX]为服从标准正态分布的随机数向量，

[WTHX]X[WTBX]（t）best是当前所有巢穴中的最优个体，因此当

[WTHX]X[WTBX]（t）i为最优个体时，下一代不会发生改变。

为便于计算莱维分布的随机值，Yang和Deb采用了Mantegna算法来模拟莱维飞行，巢穴位置更新公式为

式中：μ和v为符合正态分布的随机数，μ～N（0，δ2μ），v～N（0，1），其中参数δμ的计算公式为

式中：Γ为标准的Gamma函数;β通常取1.5。

在符合规则（3）的情况下，对被发现的巢穴进行替换称为随机迁移，其公式为

式中：r1、r2为服从[0，1]内平均分布的随机变量;

[WTHX]X[WTBX]（t）j、

[WTHX]X[WTBX]（t）k为随机选中的两个个体;H为阶跃函数。

CS算法在经过莱维飞行和随机迁移后，评价当前所有巢穴的适应度值，记录最优的个体然后完成一次迭代。莱维飞行和随机迁移分别代表全局搜索和局部搜索，通过两者的结合CS算法可以有效控制种群的多样性，优化效果好。

2.2 改进的CS算法

2.2.1 指数型自适应步长

在传统的CS算法中，计算新的巢穴位置用到的步长α是固定的，不会随着迭代次数的增加而发生改变，因此无法平衡迭代过程中的全局搜索与局部搜索，影响搜索效率，导致最终结果不够好。为提高搜索效率，得到更优的计算结果，采用自适应步长进行改进。

在搜索初始阶段，算法需要大的步长，使种群个体以较大的变化在可行域内搜索，从而加强算法的全局搜索能力;而在算法后期阶段，应当采用较小的步长，以加强算法的局部搜索能力并且使计算结果稳定收敛。本文采取指数型自适应步长。首先，引入一个变形的正态分布函数：

步长函数为

式中：α（t）为当前步长;α（t+1）是下一次迭代步长;Tmax为最大迭代次数。可以看出：在算法迭代初期，步长缓慢减小，利于快速搜索，加快迭代速度;在算法迭代后期，步长迅速减小，利于提高解的精度。

2.2.2 线性自适应发现概率

发现概率Pa决定种群个体是否被替换，也影响算法的搜索效率，因此合适的Pa可以有效地提高收敛速度。为使发现概率随迭代次数的增加而减小，并且使适应度值大的个体被发现的概率小于适应度值小的个体被发现的概率，本文提出如下发现概率函数：

式中：P（t）a，i表示经过t次迭代后第i个巢穴被发现的概率;Pa，max和Pa，min分别表示发现概率的最大值和最小值;fi表示当前第i个巢穴的适应度值;fbest和fworst分别表示当前迭代中最好和最坏的适应度值。可以看出，随着迭代的进行，适应度值越大的个体被发现的概率越小，保证了前期搜索的范围更大，不容易陷入局部最优解，后期收敛速度减小以便进行局部寻优，易于找到最优解。

3 數学建模及算法性能指标设计

在图3的基础上用改进的CS算法和其他多种算法进行求解比较，首先将Maklink图中每条链接线上的点当作变量，设定解得可行域：

式中：r1，r2，…，rn为优化问题的变量;n为优化问题的维数，即路径节点的总数。

随后任一链接线上的节点坐标可以由其端点坐标（x1，y1）和（x2，y2）确定。该点坐标（x′，y′）可用变量r表示为

通过变量r可以确定链接线上节点的坐标，然后用Dijkstra算法计算得到当前从起点到终点的最短路径长度，将这个值作为不同算法的个体适应度值，最后通过不断迭代寻优得到最优路线。

为定量评估算法的优越性，本文提出3种性能指标。

（1）优化性能指标。为评估算法的精确度并体现算法的整体搜索能力，采用平均相对误差EMR作为优化性能指标之一。

式中：是算法多次计算结果的平均值;Ctrue是路径优化问题的实际最优值，当最优值不能确定时，用已知最优值代替。指标EMR衡量了整体优化效果：其值越大说明与实际值的差值越大;其值越小说明算法优化性能越好，结果越准确。

为反映算法的波动性，采用均方误差EMS作为另一个优化性能指标：

式中：N表示实验次数;Ci为第i次实验的结果。EMS指标值越小表示算法波动性越小，优化结果越好。

（2）时间性能指标。定义算法的时间性能指标如下：

式中：a为经多次实验得到的算法最终收敛的迭代次数的平均值;t0为算法迭代一次所需的时间。该指标反映了算法整体的收敛速度。当Tmax相同时，Etime越小表示算法所需时间越少，计算速度越快。

（3）动态性能指标。为反映算法的动态性能，即算法内部迭代时的收敛情况，本文提出如下动态性能指标：

式中：C（t）j表示经第t次迭代后第j个个体的计算结果;M表示种群规模。动态性能指标实际是将每次迭代过程中单位个体的计算结果与实际最优值之差与当次迭代时间相乘，并进行累计的结果。该指标越小表示算法在迭代过程中的波动越小，寻优速度越快。

4 算例仿真及算法比较

4.1 改进的CS算法仿真结果

为验证本文算法在处理施工水域路径规划问题中的有效性，在CPU为Intel core i5-8265u并且内存为8 GB的计算机上进行仿真，仿真软件为MATLAB 2019a。经多次仿真后，改进的CS算法的参数选择如下：种群大小为20，最大发现概率为0.5，最小发现概率为0.25。

构建Maklink环境模型后，在图3的基础上进行路径优化，结果见图4a。在施工水域环境模型不变的情况下，通过改变起点规划出另外2条路径，3个起点的坐标分别为（10 m，130 m）、（50 m，160 m）、（20 m，20 m），对应的终点坐标分别为（150 m，50 m）、（160 m，10 m）、（180 m，180 m），分别标记为实验1、2、3。为进一步验证算法的准确性，在不改变3条路径起止点的情况下，改变施工水域环境模型，分别标记为实验4、5、6，仿真结果见图4b。

记录规划出的路径长度，再根据障碍物的顶点计算出实际的最短路径长度，最终的实验结果见表1。由表1可以看出，采用本文改进的算法，每次的实验结果可以固定收敛到最优值。

4.2 與其他智能算法的比较与分析

为验证本文算法在处理路径规划问题上的优越性，除与传统的CS算法对比外，还选取模拟退火（simulated annealing， SA）算法、GA、粒子群优化（particle swarm optimization， PSO）算法、ACA、免疫算法[10]（immune algorithm， IA）、 AFSA和量子遗传算法（quantum genetic algorithm， QGA）作为对比算法，每种算法的参数设置见表2。为更好地对比各算法的优劣，将迭代次数统一设置成100次。在SA算法中通过对温度值变化的设定，外部迭代次数也近似为100次。

施工水域环境模型如图4a所示，即目标水域有5片施工水域，其顶点x坐标值分别为（10 40 90 40）、（50 110 90）、（140 140 160 190 185）、（10 30 70 60 40）、（130 130 180 180 140 140 180 180），y坐标值分别为（120 140 120 70）、（140 140 125）、（100 140 160 140 100）、（40 90 60 30 20）、（20 80 80 60 60 40 40 20），单位都为m。设置起止点坐标分别为（10 m，130 m）、（150 m，50 m）。每种算法实验10次，记录每次的结果以及它们的最小值和平均值，最终结果见表3。用上文提出的3种算法性能指标进行分析，结果见表4。

从表3和表4可以看出：改进的CS算法误差为0，即每次得到的都是全局最优值;CS算法、SA算法和PSO算法表现较好，精确度较高，尤其PSO算法也多次计算出最优值，但总体来说稳定性较差;ACA

也每次收敛到固定值，稳定性较好，但只能得到较优结果而无法得到最优结果。

从单次计算时间看，GA、ACA、CS算法计算速度较快，但从时间性能指标Etime和动态性能指标Ed 可以得出，GA的收敛性比PSO算法、CS算法和改进的CS算法的收敛性差，且后三者的收敛速度相差无几，PSO算法略快于改进的CS算法。

总而言之，改进的CS算法在损失一定计算时间和收敛速度的情况下，可以使精度达到最大，求解出全局最优值，表现较为优秀。

5 结 论

本文在改进的Maklink图的基础上，提出基于布谷鸟搜索（CS）算法的路径规划方法，其中对CS算法进行了指数型自适应步长和线性自适应发现概率的改进，增加了算法前期的全局搜索能力和后期的局部搜索能力。将本文提出的算法与其他多种算法进行比较分析，通过优化性能指标、时间性能指标、动态性能指标进行定量分析。实验结果显示，本文提出的算法具有较高的精度且搜索速度较快，具有一定的实用价值和优越性。

参考文献：

[1]陈超， 唐坚. 基于可视图法的水面无人艇路径规划设计[J].中国造船， 2013， 54（1）： 129-135. DOI： 10.3969/j.issn.1000-4882.2013.01.017.

[2]GOWDA I G， KIRKPATRICK D G， LEE D T， et al. Dynamic Voronoi diagrams[J]. IEEE Transactions on Information Theory， 1983， 29（5）：724-731. DOI： 10.1109/TIT.1983.1056738.

[3]ZHOU Yiye， YAO Dengkai， SUN Qianrui， et al.Maklink graph in conflict-free airline network designing[C]//2016 4th International Conference on Machinery， Materials and Information Technology Applications， Advances in Computer Science Research. Atlantis Press， 2016，71： 385-389. DOI： 10.2991/icmmita-16.2016.180.

[4]陈晓， 戴冉， 陈昌源. 基于Maklink图和蚁群算法的航线规划[J]. 中国航海， 2017， 40（3）： 9-13. DOI： 10.3969/j.issn.1000-4653.2017.03.003.

[5]王飞， 王红勇. 基于Maklink图和遗传算法的改航路径规划方法研究[J]. 交通运输系统工程与信息， 2014， 14（5）： 154-160. DOI： 10.3969/j.issn.1009-6744.2014.05.023.

[6]刘春阳， 程亿强， 柳长安. 基于改进势场法的移动机器人避障路径规划[J]. 东南大学学报（自然科学版）， 2009， 39（S1）： 116-120.

[7]郭伟， 秦国选， 王磊， 等. 基于改进人工鱼群算法和Maklink图的机器人路徑规划[J/OL]. 控制与决策： 1-8[2019-11-11]. DOI： 10.13195/j.kzyjc.2019.0030.

[8]FISTER I，  FISTER I， Jr， YANG Xinshe， et al. A comprehensive review of firefly algorithms[J]. Swarm and Evolutionary Computation， 2013， 13： 34-46. DOI： 10.1016/j.swevo.2013.06.001.

[9]YANG Xinshe， DEB S. Cuckoo search via lévy flights[C]//2009 Proceedings of the World Congress on Nature and Biologically Inspired Computing. IEEE， 2009： 210-214. DOI： 10.1109/NABIC.2009.5393690.

[10]KHAN M T， SILVA C W. Autonomous and robust multi-robot cooperation using an artificial immune system[J]. International Journal of Robotics and Automation， 2012， 27（1）： 60-75. DOI： 10.2316/Journal.206.2012.1.206-3536.

（编辑 赵勉）

收稿日期： 2019-09-20

修回日期： 2020-11-19

基金项目：

国家重点研发计划（ 2017YFC0805309）; 中央高校基本科研业务费专项资金（3132016358）

作者简介：

张波菲（1994—），女，河北秦皇岛人，硕士研究生，研究方向为交通运输规划与管理，（E-mail）1063465140@qq.com;

谢新连（1956—），男，辽宁大连人，教授，博导，博士，研究方向为交通运输规划与管理，（E-mail）xxlian@dlmu.edu.cn