计算机工程与应用 ›› 2017, Vol. 53 ›› Issue (20): 111-115.DOI: 10.3778/j.issn.1002-8331.1604-0288

• 模式识别与人工智能 • 上一篇    下一篇

基于最优模式探测的改进遗传路径规划算法

李克伟1,张丹丹2,周之平2   

  1. 1.南昌航空大学 无损检测教育部重点实验室,南昌 330063
    2.南昌航空大学 信息工程学院,南昌 330063
  • 出版日期:2017-10-15 发布日期:2017-10-31

Improved genetic path planning algorithm based on optimal schema probing mechanism

LI Kewei1, ZHANG Dandan2, ZHOU Zhiping2   

  1. 1.Key Laboratory of Nondestructive Testing, Ministry of Education, Nanchang Hangkong University, Nanchang 330063, China
    2.School of Information Engineering, Nanchang Hangkong University, Nanchang 330063, China
  • Online:2017-10-15 Published:2017-10-31

摘要: 针对复杂环境下传统遗传路径规划时可行路径修复困难、易于早熟收敛等不足,提出一种基于最优模式探测机制的改进遗传算法。该算法将中值插入修复与邻域搜索和路径点回退操作相结合增强路径修复效率;通过自适应截断变异提高空间探索能力;引入混杂多点交叉和模式优化策略改善算法的优化性能。仿真结果表明新方法的有效性。

关键词: 路径规划, 邻域搜索, 局部截断变异, 混杂多点交叉

Abstract: Due to the shortcomings of traditional genetic path planning algorithm under complex environments, such as difficulty in repairing feasible path and the feature of premature convergence, an improved genetic algorithm based on optimum schema probing mechanism is presented. The novel algorithm has found that neighborhood searching can enhance the repair efficiency when combining it with middle-value insertion and waypoint backtracking; in addition, the operation that adaptively truncated mutation can improve the ability of space exploration; both hybrid multi-point crossover and schema optimization strategy can strengthen the optimization performance of algorithm. This method has been proved to be correct and valid in simulation experiment.

Key words: path planning, neighborhood searching, adaptively truncated mutation, hybrid multi-point crossover