。1086。 北京科技大学学报 2006年第11期 【4武元新.人工智能中A‘算法的局部改进及其实现微型电 Indianapolis.1997:401 脑应用，200016(3)：21 【刀段俊花李孝安.基于改进遗传算法的机器人路径规划。微 [5]Yang S X.M eng M.An efficient neural net work approach to 电子学与计算机200522(1)：70 dynamic robot motion planning.Neural Networks 2000.13 [8 Wu W,Ruan QQ.A gene-constrained genctic algorithm for (2):143 solving shortest path problem //Proceedings of the 7th Inter [6]Gen M.Cheng R W,Wang D W.Genetic algorithms for natioral Conference on Signal Processing.Beiing,2004:2510 solving shortest path problems /Pmoceedings of the 1997 【9身李擎张伟，尹怡欣。等.一种用于最优路径规划的改进遗 IEEE International Conference on Evolutionary Computation. 传算法.信息与控制200635(4)：444 A self-adaptive genetic algorithm for the shortest path planning of vehicles and its comparison with Dijkstra and A algorithms LI Qing,XIE Sijiang?.TONG Xinhai2.WANG Zhiliang 1) 1)Information Engineering School University of Science and Technology Beijing,Beijing 100083 China 2)Scientific Research Center.Beijing Elect mnic Science and Technobgy Institute Beijng 100070 China ABSTRACT 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.Simulat ion results under 5 different circumstances show that the pro- posed genetic algorithm can decrease the searching time for shortest path compared with Dijkstra algorithm and obtain more shortest paths than A'algorithm. KEY WORDS shortest path planning;vehicle guidance;genetic algo rithm;self-adaptive adjustment (C)1994-2019 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net[ 4] 武元新.人工智能中 A ＊算法的局部改进及其实现.微型电 脑应用, 2000 , 16(3):21 [ 5] Yang S X , M eng M .An efficient neural network approach to dynamic robot motion planning .Neural Networks, 2000 , 13 (2):143 [ 6] Gen M , Cheng R W , Wang D W .Genetic algorithms for solving short est path problems ∥ Proceedings of the 1997 IEEE International Conference on Evolutionary Computation. Indianapolis, 1997:401 [ 7] 段俊花, 李孝安.基于改进遗传算法的机器人路径规划.微 电子学与计算机, 2005 , 22(1):70 [ 8] Wu W, Ruan Q Q .A gene-constrained geneti c algorithm for solving short est path problem ∥Proceedings of the 7 th Inter￾national Conference on Signal Processing .Beijing , 2004:2510 [ 9] 李擎, 张伟, 尹怡欣, 等.一种用于最优路径规划的改进遗 传算法.信息与控制, 2006 , 35(4):444 A self-adaptive genetic algo rithm for the sho rtest path planning of vehicles and its comparison with Dijkstra and A ＊algorithms LI Qing 1) , XIE Sijiang 2) , TONG Xinhai 2) , WANG Zhiliang 1) 1)Information Engineering School, University of S cience and Technology Beijing , Beijing 100083 , China 2)Scientific Research Center , Beijing Electronic S cience and Technology Institut e, Beijing 100070 , China ABSTRACT A self-adaptive genetic algorithm w as proposed and successfully applied for the shortest path planning of vehicles .The encoding scheme , crossover and mutation operators w ere specifically designed for shortest path planning problems in the proposed genetic algorithm .A new online self-adaptive adjustment strategy fo r crossover and mutation probabilities w as 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 pro￾posed genetic algorithm can decrease the searching time for sho rtest path compared with Dijkstra algorithm and obtain more shortest paths than A ＊ algorithm . KEY WORDS shortest path planning ;vehicle guidance;genetic algo rithm ;self-adaptive adjustment · 1086 · 北 京 科 技 大 学 学 报 2006 年第 11 期