快速公交线路选线决策规则获取方法

汤旻安, 王晓明, 李 滢

(1. 兰州交通大学 自动化与电气工程学院,兰州 730070;2. 兰州理工大学 机电工程学院,兰州 730050)

快速公交线路选线决策规则获取方法

汤旻安*1,2, 王晓明2, 李 滢1

(1. 兰州交通大学 自动化与电气工程学院,兰州 730070;2. 兰州理工大学 机电工程学院,兰州 730050)

城市快速公交线路选线决策规则的优劣直接关系到公交线路的客运能力能否满足城市客流的需求.本文根据现有公交线路的交通调查客运能力数据,结合 BRT 线路的“大运量、快速性”特点,发现并提取隐藏在其中的重要选线决策规则.针对选线决策问题中的多变量因素具有不确定性的特点,提出一种基于模糊神经网络实现决策规则获取的方法.给出了基于模糊推理的 BP 神经模糊系统结构及算法,通过神经网络提高其学习能力,采用 GA 改进的算法思想克服 BP 神经网络存在的局限.最后通过实例研究验证了模型和算法的有效性,结果可为公共交通线路选线、规划方案的制定提供参考.

智能交通;线路选线;遗传神经模糊网络;快速公交;决策规则

1 引 言

快速公交系统(Bus Rapid Transit,BRT),是一种介于快速轨道交通(Rapid Rail Transit,RRT) 与常规公交(Normal Bus Transit,NBT) 之间的新型公共客运系统,是一种大运量交通方式,通常也被称作“地面上的地铁系统”.其典型的特点突出了“大运量、快速性、舒适性”.城市快速公共交通线路建设中的选线多根据城市区域规划或既有城市路网中的交通主干道来考虑选择,但不同于 NBT 选线, NBT 线路一般为突出区域交通“连通性”,“大运量、快速性”不作为主要考虑因素.好的线路选线决策能使公共交通发挥更大的效用[1,2].根据现行既有 NBT 线路的交通调查客运能力数据,发现并提取隐藏在其中的 BRT 重要选线决策规则.提取决策规则是数据挖掘中的一项重要内容,它从已知数据中挖掘一定规则(规则集)来描述各类数据的特征,并使用获得的规则,预测未知数据的类别,进行知识发现和模式识别.获取知识、运用知识进行管理与决策一直是制约城市交通管理与控制的瓶颈问题[3].在对于决策规则的获取中,文献[4,5]提出了基于粗糙集理论的最简决策规则挖掘算法.文献[6,7]引入模糊聚类,提出实现规则决策的层次型模糊神经网络.

本文研究快速公交线路选线决策规则提取问题.根据现行公共汽车线路的道路客运能力交通调查数据,结合快速公交线路要求的“大运量、快速性”特点需求,提取出快速公交线路选线的决策规则.提出利用模糊逻辑系统对不定量变量处理的优点,通过神经网络改进其学习能力不足的缺点,采用 GA 改进克服 BP 神经网络局限性.采用集成优化算法,建立决策规则获取模型,对模型进行改进优化,并设计相应的求解算法.

2 神经模糊系统模型

模糊逻辑系统技术与神经网络技术相结合,有神经模糊系统 NFS 和模糊神经系统 FNN 两种形式[8,9].神经模糊系统是按照模糊逻辑系统的运算步骤分步分层构建的.基于 BP 神经网络的Mamdani模糊系统结构如图1 所示.第一层,输入层;第二层,计算第一层各输入分量属于各语言变量值模糊集合的隶属函数,每个节点代表一个语言变量值;第三层,每个节点代表一条模糊规则,用来匹配模糊规则前件,计算出每条规则的适配度;第四层,实现第三层适配度的归一化运算,节点数与第三层相同;第五层,输出层,即为模糊判决层,实现从模糊到清晰化的计算.

图1 基于 BP 神经网络的 Mamdani模糊系统结构Fig.1 Structure of Mamdani fuzzy system based on BP neural network

系统的输出如式(1)所示:

3 神经模糊系统的学习算法

由图1知,系统从本质上是一种多层前馈神经网络,参照 BP 网络的误差反传方法来设计、调整参数的学习算法,假设系统的各输入分量的模糊分割数是预先确定的,那么需要学习和调整的参数包括连接权W以及第二层的隶属度函数的尺寸信息.选用 Gaussian 函数作为隶属度函数则包括各个隶属度函数的中心值

按照 BP 网络误差反传的方法设计、调整参数的学习算法.设误差代价函数如式(2)所示:

式中 N表示系统的输出数量;P表示训练模式数;tpi和 ypi分别表示训练输入模式 p 在网络的第 i个节点的期望输出和实际计算输出.利用误差反传算法来计算然后利用一阶梯度寻优算法来调节

4 改进的神经模糊系统

