基于改进遗传算法的交通流量小波网络预测

柴良勇,　殷礼胜,　甘　敏,　鲁照权,　谈　堃,　张　艳

(合肥工业大学 电气与自动化工程学院,安徽 合肥　230009)



基于改进遗传算法的交通流量小波网络预测

柴良勇,殷礼胜,甘敏,鲁照权,谈堃,张艳

(合肥工业大学 电气与自动化工程学院,安徽 合肥230009)

针对小波网络结构不易确定和网络参数随机选择易造成较大预测误差的问题,文章通过对采集的交通流数据进行分析和多次试验判断误差,来确定小波神经网络的结构;提出了一种改良的遗传算法来初始化神经网络的权值参数,并对种群的进化进行分析;最后将遗传算法选择出的最优个体解码成小波网络的权值和因子,用构建的小波神经网络来预测短时交通流量,得出预测结果。研究结果表明改进遗传算法优化的小波网络能够较好地预测输出,并能够降低输出误差均值。

遗传算法;小波网络;交通流量;预测

随着交通基础设施建设和智能运输系统的发展,交通规划和交通诱导成为交通领域研究的热点。对于交通规则和交通诱导来说,准确的交通流量是其实现的前提和关键。交通流量预测根据时间跨度可分为长期交通流量预测和短时交通流量预测,其中短时交通流量预测[1-2]是智能运输系统的核心内容,智能运输系统中多个子系统的功能实现都是以其为基础的。神经网络[3]是一个具有高度非线性的动力学系统,具有非线性拟合能力,因此可以利用神经网络模型对交通流量进行短时预测。本文采用基于小波分析的一种前馈神经网络,即小波网络[4]。小波网络具有学习能力强、精度高的特点，也具有较强的逼近能力和容错能力。然而小波网络的连接权值、平移因子、伸缩因子一般只通过随机选取。并且小波神经网络的结构不易确定,特别是中间隐含层数量的选取。本文通过仿真实验选定隐含层的输入,并利用改进的遗传算法对网络的权值和因子进行训练,找到最优解。

1　小波网络结构的确定

1.1小波网络

小波网络是一种以BP神经网络为基础,小波基函数作为隐含层节点传递函数,信号前向传播、误差反向传播的神经网络,拓扑结构[5]如图1所示。

图1　小波网络拓扑结构

图1中,X1,X2,…,Xk为小波神经网络的输入参数;Y1,Y2,…,Yk为小波神经网络的预测输出;ωij和ωjk为小波神经网络权值。在输入序列信号为xi(i=1,2,…,k)时,隐含层输出为：

其中,S(j)为隐含层第j个节点输出值;ωij为输入层到隐含层的连接权值;bj为小波基函数f(j)的平移因子;aj为小波基函数f(j)的伸缩因子;f(j)为小波基函数。

本文选择的小波基函数统一为Morlet母小波基函数,数学式为:

网络输出层计算公式为:

其中,ωjk为隐含层到输出层的连接权值;S(j)为隐含层第j个节点输出值;l为隐含层节点数;m为输出层节点数。

1.2小波网络结构的确定

短时交通流量某时刻的值与本路段前几个时刻的交通流量相关。可将交通流量的前几个时刻作为网络的输入,将要预测的时刻流量作为网络的输出。本文利用文献[2]中某路段的一周数据集合,采集间隔为20 min记录1次,共记录了376个时间点数据。将前280个交通数据用于训练,剩余96个数据用于预测输出。将280个数据依次每4个数据为1组,每组的下一时刻数据为要预测的流量值。这样就将这280个数据分成了276组输入和276组输出。输入的数据为4维的,输出的为1维的。同理可将剩余96组数据分成92组用于测试网络预测的拟合效果。当然在这里也可选择输入的维数为5或6甚至更高维数。一般研究表明，在无拥堵的情况下某时刻流量与之前时刻相距越远关联越小，所以在这里选择维数为4,即120 min内的流量较好。通过数据分析可将小波网络的输入节点定为4,输出节点定为1。下面讨论隐含节点的确定。

一般情况下,小波网络的隐含节点没有固定的选取办法,只通过经验确定,不过隐含节点数越多,函数的样本内数据拟合效果越好,但是会增加网络的学习时间,而且在样本外的预测会变得很差。本文通过多次仿真实验，根据预测误差确定出隐含节点数,这里的误差为平均绝对误差,即

