基于遗传算法的船舶避碰系统

李世友

摘 要：随着全球经济的飞速发展，经济贸易往来日益频繁，海上运输变得越来越频繁，海面上船舶密度不断增大，各类船舶间发生碰撞概率也不断增大。基于遗传算法研究船舶自动避碰策略并构建了一个避碰演示系统进行仿真验证。定义了确保安全距离下的最短复航路程作为适应度函数并建立碰撞危险模型并分析其避让责任及相应的避碰决策。基于Matlab构建了一个简单的仿真平台对避碰算法进行仿真验证。仿真结果验证了基于遗传算法的避碰策略的有效性。

关键词：船舶自动识别系统;船舶避碰;遗传算法;适应度函数

中图分类号：U664.82          文献标识码：A            文章编号：1006—7973（2021）12-0045-04

随着全球海运事业的快速发展，使得航线上船舶密度不断增大，随着船舶数量增多，也给海上交通的监控和管理带来严峻的挑战。据中国海上搜救中心发布的数据来分析，由船舶碰撞造成的险情占海上事故的五分之一[1]。因此，船舶避碰是海面航行安全研究的热点问题之一[2～9]。早在上世纪90年代末21世纪初就有许多相关研究，例如文献[2]提出了利用框架式专家系统与数理分析相结合的仿人智能避碰方法;文献[3]基于信息熵理论研究评价了在交叉相遇局面中让路船舶两船间初始船舶安全距离和距离采取避碰行动种类的不确定性;文献[4]分析了航海避碰专家系统软件开发的必要性与紧迫性并对整个软件开发的思路、方法及软件要求作了论述，同时还建立了船舶避碰危险度的数学模型;文献[5]在研究船舶碰撞危险度的基础上建立船舶动态避碰行动领域模型。

最近几年许多学者从不同角度开展船舶避碰相关的理论分析或者系统研究。胥文等2017年在船舶碰撞几何原理的基础上利用模糊规则和模糊综合评价方法提出一种船舶复合碰撞危险度的计算方法并进行了仿真分析[6];2019年倪生科等针对不同会遇态势下的船舶避碰路径规划问题建立一种基于遗传算法和非线性规划理论的船舶避碰路径规划模型[7];崔瑾娟通过寻找船舶运动最优最短的避碰路径提出了遗传算法规划路径的船舶避碰系统[8]。

遗传算法（genetic algorithms， GA）[9]是一种元启发式自然选择的过程，属于进化算法（EA）大类。遗传算法本身具有优胜劣汰的能力，在船舶避碰领域得到广泛应用[6～9]。本文利用遗传算法来进行船舶避让的最优避碰路径规划。首先介绍了船舶避碰系统的组成以及船舶避碰的遗传算法描述，并定义了确保安全距离下的最短复航路程作为适应度函数f。在此基础上，根据对船舶运动参数进行计算来建立碰撞危险模型并分析其避让责任及相应的避碰决策。其次构建了一个简单的仿真平台对避碰算法进行仿真验证，分别以两船的对遇和交叉情况来进行验证，实现以上两种情况下的仿真，来验证算法的有效性。

1船舶避碰系统组成遗传算法描述

1.1船舶避碰的遗传算法描述

本文采用的避碰规则为国际避碰规则，即《1972年国际海上避碰规则》[10]（下文简称《规则》）。《规则》将两船之间的会遇态势总分为三种局面：对遇、交叉相遇和追越。遗传算法的基本流程如图1所示。

其主要操作步骤如下：第一步，随机产生一个种群，作为问题的初代解;第二步，寻找一种合适的编码方案对种群中的个体进行编码，可以选择如浮点数编码或二进制编码等常用编码方案;第三步，以多峰函数的函数值作为个体的适应度，计算种群中每个个体的适应度（算出的适应度将为后续的个体选择提供依据）;第四步，根据适应度的高低选择最合适的个体，并以此不断淘汰适应度低的个体;第五步：对筛选出的个体进行遗传操作，找到最优解;第六步：根据一定的准则判断是继续执行算法，还是找出所有子代中适应度最高个体作为解返回并结束程序。

1.2遗传算法操作

