基于遗传算法的船舶避碰决策辅助

倪生科， 刘正江， 蔡垚， 王欣

(大连海事大学 航海学院，辽宁 大连 116026)

基于遗传算法的船舶避碰决策辅助

倪生科， 刘正江， 蔡垚， 王欣

(大连海事大学 航海学院，辽宁 大连 116026)

针对海上船舶避碰问题，提出一种基于多种群遗传算法(Genetic Algorithm,GA)自动生成最优避碰路径的船舶避碰辅助决策方法.该算法采用多种群协同进化的方式，通过建立移民算子和人工选择算子保持种群之间的联系.这种改进的GA不仅能解决标准GA中遗传算子参数设定的问题，而且能提高算法的有效性和效率.利用船舶避碰方面的知识和启发式方法生成初始路径，使其决策方向符合避碰规则的要求，并对种群中的个体进行适应度评价与优化.以精英种群中最优个体的最少保持代数作为算法终止条件，这种判据充分利用GA在进化过程中的知识积累，比最大遗传代数判据更为合理.仿真结果证明了多种群GA在辅助船舶避碰决策方面的可行性和优越性.

多种群遗传算法(GA)； 启发式方法； 移民算子； 人工选择算子

0 引 言

船舶避碰决策系统研究一直以来都是船舶航行安全领域的热点和难点课题.早期，船舶避碰采用几何方法确定两船最近会遇距离和到达最近会遇点时间来评价船舶间的碰撞危险.20世纪80年代后，学者们在避碰几何理论的基础上提出了船舶领域和避碰危险度的概念，并把其作为确定采取避碰行动的时机和幅度的依据.进入21世纪后，控制论、信息论、系统论等学科的出现为船舶避碰决策提供了新的思想和方法论，同时，心理学、社会心理学等理论方面的突破也为研究人类决策过程、创新思维等增加了新的可能.[1]近年来快速发展的人工智能技术与方法克服了早期用确定性方法解决避碰决策问题时遇到的抽象因素众多、量化困难等难题.[2]目前，对船舶避碰决策的研究方法逐渐由最初的数学计算模型过渡到人工智能方法，如进化算法[3]、神经网络[4-5]、模糊逻辑[6]、专家系统[7]、遗传算法(Genetic Algorithm，GA)[8-12]、蚁群算法[13]等.GA对全局优化问题具有很强的鲁棒性并且在机器人路径规划领域取得了重大突破，因此许多学者将GA应用于船舶避碰决策中.例如：TAM等[8]强调了优化指标及环境条件对算法生成路径的影响，通过引入避碰影响区域来控制GA输出结果的一致性；王则胜[9]在GA中对转向点坐标采用实数编码方式对船舶避碰路径进行规划；TSOU等[12]以避碰转向角度、复航时机和复航角度作为变量进行编码优化，将得到的结果在地理信息显示系统中进行仿真.

目前，船舶避碰决策的研究大都以标准GA为基础，但标准GA本身的缺陷使其在实际船舶会遇局面中发挥的作用有限.例如，标准GA在对某一特定船舶会遇态势进行避碰决策时，需要提前试验遗传(交叉、变异)算子参数的最优组合，才能保证得到有效的避碰路径，同时标准GA容易出现过早收敛的情况.因此，本文提出以多种群GA代替标准GA进行船舶避碰决策，通过含有不同遗传算子参数组合的多种群协同进化方式解决参数设定问题以及单种群进化时存在的过早收敛问题，同时通过移民算子和人工选择算子保证种群间的信息交换.最后，应用精英种群中最优个体的最少保持代数作为GA的终止条件，这充分利用了GA在进化过程中的知识积累，比传统最大遗传代数判据更为合理.

1 船舶会遇态势划分

在进行船舶避碰决策时，首先需要对船舶会遇态势进行划分.通过对避碰规则、航行习惯和自动避碰方法的分析将船舶间的会遇态势分为对遇(F)、交叉(A，B，E)和追越(C，D)[1]，如图1所示.图1中：对位于A，B区域的他船，本船为让路船；对位于E区域的他船，本船为直航船，这意味着，通常本船不采取任何避碰行动，只有在形成紧迫局面而他船仍不采取任何避碰行动时，本船才采取必要的避碰行动；对位于C，D区域的他船，本船为被追越船，通常本船具有保向保速的义务，只有与他船形成紧迫局面时，才采取相应的避碰行动；对位于F区域的来船，本船与他船各自采取向右转向方式，以“左对左”方式安全驶过.

图1 基于相对方位角划分 的船舶会遇态势

2 基于多种群GA的路径规划实现

