基于PSO-SVM的短期交通流预测方法
曹成涛,徐建闽
CAOCheng-tao,XUJian-min
华南理工大学交通学院,广州510641
CollegeofTrafficandCommunications,SouthChinaUniversityofTechnology,Guangzhou510641,ChinaE-mail:jncct@163.com
CAOCheng-tao,XUJian-min.SVMbasedonPSOanditsapplicationintrafficflowpredication.ComputerEngineeringandApplications,2007,43(15):12-14.
Abstract:Theaccuratepredicationofshort-termtrafficflowisessentialinITS.OnthebasisofanalyzingtheparameterperformanceofSupportVectorMachine(SVM)forregressionestimation,thepaperproposesashort-termtrafficflowpredicationmodelbasedonPSO-SVM.TheparameterofSVMisoptimizedbyusingParticleSwarmOptimization(PSO).ThemethodtakesadvantageoftheminimumstructureriskofSVMandthequicklygloballyoptimizingabilityofPSO.Astheproposedmodelcanreducethedimensionalityofdataspaceandpreservefeaturesoftrafficflowtimeseries,itcanpredicttrafficflowefficiently.ThesimulationresultsoftrafficflowcollectedfromChinesenationalhighwayG107proveitsvalidity.Theaveragepredicationerroris3.4%.
Keywords:ParticleSwarmOptimization;trafficflowpredication;SupportVectorMachine;parametersoptimization
摘
要:准确的交通流量预测是智能交通系统中的关键问题。在分析支持向量机SVM回归估计方法参数性能的基础上,提出了粒
子群算法PSO优化参数的PSO-SVM短期交通流预测模型。模型利用支持向量机具有结构风险最小化的特性和粒子群算法快速全局优化特点,实现了数据降维并且保持了交通流序列的特征,因此可以高效地预测交通流量。用G107国道现场采集的数据仿真表明了该模型的有效性,预测平均误差为3.4%。关键词:粒子群优化;交通流预测;支持向量机;参数优化文章编号:1002-8331(2007)15-0012-03
文献标识码:A
中图分类号:TP181;U491
问题时,首先将非线性问题转化为高维空间的线性问题,然后用一个核函数来代替高维空间中的内积计算,有效克服了维数灾难和局部极小问题。
1前言
交通流量预测是城市交通实现智能控制和诱导的前提。因
此实时、准确的交通流预测成为智能交通中的重要课题。传统的交通流预测方法有:回归分析、时间序列等。由于交通流具有高度的非线性、复杂性和不确定性,用常规的数学方法建立模型,不仅工作量大,而且精度难以保证。人工神经网络(ANN)作为一种新兴的方法在交通流预测领域取得了一定的成果。ANN具有较强的自学习能力和可以逼近任意非线性函数的特点。但是神经网络存在收敛速度慢,结构选择和局部极小点问题,有时出现过学习和泛化性差的问题。
支持向量机是一种新的基于结构风险最小化原理的机器学习技术,能较好地解决小样本、非线性、高维数和局部极小点等问题,已成为机器学习界的研究热点之一,在非线性系统辨识、预测预报、建模控制等领域得到了广泛的应用。SVM最初用来解决模式识别问题,后来随着不敏感函数的引入,SVM扩展为解决非线性回归问题,并展现了极好的性能。SVM的最大特点是针对结构风险最小化原则提出的,改变了传统的经验风险最小化原则,因此具有很好的泛化能力。SVM在处理非线性
SVM是基于统计学习的机器学习算法,但是其理论优势
得以实现的前提是要选取到合适的回归参数。不敏感损失系数、惩罚系数C、核函数及其参数的选择对于回归模型的学习精ε
度和泛化能力的好坏起着决定性的作用。传统的回归参数的选取都是通过反复试验,人工选取出较优的解。这种方法依赖于人的主观经验,并且要花费较多的时间[1]。本文在分析SVM各参数对其性能影响的基础上,提出了用粒子群算法PSO优化参数的PSO-SVM短期交通流预测模型,实现了数据降维并且保持了交通流序列的特征,使得SVM的参数选取由人工选取变为自动确定,用G107国道现场采集的交通流量仿真表明了该模型的有效性。预测平均误差为3.4%。
2非线性回归支持向量算法
用SVM算法进行预测时,其基本思想是通过一个非线性
映射\"(x),把输入空间的数据x映射到高维特征空间中去,然
基金项目:国家自然科学基金(theNationalNaturalScienceFoundationofChinaunderGrantNo.50578064);国家高技术研究发展计划(863)(the
NationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.2006AA11z211)。作者简介:曹成涛(1981-),男,博士生,主要研究方向:智能交通控制;徐建闽,教授,博导。
曹成涛,徐建闽:基于PSO-SVM的短期交通流预测方法
后在这一高维空间作线性回归[2]。
给定样本数据(xi,yi),i=1,2,…,N,其中,xi∈Rm为输入向量,yi∈R为相对应的输出变量,y=f(x)为估计输出量。则被估计函数可表示为:
(1)y=f(x)=!T!(x)+b
式中:!(x)为从输入空间到高维空间的非线性映射,!T为权向量,b∈R为偏置。
定义ε不敏感损失函数为:
(x,y,f)=|y-f(x)|ε)Lε=max(0,|y-f(x)|-ε
权向量!T,偏置b通过最小化风险泛函(3)求得:
(2)
2007,43(15)13
曲线变得平缓,但大的ε值会降低回归估计的精度。在非线性回归中一般不需要给出映射%的具体形式,只要给出核函数的形式即可。任何函数只要满足Mercer条件都可用作核函数,不同的核函数构造不同的非线性决策面。常用的核函数有多项式核函数、Sigmoid核函数和高斯径向基核函数[2]。选用径向基核函数式(7)。本文对参数C、和核函数的参数’进行优化。ε
K(x,xi)=exp(-
‖x-xi‖2
)
2’2
(7)
3.2粒子群算法
PSO算法中,每个粒子的位置就是一个潜在的解。PSO随
1‖!‖2+CL(x,y,f)
#εii
2i=1
2N
(3)
机初始化一群粒子和粒子的速度。第i个粒子在d维空间的位置表示为Xi=(Xi1,Xi2,…,Xid);速度Vi=(Vi1,Vi2,…,Vid),它决定粒子在搜索空间单位迭代次数的位移,d为实际解决问题中的自变量个数。计算每一个粒子的适应度,适应度函数一般由实际问题中被优化的函数决定;根据每一个粒子的适应度,更新每个粒子的个体最优值Pi=(Pi1,Pi2,…,Pid)和全局最优值gi=(gi1,gi2,…,gid)[3]。粒子根据以下公式来更新其速度和位置:
其中第一项1‖!‖2称为模型复杂性项,第二项是由ε不敏感损失函数确定的经验误差项,C为调整这二者的平衡参数,称为惩罚系数。
为了求系数!和b,引入非负的松弛变量#i和#,得到等价的原问题:
N
T
*
i
Vi(t+1)=(Vi(t)+C1R1[Pi(t)-Xi(t)]+C2R2[gi(t)-Xi(t)]Xi(t+1)=Xi(t)+Vi(t+1)
(4)
(8)(9)
minS=1‖!‖2+C$(#i+#i*)
2i=1s.t.
yi-[!!(x)+b]≤ε+#i[!!(x)+b]-yi≤ε+#i*#i,#≥0,i=1,2,…,N
*
i
其中(为惯性权重,C1和C2为加速常数,R1和R2为[0,1]之间的随机数。微粒通过不断学习更新,最终飞至解空间中最优解所在的位置,最后输出的gi就是算法找到的全局最优解。式(8)等号右边的第1部分为微粒先前的速度,它维持算法拓展搜索空间的能力;第2部分为“认知”部分,表示微粒自身的思考,防止算法陷入局部最优;第3部分为“社会”部分,表示微粒间的信息共享和互相合作。在更新过程中,粒子在每一维飞行的速度不能超过算法设定的最大速度Vmax。设置较大的Vmax可以保证粒子种群的全局搜索能力,Vmax较小则种群的局部搜索
j
由于特征空间的维数很高,直接求解(4)有很大的困难,
SVM回归方法通过引入核函数K(xi,xj)和对偶技巧将上述问
题转化为对偶问题:
maxQ($i,$i*)=$($i*-$i)yi-ε$($i*+$i)-
i=1
i=1*
j
NN
12N
i,j=1
$($-$)($-$)K(x,x)
*i
i
j
i
N
能力加强。同时,粒子每一维的坐标也被限制在允许范围Xmax内。Vmax与Xmax都是常数,由用户设定,并且每一维的Xmax可以不同。迭代终止条件根据具体问题一般选为计算达到最大迭代次数或满足规定的误差标准为止。
(5)
在标准PSO算法中,惯性权重(是控制历史速度对当前速度的影响程度、平衡PSO算法的全局搜索能力和局部搜索能力的[4]。本文将(从最大惯性权重到最小惯性权重线性减小以平衡局部和全局搜索能力:
s.t.
$($-$)=0
*
i
i
i=1
0≤$i,$i*≤C
其中核函数K(xi,xj)等于向量xi和xj在其特征空间中的像
%(xi)和!(xj)的内积,用核函数代替内积运算,实现由低维空
间到高维空间的映射,因此高维特征空间的线性回归对应于低维特征空间的非线性回归,且免去了高维空间的点积计算。&i、
&i*分别为松弛变量#i、#i*对应的拉格朗日乘子,考虑到KKT条件满足:&i&i*=0。
最后测试样本对应的回归函数(1)可表示为:
y=f(x)=$(&i-&i*)K(x,xi)+b
i=1N
(=(max-
(max-(min
ttmax
(10)
最小惯性权重。tmax为最大迭代次数,(max、(min分别为最大、
3.3基于粒子群优化的SVM算法设计
利用粒子群快速全局优化的特点对SVM的参数进行优化
(6)
可以提高预测的准确性并减少试算的盲目性,步骤如下:
(1)初始化粒子群规模及个体极值、全局极值、最大迭代次数,随机给出粒子初始位置Xi(0)和速度Vi(0)。惯性权重范围为(max、(min。粒子向量代表一个支持向量机模型,该模型对应不同的支持向量机参数,即惩罚系数C、不敏感损失系数ε和核参数’。
(2)计算每个粒子的适应度,取适应度函数如式(11):
N
1
3基于PSO算法的SVM参数优选方法
3.1SVM参数对其性能的影响
用SVM方法进行预测,模型参数的选择对预测精度有着重要的影响。惩罚系数C是在确定的特征空间中对回归曲线的平滑度和经验风险进行折中,即可以控制回归模型的鲁棒性。C取大值,由式(5)知对偶问题的拉格朗日乘子取值较大,造成较大的支持向量在式(6)中起到决定作用。因此这时对训练数据的拟合度高,但泛化能力差。不敏感损失系数ε对支持值增加,支持向量的个数减少,回归向量的数目起决定作用,ε
y-yi2)(11)S(x)=($Ni=1
其中yi为第i个样本的实测值,y为第i个样本的预测值,i=1,2,…,N,N为测试样本个数。142007,43(15)ComputerEngineeringandApplications计算机工程与应用
(3)比较适应度,确定每个粒子的个体极值点:
若S(Pi(t))<S(Pi(t-1)),Pi(t)=Pi(t);否则,Pi(t)=Pi(t-1);若S(gi(t))<S(gi(t-1)),gi(t)=gi(t);否则,gi(t)=gi(t-1)。(4)更新每个粒子的位置和速度。根据式(8)、式(9)分别更新粒子的速度和位置,并且考虑更新后的速度和位置是否在限定的范围内。
(5)比较次数是否达到最大迭代次数或精度值是否达到要求。若满足预设精度,算法收敛,最后一次迭代的全局最优值gi中每一维的参数就是我们所求的;否则返(2),算法继续迭代。
4基于PSO-SVM的短期交通流预测4.1时序相空间重构
为降低建模误差,对原始数据进行归一化处理,然后进行相空间重构。为了使重构的相空间能充分反应系统的特点,恰当选择嵌入维和延迟时间是相空间重构的关键。取延迟时间间隔为序列观测间隔,建立滑动时间窗口xt=(xt-1,xt-2,…,xt-m)。参考文献[5]m值取5最为合理,因此得到如下模式样本集:
!
\"\"\"\"\"\"\"\"\"\"#
x1x2
…
x2x3
…
……
xmxm+1
…
X=
xn-mxn-m+1…xn-1
$%%%%%%%%%%&
,Y=
!\"\"\"\"\"\"\"\"\"\"#
xm+1xm+2
…
xn
$%%%%%%%%%%&
(12)
4.2预测实例及结果
用从G107国道现场采集的一天的交通流量,时间间隔为
粒子群算法快速全局优化特点,实现了数据降维并且保持了交通流序列的特征,因此可以高效地预测交通流量。采用优化算法对支持向量机的参数进行优化可以减少试算的盲目性并且可以提高预测的精度。(收稿日期:2007年1月)
5min,共288个数据对算法进行了验证。由式(12)知n=288,n-m=283,用前200组数据作为学习样本,后83组数据作为测
试样本来验证交通流量预测的准确性。
在MATLAB环境下编写了PSO-SVM程序,取群体规模为
20,最大迭代次数为400,粒子的向量维数为3,PSO加速常数C1=C2=2,惩罚系数C取值范围为[1,150],不敏感损失系数ε取
值范围为[0,0.5],核参数\"的取值范围为[0.1,8],向量的最大速度为(100.10.5),惯性权重#max=0.9,#min=0.4。
参考文献:
[1]杨金芳,翟永杰,王东风,等.基于支持向量回归的时间序列预测[J].
中国电机工程学报,2005,25(17):110-114.
83个预测样本的实际值和预测值曲线如图1所示;预测
的平均相对误差为3.4%,最大相对误差为10.3%,预测效果比较理想;预测的误差变化曲线如图2所示。
[2]CristianiniN,Shawe-TaylorJ.AnintroductiontoSupportVector
Machinesandotherkernel-basedlearningmachine[M].北京:机械工业出版社,2005.
[3]潘昊,侯清兰.基于粒子群优化算法的BP网络学习研究[J].计算机
工程与应用,2006,42(16):41-44.
5结论
本文提出了基于粒子群优化算法的SVM算法,在分析
[4]郑小霞,钱峰.一种改进的微粒群优化算法[J].计算机工程,2006,32
(15):25-27.
SVM参数对其性能的影响的基础上,给出了参数的范围和优
化方法,并把该算法应用到了短期交通流预测中,取得了较好的效果。该算法利用支持向量机具有结构风险最小化的特性和
[5]向红艳,朱顺应.小流量下短时交通量预测最佳窗口长度与时间间
隔[J].武汉理工大学学报:交通科学与工程版,2006,30(4):626-
628.
(上接5页)
tacksforscenariorecognition[C]//Proceedings,DARPAInformation
03),Washing-SurvivabilityConferenceandExposition(DISCEX’ton,DC,IEEEComputerSociety,2003:284-292.
[32]RamakrishnanCR,SekarR.Model-basedanalysisofconfigura-
tionvulnerabilities[J].JournalofComputerSecurity,2002,10(1/2):189-209.
[33]OuXin-ming,BoyerWF,McQueenMA.Ascalableapproachto
attackgraphgeneration[C]//Proceedingsofthe13thACMConfer-enceonComputerandCommunicationsSecurity,2006:336-345.[34]WojcikM,BergeronT,WittboldT,etal.IntroductiontoOVAL:a
newlanguagetodeterminethepresenceofsoftwarevulnerabili-ties[EB/OL].(2003-11)[2004-10-28].http://oval.mitre.org/docu-ments/docs-03/intro/intro.html.
[35]BealeJ,MeerH,TemminghR,etal.Nessusnetworkauditing,
chapter11[M].[S.l.]:SyngressPublishing,1998.
因篇幅问题不能全部显示,请点此查看更多更全内容