图2　不同隐含层数的预测误差统计结果

通过图2可以得出,当隐含层数过少时,预测输出的误差可能会产生较大的误差,当隐含层数为7时,误差就达到了较小的程度,考虑到训练时间以及避免“过度吻合”的现象,这里选择隐含层节点数为7。即小波网络结构为4-7-1结构。

2　改进的遗传算法优化小波网络

2.1改进的遗传算法优化小波网络权值和因子

遗传算法是一种基于全局选择的优化算法。它通过模拟自然界的优胜劣汰的原理,一代代优化种群个体,并逐步逼近最优解。采用遗传算法对神经网络进行优化,其要素主要包括种群的初始化、设计适应度函数、选择、交叉及变异操作等。下面按步骤先后对改进的遗传算法优化网络进行说明。

2.1.1种群初始化

对于小波神经网络,将网络的输入层到隐含层权值ωij、隐含层到输出层权值ωjk以及伸缩平移因子aj、bj编码成一组染色体,本文采用实数编码,所以该染色体串形式如下:

其中,ω1为输入层到隐含层各权值;ω2为隐含层到输出层的各权值。因此染色体的编码长度为24+6+6+6=42。注意到隐含层的输出公式中伸缩因子aj为分母,因此不能为零,故在后面的种群进化变异中需要加一个测试函数来判断aj是否为0。

2.1.2数据预处理

为了加快网络的训练速度,对采集到的数据进行预处理,由于交通流量原序列变化范围较大,直接对原始数据处理会引起较大的波动,所以对数据进行归一化处理,归一化的公式如下:

在Matlab中用[inputn,inputs]=mapmin max(input-train)即可实现数据归一化,input-train为训练样本数据。

2.1.3适应度函数的选取

用个体作为网络的初始权值和因子,用训练样本训练小波网络,然后预测输出。个体的适应度值即为预测输出与期望输出的误差之和,计算公式如下:

其中,n为网络输出节点数,这里为1;yi为网络第i个节点输出;oi为第i个节点期望输出;M为用来预测的样本组数。

2.1.4选择操作

遗传算法的选择操作有锦标赛法、轮盘赌法等,轮盘赌法易造成繁殖机会少,提前收敛于局部最优解的情况,选择误差比较大,有时甚至不能选中适应度高的个体,适应度低的个体反而可能被选中。

最优保留法把适应度高的个体直接复制到下一代,不参与交叉和变异,但是这样会加速进化使其停滞在最优解,从而影响全局搜索能力。

对此,有人提出了期望值法[6],本文提出一种变系数的期望值法,首先计算出个体被选中的期望值,然后根据个体的期望值大小安排被选择的次数。计算公式如下:

按期望值M的整数部分来安排选中的个数,当所有个体选中完之后,为了保证种群的数量保持不变,则对M的小数部分进行排序,按适应度从高到底选择个体填充种群,使其达到种群要求的数量。为了保证进化开始时不能将较优个体选择过多,漏掉一些将来可能会成为最优解的个体，加入了变量β,进化开始时取β=0.9,随着进化的进行,同时为了加快收敛速度,β值变大。这里采用3段式,在种群终止代数的前1/3取β=0.9,中间1/3取β=1.4,后1/3取β=1.8,这样既能够加快进化的收敛速度,也能够避免网络开始就选择局部最优解并大肆繁殖的弊端。

2.1.5交叉操作

交叉是遗传算法的核心操作,是产生新的优秀个体最主要的手段。交叉能将2个个体中优良的性能传递给下一代串中,若交叉后性能不良,可通过选择进行摒弃。

(1) 交叉方式的选择。多点交叉容易破坏原有基因块,但可以产生较多的新基因。因此在迭代前期选取多点交叉比较合适。

进化后期优良个体较多,宜采用一点交叉,避免破坏优良个体。所以在这里采用了3段式的交叉方式:

其中,X、Y为随机选择的染色体;posn为随机选择的染色体交叉点位置,当进化代数i≤(1/3)maxgen(i为进化代数,maxgen为进化终止的代数)时,n=1,2,3;当i>(1/3)maxgen且i≤(2/3)maxgen时,n=1,2；当i>(2/3)maxgen时,n=1;其中β为随机数。

(2) 交叉概率的选择。交叉概率决定一次循环中是否进行交叉操作。交叉概率越大,交叉越频繁;交叉概率越小,则不能产生新的个体,种群进化严重迟缓。一般交叉概率取0.4～0.99之间。