GA是一种基于自然选择和基因遗传学原理的搜索方法，其基本原理就是自然界的“优胜劣汰、适者生存”的演化规则.[14]通过把问题编码为不同类型的染色体参数，再利用选择、交叉、变异等遗传算子对染色体中的编码信息不断进行优化，直到达到优化门限条件，迭代过程才终止.本文通过多种群协同进化的方式解决标准GA中存在的参数设定和过早收敛问题.图2为多种群GA的流程.

图2 多种群GA流程

2.1 编码方式

在GA中，编码技术、编码串的长度及搜索空间对系统的运行速度非常重要.本文采用实数编码技术简化GA的计算复杂度和处理复杂的决策变量约

图3 染色体编码方式

束条件.图3为染色体编码方式,其中φi(i=1,2,…,n)为本船在各对应路段上的航向.

2.2 遗传操作

选择操作.选择操作是在群体中选择生命力强的个体产生新的群体的过程.本文采用轮盘赌选择法，即种群中个体i被选中的概率为

(1)

式中:Fi为个体i的适应度值(i=1,2,…,N).

交叉操作.交叉操作是把两个同源染色体通过重组形成新的染色体从而产生新的个体或物种的过程.由于本文采用实数编码方式，所以单点交叉操作后基因位上基因值为

(2)

(3)

式中：akj和alj分别为第k个和第l个染色体上第j个基因位上的基因值；b是[0,1]上的随机数.

变异操作.变异操作是以较小的概率改变个体编码串上某些基因位上的基因值.本文采用高斯变异算子，通过MATLAB中函数指令生成符合正态分布的随机数来替换原有基因位上的基因值.

2.3 初始化种群

为使随机生成的初始路径满足《1972年国际海上避碰规则公约》(简称《避碰规则》)的要求，利用船舶避碰方面的知识和启发式方法生成初始路径，并对种群中的个体进行适应度评价与优化.例如，在船舶路径初始化过程中，首先计算分析出船舶间会遇态势及避让责任，假设分析出本船为让路船，为满足《避碰规则》中对让路船的避让行动早、大、宽、清的要求，在初始化种群操作过程中加入限制条件，即各个体初始基因位的变量下限值大于15°[15]，这就保证了让路船按规则要求的转向方向和幅度进行避让，并且种群中各个体的初始基因不参与优化过程中的交叉、变异操作，保证优化后的路径始终满足良好船艺的要求，同时在适应度函数中引入船舶领域，保证船舶在生成的避碰路径上自动避碰以及复航过程的安全.

2.4 适应度函数

以船舶安全性和航线航程作为约束条件构造适应度函数

(4)

通过分析适应度函数可知，当D与Dt-D′同时趋近0时，得到的路径适应度最好，两者属于同一数量级.通过试验方法得到α和β的值分别为0.4和0.6.当Dt

3 基于多种群GA的船舶避碰路径规划仿真

表1为3种会遇态势下本船和目标船的初始状态，包括初始坐标、航速和航向.在追越态势下，为快速完成追越过程，给定本船初始速度为11.0 m/s.运用多种群GA分别对3种会遇态势下的船舶进行路径规划，得到的结果见图4～6.

表1 3种会遇态势下本船和目标船的初始状态

a)本船最优路径

b)两船距离

a)本船最优路径

b)两船距离

a)本船最优路径

b)两船距离

图4～6中：虚线为本船以初始航速和航向航行时的运动轨迹，点划线为本船优化路径，直线为目标船运动轨迹；t为航行时间.从仿真结果看，在整个避让过程中，本船与目标船的距离都大于船舶领域半径，同时优化路径满足船舶安全性、航线平滑度和航线航程的要求.

分别利用多种群GA和标准GA对3种船舶会遇态势进行仿真，得到这两种算法的收敛曲线，见图7.通过对比图7a)和7b)可以看出，多种群GA在收敛的迭代次数和收敛的适应度方面都要优于标准GA，即用多种群GA得到的最优路径要优于用标准GA得到的最优路径.

a)标准GA

b)多种群GA

4 结 论

本文采用多种群遗传算法(GA)对船舶进行避碰辅助决策.多种群GA解决了标准GA在船舶路径规划中出现的遗传算子参数设置问题和过早收敛问题.最后，分别利用多种群GA和标准GA对3种船舶会遇态势进行仿真，得到的收敛曲线证明了多种群GA在船舶避碰决策方面的有效性和优越性.

[1]郑中义. 船舶自动避碰决策系统的研究[D]. 大连: 大连海事大学, 2000.

[2]康与涛, 朱大奇, 陈伟炯. 船舶避碰路径规划研究综述[J]. 船海工程, 2013, 42(5): 141-145. DOI: 10.3963/j.issn.1671-7953.2013.05.038.

