人工智能基础：RBF神经网络的行车路径代价函数建模.pdf_大学文库

第6卷第5期智能系统学报 Vol.6 No.5 2011年10月 CAAI Transactions on Intelligent Systems 0ct.2011 doi:10.3969/i.i8sn.1673-4785.2011.05.006 RBF神经网络的行车路径代价函数建模陈亮，何为，韩力群 (北京工商大学计算机与信息工程学院，北京100048) 摘要：行车路线优化是城市智能交通系统的研究热点之一，对整个交通系统的优化起着重要作用.分析了影响行车时间的各种因素，结合图论中最短路径算法，建立了基于RBF神经网络的路径代价函数模型.基于该函数模型，可以计算出交通图中任意给定两地间的时间最优路径.将该模型应用于实际路况进行有效性验证，得到了有实用价值的结果，说明了该模型的正确性和有效性. 关键词：智能交通；路径代价函数；行车路线优化；RBF神经网络；图论中图分类号：TP391.4文献标志码：A文章编号：16734785(2011)050424-08 Radial basis function neural network modeling of the traffic path cost function CHEN Liang,HE Wei,HAN Liqun (College of Computer and Information Engineering,Beijing Commercial and Industrial University,Beijing 100048,China) Abstract:Vehicle route optimization is one of the hot topics in research on urban intelligent transportation systems (ITS),and it plays an important role in the optimization of the entire transportation system.This paper analyzed various factors that affect the travel time and established a path cost function model with an radial basis function neural network,based on the shortest paths algorithms in graph theory.By this function model,the time-oriented optimal path between any two given places on a traffic map can be calculated.The model was applied to actual traf- fic to validate the effectiveness,and its results are of practical value,showing the correctness and validity of the model. Keywords:intelligent transportation;path cost function;vehicle route optimization;radial basis function neural network;graph theory 在城市智能交通系统中，行车路线优化对整个约束解决最短路径问题4 交通系统的优化起着重要作用，选取最优车辆行车道路交通网络的实际情况非常复杂，每个路段路线，可以加快车流速度，减少拥堵发生，还能减少的行车时间除了与距离有关外，还与路宽、路况、气因为堵车而造成的交通车辆刮蹭等事故的概率，因候及行车时段等诸多因素相关，因此最短路径并不此，该课题的研究具有重要的实用意义. 意味着最短行车时间，不能简单地用路径长度计算行车路线优化属于路径优化问题.目前关于路径路径的代价值51.鉴于此，本文从实际情况出发，综优化的研究主要集中在如何找到最短路径，其中常见合考虑了各种影响行车时间的主要因素，建立了较的一类方法是采用图论中的D以sta算法，具体实现算为实用的路段代价函数模型并进行了实验验证. 法有A--star、Bellman、Ford2 Moore、Foyd等2]；另一类常用方法是基于蚁群算法的解决方法，如2007年 1路径代价函数及其影响因素分析 Horoba等人提出的基于随机过程的改进蚁群算法最短图论中每个弧段都可用其代价函数值表示，2 路径寻优3]，2009年Punyaslok提出的多网络流最优化个给定点之间的路径代价函数值则可用构成该路径框架，2010年Zakzouk提出的基于蚁群算法利用模糊的所有弧段的代价函数值之和表示.2个给定点间收稿日期：20110422. 的最优路径即指所有可达路线中代价函数值最小的通信作者：陈亮.E-mail:newboy_01@163.com 路径6

