一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A^＊算法的比较

A self-adaptive genetic algorithm for the shortest path planning of vehicles and its comparison with Dijkstra and A* algorithms

提出了一种自适应遗传算法,并成功应用于车辆最短路径规划算法中.所采用的编码方式、交叉及变异算子等均针对最短路径规划问题而专门设计;同时,提出了一种新的交叉概率、变异概率在线自适应调整策略,以便提高遗传算法的搜索速度和搜索质量.将该算法同Dijkstra算法、A*算法进行了仿真比较.对五种不同情况的仿真研究结果表明:同Dijkstra算法相比,该自适应遗传算法可以减少搜索到最短路径的时间;同A*算法相比,该自适应遗传算法则可以搜索到更多的最短路径.

A self-adaptive genetic algorithm was proposed and successfully applied for the shortest path planning of vehicles. The encoding scheme, crossover and mutation operators were specifically designed for shortest path planning problems in the proposed genetic algorithm. A new online self-adaptive adjustment strategy for crossover and mutation probabilities was also investigated in order to improve the search speed and search quality of genetic algorithm. The comparison of the proposed genetic algorithm with Dijkstra and A^＊ algorithms was carried out. Simulation results under 5 different circumstances show that the proposed genetic algorithm can decrease the searching time for shortest path compared with Dijkstra algorithm and obtain more shortest paths than A^＊ algorithm.