本文采用变交叉概率[7]来决定交叉的操作，公式如下:

其中,Pc0为交叉初始概率;Pstep为交叉概率减少的步长;i为遗传进化的代数;Pc min为预先设定的最小交叉率。本文取Pc min=0.4,Pc0=0.99,Pstep=0.008。

2.1.6变异操作

变异是对遗传算法的改进,既能防止遗传算法收敛到局部最优解,也能对交叉中丢失的某种基因进行修复和补充。变异的概率一般取0.000 1～0.1。随着进化代数的增加,希望变异的概率越大,这样能够加大局部搜索而取得更优的个体。与前面的交叉分段操作保持一致,在总进化代数的前1/3,取变异率Pm=0.001,中间1/3取Pm=0.01,最后部分取Pm=0.1。变异操作如下:

X(pos)=X(pos)+Mu,

2.1.7解码、计算适应度及跳转

将上述经过选择、交叉、变异之后的种群个体依次解码成小波网络的权值和因子,利用解码后的权值和因子训练小波网络,训练条件满足之后,运用测试数据预测输出,进而计算出误差,即计算出个体的适应度大小。挑选出这一代种群中的最佳适应度和平均适应度,记录在进化轨迹矩阵中。然后判断是否满足进化条件,进化条件可以是适应度达到规定的要求或者进化代数达到规定的数值。条件不满足时,跳转到2.1.4节,进行新一轮的选择、交叉、变异。

2.2改进算法优化小波网络分析

通过上述分析，利用改进的遗传算法优化小波网络的初始权值和因子,在这里将种群的进化代数设置成100,种群的最佳适应度和平均适应度曲线如图3所示。

图3中并不能很直观地看出改进的效果,于是将改进前后种群进化的平均适应度曲线和最佳适应度曲线放在一起,如图4所示。

图3　改进前后种群的进化曲线

图4　改进前、后平均适应度与最佳适应度的对比

由图3、图4可以看出,改进的遗传算法在种群进化过程中平均适应度比较平缓地降低,相对于未改进前的平均适应度有着更快的收敛速度,在30代时即可达到未改进算法结束时(即100代)的平均适应度，而且进化结束时有着更低的适应度。通过最佳适应度的对比,可发现种群进化寻优的能力大大提高,不到20代即可寻得比未改进算法终止时还优的个体。

针对小波网络参数的改良[8]和用遗传算法优化神经网络[9],以及用遗传算法与小波网络结合[10-11]进行建模拟合非线性系统都有相应的研究,然而相关研究中考虑到遗传算法收敛速度问题的却不多,本文将改进后的遗传算法用来优化小波网络,进化过程、收敛速度均较好。

3　优化后的小波网络预测交通流量

3.1优化后的小波网络用于流量预测

将上面经过改进遗传算法选择后的最优个体解码成小波神经网络权值ωij、ωjk以及伸缩因子aj和平移因子bj。然后采用梯度下降法修正网络的权值和小波基函数的参数。修正过程如下:

(1) 计算网络预测误差。

其中,yo(k)为期望输出;y(k)为网络预测输出。

(2) 根据误差修正小波基因子和网络权值。

其中，调整变量由误差决定,公式如下:

取η=0.01。

(3) 判断算法是否结束,若没有结束,则继续计算误差调整权值。

(4) 当权值调整结束后,利用前面所述的92组测试数据的输入组作为网络的输入,进而可在网络的输出节点得到预测的流量输出。

3.2优化后的小波网络预测流量仿真

经过上述分析,可以得到改进后的交通流量预测图,同时与未改进的交通流量预测图作对比,结果如图5所示。

由图5可以看出，改进和未改进的小波网络都可跟踪实际交通流量的趋势,但是改进后的预测更加贴近实际流量值。在未改进的流量预测中,由于初始权值的随机性,会造成网络收敛到局部最优解,由图5a可见，在时间点的后期预测值明显与真实值相差较大，而且预测在某些点存在较大的误差,这些都是随机选择初始权值和因子而产生的一些不理想的小波预测结果。由图5b可见,改进后的小波神经网络能够将误差控制在合理的范围内,更好地预测网络的输出。

图5　未改进和遗传算法改进后小波流量预测