4.1 文献NFS模型研究

针对上述的神经Mamdani模糊系统的缺点——精度不高、训练时间长,文献提出了一种改进的网络结构,改进的网络有四层,包括输入层、隶属函数生成层、推理层及模糊判决层[10].MIMO 的模糊规则可分解为多个 MISO 的模糊规则.不失一般性,以两输入一输出的系统为例,系统结构如图2所示.

图2 改进的神经 Mamdani模糊系统结构Fig.2 Improved neural Mamdani fuzzy system structure

如图2 所示,改进的网络输出如式(3)所示:

研究发现,系统输出式(3)有别于式(1)表示的系统输出,两模型之间既有联系也有本质上的区别.因而该模型是一种新的改进的模糊神经网络系统,运用 Stone-Weirstrass 定理容易证明该模型具有全局逼近性质[10].

分析发现,上述改进的结构模型仍存在以下几个方面的不足:

(1) 第二层模糊隶属度生成函数子空间的划分和 Gaussian 函数参数 (cij,ρij) 依赖于人的经验,存在很大主观性;

(2) 基于梯度下降法的传统 BP 参数学习方法存在不足;

(3) 推理层的结论数是根据 K-means 聚类的方法对样本聚类后得到的,是分步进行的,在网络中不能根据样本特征及网络性能自动地调整规则结论数;

(4) K-means 聚类方法自身也存在不足[11,12,13].

综上所述,在考虑上述改进的基础上,不对推理层的结论数进行异步 K-means 聚类处理,而是通过对模型的学习算法进行改进.提出采用 GA 与BP 算法的集成混合学习算法,根据网络的性能对模糊神经网络连接权值和 Gaussian 隶属函数参数(cij,ρij) 同时进行优化的方法.

4.2 GA 改进的 NFS 模型建立

4.2.1 参数的确定及编码方案

用 GA 优化模糊神经网络时,需要同时优化网络的规则数、相应的权值、每个输入变量对应模糊子集的隶属度函数参数值.

假定系统有 N个输入变量,每个变量在其论域上被划分为 M 个模糊子集.那么网络第二层的节点数目为 N·M 个,网络第三层的节点数目为MN个,即表示该模糊系统最多有 MN条规则.用矩阵 WN·M表示第二层与第三层的节点连接情况,其中 wij=0,表示节点不相连;wij=1,表示节点相连.因为 WN·M表示各个输入变量所属模糊子集间的相互匹配关系,而同一变量的各个模糊子集不能匹配成一条规则,所以 WN·M中有“1”的个数最多为 N· MN,此时代表系统取完全规则数的情形.相应连接权值 (w1,w2,…,wm) 随 WN·M中“1” 的变化而变化.

在使用 GA 时,需要确定编码参数的变化范围,对于每个输入变量 xi,其模糊划分数为 M,其隶属度函数的中心、宽度赋初值由下列的式(4)-式(8)给出.

由此,给定 c1(i) 的取值范围为

ρ1(i) ≥ 0 取值范围为

[0,α·ρ1(1)];[0,α·ρ2(2)];…;[0,α·ρ1(M)]式中 α ＞ 1 用来控制 ρ1(i) ≥ 0 的变化范围.

对参数的编码使用二进制编码形式.GA 的一个染色体对应一个待求解问题的解,算法中每个染色体分为 4 个基因段,Chr=[c,ρ,W,w].

4.2.2 适应度函数

适应度函数表示为

式中 E 为神经网络的输出MAE;B=N·MN为最大规则数;R 为模糊神经网络规则数,即矩阵WN×·M中有“1” 的行个数,且每个个体中至少有 1条模糊规则前件,即 R ≥ 1.这样做的目的是在保证样本逼近精度的前提下使网络的结构尽量简单.

4.2.3 遗传操作设计

选择算子,采用优势保留与轮盘选择法作为选择算子.其中,M=种群×20%.

交叉算子,采用两点交叉算子,对实数编码基因段采用实值重组方式的中间重组方式进行交叉.本文采用一种自适应Pc和Pm方法,用适合度函数来衡量算法的收敛状况,其表达式为:,其中分别为群体中的最大适应度和平均适合

-度;fmax-f体现了群体的收敛程度;k1,k2≤ 1.0为常数.

变异算子,按照变异概率在群体中随机选出变异个体,对于被选中的个体,在字长范围内按均匀分布随机选出变异的字符.

4.3 GA 改进 FNN 算法步骤

利用 GA 进行网络结构和参数优化,应用 BP算法进行快速局部搜索,GA 保证全局优化.求解具体方法如下:

输入 给定现有多条公交线路的客运能力交通调查数据及各条线路基于 BRT“大运量、快速性”需求功能要求的专家决策给定的线路优良度;该输入的给定是采用常规公交系统(NBT)的基础数据,按照 BRT 选线的特殊性要求而分析得到.

