基于粒子群优化算法的船舶航迹规划方法研究
摘要
随着人类对海洋资源开发和海洋权益的日趋关注,人们对船舶实现智能控制和自主导航的期望和要求也越来越高,航迹规划技术在很大程度上直接关系到船舶航行操纵自动化、智能化水平的高低。其研究目的在于如何使船舶更好的完成上层指令规定的任务,按照一定的准则自动规划出由起始点到指定目标位置的最优航线。从算法执行过程来看,航迹规划主要是实现船舶在障碍环境中的航迹寻优,可以归结为优化搜索问题。实践已经证明,粒子群优化算法能够很好的解决诸多工程应用领域的复杂非线性优化问题。本文主要针对基于粒子群优化算法的船舶航迹规划问题进行研究,主要研究工作如下：
1.概述了粒子群算法的基本原理及其特点、算法的标准模型及典型改进策略、算法的种群拓扑结构,通过数值仿真实验对影响粒子群算法的主要参数进行了定性分析和讨论。
2.对粒子群算法的种群多样性问题进行了分析,讨论了变异操作和惯性权值对种群多样性的影响,并在此基础上提出了一种基于模糊逻辑的粒子群算法FPSO。通过使用SPSO、LDWPSO、FPSO三种算法对标准测试函数进行求解,验证了FPSO算法具有更好的收敛性和全局寻优能力。
3.设计了基于FPSO的船舶二维空间全局航迹规划算法,给出了航迹规划问题的数学定义和环境建模方法,讨论了航迹规划的评估准则、启发式知识的运用、算法编码方案与数据结构,确定了适应值评价函数,并针对不同环境模型进行了算法仿真实验,证明了该算法能够有效地实现船舶在二维空间的全局航迹规划。
4.考虑到航迹规划问题的复杂性,提出了多航迹规划的概念,设计了基于FPSO的多航迹规划算法。给出了算法的基本思想和算法流程,深入讨论了算法中粒子群的生成方法、粒子群的多样化方法、多种群的隔离进化策略,并针对多个仿真环境进行了算法仿真实验,验证了算法的正确性、有效性。
With more and more attention to marine resource and sea rights day-by-day, the people realize the intelligent control and the autonomous navigation request and the expectation to the ships are also getting higher and higher, track plan technology to a great extent direct relation ships navigation operation intelligence level height. The purpose of the study is how to complete the top command ship mandate better, in accordance with certain criteria automatically planning target location specified by the starting point to the optimal route. The track plan issue can be concluded as the optimize searching problems. At the same time, practice has proved that PSO can be a good solution to many complicated nonlinear optimization problems. This thesis developed to the ships track plan method applied research based on the PSO, the main research work is as follows:
The thesis introduced the particle swarm algorithm's basic principle and the characteristic firstly, and has given the algorithm standard model and the algorithm improvement strategy, then has carried on the analysis to the population topology. Finally used the value simulation experiment's method to come to affect the Particle Swarm algorithm of the main primitive parameter to carry on the qualitative analysis.
Then, analyzed the diversity of the particle swarm algorithm, discussed of the mutation and the inertia weight on diversity, this thesis proposed particle swarm optimization algorithm based on fuzzy logic(FPSO), unifies 4 commonly standard trial function to FPSO, SPSO, LDWPSO algorithm to carry on the simulation experiment, finally verified that this FPSO algorithm has better convergence and overall search capability the solution has certain superiority on precision aspect.
In based on fuzzy logic Particle Swarm algorithm's foundation, proposed the ships two-dimensional space overall situation track planning algorithm design, given the mathematical definition and environment modeling of ship track planning, discussed the assessment criteria, coding program and data structures to determine the fitness evaluation function. Simulation experiment indicate that the algorithm may effective complete the ships track planning in the two-dimensional space overall situation.
As the result of the ship track planning's complexity, this thesis proposed the multi-track planning concept, conducted the multi-track planning algorithm research and the design. Given the basic idea of the algorithm and the algorithm flow, discussed the formation of particle swarm, particle swarm diversity methods, a variety of group evolutionary strategy of isolation. Finally run the algorithm under different environment, the analysis result has indicated this algorithm's validity, usability and feasibility.
1.概述了粒子群算法的基本原理及其特点、算法的标准模型及典型改进策略、算法的种群拓扑结构,通过数值仿真实验对影响粒子群算法的主要参数进行了定性分析和讨论。
2.对粒子群算法的种群多样性问题进行了分析,讨论了变异操作和惯性权值对种群多样性的影响,并在此基础上提出了一种基于模糊逻辑的粒子群算法FPSO。通过使用SPSO、LDWPSO、FPSO三种算法对标准测试函数进行求解,验证了FPSO算法具有更好的收敛性和全局寻优能力。
3.设计了基于FPSO的船舶二维空间全局航迹规划算法,给出了航迹规划问题的数学定义和环境建模方法,讨论了航迹规划的评估准则、启发式知识的运用、算法编码方案与数据结构,确定了适应值评价函数,并针对不同环境模型进行了算法仿真实验,证明了该算法能够有效地实现船舶在二维空间的全局航迹规划。
4.考虑到航迹规划问题的复杂性,提出了多航迹规划的概念,设计了基于FPSO的多航迹规划算法。给出了算法的基本思想和算法流程,深入讨论了算法中粒子群的生成方法、粒子群的多样化方法、多种群的隔离进化策略,并针对多个仿真环境进行了算法仿真实验,验证了算法的正确性、有效性。
With more and more attention to marine resource and sea rights day-by-day, the people realize the intelligent control and the autonomous navigation request and the expectation to the ships are also getting higher and higher, track plan technology to a great extent direct relation ships navigation operation intelligence level height. The purpose of the study is how to complete the top command ship mandate better, in accordance with certain criteria automatically planning target location specified by the starting point to the optimal route. The track plan issue can be concluded as the optimize searching problems. At the same time, practice has proved that PSO can be a good solution to many complicated nonlinear optimization problems. This thesis developed to the ships track plan method applied research based on the PSO, the main research work is as follows:
The thesis introduced the particle swarm algorithm's basic principle and the characteristic firstly, and has given the algorithm standard model and the algorithm improvement strategy, then has carried on the analysis to the population topology. Finally used the value simulation experiment's method to come to affect the Particle Swarm algorithm of the main primitive parameter to carry on the qualitative analysis.
Then, analyzed the diversity of the particle swarm algorithm, discussed of the mutation and the inertia weight on diversity, this thesis proposed particle swarm optimization algorithm based on fuzzy logic(FPSO), unifies 4 commonly standard trial function to FPSO, SPSO, LDWPSO algorithm to carry on the simulation experiment, finally verified that this FPSO algorithm has better convergence and overall search capability the solution has certain superiority on precision aspect.
In based on fuzzy logic Particle Swarm algorithm's foundation, proposed the ships two-dimensional space overall situation track planning algorithm design, given the mathematical definition and environment modeling of ship track planning, discussed the assessment criteria, coding program and data structures to determine the fitness evaluation function. Simulation experiment indicate that the algorithm may effective complete the ships track planning in the two-dimensional space overall situation.
As the result of the ship track planning's complexity, this thesis proposed the multi-track planning concept, conducted the multi-track planning algorithm research and the design. Given the basic idea of the algorithm and the algorithm flow, discussed the formation of particle swarm, particle swarm diversity methods, a variety of group evolutionary strategy of isolation. Finally run the algorithm under different environment, the analysis result has indicated this algorithm's validity, usability and feasibility.
引文
[1]Kennedy J, Eberhart.RC. Particle Swarm Optimization [A]. Proceedings of IEEE International Conference on Neural Networks. Piscataway.1995:193-197.
[2]Shi Y, Eberhart R C. Empirical study of particle swarm optimization [A]. Proceeding of Congress on Evolutionary Computation:Piscataway,NJ:IEEE Service Center,1999.1945-1949.
[3]杨维,李歧强.粒子群优化算法综述[J].中国工程科学.2004,6(5)：87-94.
[4]赫然,王永吉,王青.一种改进的自适应逃逸微粒群算法及实验分析[J].软件学报.2005,16(12)：2036-2044.
[5]Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization [A], Evolutionary Programming Ⅶ:Proceedings of the Seventh Annual Conference on Evolutionary Programming,New York,1998:591-600.
[6]赫然,王永吉,王青.一种改进的自适应逃逸微粒群算法及实验分析[J].软件学报.2005,16(12)：2036-2044.
[7]Xie XF, Zhang WJ, Yang ZL. A dissipative particle swarm optimization[A]. In:Proc. of the IEEE Int'l Conf. on Evolutionary Computation. Honolulu:IEEE Inc.,2002:1456-1461.
[8]Lovbjerg M, Krink T. Extending particle swarm optimizers with self-organized critically [A]. In:Proc. of the IEEE Int'l Conf. on Evolutionary Computation. Honolulu:IEEE Inc.,2002:1588-1593.
[9]Ratnaweera A, Halgamuge SK, Watson HC. Self-Organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J]. IEEE Trans. on Evolutionary Computation,2004,8(3):240-255.
[10]张丽平.粒子群优化算法的理论及实践[D)].杭州：浙江大学博士学位论文.2005.
[11]Kennedy J, Mends R. Population structure and particle swarm performance [A]. Proceedings of IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA,2002, 1671-1676.
[12]Kennedy J. The particle swarm:social adaptiation of knowledge [A]. Proceedings of IEEE International Conference on Evolutionary Computation,1997,303-308.
[13]Mends R, Kennedy J, Neves J. The fully informed particle swarm:Simpler, Maybe better. [J] IEEE Transactions on Evolutionary Computation.2004,6(8):204-210.
[14]Kennedy J, Mends R. Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms [A]. Proceedings of the IEEE International Workshop on Soft Computing in Industrial Applications.2003:45-50.
[15]Tang P, Fang J. Faster and more stable-asymmetric bidirectional weighting topologies on PSO[J].Proceedings of the International Conference on Communications, Circuits and Systems.2006(3):2088-2092.
[16]Mohais A S, Ward C, Posthoff C. Randomized directed neighborhoods with edge migration in particle swarm optimization [A]. Proceedings of the Congress on Evolutionary Computation. 2004:548-555.
[17]Mohais A S, Mendes R, Ward C, Posthoff C. Neighborhood Re-Structuring in Particle Swarm Optimization [A]. Proceedings of the 18th Australian Joint Conference on Artificial Intelligence.2005:776-785.
[18]Shi Y, Eberhart R C.A modified particle swarm optimizer[A]. IEEE international conference of evolutionary computation. Anchorage, Alaska,1998:69-73.
[19]R K Ursem. Diversity-guided evolutionary algorithm[A]. The 7th Int'1 Conf on Parallel Problem Solving from Nature, LNCS2439. Berlin:Springer,2002.462-474.
[20]Shi Y, Eberhart R C A modified particle swarm optimization[A]. Proceedings of IEEE International Conference on Evolutionary Computation, Anchorage,1998,69-73.
[21]Shi Y, Eberhart R C. Fuzzy adaptive particle swarm optimizer[A]. Proceedings of Congress on Evolutionary Computation, Korea:IEEE Servive Center,2001,101-106.
[22]康琦,汪镭,吴启迪.微粒群多元最优信息的模糊自适应规划算法[J].信息与控制.2005,34(4)：439-443.
[23]罗强,李瑞浴,易东云.基于模糊文化算法的自适应粒子群优化[J].计算机工程与科学.2008,30(1)：88-92.
[24]Shi Y, Eberhart R C. A modified particle swarm optimizer[A]. IEEE international conference of evolutionary computation. Anchorage, Alaska,1998:69-73.
[25]胡炜.水下机器人自主导航作业系统[D].哈尔滨：哈尔滨工程大学硕士学位论文.1995
[26]彭艳.基于遗传算法的水下机器人大范围路径规划[J]应用科技.2003,Vol.30,No.2：18-21.
[27]Xiao Jing, Z. Michalewicz, L. Zhang, K. Trojanowski. Adaptive Evolutionary Planner/Navigator for Mobile Robots[J]. IEEE Trans. Evol. Comput,1997, Vol.1, No.4:18-28.
[28]李枚毅,蔡自兴.改进的进化编程及其在机器人路径规划中的应用[J].机器人.2000,Vol.22, No.6:490-494.
[29]Grefenstette J J. Incorporating Problem Specific Knowledge into Genetic Algorithms[M]. In: Davis L Ed. Genetic Algorithms and Simulated Annealing. Pitman.1987:42-60.
[30]李敏强,寇纪淞.多模态函数优化的协同多群体遗传算法[J].自动化学报.2002,Vol.28, No.4:497-504.
[31]De Jong K. A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems[D]. Ph. D Dissertation, University of Michigan,1975
[32]D.E.Goldberg, J.Richardson. Genetic Algorithms with sharing for multi-model function optimization [A]. Proceeding of the Second International Conference on Genetic Algorithms. Hillsdale,NJ:Lawrence Erlbaum Associates,1987,41-49.
[33]郝翔,李人厚.适用于复杂函数优化的多群体遗传算法[J].控制与决策.1998, Vol.13, No.3:263-266.
[34]刘铁男,陈广义,刘延力,徐宝昌.模拟生物种族形成的进化算法与多峰函数优化[J].控制与决策.1999, Vol,14, No.2:185-188.
[35]周驰,高亮,高海兵.基于PSO的置换流水车间调度算法[J].电子学报.2006,34(11)：2008-2012.
[36]倪超,李奇,夏良正.基于广义混沌混合PSO的快速红外图像分割算法[J].光子学报.2007,10：1954-1959.
[37]季一木,王汝传.基于粒子群的网格任务调度算法研究[J].通信学报.2007,10：60-66.
[2]Shi Y, Eberhart R C. Empirical study of particle swarm optimization [A]. Proceeding of Congress on Evolutionary Computation:Piscataway,NJ:IEEE Service Center,1999.1945-1949.
[3]杨维,李歧强.粒子群优化算法综述[J].中国工程科学.2004,6(5)：87-94.
[4]赫然,王永吉,王青.一种改进的自适应逃逸微粒群算法及实验分析[J].软件学报.2005,16(12)：2036-2044.
[5]Shi, Y. and Eberhart, R. C. Parameter selection in particle swarm optimization [A], Evolutionary Programming Ⅶ:Proceedings of the Seventh Annual Conference on Evolutionary Programming,New York,1998:591-600.
[6]赫然,王永吉,王青.一种改进的自适应逃逸微粒群算法及实验分析[J].软件学报.2005,16(12)：2036-2044.
[7]Xie XF, Zhang WJ, Yang ZL. A dissipative particle swarm optimization[A]. In:Proc. of the IEEE Int'l Conf. on Evolutionary Computation. Honolulu:IEEE Inc.,2002:1456-1461.
[8]Lovbjerg M, Krink T. Extending particle swarm optimizers with self-organized critically [A]. In:Proc. of the IEEE Int'l Conf. on Evolutionary Computation. Honolulu:IEEE Inc.,2002:1588-1593.
[9]Ratnaweera A, Halgamuge SK, Watson HC. Self-Organizing hierarchical particle swarm optimizer with time-varying acceleration coefficients [J]. IEEE Trans. on Evolutionary Computation,2004,8(3):240-255.
[10]张丽平.粒子群优化算法的理论及实践[D)].杭州：浙江大学博士学位论文.2005.
[11]Kennedy J, Mends R. Population structure and particle swarm performance [A]. Proceedings of IEEE Congress on Evolutionary Computation (CEC 2002), Honolulu, Hawaii USA,2002, 1671-1676.
[12]Kennedy J. The particle swarm:social adaptiation of knowledge [A]. Proceedings of IEEE International Conference on Evolutionary Computation,1997,303-308.
[13]Mends R, Kennedy J, Neves J. The fully informed particle swarm:Simpler, Maybe better. [J] IEEE Transactions on Evolutionary Computation.2004,6(8):204-210.
[14]Kennedy J, Mends R. Neighborhood topologies in fully-informed and best-of-neighborhood particle swarms [A]. Proceedings of the IEEE International Workshop on Soft Computing in Industrial Applications.2003:45-50.
[15]Tang P, Fang J. Faster and more stable-asymmetric bidirectional weighting topologies on PSO[J].Proceedings of the International Conference on Communications, Circuits and Systems.2006(3):2088-2092.
[16]Mohais A S, Ward C, Posthoff C. Randomized directed neighborhoods with edge migration in particle swarm optimization [A]. Proceedings of the Congress on Evolutionary Computation. 2004:548-555.
[17]Mohais A S, Mendes R, Ward C, Posthoff C. Neighborhood Re-Structuring in Particle Swarm Optimization [A]. Proceedings of the 18th Australian Joint Conference on Artificial Intelligence.2005:776-785.
[18]Shi Y, Eberhart R C.A modified particle swarm optimizer[A]. IEEE international conference of evolutionary computation. Anchorage, Alaska,1998:69-73.
[19]R K Ursem. Diversity-guided evolutionary algorithm[A]. The 7th Int'1 Conf on Parallel Problem Solving from Nature, LNCS2439. Berlin:Springer,2002.462-474.
[20]Shi Y, Eberhart R C A modified particle swarm optimization[A]. Proceedings of IEEE International Conference on Evolutionary Computation, Anchorage,1998,69-73.
[21]Shi Y, Eberhart R C. Fuzzy adaptive particle swarm optimizer[A]. Proceedings of Congress on Evolutionary Computation, Korea:IEEE Servive Center,2001,101-106.
[22]康琦,汪镭,吴启迪.微粒群多元最优信息的模糊自适应规划算法[J].信息与控制.2005,34(4)：439-443.
[23]罗强,李瑞浴,易东云.基于模糊文化算法的自适应粒子群优化[J].计算机工程与科学.2008,30(1)：88-92.
[24]Shi Y, Eberhart R C. A modified particle swarm optimizer[A]. IEEE international conference of evolutionary computation. Anchorage, Alaska,1998:69-73.
[25]胡炜.水下机器人自主导航作业系统[D].哈尔滨：哈尔滨工程大学硕士学位论文.1995
[26]彭艳.基于遗传算法的水下机器人大范围路径规划[J]应用科技.2003,Vol.30,No.2：18-21.
[27]Xiao Jing, Z. Michalewicz, L. Zhang, K. Trojanowski. Adaptive Evolutionary Planner/Navigator for Mobile Robots[J]. IEEE Trans. Evol. Comput,1997, Vol.1, No.4:18-28.
[28]李枚毅,蔡自兴.改进的进化编程及其在机器人路径规划中的应用[J].机器人.2000,Vol.22, No.6:490-494.
[29]Grefenstette J J. Incorporating Problem Specific Knowledge into Genetic Algorithms[M]. In: Davis L Ed. Genetic Algorithms and Simulated Annealing. Pitman.1987:42-60.
[30]李敏强,寇纪淞.多模态函数优化的协同多群体遗传算法[J].自动化学报.2002,Vol.28, No.4:497-504.
[31]De Jong K. A. An Analysis of the Behavior of a Class of Genetic Adaptive Systems[D]. Ph. D Dissertation, University of Michigan,1975
[32]D.E.Goldberg, J.Richardson. Genetic Algorithms with sharing for multi-model function optimization [A]. Proceeding of the Second International Conference on Genetic Algorithms. Hillsdale,NJ:Lawrence Erlbaum Associates,1987,41-49.
[33]郝翔,李人厚.适用于复杂函数优化的多群体遗传算法[J].控制与决策.1998, Vol.13, No.3:263-266.
[34]刘铁男,陈广义,刘延力,徐宝昌.模拟生物种族形成的进化算法与多峰函数优化[J].控制与决策.1999, Vol,14, No.2:185-188.
[35]周驰,高亮,高海兵.基于PSO的置换流水车间调度算法[J].电子学报.2006,34(11)：2008-2012.
[36]倪超,李奇,夏良正.基于广义混沌混合PSO的快速红外图像分割算法[J].光子学报.2007,10：1954-1959.
[37]季一木,王汝传.基于粒子群的网格任务调度算法研究[J].通信学报.2007,10：60-66.