基于信息熵遗传算法的舰船导航路径规划技术研究
|
摘要
随着科技的不断进步,舰船导航正逐渐向智能化的方向发展。其中路径规划是舰船智能航行的关键技术之一。本文以舰船路径规划为背景,以电子海图系统为平台,对舰船在真实海洋环境下的路径规划问题进行了深入的研究。将信息熵理论与遗传算法相结合,并根据路径规划技术特点,提出了应用于路径规划领域的信息熵遗传算法,克服了传统遗传算法在路径规划时耗时长、易陷入局部解的缺点。
针对电子海图显示特点,本文采用多边形障碍表达方式和路径点编码方式,并将遗传算法作为基本算法;为描述种群多样性,重点研究了信息熵原理,提出了基于栅格思想的路径种群熵概念,实现了种群多样性的测量;在此基础上,进一步提出了基于路径种群熵的双轮盘赌选择策略,给出了基于路径种群熵的自适应交叉、变异概率计算公式,达到了在算法前期保持种群多样性,而在算法后期加快收敛速度的目的,提高了算法性能,克服了算法缺陷;提出了先启发生成再优化的初始种群生成方法,提高了初始种群的个体质量;提出了基于区域的碰撞检测方法,减少了检测次数,提高了算法效率。
最后,利用本文设计算法进行了路径规划仿真,得到了理想的结果,验证了本文算法的有效性。同时与原有的自适应遗传算法进行了仿真对比,通过实际效果的差异验证了本文算法的优越性。
As technology progresses, the ship navigation are gradually moving towards the direction of the development of intelligent and path planning is one of the key technologies of it. In the background of path planning of ship and on the platform of electronic chart, the paper makes the thorough research in path planning for ship sailing in the real marine environment. Information entropy-genetic algorithm which applied to the field of path planning is proposed based on the integration of information entropy and genetic arithmetic and the characteristics of path planning. The defects of traditional genetic algorithm in path planning, time-consuming and falling into local solutions are overcome.
For the characteristics of the display of electronic chart, this paper adopts polygonal obstacles and path-point coding presentation, and genetic algorithm as the basic algorithm. To describe the diversity of population, a concept of path population entropy is proposed based on grid concept and focusing research on the information entropy principle and realize the diversity of population measurement. On this basis, the paper further proposed the dual -wheeled-gambling selection strategy based on path population entropy and given the adaptive formula of variation rate and cross rate based on path population entropy, reaches purpose of maintaining diversity of population in the early part of algorithm and speeding up the convergence of the algorithm in the latter part of algorithm. A method of createing initial population which optimizeing path after creating path is proposed and the quality of the initial population is improved. To reduce the detection times, a region-based collision detection method is proposed and the efficiency of the algorithm is improved.
Finally, the use of algorithms designed in this paper a path planning simulation, has been the ideal outcome, validate the effectiveness of the algorithm. At the same time with the original self-adaptive genetic algorithm simulation comparison, through the difference between the actual results validate the superiority of the algorithm.
针对电子海图显示特点,本文采用多边形障碍表达方式和路径点编码方式,并将遗传算法作为基本算法;为描述种群多样性,重点研究了信息熵原理,提出了基于栅格思想的路径种群熵概念,实现了种群多样性的测量;在此基础上,进一步提出了基于路径种群熵的双轮盘赌选择策略,给出了基于路径种群熵的自适应交叉、变异概率计算公式,达到了在算法前期保持种群多样性,而在算法后期加快收敛速度的目的,提高了算法性能,克服了算法缺陷;提出了先启发生成再优化的初始种群生成方法,提高了初始种群的个体质量;提出了基于区域的碰撞检测方法,减少了检测次数,提高了算法效率。
最后,利用本文设计算法进行了路径规划仿真,得到了理想的结果,验证了本文算法的有效性。同时与原有的自适应遗传算法进行了仿真对比,通过实际效果的差异验证了本文算法的优越性。
As technology progresses, the ship navigation are gradually moving towards the direction of the development of intelligent and path planning is one of the key technologies of it. In the background of path planning of ship and on the platform of electronic chart, the paper makes the thorough research in path planning for ship sailing in the real marine environment. Information entropy-genetic algorithm which applied to the field of path planning is proposed based on the integration of information entropy and genetic arithmetic and the characteristics of path planning. The defects of traditional genetic algorithm in path planning, time-consuming and falling into local solutions are overcome.
For the characteristics of the display of electronic chart, this paper adopts polygonal obstacles and path-point coding presentation, and genetic algorithm as the basic algorithm. To describe the diversity of population, a concept of path population entropy is proposed based on grid concept and focusing research on the information entropy principle and realize the diversity of population measurement. On this basis, the paper further proposed the dual -wheeled-gambling selection strategy based on path population entropy and given the adaptive formula of variation rate and cross rate based on path population entropy, reaches purpose of maintaining diversity of population in the early part of algorithm and speeding up the convergence of the algorithm in the latter part of algorithm. A method of createing initial population which optimizeing path after creating path is proposed and the quality of the initial population is improved. To reduce the detection times, a region-based collision detection method is proposed and the efficiency of the algorithm is improved.
Finally, the use of algorithms designed in this paper a path planning simulation, has been the ideal outcome, validate the effectiveness of the algorithm. At the same time with the original self-adaptive genetic algorithm simulation comparison, through the difference between the actual results validate the superiority of the algorithm.
引文
[1] Joao Sequeira, Maria Isabel Ribeiro.A Two Level Approach For Underwater Path Planning[J].Proceedings of the OCEANS’94,1994,Ⅱ-78,Ⅱ-91P
[2] K Sugihara.GA-based motion planning for underwater robotic Vehicle.Pore.10th in’l Symp. On Unmanned Untethered Submersible Technology.,1997,406-415P
[3] http://news.sina.com.cn/w/2004-07-06/17133007134s.shtml
[4]禹建丽,成久洋之,Valeri.Kroumov等.线性再励的自适应变步长机器人神经网络路径规划算法[J].燕山大学学报,2002,26(3):258-267页
[5]徐治非.基于海图数据的AUV全局路径规划方法研究[D].哈尔滨工程大学硕士学位论文,2004
[6]蒋新松.机器人学导论[M].辽宁:辽宁科学技术出版社,1994:511-515页, 534-554页
[7] J.T Schwartz, M.Shair. A Survey of Motion Planning and Related Geometric Algorithms[J]. Artificial Intelligence, 1988, 37 (1-3) : 157–169P
[8]周远清等.智能机器人系统[M].北京:清华大学出版社,1989:1-5页
[9]陈曦.基于免疫遗传算法的移动机器人路径规划研究[D].中南大学硕士学位论文,2008:10页
[10]雷亮.基于进化算法的移动机器人路径规划研究[D].江南大学硕士学位论文,2008:7-8页
[11]屠大维,林财兴.智能机器人视觉体系结构研究[J].机器人,2001,23(3): 206-210页
[12]耿兆丰,吴永敢.基于势场的运动避碰规划[J].机器人,1992,14(5):38-43页
[13]饶森.水面无人艇的全局路径规划技术研究[D].哈尔滨工程大学硕士学位论文,2007:8-9页
[14]李珂,王正平.多架无人机的协同攻击航路规划[J].航空计算技术,2006, 35(5):98-101页
[15]李涛.基于遗传算法的多UAV路径规划技术研究[D].哈尔滨工程大学硕士学位论文,2007:5-6页
[16]管乐乐.某型AUV全局路径规划技术研究[D].哈尔滨工程大学硕士学位论文,2007:9页
[17]陈华志,谢存禧.移动机器人导航及相关技术研究[J].机床与液压,2003, (4):12-15页
[18] Pere.Automatic planning of manipulator movement.IEEE Trans on Sys Man Cybern.1984,11(11):681-698页
[19]王志文,郭戈.移动机器人导航技术现状与展望[J].机器人,2003,25(5): 470-470页
[20] Habib M K,Asama H.Efficient method to generate collision free path for autonomous mobile robot based on new free space structuring approach[J] .Proc,IEEE/RSJ IROS,1999:563-567P
[21]黄建生.移动机器人路径规划研究[D].浙江大学硕士学位论文,2008,9页
[22] M B Metea.Planning for Intelligence Autonomous Land Vehi-clesusing Hierarchical Terrain Representation.Proc of IEEE Int Conf on Robotics and Automation, 1987,5(1):1947-1952P
[23]余炎峰.基于免疫遗传算法的移动机器人全局路径规划[D].合肥工业大学硕士学位论文,2007,12-13页
[24] Fierro R,Lewis F L.Control of nonholonomic mobile robot using neural networks[J].IEEE Trans on Neural Networks.1998,9(4):589-600P
[25]王丽.移动机器人路径规划方法研究[D].西北工业大学硕士学位论文,2007:11-12页
[26]孙羽,张汝波.神经网络在智能机器人导航系统中的应用研究[J].计算机工程,2002,28(1):128-140页
[27]王磊.海洋环境下水下机器人快速路径规划研究[D].哈尔滨工程大学硕士学位论文,2007:15页
[28] M Dorigo,V Maniezzo,A Colorni.Ant System:optimization by a colony by cooperating agent[J].IEEE Transaction on Systems,Man and Cyberbetics.1996,26(1):29-41P
[29]金飞虎,洪炳熔,高庆吉.基于蚁群算法的自由飞行空间机器人路径规划[J].机器人,2002,24(6):526-529页
[30]陈少斌.自主移动机器人路径规划及轨迹跟踪的研究.浙江大学博士论文,2008,41-43页
[31]陈浩.遗传算法在频率指配问题中的应用研究[D].北京交通大学硕士学位论文,2009,5-6页
[32]王正志,薄涛.进化计算[M].湖南:国防科技大学出版社,2002,10-15页
[33] (美)米凯利维茨.Z.演化程序:遗传算法和数据编码的结合[M].北京:科学出版社,2000,15-25页
[34]潘正君.演化计算[M].北京:清华大学出版社, 1998: 13-17页
[35] (日)玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000: 35-44页
[36]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2002:23-35页
[37]周明,孙树栋.遗传算法理论及应用[M].北京:国防工业出版社,1999: 27-40页
[38] (日)玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社, 2004: 36-45页
[39]陈国良.遗传算法及其应用[M].北京:人民邮电出版社, 1999: 25-29页
[40]张文修,梁怡.遗传算法的数学基础.第二版[M].西安:西安交通大学出版社, 2003: 28-34页
[41]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002:34-42页
[42]韩建松,吴贵芳,徐科,徐金梧.遗传算法在缺陷特征选择中的研究[J].计算机工程与应用,2009,45(15):241-244页
[43] DeJong,K.A.An analysis of the behvaeior of a class of genetic dapatic system(Ph.D Dissertation).Unverstiy of Mihcigan,1975,76-109P
[44] SrinivasM,PatnaikL.M.Adpative Probbailities of Crossover and Mutations in Gas[J].IEEE Trans.On SMC,1994,24(4):656-667P
[45]王仲民,岳宏,刘继岩.基于改进模拟退火算法的移动机器人路径规划[J].计算机工程与应用, 2005, (19) :68-73页
[46]孙秀云.基于遗传模拟退火算法的机器人全局路径规划[J].机械工程与自动化, 2007, (04):68-73页
[47] C. Shannon. A Mathematical Theory of Communication .Bell System Technical Journal, July, Oct. 1948,27:379-423, 27:379-423 :623-656
[48]曹雪虹,张宗橙.信息论与编码[M].北京:清华大学出版社,2004
[49] J. T. Tsai T. K. Liu,J. H. Chou. Hybrid Taguchi Genetic Algorithm for Global Numerical Optimization .IEEE Transactions on Evolutionary Computation, 2004,8, 8 (4) :365-377P
[50] Sebald A V, Schlenzig J. Minimax design of neural net controllers for highly uncertain plants .IEEE Transactions on Neural Networks, 1994,5, 5 (1) :73-82 P
[51] Robert M Gray. Entropy and Information Theory[M] .New York: Springer-Verlag, 1990
[52]张殿祜,方绍辉,丁潇君.熵——度量随机变量不确定性的一种尺度[J]系统工程与电子技术, 1997,(11) :58-64页
[53]彭代渊.信息论与编码理论[M].武汉:武汉大学出版社,2008
[54]姜丹.信息论与编码[M].合肥:中国科学技术大学出版社,2004
[55]蔡溪尧.信息论基础[M].哈尔滨:军事工程学院出版社,1964
[56]李亚芳,李章维.一种基于信息熵的自适应遗传算法[J].浙江工业大学学报,2007,35(6):666-670页
[57]岳承君,尹凤杰,井元伟.基于信息熵多种群遗传算法的组播路由[J].计算机工程, 2009, (11):156-160页
[58]李慧贤,庞辽军,蔡皖东.基于信息熵对遗传算法中杂交概率的研究[J].系统工程与电子技术, 2009, (07) :1743-1745页
[59] Gunter Rudolph. Convergence Analysis of Canonical Genetic Algorithms,IEEE Transactions on neural networks,1994,5(l):96-101P
[60]刘铁男,姜建国,陈继刚等.遗传算法的收敛性分析[J].大庆石油学院学报,2000,24(3):40-42页
[61]卢瑾.基于遗传算法的机器人路径规划研究[D].浙江工业大学硕士学位论文,2005
[62]李小平,王凤儒.优解保留遗传算法收敛性的研究[J].电机与控制学报, 2000,4(1):52-58页
[63]马晓岩,倪骏一种改进型遗传算法及其收敛性分析[J].系统工程与电子技术,2000,22(9):58-60页
[64] Roman Smierzchalski, Zbigniew Michalewicz. Modeling of Ship Trajectory in Collision Situations by an Evolutionary Algorithm .IEEE Trans. On Evolutionary, 2000,3, 3 (4) :227-241P
[65] Zou X B, Cai Z X, Sun G R. Non-smooth Environment Modeling and Global Path Planning for Mobile Robots .Journal of Central South University of Technology, 2003,103, 10(3) :248-254P
[66]蒋卓强.基于遗传模拟退火算法的静态路径规划研究[D].重庆大学硕士学位论文,2007,32-34页
[67]邓洋春,梁昔明.一种改进操作算子的加速收敛遗传算法[J]现代电子技术, 2009,22(02):68-89页
[68] T.M.Cover,J.A.Thomas. Elements of Information Theory[M] .New York: Wiley, 1991, :20-31
[2] K Sugihara.GA-based motion planning for underwater robotic Vehicle.Pore.10th in’l Symp. On Unmanned Untethered Submersible Technology.,1997,406-415P
[3] http://news.sina.com.cn/w/2004-07-06/17133007134s.shtml
[4]禹建丽,成久洋之,Valeri.Kroumov等.线性再励的自适应变步长机器人神经网络路径规划算法[J].燕山大学学报,2002,26(3):258-267页
[5]徐治非.基于海图数据的AUV全局路径规划方法研究[D].哈尔滨工程大学硕士学位论文,2004
[6]蒋新松.机器人学导论[M].辽宁:辽宁科学技术出版社,1994:511-515页, 534-554页
[7] J.T Schwartz, M.Shair. A Survey of Motion Planning and Related Geometric Algorithms[J]. Artificial Intelligence, 1988, 37 (1-3) : 157–169P
[8]周远清等.智能机器人系统[M].北京:清华大学出版社,1989:1-5页
[9]陈曦.基于免疫遗传算法的移动机器人路径规划研究[D].中南大学硕士学位论文,2008:10页
[10]雷亮.基于进化算法的移动机器人路径规划研究[D].江南大学硕士学位论文,2008:7-8页
[11]屠大维,林财兴.智能机器人视觉体系结构研究[J].机器人,2001,23(3): 206-210页
[12]耿兆丰,吴永敢.基于势场的运动避碰规划[J].机器人,1992,14(5):38-43页
[13]饶森.水面无人艇的全局路径规划技术研究[D].哈尔滨工程大学硕士学位论文,2007:8-9页
[14]李珂,王正平.多架无人机的协同攻击航路规划[J].航空计算技术,2006, 35(5):98-101页
[15]李涛.基于遗传算法的多UAV路径规划技术研究[D].哈尔滨工程大学硕士学位论文,2007:5-6页
[16]管乐乐.某型AUV全局路径规划技术研究[D].哈尔滨工程大学硕士学位论文,2007:9页
[17]陈华志,谢存禧.移动机器人导航及相关技术研究[J].机床与液压,2003, (4):12-15页
[18] Pere.Automatic planning of manipulator movement.IEEE Trans on Sys Man Cybern.1984,11(11):681-698页
[19]王志文,郭戈.移动机器人导航技术现状与展望[J].机器人,2003,25(5): 470-470页
[20] Habib M K,Asama H.Efficient method to generate collision free path for autonomous mobile robot based on new free space structuring approach[J] .Proc,IEEE/RSJ IROS,1999:563-567P
[21]黄建生.移动机器人路径规划研究[D].浙江大学硕士学位论文,2008,9页
[22] M B Metea.Planning for Intelligence Autonomous Land Vehi-clesusing Hierarchical Terrain Representation.Proc of IEEE Int Conf on Robotics and Automation, 1987,5(1):1947-1952P
[23]余炎峰.基于免疫遗传算法的移动机器人全局路径规划[D].合肥工业大学硕士学位论文,2007,12-13页
[24] Fierro R,Lewis F L.Control of nonholonomic mobile robot using neural networks[J].IEEE Trans on Neural Networks.1998,9(4):589-600P
[25]王丽.移动机器人路径规划方法研究[D].西北工业大学硕士学位论文,2007:11-12页
[26]孙羽,张汝波.神经网络在智能机器人导航系统中的应用研究[J].计算机工程,2002,28(1):128-140页
[27]王磊.海洋环境下水下机器人快速路径规划研究[D].哈尔滨工程大学硕士学位论文,2007:15页
[28] M Dorigo,V Maniezzo,A Colorni.Ant System:optimization by a colony by cooperating agent[J].IEEE Transaction on Systems,Man and Cyberbetics.1996,26(1):29-41P
[29]金飞虎,洪炳熔,高庆吉.基于蚁群算法的自由飞行空间机器人路径规划[J].机器人,2002,24(6):526-529页
[30]陈少斌.自主移动机器人路径规划及轨迹跟踪的研究.浙江大学博士论文,2008,41-43页
[31]陈浩.遗传算法在频率指配问题中的应用研究[D].北京交通大学硕士学位论文,2009,5-6页
[32]王正志,薄涛.进化计算[M].湖南:国防科技大学出版社,2002,10-15页
[33] (美)米凯利维茨.Z.演化程序:遗传算法和数据编码的结合[M].北京:科学出版社,2000,15-25页
[34]潘正君.演化计算[M].北京:清华大学出版社, 1998: 13-17页
[35] (日)玄光男,程润伟.遗传算法与工程设计[M].北京:科学出版社, 2000: 35-44页
[36]李敏强.遗传算法的基本理论与应用[M].北京:科学出版社,2002:23-35页
[37]周明,孙树栋.遗传算法理论及应用[M].北京:国防工业出版社,1999: 27-40页
[38] (日)玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社, 2004: 36-45页
[39]陈国良.遗传算法及其应用[M].北京:人民邮电出版社, 1999: 25-29页
[40]张文修,梁怡.遗传算法的数学基础.第二版[M].西安:西安交通大学出版社, 2003: 28-34页
[41]王小平,曹立明.遗传算法-理论、应用与软件实现[M].西安:西安交通大学出版社,2002:34-42页
[42]韩建松,吴贵芳,徐科,徐金梧.遗传算法在缺陷特征选择中的研究[J].计算机工程与应用,2009,45(15):241-244页
[43] DeJong,K.A.An analysis of the behvaeior of a class of genetic dapatic system(Ph.D Dissertation).Unverstiy of Mihcigan,1975,76-109P
[44] SrinivasM,PatnaikL.M.Adpative Probbailities of Crossover and Mutations in Gas[J].IEEE Trans.On SMC,1994,24(4):656-667P
[45]王仲民,岳宏,刘继岩.基于改进模拟退火算法的移动机器人路径规划[J].计算机工程与应用, 2005, (19) :68-73页
[46]孙秀云.基于遗传模拟退火算法的机器人全局路径规划[J].机械工程与自动化, 2007, (04):68-73页
[47] C. Shannon. A Mathematical Theory of Communication .Bell System Technical Journal, July, Oct. 1948,27:379-423, 27:379-423 :623-656
[48]曹雪虹,张宗橙.信息论与编码[M].北京:清华大学出版社,2004
[49] J. T. Tsai T. K. Liu,J. H. Chou. Hybrid Taguchi Genetic Algorithm for Global Numerical Optimization .IEEE Transactions on Evolutionary Computation, 2004,8, 8 (4) :365-377P
[50] Sebald A V, Schlenzig J. Minimax design of neural net controllers for highly uncertain plants .IEEE Transactions on Neural Networks, 1994,5, 5 (1) :73-82 P
[51] Robert M Gray. Entropy and Information Theory[M] .New York: Springer-Verlag, 1990
[52]张殿祜,方绍辉,丁潇君.熵——度量随机变量不确定性的一种尺度[J]系统工程与电子技术, 1997,(11) :58-64页
[53]彭代渊.信息论与编码理论[M].武汉:武汉大学出版社,2008
[54]姜丹.信息论与编码[M].合肥:中国科学技术大学出版社,2004
[55]蔡溪尧.信息论基础[M].哈尔滨:军事工程学院出版社,1964
[56]李亚芳,李章维.一种基于信息熵的自适应遗传算法[J].浙江工业大学学报,2007,35(6):666-670页
[57]岳承君,尹凤杰,井元伟.基于信息熵多种群遗传算法的组播路由[J].计算机工程, 2009, (11):156-160页
[58]李慧贤,庞辽军,蔡皖东.基于信息熵对遗传算法中杂交概率的研究[J].系统工程与电子技术, 2009, (07) :1743-1745页
[59] Gunter Rudolph. Convergence Analysis of Canonical Genetic Algorithms,IEEE Transactions on neural networks,1994,5(l):96-101P
[60]刘铁男,姜建国,陈继刚等.遗传算法的收敛性分析[J].大庆石油学院学报,2000,24(3):40-42页
[61]卢瑾.基于遗传算法的机器人路径规划研究[D].浙江工业大学硕士学位论文,2005
[62]李小平,王凤儒.优解保留遗传算法收敛性的研究[J].电机与控制学报, 2000,4(1):52-58页
[63]马晓岩,倪骏一种改进型遗传算法及其收敛性分析[J].系统工程与电子技术,2000,22(9):58-60页
[64] Roman Smierzchalski, Zbigniew Michalewicz. Modeling of Ship Trajectory in Collision Situations by an Evolutionary Algorithm .IEEE Trans. On Evolutionary, 2000,3, 3 (4) :227-241P
[65] Zou X B, Cai Z X, Sun G R. Non-smooth Environment Modeling and Global Path Planning for Mobile Robots .Journal of Central South University of Technology, 2003,103, 10(3) :248-254P
[66]蒋卓强.基于遗传模拟退火算法的静态路径规划研究[D].重庆大学硕士学位论文,2007,32-34页
[67]邓洋春,梁昔明.一种改进操作算子的加速收敛遗传算法[J]现代电子技术, 2009,22(02):68-89页
[68] T.M.Cover,J.A.Thomas. Elements of Information Theory[M] .New York: Wiley, 1991, :20-31