改进蛙跳算法的小波神经网络短时交通流预测

2020-06-19 08:45郑俊褒饶珊珊
软件导刊 2020年4期

郑俊褒 饶珊珊

摘要:为改进小波神经网络模型对短时交通流的预测效果,提出一种基于改进混合蛙跳算法的短时交通流预测模型用以优化小波神经网络。该算法使用交叉分组法对子群进行划分,再利用具有自适应因子的局部搜索策略平衡混合蛙跳算法局部与全局搜索能力,最后把得到的最优解用于优化小波神经网络模型初始值,并对短时交通流进行预测。实验结果表明,该方法对短时交通流预测精确度达到97.43%,比传统方法提高1.0161%.均方根误差比传统方法降低了5.5879%,具有较高的应用价值。

关键词:交通流预测;混合蛙跳算法;小波神经网络;交叉分组;自适应因子

DOI: 10. 11907/rjdk.191771

开放科学(资源服务)标识码(OSID):

中图分类号:TP306

文献标识码:A

文章编号:1672-7800(2020)004-0050-05

Short-term Traffic Flow Prediction of Wavelet Neural Network

Based on the Improved Shuffled Flog Leaping Algorithm

ZHENG Jun-bao . RAO Shan-shan

(Sch.ool of Information Scierzce and Technology , Zhejiang Sci- Teclz University . Hangzhou 3 1 00 1 8 . Ch.ina )Abstract: In order to improve the prediction effect of' wavelet neural network model on short-time traffic flow. a short time traf'fic flowprediction model based on improved shuffled frog leaping algorithm is proposed to optimize ,,-avelet neural network. The algorithm usescross grouping method to divide the subgroups, and then uses the local search strategy with adaptive factors to halance the local andglobal search ability of the hyhrid frog jump algorithm. Finally the optimal solution is used to optimize the initial value of the waveletneural network model and predict the short-time traffic flow. The experimental results sho,,-, that the accuracy of this method f'orshort-terru traff'ic flow prediction is 97.43% .which is l.0161% higher than the traditional method. and the root mean square error is5.587 9c7e lo\ver than the traditional method . "-hich has high application valu e.Key Words : traf'fic flow prediction ; shuffled flog leaping algorithm ; wavelet neural network ; cross grouping; adaptive factor

O 引言

隨着我国社会经济水平的不断提高和城市化建设规模的扩大,汽车需求量和使用量也随之增加。大量汽车行驶在道路上必然造成交通拥堵,同时道路拥堵也使汽车燃料燃烧不充分,进而加重环境污染。因此如何解决城市交通拥堵、减少交通事故等问题迫在眉睫。智能交通系统[1](Intelligence Transport System,ITS)是一个可以实时准确控制交通运输状况的智能系统,其核心是交通诱导与交通控制。作为现代智能交通系统的核心内容之一,短时交通流预测是实现交通控制与车辆诱导的基础和关键。从20世纪七十年代开始,国内外学者针对短时交通流预测问题提出了多种非线性预测模型,比如支持向量机回归预测模型、小波神经网络模型( Wavelet Neural Networks,WNN)与径向基函数( Radial Basis Function.RBF)神经模型等[2-3]。小波神经网络由小波变换与人T神经网络结合而成,可白由选择合适的非线性小波基函数,使其既具备小波变换的良好特性,义充分利用神经网络对非线性信号的处理能力,使小波神经网络模型在交通线预测应用中取得了较好的预测效果[4];但另一方面,WNN模型中的梯度下降算法有权值、参数初始值敏感及容易陷入局部最优解等固有缺陷,因此该模型在短时交通流预测方面有较大的优化空间。

针对WNN模型中梯度下降算法的缺陷,近年来学者们提出用群体智能算法优化小波神经网络。混合蛙跳算法(Shuffled Flog Leaping Algorithm,SFLA)是一种新兴的群体智能算法,在处理具有复杂多峰的高维交通流信号时表现出良好的鲁棒性与全局收敛性,不过由于经典SFLA算法在更新搜索时具有随机性,容易在寻优过程中陷入局部最优或错过全局最优解。为了避免上述问题,国内外学者进行了大量研究。文献[5]在经典SFLA算法的基础上,提出了一种新的搜索策略,该方法对每只青蛙权重进行更新,并且重新划分青蛙种群,以此避免算法在搜索过程中的不确定性;文献[6]将模拟退火的思想与SFLA算法结合,利用静态的罚函数法把多目标有约束情况转化成无约束情况,提升算法鲁棒性与寻优效果;文献[7]从青蛙子群内的更新方式人手,用最优个体的惯性矩替换原更新方式,以提升SFLA算法收敛特性;文献[8]结合云模型,利用其在定量和定性之间的转换,提出一种白适应变化分组的混合蛙跳算法,一定程度上降低了算法在寻优时陷入局部最优的可能性。以上方法在一定程度上优化了SFLA算法缺陷,但考虑到交通流预测的复杂性和对实时性要求,亟需效果更好的SFLA优化算法,且该算法在基于WNN模型的短时交通流预测中还有较大优化空间。