为了说明改进前、后的交通流量误差情况,再进行一组实验,将实际流量与预测流量的误差刻画在一张图中,分别为改进前和改进后的误差。在这里误差取为预测值与真实值之差。误差图如图6所示。

图6　改进前、后误差对比

从图6可以看出,改进后的预测误差可以控制在一个较小的范围内波动,而未改进的误差均值明显大于改进后网络预测输出的误差。由此可见改进后的小波网络能够较好地预测交通流量。此外,进行了50组的仿真实验预测,将每个时间点的预测绝对误差求和再平均,得到下面2个数据：未改进的总平均绝对误差为24.54,且在这50组中出现了6次平均误差大于40的情况；而改进后的预测平均误差为18.72,且没有1组误差大于25。由此可以得出结论,基于改进遗传算法的小波网络能更好地预测交通流量。

4　结　论

与传统预测交通流量相比,神经网络具有更优的预测能力,这得益于它自身的特点,它擅长于描述非线性系统以及数学模型难以表达的复杂系统。关于小波网络结构的选取,目前还没有很好的定论,在这里只是经过简单的试凑找出相对合适的隐含层节点数。小波网络连接权值和伸缩平移因子的初始值选择不当,会导致整个网络学习不收敛,预测误差加大。因此本文加入了遗传算法去初始化网络的权值和因子,同时对遗传算法进行了改进,可以加快它收敛到最优解的速度,仿真结果表明改进的遗传算法能够更快地收敛到最优解。采用优化的权值因子来构建小波网络用来预测输出,能够更好地跟踪预测真实值。

[1]高慧，赵建玉,贾磊.短时交通流预测方法综述[J].济南大学学报(自然科学版)，2008,22(1):88-94.

[2]YANG L C，JIA L,WANG H.Wavelet network with genetic algorithm and its applications for traffic flow forecasting[C]//Fifth World Congress on Intelligent Control and Automation,Vol 6.IEEE,2004:5330-5333.

[3]刘金锟.智能控制[M].3版.北京:电子工业出版社,2014:198-224.

[4]DING Y，SHOUSHENG L I U，SHOUSONG H U.Extended wavelet neural network structure and its optimal method[J].Control Theory & Applications,2003:564-570.

[5]史峰,王小川,郁磊,等.MATLAB神经网络30个案例分析[M].北京: 北京航天航空大学出版社，2009:208-217.

[6]许奎.基于改进自适应遗传算法的配电网重构的研究[D].南宁: 广西大学，2008.

[7]蒲永红.改进遗传算法在无功优化中的应用研究[D].济南:山东大学，2007.

[8]张清华.小波神经网络参数优化及其应用[D].沈阳:东北农业大学，2009.

[9]孙丽娟.基于遗传算法的小波神经网络短时交通流预测[D].济南:山东科技大学，2009.

[10]邹巍,陆百川,邓捷,等.基于遗传算法与小波神经网络的客流预测研究[J].武汉理工大学学报:交通科学与工程版，2014,38(5):1148-1151.

[11]李婧瑜,李歧强,侯海燕,等.基于遗传算法的小波神经网络交通流预测[J].山东大学学报(工学版)，2007,37(2):109-112.

(责任编辑张镅)

Prediction of traffic flow with wavelet network based on improved genetic algorithm

CHAI Liangyong,YIN Lisheng,GAN Min,LU Zhaoquan,TAN Kun,ZHANG Yan

(School of Electric Engineering and Automation, Hefei University of Technology, Hefei 230009, China)

For the problems that hidden layers of the wavelet network are not easy to determine and random selection of network parameters easily causes greater prediction errors, the structure of wavelet neural network is determined through the analysis of traffic data collected and the error determination using the simulation of several tests. Then an improved genetic algorithm is proposed to initialize the neural network weights and thresholds, and to analyze the evolution of the population. Finally, the best individual selected by the genetic algorithm is decoded into the wavelet network connection weights and factor. The short-term traffic flow is predicted by using the wavelet neural network constructed, and the predicted results are gotten. The results show that the wavelet network optimized by the improved genetic algorithm can predict output and reduce the average output error.

genetic algorithm; wavelet network; traffic flow; prediction

2015-03-05

柴良勇(1991-),男,安徽宣城人,合肥工业大学硕士生;

鲁照权(1962-),男,安徽庐江人,博士, 合肥工业大学教授,硕士生导师.

10.3969/j.issn.1003-5060.2016.07.008

TP202

A

1003-5060(2016)07-0900-06