第5期陈亮，等：RBF神经网络的行车路径代价函数建模 ·425· 实际应用中，弧段对应于两相邻路口之间的路种影响因素的完全搭配可产生243个样本对，而每段，路径对应于出发地到目的地之间的行车路线，代个样本对中的教师信号必须来自与输入条件相符的价函数值则对应于行车时间代价.实际道路中，很多实际情况.为了减少工作量，采用正交实验设计法来因素都会影响车辆通过路段的时间，表1列出了可构造样本集，其优点是：正交表能在保证采集数据均能影响车辆通过路段时间的主要因素[们匀分布的前提下，大大减少训练网络所需的样本数表1车辆通行时间的影响因素本文将每个影响因素分成3个水平，如表2所示.表 Table 1 The influencing factors of vehicle travel time 2给出了水平因素表，1~是对道路通行时间不影响因素同的影响因素，再将每一个影响因素具有的3个水时间段、天气情况（风、雨、雪、雾、沙尘）、季平填入表中. 自然节变化：表2正交实验法水平因素表 Table 2 The level of factor orthogonal experiment table 车道数、车辆转向、自助红绿灯数量、路段长系统度、实时交通路况因素水平第2 名3 多 xs 管理交通事故、交通管制、交通限行水平1畅通1~20 ,≤500 直行在诸影响因素中，可进一步筛选出相互独立的水平2缓行31 5001000 右转的影响因素：实时交通路况、车道数（路宽）、道路长采用的正交试验如表3所示.将5个不同因素度、自助红绿灯数量以及车辆转向的不同水平分别排列组合得到的18种实验组合情 2基于RBF网络的路段代价函数建模况.虽然只给出了18种实验组合情况，但是用这个表设计的训练集保证了实验数据的代表性，在实际道路中，车辆通过路段的时间与其影响表3正交实验设计表因素之间存在着严重的非线性和不确定性，因此很 Table 3 Orthogonal experiment 难用解析式来表达.人工神经网络适于处理非线性样本号竹节￥4 问题，利用神经网络建立路径代价函数模型，是一种 0 0 0 0 0 可行的途径⑧].适合拟合非线性关系的神经网络主 0 2 1 要有BP网络和RBF网络，经实验对比，采用效果较 0 2 2 好的RBF网络进行建模91」 4 1 0 0 1 1 2.1基于正交实验的训练集设计 5 1 1 2 2 6 2 0 0 RBF网络的输入是影响车辆通行时间的因素， 2 教师信号是车辆通过路段的实际时间.本文所确定 P 0 的影响因素包括：实时路况x1、车道数量2、行人自 9 0 2 1 助式红绿灯数量x3、路段长度x4、车辆在路口的转 10 2 1 向方式5 11 0 2 可以看出，上述影响因素既有语言变量，又有数 12 0 值变量.首先，对各影响因素进行数值化和离散化 13 0 1 2 0 其中：x1为语言变量，根据北京市交通管理局现有 14 1 0 1 标准划分，共分为3种路况：“畅通”、“缓行”、“拥 15 1 0 2 堵”，与3个语言值对应，x1取值分别为0、1、2；x2可 16 2 0 1 2 直接采用实际车道数，分为1~2条、3条、4条3种公 2 1 0 2 0 情况，2取值分别对应为0、1、2；行人自助式红绿灯 e 2 0 1 数量x3,可直接采用实际数量，取值分别为0、1、2. 2.2基于RBF网络的路段代价函数建模路段长度4可离散为3个区间，分别为小于500m、由于采集到的输入输出数据取值范围差别很 500~1000m、大于1000m,对应的x4取值为0、1、大，需进行归一化处理，将输入数据归一化到[-1， 2；x也是语言变量，可分为“直行”、“左转、“右转” 1]区间，教师信号的时间单位采用小时，归一化到 3种情况01，分别用0、1、2表示.按照上述规定，5 (0,1]区间四.数据归一化后的情况如表4所示

