Vol.28No.11李擎等：一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A算法的比较·1085· 法，它虽然能够保证找到最优解但其搜索速度较 径，所以对每张具有n个节点的地图而言，应该 慢，搜索效率非常低，时间花费较多，一般只能用 规划出n一1条最短路径. 于离线的路径规划问题；A算法则是人工智能中 对5张地图分别采用三种算法进行路径规 一种典型的启发式搜索算法，它不用遍历整个搜 划，三者各自搜索到最短路径的情况如表4所示. 索空间，而是根据所选择的启发式函数朝着最有 表中括号外数据为各算法实际得到最短路径数， 希望的方向前进，它的搜索速度虽然较快理论 括号内数据则为各算法实际得到最短路径数和应 上也能找到最优解，但在实际应用过程中往往由 该规划出的最短路径数n一1之比. 于启发式函数选取不当而经常找不到最短路径， 表4三种算法在授索质量方面的对比 即搜索的成功率并不是很高. Table 4 Comparison of the search quality of three algorithms 将遗传算法分别同Dijkstra算法和A*算法 节点数 Dijkstra算法 A"算法 遗传算法 进行仿真比较，用于比较的性能指标主要有两个： 16 15(100%) 12(80%) 15(100%) 一是搜索速度，用时间来表示：另一个是搜索到最 32 31(100%) 25(81%) 29(94%) 短路径的成功率，用百分数表示.利用C语言编 43 42(100%) 32(76%) 38(90%) 制了三种算法的最短路径搜索程序，运行程序的 62 61(100%) 40(66%) 56(92%) 计算机为AMD Turion64 Processor,512MB 示 77(100%) 45(58%) 71(92%) DDR.采用自行绘制的地图，共5张：第1张图16 个节点，共24条弧；第2张图32个节点，共55条 由表4可以看出：当地图节点个数和弧数量 弧：第3张图43个节点，共75条弧；第4张图62 比较多时，遗传算法搜索到最短路径的成功率虽 个节点，共111条弧：第5张图78个节点，共139 然比Dijkstra算法稍低一些（由于Dijkstra算法是 条弧. 一种遍历算法，所以每次能保证100%的搜索到 2.1搜索速度的比较 最短路径)，但比A算法要高得多，而且这种高 对5张地图分别采用Dijkstra算法、A算法 成功率在节点和弧的数量越大时表现得更加明 以及所提出的遗传算法进行路径规划，它们各自 显.故对于实际的电子地图而言，使用本文的遗 花费的搜索时间如表3所示 传算法将比A算法得到更多的最短路径， 表3三种算法在搜索速度上的对比 3结语 Table 3 Comparison of the search speed of three algorithms 搜索速度/s 针对车辆最短路径规划问题提出了一种自适 节点数 Dikstra算法 A算法 遗传算法 应遗传算法，同其他常见路径规划算法一Dk- 16 1 1 2 sta算法和A算法一相比，该自适应遗传算法 32 4 3 4 具有以下三个特点： 2 个 (1)同Dijkstra算法相比，其搜索成功率虽然 62 15 5 9 稍低一些但其搜索速度要比Dijkstra算法快很 78 25 7 12 多； (2)同A算法相比，其搜索速度虽然相对较 由表3可以看出：当地图节点个数和弧的条 慢，但却大大提高了搜索到最短路径的成功率； 数比较多时，遗传算法的搜索速度比A算法慢 (3)该遗传算法在搜索速度和搜索成功率二 但比Di冰sta算法快得多，而且这种快速性将随 者之间达到了一种折衷，为解决实际的车辆最短 着节点和弧数量的增加而变得更加明显.对于实 路径规划问题提供了一种新思路、新方法. 际的电子地图而言，由于节点和道路的数量一般 都很大，所以同Dijkstra算法相比，使用遗传算法 参考文献 在搜索速度方面将具有较大的优越性. 【刂龚洁辉白玲，高健美。最短路径算法的改进及其实现.解 2.2搜索成功率的比较 放军测绘学院学报。199815(2)：23 【)周培德.交通道路网中任意两点之间最短路径的快速算 对于具有n个节点的地图，其待规划节点的 法.计算机研究与发展，2002.24(2)：35 个数为n一1（除起始节点外，其他均可作为待规 【引段莉琼，朱建军，王庆社，等.改进的最短路径搜索A'算法 划范点电于每个待规划节点对究盂a条最短路c Publishf的商赛瑰海洋测徐3419tip小www.enki.net法,它虽然能够保证找到最优解,但其搜索速度较 慢,搜索效率非常低 ,时间花费较多, 一般只能用 于离线的路径规划问题;A ＊算法则是人工智能中 一种典型的启发式搜索算法, 它不用遍历整个搜 索空间 ,而是根据所选择的启发式函数朝着最有 希望的方向前进 .它的搜索速度虽然较快, 理论 上也能找到最优解 , 但在实际应用过程中往往由 于启发式函数选取不当而经常找不到最短路径, 即搜索的成功率并不是很高. 将遗传算法分别同 Dijkstra 算法和 A ＊算法 进行仿真比较, 用于比较的性能指标主要有两个: 一是搜索速度, 用时间来表示 ;另一个是搜索到最 短路径的成功率 ,用百分数表示.利用 C 语言编 制了三种算法的最短路径搜索程序, 运行程序的 计算 机 为 AMD Turion 64 Processor, 512 MB DDR .采用自行绘制的地图 ,共 5 张:第 1 张图 16 个节点,共 24 条弧;第 2 张图 32 个节点 ,共 55 条 弧;第 3 张图 43 个节点, 共 75 条弧 ;第 4 张图 62 个节点,共 111 条弧 ;第 5 张图 78 个节点, 共 139 条弧 . 2.1 搜索速度的比较 对 5 张地图分别采用 Dijkstra 算法、A ＊算法 以及所提出的遗传算法进行路径规划 , 它们各自 花费的搜索时间如表 3 所示. 表 3 三种算法在搜索速度上的对比 Table 3 Comparison of the search speed of three algorithms 节点数 搜索速度/ s Dijk stra 算法 A＊算法 遗传算法 16 1 <1 2 32 4 2 4 43 7 3 6 62 15 5 9 78 25 7 12 由表 3 可以看出 :当地图节点个数和弧的条 数比较多时,遗传算法的搜索速度比 A ＊算法慢, 但比 Dijkstra 算法快得多, 而且这种快速性将随 着节点和弧数量的增加而变得更加明显 .对于实 际的电子地图而言 , 由于节点和道路的数量一般 都很大 ,所以同 Dijkstra 算法相比 ,使用遗传算法 在搜索速度方面将具有较大的优越性. 2.2 搜索成功率的比较 对于具有 n 个节点的地图 , 其待规划节点的 个数为 n -1(除起始节点外, 其他均可作为待规 划节点), 由于每个待规划节点对应于一条最短路 径,所以对每张具有 n 个节点的地图而言, 应该 规划出 n -1 条最短路径. 对5 张地图分别采用三种算法进行路径规 划,三者各自搜索到最短路径的情况如表 4 所示. 表中括号外数据为各算法实际得到最短路径数, 括号内数据则为各算法实际得到最短路径数和应 该规划出的最短路径数 n -1 之比 . 表 4 三种算法在搜索质量方面的对比 Table 4 Comparison of the search quality of three algorithms 节点数 Dijkstra 算法 A ＊算法 遗传算法 16 15(100%) 12(80%) 15(100%) 32 31(100%) 25(81%) 29(94%) 43 42(100%) 32(76%) 38(90%) 62 61(100%) 40(66%) 56(92%) 78 77(100%) 45(58%) 71(92%) 由表 4 可以看出 :当地图节点个数和弧数量 比较多时, 遗传算法搜索到最短路径的成功率虽 然比 Dijkstra 算法稍低一些(由于 Dijkstra 算法是 一种遍历算法, 所以每次能保证 100 %的搜索到 最短路径), 但比 A ＊算法要高得多, 而且这种高 成功率在节点和弧的数量越大时表现得更加明 显.故对于实际的电子地图而言, 使用本文的遗 传算法将比A ＊算法得到更多的最短路径 . 3 结语 针对车辆最短路径规划问题提出了一种自适 应遗传算法,同其他常见路径规划算法———Dijk￾stra 算法和A ＊算法 ———相比 ,该自适应遗传算法 具有以下三个特点: (1)同Dijkstra 算法相比 ,其搜索成功率虽然 稍低一些, 但其搜索速度要比 Dijkstra 算法快很 多; (2)同 A ＊算法相比, 其搜索速度虽然相对较 慢,但却大大提高了搜索到最短路径的成功率; (3)该遗传算法在搜索速度和搜索成功率二 者之间达到了一种折衷 ,为解决实际的车辆最短 路径规划问题提供了一种新思路、新方法. 参 考 文 献 [ 1] 龚洁辉, 白玲, 高健美.最短路径算法的改进及其实现.解 放军测绘学院学报, 1998 , 15(2):23 [ 2] 周培德.交通道路网中任意两点之间最短路径的快速算 法.计算机研究与发展, 2002 , 24(2):35 [ 3] 段莉琼, 朱建军, 王庆社, 等.改进的最短路径搜索 A ＊算法 的高效实现.海洋测绘, 2004 , 24(5):19 Vol.28 No.11 李 擎等:一种用于车辆最短路径规划的自适应遗传算法及其与 Dijkstra 和 A ＊算法的比较 · 1085 ·