改进GA优化BP神经网络的短时交通流预测

2016-01-04卢建中,程浩

合肥工业大学学报（自然科学版） 2015年1期

程浩(1979-),男,安徽桐城人,博士,合肥工业大学讲师.

卢建中,程浩

(合肥工业大学管理学院,安徽合肥230009)

摘要:为了提高BP 神经网络预测模型对短时交通流的预测准确性,文章提出了一种基于改进遗传算法优化BP神经网络的短时交通流预测方法。由于模拟退火算法具有较强的局部搜索能力,能够在搜索过程中避免陷入局部最优解,因此引入模拟退火算法中的Metropolis接受准则来增加遗传算法的局部搜索能力,避免了遗传算法过早收敛和陷入局部最优解。通过改进的遗传算法优化BP 神经网络的权值和阈值,然后训练BP 神经网络预测模型以求得最优解。仿真结果表明,该方法对短时交通流预测具有较好的预测精确性。

关键词:交通流预测;BP神经网络;遗传算法;模拟退火算法;Metropolis接受准则

Short-termtrafficflowforecastbasedon

modifiedGAoptimizedBPneuralnetwork

LUJian-zhong,CHENGHao

(SchoolofManagement,HefeiUniversityofTechnology,Hefei230009,China)

Abstract:In order to improve the accuracy of short-term traffic flow forecast based on BP neural network prediction model, a forecast method based on modified genetic algorithm(GA) optimized BP neural network is proposed. Because the simulated annealing(SA) algorithm has strong local searching capability and can avoid getting into limited optimum solution in the searching process, the Metropolis acceptance criteria in the SA algorithm is introduced to GA, which effectively overcomes premature convergence and getting into limited optimum solution. The modified genetic algorithm is used to optimize BP neural network’s weights and thresholds, then the BP neural network model is trained to obtain the optimal solution. The simulation results show that this method is accurate in short-term traffic flow forecast.

Keywords:trafficflowforecast;BPneuralnetwork;geneticalgorithm(GA);simulatedannealing(SA)algorithm;Metropolisacceptancecriteria

物联网被认为是继计算机、互联网与移动通信之后的世界信息产业的又一次浪潮,而车联网是物联网应用于智能交通领域的集中体现,也是物联网的一个重点领域。车联网可以实现车与人之间、车与车之间、车与基础设施之间信息通讯的交换,但是组建车联网过程中还有一些关键的技术问题需要研究,如RFID技术、车联网新协议研发、智能交通等。其中智能交通是国内外学者研究的热点,而实时准确的交通流预测是智能交通的前提和关键。

根据交通流预测的时间可以将交通流划分为短时交通流、中期和长期交通流,而短时交通流预测的实时性最强、反映最为快捷,因此实际应用也最为广泛。国内外学者针对短时交通流预测建立了各种模型,如BP神经网络模型[1]、小波理论模型[2]以及混沌理论模型[3-4]等。其中BP神经网络模型是目前广泛应用的预测模型,但是该模型存在易陷入局部极小值、收敛速度慢等缺点,文献[5]利用遗传算法(GA)优化的BP神经网络克服了这些缺点,但是遗传算法存在过早收敛和局部收敛性差的问题。

为了克服上述缺点,本文采用改进的遗传算法优化BP神经网络预测模型——MGABP模型,该算法利用GA优化BP神经网络中的初始权值和阈值,利用模拟退火算法(SA)[6-7]中Metropolis接受准则对GA新适应度和上次迭代适应度进行比较,更有效地找出最优适应度,从而克服了上述遗传算法的缺点。实验结果证明了本文提出的MGABP模型不仅改善了BP神经网络收敛速度慢等缺点,而且对遗传算法的过早收敛和局部收敛性差进行了优化。

1算法基本原理

1.1　遗传算法

遗传算法(geneticalgorithm,GA)[8]是一种借鉴自然界中适者生存、优胜劣汰的进化机制演化而来的高度并行、随机、自适应搜索算法,它目前已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域,它是现代智能计算中的关键技术。在遗传算法计算中,首先对所优化参数进行编码,随机产生n个初始种群,然后根据种群择优目标方向确定种群的适应度函数。通过对种群的选择运算、交叉运算、变异运算后,最终得到遗传算法的解。

1.2　 BP神经网络算法

BP神经网络算法[9]由信号的正向传播和误差的反向传播2个部分组成。正向传播是样本从输入层传入,到达隐含层处理再传向输出层;如果输出与期望的输出有偏差,则将偏差沿着网络反向传播,逐层修改权值和阈值,来达到预测目标。