[3]MIERZCHALSKI R, MICHALEWICZ Z. Modeling of a ship trajectory in collision situations at sea by evolutionary algorithm[J]. IEEE Transaction on Evolutionary Computation, 2000, 4(3): 227-241.

[4]ZHU Xiaolin, XU Hanzhen, LIN Junqing. Domain and its model based on neural networks[J]. Journal of Navigation, 2001, 54(1): 97-103. DOI: 10.1017/S0373463300001247.

[5]陈建华, 陈红卫, 刘科. 基于模糊神经网络的一种船舶碰撞危险度计算方法[J]. 舰船科学技术, 2008, 30(2): 135-138. DOI: 10.3404/j.issn.1672-7649.2008.02.027.

[6]LEE S, KWON K, JOH J. A fuzzy logic for autonomous navigation of marine vehicles satisfying COLREG guidelines[J]. International Journal of Control Automation and Systems, 2004, 2(2): 171-181.

[7]EFSTATHIOU J. Expert systems, fuzzy logic and rule-based control explained at last[J]. Transactions of the Institute Of Measurement and Control, 1988, 10(4): 198-206.

[8]TAM C, BUCKNALL R. Path-planning algorithm for ship in close-range encounters[J]. Journal of Marine Science and Technology, 2010, 15(4): 395-407. DOI: 10.1007/s00773-010-0094-x.

[9]王则胜. 基于遗传算法的船舶避碰决策研究[D]. 上海: 上海海事大学, 2005.

[10]唐琳, 蔡德荣, 黄猛. 基于改进遗传算法的舰船路径规划[J]. 计算机工程与设计, 2009, 30(6): 1452-1457.

[11]田鹤, 李启华, 孟一鸣. 基于改进型遗传算法的舰艇航路规划研究[J]. 舰船电子工程, 2011, 31(10): 46-48.

[12]TSOU M, KAO S, SU C. Decision support form genetic algorithms for ship collision avoidance route planning and alerts[J]. Journal of Navigation, 2010, 63(1): 167-182. DOI: 10.1017/S037346330999021X.

[13]王莹. 综合船桥系统航迹规划技术研究[D]. 江苏: 江苏科技大学, 2011.

[14]雷英杰, 张善文, 李续武, 等. MATLAB遗传算法工具箱及应用[M]. 西安: 西安电子科技大学出版社, 2005: 1-10.

[15]SZLAPCZYNSKI R. A unified measure of collision risk derived from the concept of a ship domain[J]. Journal of Navigation, 2006, 59(3): 477-490. DOI: 10.1017/S0373463306003833.

[16]孙立成. 船舶避碰数学模型的研究[D]. 大连: 大连海事大学, 2000.

(编辑 赵勉)

Ship collision avoidance decision aids based on genetic algorithm

NI Shengke, LIU Zhengjiang, CAI Yao, WANG Xin

(Navigation College, Dalian Maritime University, Dalian 116026, Liaoning, China)

For the ship collision avoidance problem at sea, a method to ship collision avoidance decision aids is presented, where the multi-population Genetic Algorithm(GA) is adopted to automatically generate the optimal path of collision avoidance. In the algorithm, multiple populations evolve simultaneously, and the immigration operator and the artificial selection operator are established to keep relationships among populations. The improved GA can not only solve the problem of parameter settings for genetic operators in the traditional GA, but also improve the algorithm’s effectiveness and efficiency. The knowledge of ship collision avoidance and the heuristic method are used to generate the initial path whose decision direction meets the requirements of collision avoidance rules, and to carry out the fitness evaluation and optimization for individuals of the populations. The termination condition of the algorithm is the minimum iteration times predefined that the optimal individual is kept in the elite population, which makes full use of the knowledge accumulation in the iteration process of GA, and is more reasonable than the criterion of the maximum genetic iteration times. Simulation results demonstrate the feasibility and superiority of the multi-population GA in aiding ship collision avoidance decision.

multi-population Genetic Algorithm (GA); heuristic method; immigration operator; artificial selection operator

10.13340/j.jsmu.2017.01.003

1672-9498(2017)01-0012-04

2016-08-09

2016-11-10

国家自然科学基金(51179019)；工业及信息化部高技术船舶科研项目(9014491)

倪生科(1990—)，男，辽宁大连人，博士研究生，研究方向为交通信息工程及控制，(E-mail)863369021@qq.com； 刘正江(1959—)，男，江苏如皋人，教授，博导，博士，研究方向为交通信息工程及控制，(E-mail)liuzhengjiang@dlmu.edu.cn

U675.96

A