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