设Xi=(x1,x2,…,xn)(i=1,2,…,n)为系统输入,输出为Yi=xi+1,选择典型的BP神经网络3层设计,取BP神经网络输入层个数为n、隐含层个数为p、输出层个数为1,转移函数采用Sigmoid函数,则隐含层各个节点的输入与输出为：

(1)

(2)

其中,ωij为连接输入层与隐含层的权值;θj为隐含层节点的阈值。

同理,输出层的节点输入和输出分别为:

(3)

(4)

其中,vj为连接隐含层与输出层的权值;γ为输出层的阈值;bj为隐含层节点的输出。因此输出yi是可以预测的。

1.3　交通流

交通流[10]是指在单位时间内通过道路某一地点、某一断面或者某一车道的实际车辆数,而交通流预测是指利用已有的交通流的历史数据,通过某种方法对将来某时间内的交通流进行预测的技术。其中短时交通流预测是在时间跨度不超过15min,在此时刻t对下一决策时刻t+1乃至以后若干时刻t+n的交通流做出实时精准的预测。

2理论分析与改进

2.1　传统 GA缺陷原因分析

过早收敛和局部收敛性差的原因可以归结如下[11]:

(1) 选择压力。采用排序选择或者竞赛选择模式,当前群体的最优个体期望抽样比较大时,个体选择压力太大,导致群体的多样性迅速减低;反之,则个体选择压力太小,模式竞赛减弱,遗传算子重组生成高阶模式的能力降低,也会出现进化停滞现象。

(2) 变异概率。当变异概率比较小时,群体多样性下降太快,容易导致有效基因迅速丢失且难以恢复;反之,尽管群体多样性可以保持在较高水平,但是高阶模式被破坏的概率也随之增大。

(3) 适应函数性质。当适应度函数高度非线性,染色体基因位之间高度相关,有效模板更容易被破坏;或者最优解附近为非常平缓的超平面,高阶竞争模式适应值的差异非常小,在适应值比例选择方式下的模式竞争激烈,导致当前最佳个体适应值的改进出现停滞。

(4) 群体初始化。初始群体分布在编码空间的局部区域,导致GA的搜索范围受到限制。

2.2　对 GA缺陷问题的改进

针对上述分析可以看出，遗传算法是把握搜索过程的总体能力,但是在遗传的迭代过程中容易错过最优解,导致局部空间搜索能力较弱,从而收敛到全局最优解能力较弱,在优化BP神经网络的过程中存在着过早收敛和局部收敛性差的问题,而模拟退火算法正好克服了这些缺点。

本文借鉴了模拟退火算法(simulatedannealing,SA)思想。SA是在金属加工工艺中,金属材料加热到某一高温状态,然后慢慢冷却下来的金属热处理过程。基于这一机理建立起来了一种局部最优化方法,能够以随机搜索技术从概率意义上找出目标函数的全局最优解。它开始从某个初始解出发,经过大量解的变换后,可以求得给定控制参数值时组合优化问题的相对最优解;然后减小控制参数t的值,重复执行Metropolis算法,就可以在控制参数t趋于0时,最终求得组合优化问题的整体最优解。

由此可以看出模拟退火算法具有较强的局部搜索能力,能够在搜索过程中避免陷入局部最优解。利用SA的这一特性来优化GA,在GA的选择、交叉、变异产生新的适应度后,利用SA中的Metropolis接受准则对GA新适应度和上次迭代适应度进行判断,从而选择最优的适应度,因此有效地抑制遗传算法过早收敛,提高算法局部寻优的精确性。GA缺陷改进流程图如图1所示。

图1　 GA缺陷改进流程图

2.3　 MGABP建模

算法基本步骤如下:

(1) 初始化参数。包括神经网络训练数据归一化、各个网络层节点数;遗传算法种群规模、迭代次数、编码长度计算;模拟退火算法初始温度、温度降低参数以及模拟退火次数初始化。

(2) 创建BP神经网络,将归一化后的训练数据给神经网络的输入层,然后得到神经网络初始网络的权值和阈值作为改进遗传算法的初始种群。假设生成P个个体的初始种群M=(M1,M2,…,MP)T, 为了得到高精度权值和阈值,采用实数编码方式,编码长度为:

(5)

其中,R、S1、S2分别为BP神经网络输入层节点数、隐含层节点数、输出层节点数。

(3) 确定个体的适应度函数。适应度函数的选择是通过BP神经网络对数据进行训练,以其预测值与实际值差的倒数,即预测值的误差倒数作为改进遗传算法的适应度。

(6)

其中,yi为BP神经网络第i节点实际输出;oi为BP神经网络第i节点预测输出;a为(0,1)之间的任意值。

(4) 采用轮盘赌法选择算子,即基于适应度比例的选择策略对每一代种群中的染色体进行选择。选择概率为:

(7)

(5) 由于个体采用实数编码,交叉操作方法采用实数交叉法。第k个染色体ak和第l个染色体al在第j位的交叉操作方法如下:

(8)

其中,b为[0,1]间的随机数。

(6) 变异操作。选取第i个个体的第j个基因aij进行变异操作,即

(9)

(10)

其中,amax、amin分别为基因aij的最大值和最小值;r为[0,1]之间的随机数;r1为随机数;g为当前迭代次数;Gmax为最大进化代数。

(11)

其中,Δf为新的适应度减去上一次迭代适应度的差;T为模拟退火初始温度参数。

(8) 将改进GA得到的最优个体,即BP神经网络输入层到隐含层的权值和阈值, 通过BP神经网络进行训练,训练过的网络再输入一组预测输入数据,通过网络得到最终预测输出值,即短时交通流量的预测值。

3仿真实验及结果

3.1　仿真条件

为了验证本文算法的有效性,在Matlab2012a环境下,采用Matlab语言编写算法程序,并且利用Matlab神经网络工具箱建立如下3种预测模型:BP神经网络短时交通流预测(BP)、遗传算法优化BP神经网络短时交通流预测(GABP)、改进遗传算法优化BP神经网络短时交通流预测(MGABP)。实验分别采用这3种模型对同一路段的交通流量数据进行预测对比。首先在实验中对交通流预测数据进行归一化处理,且处理到[0,1]之间,即

(12)

其中,xmin、xmax为归一化前数据的最小值和最大值;xi为归一化前训练数据;yi为归一化后数据。

实验误差评价采用绝对误差E、平均绝对误差MAE、均方误差MSE、平均相对误差MRE,计算公式如下:

(13)

(14)

(15)

(16)

其中,n为交通流数据个数;xk为交通流量真实值;xk′为交通流量预测值。

实验采用3层BP神经网络结构,BP神经网络参数设定如下:训练次数为100,训练目标为0.000 1,学习率为0.1。遗传算法参数设定为:迭代次数100,种群规模30。模拟退火算法参数设定:初始温度为100,温度降低参数为0.98,模拟退火次数初始为1。

3.2　实测交通流量数据的实证分析

仿真实验数据引用文献[12],在这些数据中,前10组数据的前15行数据为训练输入数据,前10组数据中最后1行数据为训练输出数据。预测输入数据为后8组数据中的前15行数据,后8组数据最后1行数据为真实输出数据。BP、GABP、MGABP神经网络模型预测结果如图2～图4所示。

实验误差结果见表1所列。

图2　 BP神经网络模型预测

图3　 GABP神经网络模型预测

图4　 MGABP神经网络模型预测

从表1中可以看出,在训练样本是150和预测样本为8时,从MAE(平均绝对误差)、MSE(均方误差)和MRE(平均相对误差)可以看出,MGABP模型的数值明显小于GABP模型和BP模型,说明MGABP预测模型对实测交通流的预测效果较好。

表1　实验误差

4结束语

本文针对BP神经网络预测易陷入局部极小值和收敛速度慢的缺点,在GA算法中引入了模拟退火算法中Metropolis接受准则进行判断,提出了改进GA的优化BP神经网络的短时交通流预测方法,可用于车联网交通数据的预测。通过该方法和BP神经网络、GABP神经网络的误差对比分析发现,MGABP模型提高了收敛速度,克服了陷入局部极小值,达到了很好的预测精度。

[参考文献]

关键词[1]白晓雷，黄广君，段建辉.一种基于BP神经网络的抽取方法[J].合肥工业大学学报：自然科学版，2014，37(7)：808-811,896.

收稿日期：2014-01-03；修回日期：2014-08-10

基金项目：国家自然科学基金重点资助项目(71231004)

作者简介：卢建中(1986-),男,安徽庐江人,合肥工业大学硕士生;

doi:10.3969/j.issn.1003-5060.2015.01.027

中图分类号:TP183;U491文献标识码：A

[2]贺国光,李宇,马寿峰.基于小波分解与重构的交通流短时预测法[J].系统工程理论与实践,2002(9):101-106.

[3]董春娇,邵春福,李娟,等. 基于混沌分析的道路网交通流短时预测[J].系统工程学报,2001,26(3):340-345.

[4]卢宇,贺国光.一种新的交通流混沌实时判定方法[J].系统工程理论方法应用,2006,15(5):445-450.

[5]李松,刘力军,解永乐.遗传算法优化BP神经网络的短时交通流混沌预测[J].控制与决策,2011,26(10):1581-1585.

[6]康立山,谢云,尤矢勇,等.非数值并行算法(第一册):模拟退火算法[M].北京: 科学出版社, 2003:1-38.