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

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

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