具体遗传操作分为编码、群体设定、定义适应度函数、选择遗传算子等操作。其中，选择遗传算子包括交叉算子、变异算子、迁移算子等。

1.3定义适应度函数

在GA中，很少使用搜索空间以外的知识以及通过其他方式获得的其他辅助信息，而是使用设计好的适应度函数来评价每个个体的优或者劣。适应度高的，也就是优秀的个体有更大的几率参与繁衍，遗传自己的基因。一般的，适应度函数根据目标函数来确定，有时候直接将目标函数值作为适应度。

本文采用确保安全距离下的最短复航路程作为总适应度函数。该适应度函数包括安全性适应度、路径总长适应度和航线偏离适应度三个适应度。这三个适应度分别定义如下：①安全性适应度，其中为避碰过程中时刻本船的路径点与对应时刻干扰船之间的安全性，由安全距离决定，如果距离大于安全距离，则为1否则为0;②路径总长适应度，其中为避碰过程中从时刻到时刻本船经过的路程，则代表从采取避碰措施偏离原来航线到复航至原来的航线上的实际避碰航线的总长度;③航线偏离适应度点路： 其中为在避碰过程中实际位置与原航线的对应时刻的对应位置之间的偏移距离。上述定义中的代表时刻。总适应度函数，其中为路径长度和偏离度的权重，且满足。时刻的总适应度函数。

2 船舶避碰仿真系统设计

2.1船舶避碰仿真系统界面设计

本文在MATLAB GUI界面下设计船舶避碰系统的仿真界面并对避碰算法进行仿真验证。本文设计的船舶避碰系统的仿真界面如图2所示。该船舶避碰仿真界面主要设计了本船和临近干扰船的相关参数，包括初始位置、目标位置及速度等信息，用来模拟AIS的数据源。

2.2船舶避碰仿真系统软件设计

在船舶避碰仿真程序的設计过程中，通过输入本船与干扰船的相关参数，模拟AIS的监测结果，完成程序的初始条件设定。设置了本船与干扰船之间对遇与交叉会遇的两种状态，通过调用第1节的遗传算法，最终得到最优避碰路径。船舶避碰系统的主程序流程图如图3所示。

3 基于AIS数据的避碰仿真

3.1基于天拓三号星载AIS数据的船舶交叉案例

本节首先给出一个基于真实星载AIS数据的船舶交叉的案例。国防科技大学2015年发射了我国第二颗AIS微纳卫星[11]。天拓三号星载AIS载荷是我国第二代星载AIS，优势在于它拥有更好的覆盖范围，极大地提高了信号侦收能力;并且，天拓三号的AIS系统实现了对每一条信息的精确时间显示，为今后实现对海面船舶进行连续跟踪与监视提供了良好的技术基础[13]。

图4给出两船交叉会遇的例子。A船最初位置的经纬度为（121.0760， 27.2450），B船所在的位置为（121.0760， 27.3450），两船舶航行方向成一个夹角，两船最初的相距11.1195公里，经过一段时间的航行，两船之间的距离不断减少，最终在A船所在位置为（121.6640，27.3250），B船所在位置为（121.6640，27.3450），两船舶的距离为2.2239公里。两船小于最小预警距离（3公里），如果不采取避碰措施，两船将很快相撞。

3.2船舶交叉会遇避碰仿真分析

以3.1小节的例子为蓝本对两船交叉会遇进行两船交叉避碰仿真分析。本船与干扰船（来船）的初始会遇态势如图5所示。图中，红色方框和黑色圆圈分别代表本船和干扰船的初始位置;红色实线和黑色实线分别表示本船和干扰船的初始航线。本船的航速为14.4 kn，本船的航向45°;干扰船的航速是也是14.4 kn，干扰船的航向是270°，与本船的相对方位是225°，与本船之间的距离是8.2nmile。两船安全会遇距离为1.55 nmile，约为2.87 km。当本船与干扰船的距离小于安全距离时，则本船与来船存在碰撞危险，需要采取避碰行动，用避碰算法进行避让航线选择。

