D01:10.13374j.isml00103x2006.11.018 第28卷第11期 北京科技大学学报 Vol.28 No.11 2006年11月 Journal of University of Science and Technology Beijing Now.2006 一种用于车辆最短路径规划的自适应遗传算法及其 与Dijkstra和A算法的比较 李擎》谢四江2) 童新海2)王志良D 1)北京科技大学信息工程学院。北京1000832)北京电子科技学院科研中心，北京100070 摘要提出了一种自适应遗传算法并成功应用于车辆最短路径规划算法中.所采用的编码方 式、交叉及变异算子等均针对最短路径规划问题而专门设计：同时，提出了一种新的交叉概率、变 异概率在线自适应调整策略，以便提高遗传算法的搜索速度和搜索质量.将该算法同D冰st算 法，A`算法进行了仿真比较.对五种不同情况的仿真研究结果表明：同Dt阳算法相比.该自适 应遗传算法可以减少搜索到最短路径的时间：同A”算法相比。该自适应遗传算法则可以搜索到更 多的最短路径. 关键词最短路径规划：车辆导航：遗传算法：自适应调节 分类号TP273.2TP273.4 现今比较流行的车辆最短路径规划算法主要 为节点，在实际电子地图中表示公路的交叉点：节 有以下三类：第一类是基于图论理论的算法如 点之间的数据称为权值，在实际电子地图中则表 Dijkstra及其改进算法F3、Floyd算法等；第二类 示各公路交叉点之间的实际路径长度 则是基于传统人工智能理论的算法，如A“及其 改进算法，深度优先、宽度优先算法等；第三 2.9⊙ 18 D 4.4 类则是基于智能控制技术的算法，如人工神经网 R 络算法，遗传算法⑨等.特别是近10年来，智 3.2 2⑩ 能控制技术在路径规划问题中得到了广泛的应 A 2.9 3.4 2.8 12 5.6 3.4 3 用，人们的研究兴趣也逐渐从对前两类算法的改 LY2.2 4.2 4.2 10 进转到了对第三类算法的进一步研究中. 4 022四 2.2 本文根据车辆最短路径规划算法的具体需 6 8 1012 14 要，提出了一种自适应遗传算法.该算法所采用 的编码方式、初始种群的产生方法以及交叉和变 图1最短路径规划仿真地图 异算子均不同于传统遗传算法.其中编码采用了 Fig.I Simulation map of the shortest path planning 变长度的符号编码方式：初始种群的产生采用了 11编码方式 文献7刀的方法：交叉和变异操作则采用了文献 采用变长度的符号编码方式，能直接、具体地 [9习中的方法.为了提高遗传算法的性能，本文还 表达路径的实际意义，同时也有利于适应度函数 提出了一种新的基于模糊控制的交叉概率、变异 值的计算.在图1中，一条从起始节点A到目标 概率在线自适应调整策略， 节点P的路径可以编码成一个由路径前进方向 1 自适应遗传算法 的节点组成的字符串，如个体(A,C,F,J,M,O, P).需要指出的是，每个个体都必须对应路网中 采用图1作为仿真地图，其中A,B,C等称 的一个实际连接. 收稿日期：2005-09-01修回日期：200606-22 1.2初始种群的产生 基金项目：国家十五科技攻关项目No.2001BA605A一02) 初始种群中的个体不能是断路或环路，否则 作者简介：李擎(1971一)，男，副撒授博士 者简介g2hh界装，将oumaPu进桃膏将毫无意i为避兔这种视象的出现ki.net
一种用于车辆最短路径规划的自适应遗传算法及其 与 Dijkstra 和 A ＊算法的比较 李 擎 1) 谢四江 2) 童新海 2) 王志良 1) 1)北京科技大学信息工程学院, 北京 100083 2)北京电子科技学院科研中心, 北京 100070 摘 要 提出了一种自适应遗传算法, 并成功应用于车辆最短路径规划算法中.所采用的编码方 式、交叉及变异算子等均针对最短路径规划问题而专门设计;同时, 提出了一种新的交叉概率、变 异概率在线自适应调整策略, 以便提高遗传算法的搜索速度和搜索质量.将该算法同 Dijkstra 算 法、A ＊算法进行了仿真比较.对五种不同情况的仿真研究结果表明:同 Dijkstra 算法相比, 该自适 应遗传算法可以减少搜索到最短路径的时间;同 A ＊算法相比, 该自适应遗传算法则可以搜索到更 多的最短路径. 关键词 最短路径规划;车辆导航;遗传算法;自适应调节 分类号 TP273 +.2;TP273 +.4 收稿日期:2005 09 01 修回日期:2006 06 22 基金项目:国家十五科技攻关项目(No .2001 BA 605A-02) 作者简介:李 擎(1971—), 男, 副教授, 博士 现今比较流行的车辆最短路径规划算法主要 有以下三类 :第一类是基于图论理论的算法, 如 Dijkstra 及其改进算法 [ 1-2] 、Floy d 算法等;第二类 则是基于传统人工智能理论的算法, 如 A ＊及其 改进算法[ 3-4] , 深度优先 、宽度优先算法等;第三 类则是基于智能控制技术的算法, 如人工神经网 络算法[ 5] ,遗传算法[ 6-8] 等 .特别是近 10 年来 ,智 能控制技术在路径规划问题中得到了广泛的应 用,人们的研究兴趣也逐渐从对前两类算法的改 进转到了对第三类算法的进一步研究中 . 本文根据车辆最短路径规划算法的具体需 要, 提出了一种自适应遗传算法 .该算法所采用 的编码方式 、初始种群的产生方法以及交叉和变 异算子均不同于传统遗传算法.其中编码采用了 变长度的符号编码方式 ;初始种群的产生采用了 文献[ 7] 的方法 ;交叉和变异操作则采用了文献 [ 9] 中的方法.为了提高遗传算法的性能, 本文还 提出了一种新的基于模糊控制的交叉概率 、变异 概率在线自适应调整策略 . 1 自适应遗传算法 采用图 1 作为仿真地图, 其中 A , B , C 等称 为节点,在实际电子地图中表示公路的交叉点;节 点之间的数据称为权值 ,在实际电子地图中则表 示各公路交叉点之间的实际路径长度. 图 1 最短路径规划仿真地图 Fig.1 Simulation map of the shortest path planning 1.1 编码方式 采用变长度的符号编码方式, 能直接、具体地 表达路径的实际意义 , 同时也有利于适应度函数 值的计算 .在图 1 中,一条从起始节点 A 到目标 节点 P 的路径可以编码成一个由路径前进方向 的节点组成的字符串 ,如个体(A , C ,F , J , M , O , P).需要指出的是 ,每个个体都必须对应路网中 的一个实际连接. 1.2 初始种群的产生 初始种群中的个体不能是断路或环路, 否则 进化计算将毫无意义 .为避免这种现象的出现, 第 28 卷 第 11 期 2006 年 11 月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol.28 No.11 Nov.2006 DOI :10.13374/j .issn1001 -053x.2006.11.018
Vol.28No.11李擎等：一种用于车辆最短路径规划的自适应遗传算法及其与Dijkstra和A“算法的比较·1083· 采用文献刁中的方法.具体过程为：从起始点出 出现断路. 发，随机选取与起始点直接相连的一个点作为下 15交叉和变异概率的在线自适应调整策略 一个节点，如此反复直到找到终点为止.在路径 交叉概率和变异概率的选取对遗传算法的影 的产生过程中为了避免出现环路，规定在一条路 响非常大.为了更好地使用遗传算法对路径进行 径中当一个节点被选中以后，给该节点一个标记， 规划，本文提出了一种新的基于模糊控制的交叉 只有没有标记过的节点才能被选作新的路径节 概率和变异概率在线自适应调节策略.其中，模 点，每条路径选择完后标记全部刷新. 糊控制器的输入变量为相邻两代群体平均适应度 13适应度函数 函数值的变化量△∫ag(k)和相邻两代群体之间 为方便计算，适应度函数取为： 标准差的变化量△σ(k),输出变量为下一代交叉 f(xi)=Distance(xi),i=1,2,.,M (1) 概率和变异概率的变化量△p。(k+1)和 其中，x表示第i个个体，Distance(x:)表示个体 △pm(k+1). x:所代表路径的长度，M表示种群规模.从适应 △fawg(k)的计算公式如下： 度函数可以看出：最短路径将具有最小的适应度 △fwg(k)=fawg(k-1)-fmg(k)(k=2,3,…) 函数值. (2) 1.4交叉和变异算子 其中，∫g(k)为第k代种群的平均适应度函数 采用文献[9]中的交叉算子和变异算子.其 值，它代表了该代群体的整体水平，计算公式为： 中当交叉运算应用于父代个体V1和'2时，操作 过程为： 人女会阳 (3) (1)列举出V1和V2中均含有的节点集合 式中，M仍表示种群规模fi(k)(i=1,2,…,M) N(不包括起始节点和目标节点)： 则代表第k代群体中各个体的适应度函数值. (2)从Ne中随机选择一个节点i∈Ne作为 同理，△σ(k)的计算公式为： 交叉点； △G(k)=G(k-1)-G(k)(k=2,3,)(4) (3)检查V1和？中节点i之前或之后的 其中，σ(k)表示第k代种群的标准差，它描述了 内容是否相同，如相同，则取消本次交叉操作：否 该代群体中各个体的分散程度（即种群的多样 则，进行下一步； 性)，其计算公式为： (4)通过交换交叉点后的所有节点得到交叉 M 后新的子代个体； (k)= f后(k)-fag(k】2 (5) (⑤)若交叉后的子代个体中存在环路，则按 为了增加在线自适应调节算法的通用性需 文献[8的方法进行处理. 要对输入变量进行归一化处理，△∫g(k)对应的 变异操作过程为： 归一化公式为： (1)从待变异父代个体V中随机选择变异 节点i(i=2,…,M-1),其中M为待变异个体 a △fg(k) 的编码长度； fwg(k)≤favg(k-1) (2)找出所有和节点i(i=2,…,M-1)直 △fg(k)= (6) 接相连的节点集合Nm(不包括起始节点和目标 △fsk)_fmk-D-l, favg(k)favg (k) 节点)： favg(k favg (k-1) (3)从中Nm随机选择一个节点j,j∈Nm; △σ(k)归一化公式为： (4)应用A*算法产生从一条从起始节点到 节点j的准最短路径r1(因为A算法在实际应 1 △G(k) 用过程中未必一定能够找到最短路径)： G(k)≤G(k-1) (5)再次应用A算法产生从一条从节j点 △σ*(k)= △a(k)=k-D-1, (1) 到目标节点的准最短路径r2: 6(k) a(k) (6)如果r1和r2中存在重复节点（节点j 6(k>G(k-1) 除外)，则放弃路径.不进行变异，防止出现环路； 为了提高路径规划算法的搜索速度，采用模 否吧，接两段路径组成变异后的新个体保证不。P糊控制套询表方式进行模糊推稞条过计算得到i
采用文献[ 7] 中的方法.具体过程为 :从起始点出 发,随机选取与起始点直接相连的一个点作为下 一个节点, 如此反复直到找到终点为止.在路径 的产生过程中为了避免出现环路, 规定在一条路 径中当一个节点被选中以后, 给该节点一个标记, 只有没有标记过的节点才能被选作新的路径节 点,每条路径选择完后标记全部刷新. 1.3 适应度函数 为方便计算 ,适应度函数取为 : f(xi)=Distance(x i), i =1 , 2 , …, M (1) 其中, xi 表示第 i 个个体, Distance(xi)表示个体 x i 所代表路径的长度, M 表示种群规模 .从适应 度函数可以看出:最短路径将具有最小的适应度 函数值. 1.4 交叉和变异算子 采用文献[ 9] 中的交叉算子和变异算子 .其 中当交叉运算应用于父代个体 V 1 和 V2 时, 操作 过程为: (1)列举出 V 1 和 V2 中均含有的节点集合 Nc(不包括起始节点和目标节点); (2)从 Nc 中随机选择一个节点 i ∈ Nc 作为 交叉点; (3)检查 V 1 和 V2 中节点 i 之前或之后的 内容是否相同 ,如相同, 则取消本次交叉操作 ;否 则,进行下一步 ; (4)通过交换交叉点后的所有节点得到交叉 后新的子代个体 ; (5)若交叉后的子代个体中存在环路, 则按 文献[ 8] 的方法进行处理 . 变异操作过程为 : (1)从待变异父代个体 V 中随机选择变异 节点i(i =2 , … , M -1),其中 M 为待变异个体 的编码长度; (2)找出所有和节点 i(i =2 , … , M -1)直 接相连的节点集合 N m (不包括起始节点和目标 节点); (3)从中 N m 随机选择一个节点j , j ∈ N m ; (4)应用 A ＊算法产生从一条从起始节点到 节点 j 的准最短路径 r 1(因为 A ＊算法在实际应 用过程中未必一定能够找到最短路径); (5)再次应用 A ＊算法产生从一条从节 j 点 到目标节点的准最短路径 r 2 ; (6)如果 r 1 和 r 2 中存在重复节点(节点 j 除外), 则放弃路径, 不进行变异, 防止出现环路; 否则 ,连接两段路径组成变异后的新个体,保证不 出现断路 . 1.5 交叉和变异概率的在线自适应调整策略 交叉概率和变异概率的选取对遗传算法的影 响非常大 .为了更好地使用遗传算法对路径进行 规划, 本文提出了一种新的基于模糊控制的交叉 概率和变异概率在线自适应调节策略 .其中, 模 糊控制器的输入变量为相邻两代群体平均适应度 函数值的变化量 Δf avg(k)和相邻两代群体之间 标准差的变化量 Δσ(k),输出变量为下一代交叉 概率 和 变 异 概 率 的变 化 量 Δp c (k +1)和 Δp m(k +1). Δf avg(k)的计算公式如下 : Δf avg(k)=f avg(k -1)-f av g(k) (k =2 , 3 , …) (2) 其中 , f av g(k)为第 k 代种群的平均适应度函数 值,它代表了该代群体的整体水平 ,计算公式为: f av g(k)= 1 M ∑ M i =1 fi(k) (3) 式中 , M 仍表示种群规模, fi(k)(i =1 , 2 , … , M) 则代表第 k 代群体中各个体的适应度函数值. 同理 ,Δσ(k)的计算公式为 : Δσ(k)=σ(k -1)-σ(k) (k =2 , 3 , …)(4) 其中, σ(k)表示第 k 代种群的标准差 ,它描述了 该代群体中各个体的分散程度(即种群的多样 性), 其计算公式为: σ(k)= 1 M ∑ M i =1 [ fi(k)-f avg(k)] 2 (5) 为了增加在线自适应调节算法的通用性, 需 要对输入变量进行归一化处理, Δf avg(k)对应的 归一化公式为 : Δf ＊ avg(k)= Δf avg(k) f avg(k -1)=1 - f avg(k) f avg(k -1), f avg(k)≤f avg(k -1) Δf avg(k) f av g(k) = f av g(k -1) f avg(k) -1 , f avg(k)>f avg(k -1) (6) Δσ(k)归一化公式为 : Δσ ＊(k)= Δσ(k) σ(k -1) =1 - σ(k) σ(k -1) , σ(k)≤σ(k -1) Δσ(k) σ(k) = σ(k -1) σ(k) -1 , σ(k)>σ(k -1) (7) 为了提高路径规划算法的搜索速度, 采用模 糊控制查询表方式进行模糊推理, 经过计算得到 Vol.28 No.11 李 擎等:一种用于车辆最短路径规划的自适应遗传算法及其与 Dijkstra 和 A ＊算法的比较 · 1083 ·
。1084· 北京科技大学学报 2006年第11期 的交叉概率和变异概率模糊控制查询表分别如表1和表2所示. 表1交叉概率△P(k+1)模糊控制查询表 Table 1 Fuzzy control inquiry table for crossover probability Ap(k+1) △f(k) △a"(k) -08 -06 -04 -02 0 02 04 06 08 -08 0 002 0.02 004 004 006 0.06 008 008 -06 0 0 002 002 004 004 0.06 006 008 -04 -002 0 0 002 002 004 0.04 006 0.06 -02 -0.02 -002 0 0 002 002 0.04 004 0.06 0 一004 -002 一002 0 004 002 0.02 0.04 004 02 -004 -004 -0.02 -002 0 0 0.02 002 004 04 -006 -004 -004 -002 一002 0 0 002 002 06 -006 -006 -004 -004 -002 -002 0 0 002 08 -008 -006 -006 -004 -004 -002 -0.02 0 0 表2变异概率△Pm(k十1)模糊控制查询表 Table 2 Fuzzy control inquiry table for mutation probability p(1) △f(k) △a"(k) -08 -06 -04 -02 0 02 04 06 08 -08 -0008 -0.006 -0006 一0004 -0004 -0002 -0002 0 0 -06 -0.006 -0006 -0004 -0004 -0002 -0002 0 0 0002 -04 -0.006 -0004 -0004 -0002 -0002 0 0 0002 0002 -02 -0004 -0004 -0002 -0002 0 0 0002 0002 0004 0 -0.004 -0002 -0002 0 0004 0002 0002 0004 0004 02 -0002 -0002 0 0 0002 0002 0004 0004 0006 04 -0.002 0 0002 0002 0004 0004 0006 0006 06 0 0 0002 0002 0.004 Q004 0006 0006 0008 08 0 0.002 0002 0004 0.004 Q006 0006 0008 0.008 根据第k代的△f(k)和△o*(k),通过查 为10，最大迭代代数设为50.初始交叉概率取为 询表1即可得到第k十1代交叉概率的变化量 05,初始变异概率取为0.1，之后二者将根据所 △p(k+1,从而得到第k十1代交叉概率 给出的控制查询表在线进行调节.采用赌轮法进 Pe(k十I)的值为： 行选择操作，采用所给出的交叉和变异算子进行 pe(k+1)=pe(k+△pe(k+1)(k=2,3,…) 相应的进化操作，进化结束的条件设定为各代中 (8) 的最优个体连续5代不发生变化或达到所设定的 同理，通过查询表2可以得到第k十1代变 最大迭代代数.此外，为了提高搜索速度，还采用 异概率的变化量△pm(k十I),从而得到第k十1 了最优个体保留策略. 代变异概率pm(k十I)的值为： 经过16代进化，遗传算法收敛，得到的最短 pm(k+1)=pm(k)十△pm(k+1)(k=2,3,…) 路径为(A,C,F,J,M,O,P),该路径的长度为 I83.Dikstra算法的搜索结果验证了它确实是 (9) 一条从起始节点A到目标节点P的最短路径. 1.6应用实例 以图1中从起始节点A到目标节点P的最 2 遗传算法与Dijkstra及A算法 短路径的求取过程为例，说明本文提出的遗传算 的比较 法是如何进行路径寻优的 Dijkstra算法是一种基于图论理论的遍历算 (C遗转算法的参数选取恕下：种群规模eM取e Publishing Housereserved.即nki.net
的交叉概率和变异概率模糊控制查询表分别如表 1 和表 2 所示 . 表1 交叉概率 Δp c(k +1)模糊控制查询表 Table 1 Fuzzy control inquiry tabl e for crossover probability Δpc(k +1) Δσ＊(k) Δf ＊ avg(k) -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 -0.8 0 0.02 0.02 0.04 0.04 0.06 0.06 0.08 0.08 -0.6 0 0 0.02 0.02 0.04 0.04 0.06 0.06 0.08 -0.4 -0.02 0 0 0.02 0.02 0.04 0.04 0.06 0.06 -0.2 -0.02 -0.02 0 0 0.02 0.02 0.04 0.04 0.06 0 -0.04 -0.02 -0.02 0 0.04 0.02 0.02 0.04 0.04 0.2 -0.04 -0.04 -0.02 -0.02 0 0 0.02 0.02 0.04 0.4 -0.06 -0.04 -0.04 -0.02 -0.02 0 0 0.02 0.02 0.6 -0.06 -0.06 -0.04 -0.04 -0.02 -0.02 0 0 0.02 0.8 -0.08 -0.06 -0.06 -0.04 -0.04 -0.02 -0.02 0 0 表 2 变异概率 Δp m(k +1)模糊控制查询表 Tabl e 2 Fuzzy control inquiry table for mutation probability Δpm(k +1) Δσ＊(k) Δf ＊ avg(k) -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 0.8 -0.8 -0.008 -0.006 -0.006 -0.004 -0.004 -0.002 -0.002 0 0 -0.6 -0.006 -0.006 -0.004 -0.004 -0.002 -0.002 0 0 0.002 -0.4 -0.006 -0.004 -0.004 -0.002 -0.002 0 0 0.002 0.002 -0.2 -0.004 -0.004 -0.002 -0.002 0 0 0.002 0.002 0.004 0 -0.004 -0.002 -0.002 0 0.004 0.002 0.002 0.004 0.004 0.2 -0.002 -0.002 0 0 0.002 0.002 0.004 0.004 0.006 0.4 -0.002 0 0 0.002 0.002 0.004 0.004 0.006 0.006 0.6 0 0 0.002 0.002 0.004 0.004 0.006 0.006 0.008 0.8 0 0.002 0.002 0.004 0.004 0.006 0.006 0.008 0.008 根据第 k 代的 Δf ＊ avg(k)和 Δσ ＊(k),通过查 询表 1 即可得到第 k +1 代交叉概率的变化量 Δp c(k +1), 从而 得到第 k +1 代 交叉概率 pc(k +1)的值为 : pc(k +1)=pc(k)+Δpc(k +1) (k =2 , 3 , …) (8) 同理, 通过查询表 2 可以得到第 k +1 代变 异概率的变化量 Δpm(k +1), 从而得到第 k +1 代变异概率 pm(k +1)的值为 : pm(k +1)=pm(k)+Δpm(k +1) (k =2 , 3 , …) (9) 1.6 应用实例 以图 1 中从起始节点 A 到目标节点 P 的最 短路径的求取过程为例 ,说明本文提出的遗传算 法是如何进行路径寻优的 . 遗传算法的参数选取如下:种群规模 M 取 为 10 ,最大迭代代数设为 50 .初始交叉概率取为 0.5 ,初始变异概率取为 0.1 , 之后二者将根据所 给出的控制查询表在线进行调节 .采用赌轮法进 行选择操作 ,采用所给出的交叉和变异算子进行 相应的进化操作, 进化结束的条件设定为各代中 的最优个体连续 5 代不发生变化或达到所设定的 最大迭代代数 .此外 ,为了提高搜索速度 ,还采用 了最优个体保留策略 . 经过 16 代进化 , 遗传算法收敛 ,得到的最短 路径为(A , C , F , J , M , O , P), 该路径的长度为 18.3 .Dijkstra 算法的搜索结果验证了它确实是 一条从起始节点 A 到目标节点P 的最短路径 . 2 遗传算法与 Dijkstra 及 A ＊算法 的比较 Dijkstra 算法是一种基于图论理论的遍历算 · 1084 · 北 京 科 技 大 学 学 报 2006 年第 11 期
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 结语 针对车辆最短路径规划问题提出了一种自适 应遗传算法,同其他常见路径规划算法———Dijkstra 算法和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 ·
。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 International 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 proposed 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 期