综上所述,本文提出改进混合蛙跳算法优化小波神经网络的短时交通流预测。该方法利用改进的混合蛙跳算法弥补小波神经网络权值、阈值随机性的缺陷,将SFLA算法良好的鲁棒性与WNN模型非线性拟合能力结合构建预测模型,进一步提升短时交通流预测效果。

1小波神经网络与混合蛙跳算法

1.1 小波神经网络

在20世纪90年代,张清华等学者[9-10]综合人T神经网络与小波变换的优点,提出具备更快学习能力与更好时频性质的小波神经网络。本文采用3层紧密型小波神经网络,将小波基函数作为隐含层神经元激励函数,其拓扑结构如图1所示。

其中,最左侧的xi是输入向量,h,是隐含层输出yi。是输出向量,m是输入层节点数,s是隐含层节点数,n是输出层对应的節点数,(x)是小波基函数,wij是输入层节点与隐含层节点之间连接的权值,ejk是隐含层节点与输出层节点之间连接的权值。隐含层节点神经元激励函数取Morlet小波基函数,其母小波表达式为:

输入层和输入层与隐含层之间的权值乘积和为隐含层的输入xj:。

则隐含层的输出矗,计算公式为:

其中,h是选定的Morlet小波基函数,a:是伸缩因子,bj是平移因子。

根据隐含层输出,计算输出层的输出 yk为:其中,Wjk是隐含层与输出层之间的权值。

小波神经网络在小波基函数与权值之间的修正过程中,使用梯度下降算法调整实际值与预测输出的误差。权值修正一般有两种方法:将所有样本输入后再相应修正或每输入一次样本即进行修正。本文使用第二种方式,该方法误差值ek可表示为:其中,yk是输出层实际期望的输出值。

1.2 混合蛙跳算法

混合蛙跳算法是一个模仿青蛙在有限空间里觅食过程的算法,它同时具备全局搜索与局部更新的能力[11-13],其迭代步骤可总结为:

(1)参数设置和初始化。首先设定种群规模是F,子群数为m,子群中的个体数为n,有F=m×n,子群最大进化代数为G。。其中种群F的解记为{XI,x2,x3,…,xf},则S维解空间里的第i个解可记为x1=(xi1,xi2,xi3,…,xis)(i=1,2,3,…,F)。

(2)划分子群。种群中每个个体的适应度记为f(x1)(=1,2,3,…,F),每只青蛙的适应度按照降序排列,适应度最高的青蛙x记为种群最优解,然后将种群分成m个子群,记为yl,y2,y3,…,Ym,每个子群里有n只个体。划分子群的规则为:首先把适应度最高的个体分到Y1子群中,把适应度第二高的青蛙个体分到Y子群中,按该顺序依次把适应度第m的个体分到y子群中;再将适应度第m+l的个体分到¨中,第m+2的个体分到y中,直到全部个体分完[14]。此时子群中存在的最优解和最差解为x6和xw。

(3)子群局部搜索。在子群中,每一次跳跃(迭代)均会更新一次适应度最低的个体,方法为:其中,Rand()是在[0,1]之间取的随机数,D.是青蛙移动的步长, 是青蛙最大的移动步长。

使用式(6)更新适应度最小的青蛙位置,如果更新后的解优于最差解xw,则用该解替换xw,反之则使用xg替换式(7)中的xb,然后重新计算式(6)、式(7)并更新xw”,若得到的解没有优于最差解,则产生一个随机新解替换原来的xw,对子群中位置最差的青蛙进行更新,即完成一次迭代。重复上述操作,直到子群迭代次数达到预先设定的最大进化代数时,结束局部搜索。

(4)子群种群混合。当m个子群完成一轮进化后,重新混合种群的所有个体,得到X={Y,UY2U Y3U -UYm),并且计算每个个体的适应度,按照从大到小的顺序重新排列并记录种群最优个体x8,再按照划分规则重新划分子群,进行局部搜索与全局混合,直到达到终止条件,结束SFLA算法。