在两船交叉仿真中，根据《规则》的相关要求，当两艘机动船交叉相遇致有构成碰撞危险时，有干扰船在本船右舷的船舶应给他船让路，如当时环境许可，还应避免横越他船的前方。因此在遗传算法控制下，令干扰船保速保向而只让本船采取向右转向进行避让行动。

图5为两船在交叉情况下不采取避碰措施和调用遗传算法进行避碰的仿真结果。上图为不调用遗传算法时候的两船航行状态。在此情况下，两船都沿着既定行驶路线继续航行，则在某时刻本船与干扰船会相撞;下图为调用遗传算法子程序的时候的两船航行状态，红色虚线代表本船原来的航线，红色实线代表避碰航线。调用遗传算法，使用避碰程序设定干扰船与本船的初始状态参数后，应用随机的方式产生初始种群，该种群中包括一条初始的路径。然后利用已经寻找到的适应度函数对每一条初始遗传算法在船舶避碰行动决策中的应用研究路径进行相应的评价，最后寻找出初始种群中适应度函数值最大的一条初始路径，这条路径就是我们所要寻找的最佳的初始路径，如图5下图所示。

本节案例仿真结果表明，在两船对遇的情况下，本船执行避碰策略，在判断可能存在与干扰船的对遇碰撞的时候通过遗传算法得到向右转向的策略从而避免与干扰船碰撞，最终完成与对遇干扰船的避碰过程。结果表明避碰算法是合理可行的。

4 结论

本文基于遗传算法研究船舶自动避碰策略并构建了一个避碰演示系统进行仿真验证。首先定义了确保安全距离下的最短复航路程作为适应度函数。该适应度函数包括安全性适应度、路径总长适应度和航线偏离适应度三个适应度。在此基础上，根据对船舶运动参数进行计算来建立碰撞危险模型并分析其避让责任及相应的避碰决策。其次构建了一个简单的仿真平台对避碰算法进行仿真验证，分别以两船的对遇和交叉情况来进行验证，实现以上两种情况下的仿真，来验证算法的有效性。仿真结果表明，基于遗传算法的避碰模型能够将最优良的基因保留下来从而进化出更加强大、更适合生存的基因，从而得到最优的避碰航线完成船舶避碰。

本文的研究主要构建仿真平台进行仿真分析以验证算法的可行性，下一步将结合实际的AIS数据进行实际应用。

参考文献：

[1]李晓松， 孔宪卫. 船舶碰撞事故致因及管控措施研究[J]. 水道港口， 2019， 40（3）：313-318.

[2]李丽娜， 陈聪贵. 船舶自动避碰方法的研究[J]. 中国航海， 1999， 22（1）：20-24.

[3]郑中义， 吴兆麟. 交叉相遇局面中船舶避碰行动的不确定性[J]. 中国航海， 2000， 23（02）：56-61.

[4]杨帆， 刘克中. 船舶智能避碰软件开发的研究[J]. 武汉交通科技大学学报， 2000， 24（5）：580-582.

[5]毕修颖， 贾传荧， 吴兆麟，等. 船舶避碰行动领域模型的研究[J]. 大连海事大学学报， 2003， 24（01）：9-12.

[6]胥文， 胡江强， 尹建川，等. 基于模糊理論的船舶复合碰撞危险度计算[J]. 舰船科学技术， 2017， 39（7）：78-84.

[7]倪生科， 刘正江， 蔡垚，等. 基于混合遗传算法的船舶避碰路径规划[J]. 上海海事大学学报， 2019， 40（1）：21-26.

[8]崔瑾娟. 基于遗传算法规划路径的船舶避碰系统[J]. 舰船科学技术， 2019，41（6A）：43-45.

[9]吉根林. 遗传算法研究综述[J]. 计算机应用与软件， 2004， 21（2）： 69-73.

[10]海司航保部. 1972年国际海上避碰规则[M]. 人民交通出版社， 1978.

[11] LI S Y， CHEN X Q， CHEN L H， et al. Data Reception Analysis of the AIS on board the TianTuo-3 Satellite [J]. The Journal of Navigation， 2017b， doi：10.1017/S0373463316000916.

基金项目：湖南省教育厅优秀青年项目（编号18B572）;湖南省自然科学基金资助项目（编号2020JJ4451）。