基于混合遗传算法的船舶避碰路径规划

倪生科 刘正江 蔡垚 王欣

摘要：针对不同会遇态势下的船舶避碰路径规划问题，建立一种基于遗传算法和非线性规划理论的避碰路径规划模型。该模型结合遗传算法全局搜索能力强与非线性规划方法局部搜索能力强的特点，使混合后的遗传算法在性能和效率上都得到提高。综合考虑船舶安全性、路径平滑度和路径长度等因素的影响建立避碰目标函数，采用基于实数编码方式的轮盘赌选择算子、算术交叉算子和高斯变异算子，通过迭代获取全局范围内的最优解。通过仿真对模型进行可行性验证和必要性分析。

关键词：遗传算法; 非线性规划; 实数编码; 避碰

中图分类号：  U675.96

文献标志码：  A

Abstract：For ship collision avoidance path planning issue in different encounter situations， a collision avoidance path planning model is proposed based on the genetic algorithm and the nonlinear programming theory. This model combines the strong global search ability of the genetic algorithm and the strong local search ability of the nonlinear programming method， which greatly improves the performance and efficiency of the hybrid genetic algorithm. Considering the influence of ship safety， path smoothness and path length， an objective function of collision avoidance is established. The roulette selection operator， arithmetic crossover operator and Gaussian mutation operator based on real number encoding are adopted. The optimal solution in the global range is obtained through iteration. The feasibility and necessity of the model are verified through simulation.

Key words：genetic algorithm; nonlinear programming; real number encoding; collision avoidance

0 引 言

为减轻船舶驾驶人员在海上工作的负担和避免避碰过程中的操作失误，可利用现代化的科学手段和方法进行智能决策。大数据、互联网、人工智能等技术和理论的快速发展为船舶智能避碰决策的研究提供了强有力的技术和硬件支撑。船舶避碰路径规划是实现船舶智能避碰决策的关键技术之一，它经过大半个世纪的发展，从早期的经典数学理论逐渐过渡到基于人工智能和学科交叉的路径规划研究，取得了一定的研究成果。TAM等[1]将避碰路径规划的研究方法归纳为确定性算法和启发式算法：确定性算法是遵循一定的计算流程来确定最终方案的，主要包括专家系统[2-4]、模糊逻辑[5-8]、人工势场法[9-11]等;启发式算法是在一个搜索区域的子空间内寻找一个滿足设计要求的优化方案的，主要包括遗传算法[12-17]、蚁群算法[18-20]、粒子群优化算法[21-22]等。不同方法具有各自独特的优势，但都存在一定的缺陷。例如：专家系统的重点是建立避碰知识库和推理机制，可是存在知识获取困难，完备、简练的知识库难以形成，系统实时性较差，智能学习的能力不具备等问题[23];虽然模糊逻辑在船舶避碰领域的应用能在一定程度上实现对避碰这种非确定性问题的推理，但模糊推理的输出依赖于事先设定的参数，目前对模糊控制量的设定均使用经验参数，对环境因素考虑较少，环境自适应性有待提高[24];基于人工势场法对船舶进行避碰决策具有计算简洁、实时性强、便于数学描述等优点，但是存在局部极小值导致的陷阱区域、在碍航物前发生振荡、在邻近碍航物间不能发现路径等固有缺陷[25]。用确定性算法对船舶避碰路径进行规划的特点是计算量小、收敛速度快，但是往往基于其他变量确定的假设对某一变量进行确定，实际上船舶避碰路径规划是一个包含避碰规则、动态障碍避让、船舶操纵性能等多方面的决策优化问题。因此，很多专家学者转向基于启发式算法的船舶避碰路径规划研究，取得了一定的研究成果。然而启发式算法经常存在早熟收敛的问题，致使得到的决策方案不符合要求，因此采用不同的混合方式对各种技术进行优势互补以获得求解能力更强的路径规划模型成为一种新的趋势。