2 基于改进混合蛙跳算法的小波神经网络优化

小波神经网络的梯度下降算法对权值等参数初始值敏感且容易陷入局部极小值,混合蛙跳算法虽然具有原理简单、容易实现等优点,但也存在不同子群中个体差异较大及移动步长有随机性等缺陷。针对以上不足,本文充分考虑交通流信号强非线性、时空性和周期性,提出一种改进的SFLA算法,即利用交叉分组法划分子群,然后利用具有白适应因子的局部搜索策略,以此平衡算法局部与全局搜索能力,并用得到的最优解和权值解决WNN模型初始值敏感的问题,组成改进的ISFLA-WNN预测模型,优化模型收敛性能,提升短时交通流预测速度与精度。

2.1基于种群交叉的分组方法

在经典混合蛙跳算法中,子群划分规则会使各个子群内的个体分布不均匀,导致分在最后一个子群内所有个体的适应度相对较差。为降低各子群间的个体差异,本文使用一种不同的子群划分规则——交叉分组法。与经典子群划分规则类似,先将F只青蛙按照适应度从大到小排列,但划分到m个子群内的规则不同,即把适应度最大的青蛙划分到Y子群中,把适应度第二的青蛙划分到y2子群中,依次把适应度第m的青蛙划分到Y子群中;然后将适应度第m+l的青蛙划分到y中,第m+2的青蛙划分到ym-1,中;重复第一次的划分规则,把适应度第2m的青蛙划分到y1中,第2m+l的青蛙划分到y2中,如此循环,直到全部青蛙均被划分到子群中。该规则使各子群之间的差异减小,可以较好地保持子群多样性,加快算法收敛速度。

2.2基于自适应因子的局部搜索策略

SFLA算法求得的最优解直接影响算法优劣,而寻优过程的核心思想是子群局部搜索。在局部搜索时,如果个体移动步长太短,则搜索速度会减慢,从而导致算法陷入局部极值的误区;反之如果步长过长,该个体可能超出所在子群,搜索整个种群时很容易错过全局最优解。在标准SFLA算法中,子群是按照式(6)和式(7)对位置最差个体进行局部搜索,由于随机函数Rand()的存在,移动步长具有较强的随机性,无法充分发挥最优解的引导作用,使局部搜索陷入局部极值或错过全局最优解的情况[15-17]。

针对以上情况,本文考虑在子群进行局部搜索的过程中,加入一个含有白适应因子的参数,使移动步长得到优化。参考式(7),Rand()是一个在0-1之间取值的函数,本言语引入双曲正切函数,设计一个具有不同递增速率的白适应因子。

在SFLA算法中,预先设定子群中最大迭代次数为j、当前迭代次数i则子群中最差个体在更新位置时,其第j次白适应因子设计为:

从图2和式(8)可以看m,在j只取正整数右半边的曲线时,其纵坐标同样位于0-1区间内,符合Rand()函数取值范围,不过该曲线具备两个优点:①函数在区间内单调递增;②函数在区间单调递增时速度不同,开始增长速度较快,使子群中的个体在进行局部搜索时,用较快的速度寻找最优解,可有效避免算法由速度过慢而陷入局部极值的误区;而在函数曲线接近结束时,增长速度较为平缓,使种群在快要结束搜索时用一个比较慢的速率进行局部搜索,个体在最优解周围聚集,算法易收敛于最优解。

所以在加入y=tanh(x)后,SFLA局部搜索寻优能力增强,把式(8)代入到式(7)中,得到SFLA算法移动步长更新公式为:

从式(10)得知,子群中个体不再随机更新移动步长,而是与当前迭代次数相关。随着个体中迭代次数的增加,子群里每个个体的移动步长会随着双曲正切函数白适应因子的增加,以一个合适的速率逐步慢慢扩大。在算法刚开始迭代过程时,白适应因子接近于零,个体移动步长很小,则会在子群范围内进行搜索,使算法全局搜索能力降低,保持整个种群多样性;当算法逐渐迭代到一定次数,白适应因子加大让移动步长同步增大,个体可在全局中进行搜索,有效降低陷入局部极值的可能性。因此引入具有双曲正切函数特性的白适应因子,可以有效优化SFLA算法局部搜索策略,从而进一步提高算法寻优性能。

2.3小波神经网络优化步骤