·426 智能系统学报第6卷表4数据归一化表4根据x1~x这5个影响行车时间因素的 Table 4 Data normalization 实际情况，依据表3，然后分别将其归一化，如x1~ 路况车道数红绿灯数路段长转向行车时间 4归一化的原则是本身对应的3个水平，将其归一化至[-1,0,1]，是时间，将其归一化至[0,1]. -1 -1 -1 -1 -1 0.071 0 RBF网络的设计与训练采用函数net= -1 -1 -1 0.040 -1 0 0 0 0 0.130 newb(P,T,goal,spread),其中，P为5维输人向量， -1 0 0 -1 0.082 T为网络输出的行车代价值，训练误差目标值goal -1 1 1 0.111 设定为0.O1,spread为径向基函数的扩展系数，经调 -1 1 1 0 0.156 试取为1.52 0 -1 -1 0 0 0.231 2.3模型验证 0 1 -1 0 1 0.201 由于特定路段的行车时间具有不确定性，采用 0 1 0.221 0 -1 0 -1 0.244 上述方法建立的路段代价函数其输出并非准确的行 1 -1 0 0.401 车时间，而是行车代价值，其作用是通过比较不同可 -1 1 -1 0.381 达路线的行车代价从而确定最优行车路线.本文用 0 0.308 表5中的15组实际数据对模型进行验证，结果如表 1 0 0 0.371 5的第7列所示 0.360 表5仿真结果对比 Table 5 Simulation results comparison 路况车道数红绿灯数路段长/m 转向实测行车时间/8 网络预测的行车代价值畅通 2 0 440 右转 168 畅通 2 1 470 直行 55 178 畅通 2 1 470 左转 65 179 畅通 3 800 直行 58 173 畅通 800 右转 75 169 缓行 3 800 左转 90 219 缓行 3 1 800 右转 200 213 缓行 4 0 1220 左转 254 233 缓行 2 500 直行 225 209 缓行 470 直行 218 223 缓行 0 1700 左转 225 233 拥堵 2 500 右转 271 251 拥堵 3 0 1700 左转 305 271 拥堵 0 1700 右转 299 256 拥堵 3 2 760 右转 302 269 从表5可知，拥堵路段的网络预测代价值要明显 x4都是正向关因素，即水平越高，所花费时间越长，网大于畅通与缓行的值，说明实际道路路况是影响车辆络的预测值同样也越大，而2是反相关因素.仿真结行驶时间的主要因素，当其他因素相同时，转向会影果如图1所示，同样也可以看出，神经网络的仿真预响所用的时间，如左转比直行和右转花费的时间都测结果与实测结果趋势一致，表明所设计的路段行车多，这与日常常识是相符的.5个影响因素中的x1x3、代价函数模型可靠.图1中需要说明的是，实际行车路线是以秒为单位计时，而神经网络计算的行车代价

第5期陈亮，等：RBF神经网络的行车路径代价函数建模 .427… 值没有单位，不表示实际消耗的时间，表示的是车辆 3应用实例行驶在不同的路段所耗费时间多少的横向比较，并以此为依据，最终选择出最优路径 3.1应用实例概述 7*10 本文应用实例是利用路段代价函数模型确定特 ·行车代价值 6 定路况条件下，从航天桥至西单路口的最优路线，实 -实测行车时问s 际道路如图2.具体步骤是：首先将交通网络图抽象成为加权有向图3]，找出连通起点和终点的所有可 3 达路线，2个相邻交通路口之间是一个路段，从而可将各可达路线表示为一个路段系列，其中每个路段 6 9 12 的实际情况可用一个5维向量进行描述，代入路段数据组号代价函数模型后可计算出该路段的行车代价值，所图1仿真值与实际测量值有路段的代价值之和即为路径的行车代价值，其中 Fig.1 Simulation and test values 行车代价值最小的路径为最优路径4」创月坛图2实际交通道路 Fig.2 Actual traffic roads 可达路径的搜索方法如下，情况近似的路径，选出差别较大的20条路径，根据 1)将图2中的交通图抽象为加权有向图，对不距离长短对可达路线编号，如表6所示. 能提供实时路况信息的路段视为不可达，从而得到 10 13 图3.图3中，1号节点为航天桥，15号节点为西单路口. 2)建立加权有向图的邻接矩阵 14 3)根据邻接矩阵，从起始点开始找出下一节点；若下一个节点等于目标点，则返回2). 4)将起点到终点经过的全部节点串连起来，形 2 6 9 12 15 成完整路径，将路径中经过点的权值相加，得到整条图3加权有向图路径的权值5] Fig.3 Weighted directed graph 根据上述算法共得到92条可达路线16，略去表6均匀抽出20条可达路线 Table 6 Uniform extraction 20 paths 实际距离路径用节点标出的可达路线 km R1 13 5 7 1215 6.55 R2 1246 9 12 15 6.70 R3 135710 131415 7.05