遗传算法具有对可行解编码的广泛性和易于与其他人工智能技术混合等特点，在船舶避碰路径规划领域受到广泛关注。本文基于遗传算法和非线性规划理论建立船舶避碰路径规划模型，解决遗传算法的早熟收敛问题，使混合后的算法在性能和效率方面都得到提高，为驾驶员的避碰决策提供科学依据和支撑。

1 会遇局面的定量划分

从运动路径可以看出，船舶的避让路径满足平滑度的要求。从两船距离变化曲线可以看出，船舶间距离满足船舶安全参数（船舶领域）的要求。在t2时刻，船舶的最近会遇距离（distance to closest point of approach， DCPA）接近船舶领域半径。船舶间距离变化曲线是一条光滑的曲线，表明船舶间的距离是均匀变化的，故避碰路径满足避碰过程中船舶安全性和路径长度的要求。因此，利用混合遗传算法可以得到有效的船舶避碰路径。

3.2 必要性分析

船舶避碰路徑规划是避碰决策中最关键的问题，需要综合考虑船舶安全性、路径平滑度和路径长度的影响。本文使用混合遗传算法不但提高了对避碰路径的搜索能力，而且极大地提高了避碰路径的质量。为证明混合遗传算法在避碰路径规划方面相对于标准遗传算法的优越性，分别利用两种算法对表3中的案例进行仿真，图7为这两种算法的适应度曲线。

由图7可知：混合遗传算法的适应度曲线在迭代25次后达到了相对稳定的状态，比标准遗传算法的适应度曲线达到相对稳定时的迭代次数大约少了10次;混合遗传算法的适应度曲线的斜率在迭代大约20次时有明显的跳跃，其最终的适应度值也明显更优。因此，在同等条件下，基于混合遗传算法的路径规划方法在收敛速度和求解结果上都优于基于标准遗传算法的路径规划方法。

4 结 论

本文首先对船舶会遇局面及避让责任进行判断，通过一维真值实数编码方式对避碰路径进行编码并根据转向避让方向和良好船艺对避碰路径进行初始化操作;再综合考虑船舶安全性、路径平滑度和路径长度对船舶避碰路径规划的影响，提出分类评价的方式，以此建立适应度函数模型;然后，基于遗传算法和非线性规划理论建立避碰路径规划模型，消除以往遗传算法在路径规划方面局部优化能力弱的缺陷;最后，通过船舶避碰仿真对混合遗传算法的有效性和必要性进行验证。

参考文献：

[1]TAM C K， BUCKNALL R， GREIG A. Review of collision avoidance and path planning methods for ships in close range encounters[J]. The Journal of Navigation， 2009， 62（3）： 455-476.

[2]毕京强. 内河船舶自动避碰决策研究[D]. 大连： 大连海事大学， 2016.

[3]LEE Han-Jin， RHEE Key-Pyo. Development of collision avoidance system by using expert system and search algorithm[J]. International Shipbuilding Progress， 2001， 48（3）： 197-210.

[4]AHN Jin-Hyeong， RHEE Key-Pyo， YOU Young-Jun. A study on the collision avoidance of a ship using neural networks and fuzzy logic[J]. Applied Ocean Research， 2012， 37（4）： 162-173.

[5]HWANG Cheng-Neng， YANG Joe-Ming， CHIANG Chung-Yen. The design of fuzzy collision-avoidance expert system implemented by H∞-autopilot[J]. Journal of Marine Science and Technology， 2001， 9（1）： 25-37.

[6]KAO Sheng-Long， LEE Kuo-Tien， CHANG Ki-Yin， et al. A fuzzy logic method for collision avoidance in vessel traffic service[J]. The Journal of Navigation， 2007， 60（1）： 17-31.

[7]PERERA L P， CARVALHO J P， SOARES C G. Fuzzy logic based decision making system for collision avoidance of ocean navigation under critical collision conditions[J]. Journal of Marine Science and Technology， 2011， 16（1）： 84-99. DOI： 10.1007/s00773-010-0106-x.

