基于改进遗传算法的船舶路径规划
|
摘要
针对传统遗传算法解决船舶路径规划问题的不足,提出了一种改进的遗传算法。改进算法改变了种群的编码方式,由二维编码变为基于坐标轴的一维编码;在传统遗传算法的基础上增加三种新的遗传操作:复原操作、重构操作和录优操作;复原、重构操作能够避免算法收敛于局部最优解,使算法尽早收敛于全局最优解,录优操作保证种群朝着最优解方向进化。另外设计了插入算子、删除算子和平滑算子来提高种群进化效率和生成路径的现实意义。计算机仿真结果表明,在不同的航海环境中,该算法能够找到平滑的全局最优路径,验证了算法的可行性、有效性和现实性。另外,该算法生成路径的长度和运行时间相比于传统算法均有所提高。
Aiming at the shortcomings of traditional genetic algorithm to solve ship path planning problems,we propose an improved genetic algorithm. This algorithm changes the coding mode of the population from two-dimensional coding to one-dimensional coding based on coordinates axes,and adds three new operations:restoration,reconstruction and recording. The restoration and reconstruction can avoid the convergence of the algorithm to the local optimal solution and makes it converge to the global optimal solution as soon as possible,and the recording ensures that the population evolves toward the direction of the optimal solution. The insertion,deletions and smoothing operators are designed to improve the evolutionary efficiency of populations and their practical significance. Finally,the computer simulation shows that the algorithm can find a smooth global optimal path in different navigation environments,which verifies its feasibility,validity and reality. In addition,the path length and run time of the improved algorithm generation are better than traditional algorithms.
Aiming at the shortcomings of traditional genetic algorithm to solve ship path planning problems,we propose an improved genetic algorithm. This algorithm changes the coding mode of the population from two-dimensional coding to one-dimensional coding based on coordinates axes,and adds three new operations:restoration,reconstruction and recording. The restoration and reconstruction can avoid the convergence of the algorithm to the local optimal solution and makes it converge to the global optimal solution as soon as possible,and the recording ensures that the population evolves toward the direction of the optimal solution. The insertion,deletions and smoothing operators are designed to improve the evolutionary efficiency of populations and their practical significance. Finally,the computer simulation shows that the algorithm can find a smooth global optimal path in different navigation environments,which verifies its feasibility,validity and reality. In addition,the path length and run time of the improved algorithm generation are better than traditional algorithms.
引文
[1] YAO Peng,WANG Honglun,SU Zikang.Real-time path planning of unmanned aerial vehicle for target tracking and obstacle avoidance in complex dynamic environment[J].Aerospace Science and Technology,2015,47:269-279.
[2] 雷英杰,张善义,李续武,等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:1-10.
[3] 王雷,李明,唐敦兵,等.基于改进遗传算法的机器人动态路径规划[J].南京航空航天大学学报,2016,48(6):841-846.
[4] 郑广成.基于遗传算法的船舶导航路径规划研究[J].舰船科学技术,2017,39(5A):76-78.
[5] 张毅,代恩灿,罗元.基于改进遗传算法的移动机器人路径规划[J].计算机测量与控制,2016,24(1):313-316.
[6] LEE J,KIM D W.An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph[J].Information Sciences,2016,332:1-18.
[7] SAMADI M,FAUZI M,OTHMAN.Global path planning for autonomous mobile robot using genetic algorithm[C]//International conference on signal image technology & internet based systems.Kyoto,Japan:IEEE,2013:726-730.
[8] 田鹤,李启华,孟一鸣.基于改进型遗传算法的舰艇航路规划研究[J].船舰电子工程,2011,31(10):46-48.
[9] 隋海腾,牛文铁.基于迷宫算法和遗传算法的船舶管路路径规划[J].工业设计学报,2016,23(2):188-194.
[10] 沈海青,郭晨,李铁山,等.考虑航行经验规则的无人船舶智能避碰导航方法[J].哈尔滨工程大学学报,2018,39(6):998-1005.
[11] LI Ming,LU Yuming,JIE Lilin.Hybrid multipopulation cellular genetic algorithm and its performance[J].Transactions of Nanjing University Aeronautics and Astronautics,2014,31(4):405-412.
[12] TAM C,BCCKNALL R.Path-planning algorithm for ship in close-range encounters[J].Journal of Marine Science and Technology,2010,15(4):395-407.
[13] 唐琳,蔡德荣,黄猛.基于改进遗传算法的舰船路径规划[J].计算机工程与设计,2009,30(6):1452-1454.
[14] 王莹.综合船桥系统航迹规划技术研究[D].镇江:江苏科技大学,2011.
[15] 倪生科,刘正江,蔡垚,等.基于遗传算法的船舶避碰决策辅助[J].大连海事大学学报,2017,38(1):12-15.
[2] 雷英杰,张善义,李续武,等.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:1-10.
[3] 王雷,李明,唐敦兵,等.基于改进遗传算法的机器人动态路径规划[J].南京航空航天大学学报,2016,48(6):841-846.
[4] 郑广成.基于遗传算法的船舶导航路径规划研究[J].舰船科学技术,2017,39(5A):76-78.
[5] 张毅,代恩灿,罗元.基于改进遗传算法的移动机器人路径规划[J].计算机测量与控制,2016,24(1):313-316.
[6] LEE J,KIM D W.An effective initialization method for genetic algorithm-based robot path planning using a directed acyclic graph[J].Information Sciences,2016,332:1-18.
[7] SAMADI M,FAUZI M,OTHMAN.Global path planning for autonomous mobile robot using genetic algorithm[C]//International conference on signal image technology & internet based systems.Kyoto,Japan:IEEE,2013:726-730.
[8] 田鹤,李启华,孟一鸣.基于改进型遗传算法的舰艇航路规划研究[J].船舰电子工程,2011,31(10):46-48.
[9] 隋海腾,牛文铁.基于迷宫算法和遗传算法的船舶管路路径规划[J].工业设计学报,2016,23(2):188-194.
[10] 沈海青,郭晨,李铁山,等.考虑航行经验规则的无人船舶智能避碰导航方法[J].哈尔滨工程大学学报,2018,39(6):998-1005.
[11] LI Ming,LU Yuming,JIE Lilin.Hybrid multipopulation cellular genetic algorithm and its performance[J].Transactions of Nanjing University Aeronautics and Astronautics,2014,31(4):405-412.
[12] TAM C,BCCKNALL R.Path-planning algorithm for ship in close-range encounters[J].Journal of Marine Science and Technology,2010,15(4):395-407.
[13] 唐琳,蔡德荣,黄猛.基于改进遗传算法的舰船路径规划[J].计算机工程与设计,2009,30(6):1452-1454.
[14] 王莹.综合船桥系统航迹规划技术研究[D].镇江:江苏科技大学,2011.
[15] 倪生科,刘正江,蔡垚,等.基于遗传算法的船舶避碰决策辅助[J].大连海事大学学报,2017,38(1):12-15.