430 智能系统学报第6卷从表8可以看出，附加限制条件后，选出的可达路 JIANG Guiyan,ZHENG Zuduo.Dynamic traffic path opti- 线即距离最短的前9条路径，当加上约束条件对最优 mization algorithm based on mnemonic mechanism [J]. 路径的选择会产生一定影响，但却大大提高了计算效 Journal of Jilin University:Engineering and Technology Edi- 率，并能保证行车时间和距离双优化.可以看出，表8 ion,2007,37(5):1043-1048. 中的改进路径R9和表7中的路径3相同 [3]HOROBA C.SUDHOLT D.Ant colony optimization for sto- chastic shortest path problems[C]//Proceedings of the 12th 在根据常识设计约束条件时，也可考虑允许在 Annual Genetic and Evolutionary Computation Conference 某一个方向上“绕行”.例如，起点到终点在东西方 New York,USA:ACM,2008:1465-1472. 向上的距离比南北方向的距离长，通常人们会选择 [4]ZAKZOUK AAA,ZAHER H M,EL-DEEN R A Z.An 在东西方向少走回头路，在南北方向上可视路况适 ant colony optimization approach for solving shortest path 当绕行，反之亦然.本例中，东西方向距离比南北方 problem with fuzzy constraints[C]//2010 The 7th Interna- 向距离长，当设定禁止向西行驶的约束条件时，得到 tional Conference on Informatics and Systems.Cairo,E 的可达路线数为72；若附加条件为禁止向北行驶， gypt,2010:1201-1208. 则可达路线数为12 [5]王泉啸，蔡先华.动态最佳路径算法研究[J].城市勘测， 3.4有效性验证 2009,73(1):73-75. 本文从表7中选取R1、R3和93条路径，请3 WANG Quanxiao,CAI Xianhua.Study on the algorithm of dynamic optimal routeJ].Urban Geotechnical Investigation 位志愿者同时开车从航天桥出发，分别按照规定的 &Surveying,2009,73(1):73-75. 路径前往西单，并记下行程时间.结果是：9的行车 [6]徐俊明.图论及其应用[M].3版.合肥：中国科学技术大时间为41min,R1的行车时间为52min,R3的行车学出版社，2010：21-53. 时间为66min.可以得出，RBF行车代价函数模型 [7]刘海燕.智能交通系统的车辆行驶最佳路径算法[J].北给出的行车路线排序与实际情况相同. 京工商大学学报：自然科学版，2006,24(1)：5355， LIU Haiyan.Best running path arithmetic of vehicles in in- 4结束语 telligent transport system[J].Journal of Beijing Technology 本文的特点是利用RBF神经网络建立最优路 and Business University:Natural Science Edition,2006,24 (1):53-55. 径代价函数模型，通过图论中的算法找到起点和终 [8]韩力群.人工神经网络教程[M].北京：北京邮电大学出点的时间最优路径.在设计神经网络模型过程中，训版社，2006：127-143. 练集的设计由正交实验法给出，圳练出的网络模型 [9]马君，刘晓东，孟颗.基于神经网络的城市交通流预测研测试结果较好，最后将模型应用到实例中，从最优路究[J].电子学报，2009,37(5)：1092-1094. 径代价函数模型给出的最优路径排序中选取差异较 MA Jun,LIU Xiaodong,MENG Ying.Research of urban 大的3条路径，经实际验证取得了较好结果.本次研 traffic flow forecasting based on neural network[J].Acta 究的不足在于，诸如天气因素（风、雨、雪、雾4类天 Electronica Sinica,2009,37(5):1092-1094. 气)并没有加入到网络的训练集中，原因在于这些 [10]朱文兴，贾磊，丁绪东，等.城市交通网络中的路径优化因素在研究过程中较难采集，在以后的时间范围内研究[J].山东大学学报：工学版，2005,35(1)：74- 将继续观察采集并加入这些因素的数据，将神经网 77. ZHU Wenxing,JIA Lei,DING Xudong,et al.Research 络的训练集丰富完善，使其能够更加真实地反映出 on the route optimization in urban traffic network J]. 交通网络路径的代价函数值，更加贴近实际情况， Joumal of Shandong University:Engineering Science, 参考文献： 2005.35(1):74-77. [11]韩力群.人工神经网络理论、设计及应用[M].2版.北 [1]张渭军，王华.城市道路最短路径的Dijkstra算法优化京：化学工业出版社，2007：164-191. [J].长安大学学报：自然科学版，2005,25(6)：6265. [12]傅荟璇，赵红.MATLAB神经网络应用设计[M].北京： ZHANG Weijun,WANG Hua.Optimation Dijkstra arithme- 机械工业出版社，2010：6263. tic for shortest path of urban traffic net[J].Journal of [13]刘张雷，史忠科.城市动态时间最短路径诱导系统实现 Chang'an University:Natural Science Edition,2005,25 研究[J].控制工程，2010,17(3)：351-355 (6):62-65 LIU Zhanglei,SHI Zhongke.Implementation of urban [2]姜桂艳，郑祖舵.基于记忆机制的动态交通路径优化算 tmie-dependent shortest route guidance system[J].Control 法[J].吉林大学学报：工学版，2007,37(5)：1043- Engineering of China,2010,17(3):351-355. 1048. [14]罗嵩，王坚.智能交通系统的最优路径搜素算法的研究