基于改进的}昆合蛙跳算法ISFLA优化小波神经网络预测模型的过程分为3个部分,即交通流数据预处理、ISF-LA算法得到最优解、WNN预测模型建立[18]。,主要步骤包括:①首先导人采集到的数据集,对数据集进行预处理,包括缺失及异常数据修复、数据降噪、重构;②利用Mapmin-max函数对数据集进行归一化处理;③对小波神经网络模型与混合蛙跳算法参数初始化;④利用交叉分组法对种群进行划分,用式(9)、式(10)进行局部搜索更新,然后}昆合子群种群,直到达到结束条件;⑤使用改进}昆合蛙跳算法对小波神经网络模型进行权值、伸缩因子与平移因子寻优,把寻优后的值赋给网络模型;⑥输入训练数据对小波神经网络进行训练,计算得到网络输出值与误差值;⑦使用加入动态因子的梯度下降算法调整小波神经网络参数,直到满足结束条件时终止,保存权值、伸缩因子与平移因子;⑧把测试数据输入到已训练的小波神经网络模型中进行预测,得到预测结果;⑨对比实际输出与预测输出,计算评价指标。

3 实验与分析

3.1 實验设计与说明

为验证利用改进}昆合蛙跳算法优化小波神经网络的交通流预测模型的可行性和有效性,在配置为64位、2GB随机存储器的Windows 7操作系统与MATLAB R2014a平台上进行仿真实验,本文实验数据集为PeMs系统采集的2018年5月12日至16日,在USl01-N、District 6共5天的历史数据,时间间隔为5分钟,共1440组数据。

本文将改进混合蛙跳算法与小波神经网络结合,构成ISFLA-WNN模型,用ISFLA算法确定网络权值、伸缩因子与平移因子初始值。ISFLA算法利用子群中其它个体对最差个体的吸引与排斥的合力更新策略,使子群种群中的每个个体都参与到进化过程中,保持了种群多样性,提高了算法收敛性能。选择小波神经网络模型中预测误差的倒数作为ISFLA算法的适应度函数,适应度值越大,则青蛙个体位置越好,网络模型权值等参数反映短时交通流内部规律的能力越强。本文实验相关参数如表1、表2所示。

3.2实验评价指标

为定量分析预测效果,本文选用平均绝对误差、平均绝对百分比误差、均方根误差、均等系数4个指标对预测结果进行评价[19-20],依次如式(11)-(14)所示。这4个系数是评价预测效果的重要指标,其中MAPE与RMSE的值越小表示误差越小,EC值越大表示预测拟合度越好,网络预测值越接近实际值,预测效果更优。

其中,Yp(t)表不t时刻小波神经网络预测输出值,Yr(f)表示t时刻交通流实际采集值,N表示交通流预测长度。

3.3 实验结果与分析

为验证本文算法的准确性,使用训练数据分别训练基于传统的SFLA-WNN模型、文献[16]优化的SFLA-WNN模型及本文改进的ISFLA-WNN模型,并把训练好的模型用于预测测试集的交通流,模型预测结果如图3-图5所示,文献[16]优化的CSFLA-WNN模型和本文模型预测交通流与实际交通流之间的误差对比如图6所示。

从图3-图5可以看出,本文改进ISFLA-WNN模型的预测曲线更加贴合,精度相对更高;从图6可看出,ISF-LA-WNN模型预测在极值点处的误差明显下降,由17下降到10,说明改进后的算法模型预测效果得到提升。3种模型预测评价指标如表3所示。

由表3可知,对比另外两个模型,ISFLA-WNN模型预测误差最小,拟合度相比经典算法提高了1.0161%,比CS-FLA-WNN提高了0.4329%,运行时间虽小幅度增加,不过仍在合理范围内,说明ISFLA算法对短时交通流预测的效果具备较高的准确度和较快的收敛速度。考虑到交通流信号在各个道路的表现不同,本文同时对另外一条路段上的数据二进行实验,该组数据来白TMC系统采集的2018年10月12日至16日、Interstrate78号道路上的1440组数据,使用上述3种预测模型对该组数据进行预测,运行指标如表4所示。

从表4的数据可以看出,ISFLA-WNN算法对数据二的预测百分比误差、均方根误差较小,拟合度最高,进一步证明本文使用优化ISFLA-WNN模型对短时交通流预测是有效的。

4 结语