输出 模糊神经网络规则数、相应连接权值、隶属度函数参数(cij, ρij) 值.

Step1样本数据的预处理,将样本数据归一化处理.

Step2初始化GA相关参数:种群大小pop_size;最大遗传代数 max_gen;交叉概率 Pc参数 k1、变异概率 Pm参数 k2.

Step3结合具体问题根据染色体编码方案Chr=[c,ρ,W,w],生成随机初始种群,将每个个体表示为染色体的基因编码.

Step4计算个体的适应度值.

Step5对种群进行遗传操作,并判断 W 基因编码中有“1”的行数,如果行数为 0,则随机将 W中某一基因位赋为“1”,否则转第向 6 步.

Step6在一定的规则个数下对每个个体实施 BP 算法,调整参数 c 、 ρ 、 w,获得 Chr*=[c, ρ,W,w],计算适应度值.

Step7令 gen=gen+1, 如 果 gen ＜max_gen,转向第 5 步进行迭代操作;否则停止迭代,输出最优个体 best_chr,则得到最优的网络的规则数与相应的权值及每个输入变量对应模糊子集的隶属度函数参数(cij,ρij) 值.

5 实例研究

5.1 研究对象及样本数据

学习样本及数据采用文献《兰州市综合交通规划—机动车 OD·客运交通·停车调查报告》中的数据.依据现行公共汽车 67 条线路对城市快速公交干线选线进行模糊规则提取实例研究,根据BRT“大运量、快速性”的特点,在此选择现有公交线路车速属性和客流量属性作为系统输入.分别为高峰期上行(1)、高峰期下行(2)、平峰期上行(3)、平峰期下行(4)共4种车速属性数据和单车单向全线高峰期上行(5)、高峰期下行(6)、平峰期上行(7)、平峰期下行(8)共 4 种客流量属性,此 8种输入数据,用来提取快速公交干线选址的模糊规则.在 NFS 网络条件下,首先对数据进行预处理,归一化处理后的数据如表1所示.

表1 用于规则获取的现有公交线路数据Table1 Used for rule acquisition of the existing data from bus lines

5.2 试验各种参数选择

利用 Matlab R2010a 及神经网络工具箱、遗传算法优化工具箱进行算例计算.GA 相关参数的设置为: 种 群 规 模 pop_size=30; 最大迭代次数max_gen=200,k1=0.5,k2=0.1,N=8,M=3, W 的位数为 52 488.同时,在保证参数 c 、ρ保留 4位小数精度的二进制位长.BP 参数调整的步骤为200 步.

受遗传算法的随机性影响,每次运行得到的结果均不一样,对多次计算选择得到优化后的一组(cij, ρij) 参数如表2 所示.

表2 一组模糊规则参数表Table2 Fuzzy rules parameter table

由表2 可知,GA-FNN 将每个输入分量和输出分为三个模糊集合.根据计算结果,表中数据各输入分量的隶属度函数图形如图3、图4 所示.

图3 车速隶属度函数Fig.3 Membership function of speed

图4 流量隶属度函数Fig.4 Membership function of vehicle flow rate

5.3 模糊规则提取

如前 5.2 的结果,选取提取的 2 条模糊规则如表3所示.

表3 提取的决策规则Table3 Extraction of decision rules

5.4 提取规则对比及分析

在上述数据的基础上,将算法改进前后获得的决策规则进行对比如表4所示.

表4 提取的决策规则对比Table4 Comparison of extraction decision rules

为进一步判定获取的决策规则对选线的模式识别,根据表1的各条现行线路客运能力数据,进行线路筛选可获得快速公交线路.结合研究对象的实际路网状况,可获得快速公交线路路由为途经 103、105、109、124、33、50、56、58号线路的路由为最优.

6 研究结论

本文根据 BRT 线路的“大运量、快速性”特点,以常规公交线路的客运能力“客流量属性、车速属性”交通调查数据为基础,研究了快速公交线路选线决策规则的获取方法,针对 BRT 选线决策问题中的多变量(客流量、车速)因素不确定的特点,提出一种基于模糊神经网络实现决策规则获取的方法,并给出了基于模糊推理的 BP 神经模糊系统结构及算法.通过神经网络提高其学习能力,采用GA 改进的算法思想克服 BP 神经网络存在的局限,设计了基于遗传改进的模糊神经网络算法的求解方法.并对该模型进行了实例验证和分析.结果表明,客流量、车速因素的考虑将对 BRT 线路选线结果产生明显影响,因此该模型用于 BRT 选线问题是可行的.

[1] LI Q,WANG Y J,ZHOU Y.Readjustment effect analysis of public bus network in Beijing[J].Journal of Transportation Systems Engineering and Information Technology,2008,8(2):27-33.