第5期陈亮等：BF神经网络的行车路径代价函数建模 431。与实现[0.机电产品开发与创新，2008,21(2))：10 作者简介： 12. 陈亮，男，1986年生，硕士研究生，主 LUO Song,WANG Jian.Optimal path search study and 要研究方向为人工神经网路、智能交通 practice based on the intelligent transportation systems[J]. Development and Innovation of Machinery and Electrical Products,2008,21(2):10-12. 15].PETTIE S,RAMACHANDRA V.A shortest path algo- rithm for real-weighted undirected graphs[J].SIAM Jour- nal of Computing,2005,34(6)）:1398-1427. 何为，男，1953年生，高级工程师， 16]王海英，黄强，李传涛，等.图论算法及其MATLAB实现 EEE会员，中国人工智能学会理事、智 [M].北凉：北京航空航天大学出版社，2010：12-18 能产品与产业工作委员会秘书长，中国 [7]王晓丽，杨兆升，吕旭涛，等.平行四边形限制最短路径计量测试学会高级会员.主要研究方向算法及其在交通网络中的应用[J刀，吉林大学学报：：工为非电量检测技术、计算机测控技术、学版，2006,36(1))：123-127. 嵌入式技术应用，主持或参与国家科技 WANG Xiaoli,YANG Zhaosheng,LV Xutao.Shortest 攻关、省部级、横向等各类科研项目30余项，发表学术论文 path algorithm based on limiting parallelogram[]Journal 30余篇，获国家发明专利3项. of Jilin University::Engineering and Technology Edition, 2006,36(1):123-127. 韩力群，女，1953年生，教授，中国人 18引魏二虎，贾满，李林燕.最短路径算法的改进方法研究工智能学会副理事长主要研究方向为智 [0.测绘信息与工程，2007,32(4)：40-2 能信息处理与图像工程技术，主持各类科 WEI Erhu,JIA Man,LI Linyan.On improvements for 研项目30余项，获国家发明专利3项、北 shortest path algorithm[J].Journal of Geomatics,2007, 京发明创新大赛银奖1项发表学术论文 32(④）：40-42. 120余篇，出版专著10部. 2012IEEE物联网自动化、控制与智能系统国际会议 2012 IEEE International Conference on Cyber Technology in Automation,Control,and Intelligent System May 27-31,2012Bangkok,Thailand IEE-CYBER is a newly established international conference focusing on intelligent cyber systems in automation and control.Today's automation systems are increasingly equipped with sophisticated sensors and network inter- faces to facilitate real-time monitoring and control through the cyber space.As networking technology continues to increase in bandwidth and decrease in price,this trend is expected to grow by leaps and bounds as new generations of internet-friendly automation systems become increasingly interconnected to provide not only fast and cost-effec- ive,but also advanced intelligent control to a wide variety of disciplines such as healthcare,homeland security, energy,telecommunications,environment,transportation,and manufacturing Important Dates: Deadline of fll paper(4 to 6 pages))for review.:December 20,2011 Notification of acceptance::January 31,2012 Early bird registration::February 15,2012 Deadline of final version of full paper:February 28,2012 Website:http:://www.iee-cyber.org/2012/

韩力群,女,1953年生,教授,中国人工智能学会副理事长.主要研究方向为智能信息处理与图像工程技术,主持各类科研项目30余项,获国家发明专利3项、北京发明创新大赛银奖1项.发表学术论文 120余篇,出版专著10部. 16] 王海英,黄强,李传涛,等.图论算法及其MATLAB 实现 [M].北京: 北京航空航天大学出版社,2010: 12-18. 431。何为,男,1953年生,高级工程师, EEE会员,中国人工智能学会理事、智能产品与产业工作委员会秘书长,中国计量测试学会高级会员.主要研究方向为非电量检测技术、计算机测控技术、 18] 嵌入式技术应用,主持或参与国家科技攻关、省部级、横向等各类科研项目30余项,发表学术论文 30余篇,获国家发明专利3项. 魏二虎,贾满,李林燕.最短路径算法的改进方法研究 mportant Dates: WANG Xiaoli,YANG Zhaosheng,LV Xutao. Shortest path algorithm based on limiting parallelogram[J] . Journal of Jilin University: Engineering and Technology Edition, 2006,36(1) :123-127. 陈亮,等: RBF神经网络的行车路径代价函数建模 May 27-31,2012Bangkok,Thailand 15] PETTIE S,RAMACHANDRA V. A shortest path algorithm for real-weighted undirected graphs[J] . SIAM Journal of Computing,2005,34(6) : 1398-1427. LUO Song,WANG Jian. Optimal path search study and practice based on the intelligent transportation systems[J]. Development and Innovation of Machinery and Electrical Products,2008,21(2) : 10-12. IEE-CYBER is a newly established international conference focusing on intelligent cyber systems in automation and control. Today's automation systems are increasingly equipped with sophisticated sensors and network interfaces to facilitate real-time monitoring and control through the cyber space. As networking technology continues to ncrease in bandwidth and decrease in price,this trend is expected to grow by leaps and bounds as new generations of internet-friendly automation systems become increasingly interconnected to provide not only fast and cost-effecive,but also advanced intelligent control to a wide variety of disciplines such as healthcare,homeland security, energy,telecommunications,environment,transportation,and manufacturing. 与实现[J] .机电产品开发与创新,2008,21(2) : 10- 12. [17] 王晓丽,杨兆升,吕旭涛,等.平行四边形限制最短路径算法及其在交通网络中的应用[J] .吉林大学学报: 工学版,2006,36(1) : 123-127. 2012 IEEE物联网自动化、控制与智能系统国际会议 2012 IEEE International Conference on Cyber Technology in Automation, Control,and Intelligent System 作者简介: 陈亮,男,1986年生,硕士研究生,主要研究方向为人工神经网络、智能交通. Deadline of fll paper(4 to 6 pages) for review: December 20,2011 Notification of acceptance: January 31,2012 Early bird registration: February 15,2012 Deadline of final version of full paper: February 28,2012 Website: http: //www.iee-cyber.org/2012/ [J] .测绘信息与工程,2007,32(4) : 40-42. WEI Erhu,JIA Man,LI Linyan. On improvements for shortest path algorithm[J]. Journal of Geomatics,2007, 32(4) :40-42. 第5期