考虑到交通流具有很强的非线性和实时性,本文结合具有良好寻优能力的混合蛙跳算法与对非线性信号拟合度强的小波神经网络,构建了一种基于改进混合蛙跳算法优化小波神经网络的短时交通流预测模型,该模型利用交叉分组法与白适应因子的局部搜索策略改进SFLA算法,将得到的最优权值与小波因子输入到WNN模型中作为初始值,并将优化后的WNN模型用于短时交通流预测,最后与经典SFLA-WNN、改进CSFLA-WNN进行对比。实验结果表明,该模型预测误差值变小,精度提高,预测效果优于其它两种预测模型,可为交通诱导和交通控制提供更完善、精确的预测信息。

参考文献:

[1]郑晓鸿,基于ITS的道路交通事故预警系统设计[J]科技视界,2017( 10):56-56

[2]赵娜,袁家斌,徐晗.智能交通系统综述[J].计算机科学,2014,41(11):7-11

[3]OKUTANI I, STEPHANEDES Y J Dvnamic prediction of traffic vol-ume through Kalman filtering theory[J]Transportation Research PartB Methodolngical, 1984, 18(1):1-11.

[4]KALMAN R E.A new approach to linear filtering and prediction prob-lems[J]Journal of Basic Engineering Transactions, 1960, 82: 35-45.

[5]赵芳,张桂珠.基于新搜索策略的混合蛙跳算法[J].计算机应用与软件,2015(8):224-228.

[6]张潇丹,赵力,邹采荣.一种改进的混合蛙跳算法求解有约束优化 问题[J].山东大学学报(工学版),2013 ,43(1):1-8

[7]KAUR P.MEHTA S. Resource prorisioning and work flow schedulingin clouds using augmented shuffled frog leaping algorithm[J]. Journalof Parallel&Distributed Computing, 2016, 101: 41-50

[8]张强,李盼池.自适应分组混沌云模型蛙跳算法求解连续空间优化问题[J].控制与决策,2015. 30(5):923-928.

[9]ZANC D. FANG Y. WANG D, et al. Long term traffic flow predictionusing residual net and deconvolutional neural network[C]. ChineseConference on Pattern Recognition and Computer Vision.2018: 62-74

[10]YAN Y. ZHANG S,TANG J,et al. Understanding characteristics inmultivariate traffic flow time series from complex network structure[J]. Phvsica A Statistical Mechanics&Its Applications, 2017, 477(C):149-160

[II]EUSLFF M, LANSEY K, PASHA F.Shuffled frog-leaping algo-rithm:a memetic meta-heuristic for discrete optimization[J].Engi- neering Optimization, 2006, 38(2):129-154.

[12] 許金元.混合型蛙跳算法及其应用研究[J].计算机应用研究,2011. 28(8):2835-2837.

[13]牛凡超.基于改进蛙跳算法的小波神经网络短期电力负荷预测研究[D]成都:西南交通大学,2017.

[14]姚志远.基于混沌蛙跳算法的立式淬火炉传感器优化配置研究[D].长沙:中南大学,2013.

[15]张强,李盼池.进化策略自主选择的改进混洗蛙跳算法[J]哈尔滨工程大学学报,2019,40(5):979-985

[16] 李敏楠,刘升.一种基于自适应同步因子的混合蛙跳算法[J].计算机与数字工程,2018. 344(6):20-25.

[17]Jlhr F,SUN S. hreural network multitask learning for traffic flow fore-casting[C]. Proceedings of the International Joint Conference onhreural Networks, 2008: 1897-1901.

[18]CHEN D.Researc.h on traffic flow prediction in the big data environ-ment based on the improved RBF neural network[J]. IEEE Transac-tions on Industrial Informatics, 2017, 99:1.

[19]HONC H. HUANG W,ZHOU X, et al. Short-term traffic flow fore-casting: multi-metric KNN with related station discovery[C].Zhangjiajie: International Conference on Fuzz\ Svstems&Kno\vl-edge Discovery, 2016

[20]WU Y. TAN H. Short-term traffic flow forecasting with spatial-tem-poral correlation in a hybrid deep learning framework[DB/OL].https: //a rxiv.org/pdf/16 12.01022.pdf

(责任编辑:江艳)

收稿日期:2019-06-10

基金项目:浙江省自然科学基金委项目(LY17F020032)

作者简介:郑俊褒(1978-),男,博士,浙江理工大学信息学院副教授、硕士生导师,研究方向为智能信息处理与大数据;饶珊珊

(1995-),女,浙江理工大学信息学院硕士研究生,研究方向为计算机应用技术。