[2] 文国玮.城市交通与道路系统规划[M]. 北京:清华大学出版社,2009.[WEN G W.The urban traffic& road system planning[M]. Beijing: Tsinghua University Press,2009.]

[3] 刘锐,严宝杰,黄志鹏.城市公共交通网络的复杂性分析[J].交通运输系统工程与信息,2009,9(3): 17-22.[LIU R,YAN B J,HUANG Z P.Complexity analysis of urban public transit network[J].Journal of Transportation Systems Engineering and Information Technology,2009,9(3):17-22.]

[4] 钱进,孟祥萍,刘大有,等.一种基于粗糙集理论的最简决策规则挖掘算法[J].控制与决策,2007,22 (12):1368-1372.[QIAN J,MENG X P,LIU D Y, et al.A mining algorithm for concise decision rules based on rough setstheory [J]. Controland Decision,2007,22(12):1368-1372.]

[5] 鄂旭,邵良杉,张毅智,等. 一种基于粗糙集理论的规则提取方法[J]. 计算机科学,2011,38(1): 232-235.[E X,SHAO L S,ZHANG Y Z,et al. Method of rule extraction based on rough set theory [J].Computer Science,2011,38(1):232-235.]

[6] 杜建凤,宋梅,张璋,等. 模糊神经网络在决策专家系统中的研究与应用[J].系统工程与电子技术, 2002,24(2):45-47,53.[DU J F,SONG M, ZHANG Z,et al.Research and application of fuzzy neural network in decision expert system[J].Systems Engineering and Electronics,2002,24(2):45-47,53.]

[7] 许翔,张东波,王耀南,等. 基于论域空间模糊划分的粗集神经网络[J].计算机工程,2010,36(21): 199-201.[XU X,ZHANG D B,WANG Y N,et al. Rough set neural network based on fuzzy partition in universal space[J].Computer Engineering,2010,36 (21):199-201.]

[8] Ishigami Hideyuki.Structure optimization of fuzzy neural network by genetic algorithm[J].Fuzzy Sets and Systems,1995,71(3):257-264.

[9] Tahmasebi Pejman.A hybrid neural networks-fuzzy logic-genetic algorithm for grade estimation[J]. Computers and Geosciences,2012,4:18-27.

[10] Leung FHF.An improved genetic-algorithm-based neural-tuned neural network[J].International Journal of Computational Intelligence and Applications,2008, 7(4):469-492.

[11] Malek Hamed,Ebadzadeh Mohammad Mehdi,Rahmati Mohammad.Three new fuzzy neural networks learning algorithms based on clustering,training error and genetic algorithm[J].Applied Intelligence,2012, 37(2):280-289.

[12] WANG Y Q.Application of elevator group control system based on genetic algorithm optimize BP fuzzy neuralnetwork[C]//Proceedings ofthe World Congress on IntelligentControland Automation, 2008,8702-8705.

[13] GERETTI Luca.The synthesis of a stochastic artificial neural network application using a genetic algorithm approach[J].Advances in Imaging and Electron Physics,2011,168:1-63.

Decision Rule Acquisition of Route Selection for Rapid Transit Line

TANG Min-an1,2,WANG Xiao-ming2,LI Ying1
(1.School of Automation and Electrical Engineering,Lanzhou Jiaotong University.,Lanzhou 730070,China; 2.School of Mechanical and Electronical Engineering,Lanzhou University of Technology,Lanzhou 730050,China)

Decision rule of route selection for rapid transit line determines the public transport effect. According to the current existing bus lines ability of passenger traffic survey data,combining with “ rapidity, mass transit” characteristics of BRT lines,this paper is to find and extract important decision rules of route selection,For the problem of route selection,it is required to acquire evolution rule of system status from the changes of multiple environment variable factors,and all kinds of factors are of “ fuzziness” uncertainty characteristics.FLS has the advantages of processing non-quantitative variable,but has the disadvantage of deficient learning capability.The BP neural fuzzy system structure and algorithm is given based on fuzzy inference,to improve its learning capability.Meanwhile,in order to overcome the existing limitations of BP neural network,it puts forward the thought of algorithm improved on the basis of GA.The model and effectiveness of the algorithm are clarified by computational experiments.The results can provide reference for the transit route selection and planning.

intelligent transportation;route selection;genetic neural fuzzy network;rapid transit; decision rule

1009-6744(2014)01-0158-08

U491.1

A

2013-06-19

2013-08-03录用日期:2013-08-16

国家自然科学基金项目(61263004);甘肃省自然科学研究基金项目(0803RJZA020);甘肃省科技支撑计划项目(090GKCA009,1304GKCA023).

汤旻安(1973-),男,陕西勉县人,博士,副教授.*通讯作者:tangminan@yahoo.com