[8]BRCKO T， VETAK J. Fuzzy reasoning as a base for collision avoidance decision support system[J]. Promet - Traffic & Trasportation， 2013， 25（6）： 555-564.

[9]XUE Yanzhuo， CLELLAND D， LEE B S， et al. Automatic simulation of ship navigation[J]. Ocean Engineering， 2011， 38（17/18）： 2290-2305.

[10]NAEEM W， HENRIQUE S C， HU Liang. A reactive COLREGs-compliant navigation strategy for autonomous maritime navigation[C]//IFAC-PapersOnLine， 2016， 49（23）： 207-213.

[11]李刚. 面向危险环境的UUV动碍航物规避方法研究[D]. 哈尔滨： 哈尔滨工程大学， 2015.

[12]TSOU Ming-Cheng， KAO Sheng-Long， SU Chien-Min. Decision support from genetic algorithms for ship collision avoidance route planning and alerts[J]. The Journal of Navigation， 2010， 63（1）： 167-182. DOI： 10.1017/S037346330999021X.

[13]TAM C K， 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.

[14]SZLAPCZYNSKI R， SZLAPCZYNSKA J. On evolutionary computing in multi-ship trajectory planning[J]. Applied Intelligence， 2012， 37（2）： 155-174. DOI： 10.1007/s10489-011-0319-7.

[15]李瑶. 遗传算法在船舶避碰行动决策中的应用研究[D]. 大连： 大连海事大学， 2013.

[16]刘佳男. 基于进化遗传算法的无人艇避碰系统研究[D]. 大连： 大连海事大学， 2015.

[17]TSOU Ming-Cheng. Multi-target collision avoidance route planning under an ECDIS framework[J]. Ocean Engineering， 2016， 121： 268-278.

[18]TSOU Ming-Cheng， HSUEH Chao-Kuang. The study of ship collision avoidance route planning by ant colony algorithm[J]. Journal of Marine Science and Technology， 2010， 18（5）： 746-756.

[19]LAZAROWSKA A. Ships trajectory planning for collision avoidance at sea based on ant colony optimisation[J]. The Journal of Navigation， 2015， 68（2）： 291-307.

[20]LAZAROWSKA A. Method of considering the dynamics of a ship in the process of determining a safe trajectory using an algorithm based on ant colony optimization[C]//International Conference on Methods and Models in Automation and Robotics. IEEE， 2016.

[21]王得燕. 粒子群算法在多船转向避碰中的研究[D]. 无锡： 江南大学， 2009.

[22]潘朋朋. 基于粒子群优化算法的船舶避碰研究[D]. 镇江： 江苏科技大学， 2010.

[23]吕红光， 尹勇， 尹建川， 等. 基于人工智能和软计算的船舶自动避碰决策算法[J]. 中国航海， 2016， 39（3）： 35-40.

[24]谢朔， 初秀民， 柳晨光， 等. 船舶智能避碰研究综述及展望[J]. 交通信息与安全， 2016（1）： 1-9. DOI： 10.3963/j.issn1674-4861.2016.01.001.

[25]林晓杰. 基于改进势场法的受限水域中船舶自动避碰模型研究[D]. 哈尔滨： 哈尔滨工程大学， 2015.

[26]TAM C K， BUCKNALL R. Collision risk assessment for ships[J]. Journal of Marine Science and Technology， 2010， 15（3）： 257-270. DOI： 10.1007/s00773-010-0089-7.

[27]史峰， 王辉， 郁磊， 等. MATLAB智能算法30个案例分析[M]. 北京： 北京航空航天大学出版社， 2011： 17-25.

[28]孙立成. 船舶避碰数学模型的研究[D]. 大连： 大连海事大学， 2000.

[29]唐冲. 基于MATLAB的非线性规划问题的求解[J]. 计算机与数字工程， 2013， 41（7）： 1100-1102.

（編辑 赵勉）