基于改进的QPSO训练BP网络的网络流量预测

ApplicationResearchofComputersVol.26No.1Jan.2009

基于改进的QPSO训练BP网络的网络流量预测

王 鹏,刘 渊

a

a,b

*

(江南大学a.信息工程学院;b.数字媒体创意中心,江苏无锡214122)

摘 要:为了提高网络流量预测的精度,采用一种改进的QPSO算法训练BP神经网络对网络流量数据的时间序列进行建模预测。针对标准的QPSO算法不可避免地出现早熟的不足,提出一种新的基于参数自适应的QPSO算法,较好地避免了粒子群的早熟,提高了算法的全局收敛性能。仿真实验结果表明,与PSO训练的BP网络、QPSO训练的BP网络作为预测模型相比,该模型具有更高的预测精度及很好的稳定性。关键词:量子粒子群优化算法;粒子群优化算法;早熟;神经网络;网络流量预测

中图分类号:TP393.01 文献标志码:A 文章编号:1001-3695(2009)01-0299-03

NetworktrafficpredictionbasedonBPneuralnetworktrainedbyimprovedQPSO

WANGPenga,LIUYuana,b

(a.SchoolofInformationEngineering,b.DigitalMediaResearchCenter,JiangnanUniversity,WuxiJiangsu214122,China)

Abstract:Inordertoimprovetheprecisionofthenetworktrafficprediction,proposedtheBPneuralnetwork(BPNN)trainedbyanoptimizedQPSOalgorithmtomodelandpredictthetimeseriesofnetworktrafficdata.Proposedanewadaptiveparame-tercontrolmethodforQPSOtoavoidtheparticleprematurelyandimprovedtheabilityofglobalconvergence.Theexperimentalresultsprovethat,comparedwiththemodelofBPNNtrainedbyPSO,andBPNNtrainedbyQPSO,thismodelismoreeffi-cientinnetworktrafficpredictionwithhigherprecisionandbetterstability.Keywords:quantum-behavedparticleswarmoptimization(QPSO);particleswarmoptimization(PSO);particleprematuri-ty;neuralnetwork;networktrafficprediction

网络流量预测在网络设计、管理、控制以及最优化等方面均起到重要的作用,因而一直备受关注。流量预测问题可定义为:给定当前时刻的一组观测流量数据Xn-i(i=0,1,2,…,n)则未来某一时刻的流量Xn+k可由Xn-i给出,这里k是预测步长。大量研究发现,网络流量的某些特性已远远超出了传统队列论中泊松和马尔可夫流量模型的框架[1],用线性方法来预测非线性的网络流量在理论上就存在不足,其预测精度不高。科研人员早已证明具有非线性结构的神经网络系统可以逼近任意的非线性函数[2]。由于神经网络具有自学习能力,它可以只通过输入输出数据构建出非线性模型,因而被广泛用于计算机网络的流量控制和流量预测[3,4]。目前BP网络是应用最广泛和成功的神经网络之一,它结构简单、可塑性强,然而BP网络却存在着易陷入局部极小和收敛速度慢等缺陷。进化算法具有较强的全局收敛能力和较强的鲁棒性,且无须借助问题的特征信息,如导数等梯度信息。因此,将其应用于神经网络学习算法,不仅能发挥神经网络的泛化映射能力,而且能够提高神经网络的收敛速度及学习能力。已经有许多学者将粒子群算法(PSO)应用到BP网络的训练中并用于预测,均取得了较好的效果[5,6]。量子粒子群算法(QPSO)是在对PSO收敛性基础上提出的一种全新的群体智能优化算法。QPSO算法

[7,8]

有的粒子均向最优解的方向飞去,导致粒子不可避免地趋向同一化(多样性损失),使得后期收敛速度明显变慢;同时算法收敛到一定精度时,无法继续优化,进而陷入局部最优解。这是群体智能算法包括PSO算法所固有的缺点。孙俊等人[9,10]已经提出了一些关于参数自适应的QPSO改进方法。文献[9]提出了两种改进方法:a)根据每个粒子所经历的最佳位置与当前全局最佳位置之间的距离来确定每个粒子的参数值;b)为参数设定一个阈值,若参数小于这个阈值,则将参数设为一个在[0,1]的随机值。文献[10]将粒子群分成多个群组、多个阶段进行搜索,每个群组的不同阶段β值分别选为小于1.7和大于1.8的值,保证在一个群组中,一阶段的粒子扩张时,另一个阶段的粒子就收缩,避免了粒子趋于早熟收敛。

1 粒子群算法和量子粒子群算法

1.1

粒子群算法

PSO是在1995年由美国社会心理学家J.Kennedy和电气工程师R.Eberhart共同提出的,其基本思想是受他们早期对鸟类群体行为研究结果的启发,并利用了生物学家F.Heppner的生物群体模型。目前,有关PSO算法的研究大多以带惯性权重的PSO算法为基础进行扩展和修改,为此将带惯性权重的PSO算法称之为标准PSO算法。该算法将每个粒子看做是在n维搜索空间中的一个没有重量和体积的微粒,并在搜索空间中以一定的速度飞行。其飞行速度由粒子的飞行经验和群

具有模型简单、收敛速度更快以及收敛性能更好的优点。虽然QPSO能够保证算法的全局收敛性,并且算法中用来控制算法收敛速度的惟一参数易于控制,但是在收敛的情况下,由于所

收稿日期:2008-05-07;修回日期:2008-07-16 基金项目:国防基础研究基金资助项目(A1420061266);高等学校科技创新工程重大项目培育资金项目

作者简介:王鹏(1984-),女,吉林蛟河人,CCF会员,硕士研究生,主要研究方向为网络流量、网络安全(wangpeng2284@yahoo.com.cn);刘渊(1967-),男,江苏无锡人,教授,主要研究方向为网络流量、网络安全.

・300・

计算机应用研究第26卷

体的飞行经验进行动态调整。标准PSO算法的进化方程为[10]

vij(t+1)=ωvij(t)+c1r1j(t)(pij(t)-xij(t))+

c2r2j(t)(pgj(t)-xij(t))(1)xij(t+1)=xij+vij(t+1)

(2)

其中:x、v表示种群中相应的粒子i的位置和速度;r1和r2为两两相互的[0,1]内变化的随机变量;pi是粒子i的最佳位置;pg是群体中所有粒子的最佳位置;ω是惯性权重因子;c1、c2为加速常数。

根据文献[11]关于粒子收敛行为的分析,要保证算法的收敛性,每个粒子必须收敛于各自的p点,这由粒子的追随性和粒子群的聚集性决定。第i个粒子p点的第j维坐标为

pj=(φ1jpij+φ2jpgj)/(φ1j+φ2j)

(3)

其中:φ1j=c1r1j;φ2j=c2r2j。

从动力学的角度看,粒子群算法中的粒子收敛过程是以p点为吸引子,随着速度的减小不断接近p点,最后收敛到p点。整个过程中,在p点处实际上存在某种形式的吸引势能场吸引着粒子,这正是整个粒子能保持聚集性的原因。但由于在标准PSO系统中,粒子的收敛以轨道的形式实现,并且又由于粒子的速度总是有限的,在搜索过程中粒子的搜索空间是一个有限的区域,不能覆盖整个可行空间。PSO算法不能保证以概率1收敛到全局最优解,这正是其最大的缺点。1.2 量子粒子群算法

2004年,Sun等人在研究了Clerc等人的关于粒子收敛行为的研究成果后,从量子力学的角度出发提出了一种新的PSO算法模型。这种模型是以DELTA势阱为基础,认为粒子具有量子的行为,并根据这种模型提出了量子粒子群算法(QP-SO)

[7]

。

在量子空间中粒子满足聚集态的性质完全不同,它可以在整个可行解空间中进行搜索,因而QPSO算法的全局搜索性能远远优于标准PSO算法。在量子空间中,粒子的速度和位置是不能同时确定的,因此文献[12]通过波函数ψ(x,t)(其物理意义为:波函数的平方是粒子在空间某一点出现的概率密度)来描述粒子的状态,并通过求解薛定谔方程得到粒子在空间某一点出现的概率密度函数,随后通过蒙特卡罗随机模拟的方式得到粒子的位置方程为

X(t)=P±(L/2)×ln(1/u)

(4)

其中:u为[0,1]内变化的随机数。文献[17]中L被定义为

L(t+1)=2β×|mbest-X(t)|

(5)

M

mbest=６P(6)

i=1i/M

其中:β为收缩扩张系数;M为粒子的数目;D为粒子的维数;Pi为第i个粒子的pbest。最后得到粒子的位置方程为

X(t+1)=P±β×|mbest-X(t)|×ln(1/u)

(7)

在QPSO算法中,粒子的状态只需用位置向量来描述,并且算法中只有一个控制参数β,对这个参数的选择和控制是非常重要的,它关系到整个算法的收敛速度。在传统的PSO算法中,有限的搜索范围将粒子在一个固定的区域;而在QPSO算法中,粒子能够以某一确定的概率出现在整个可行搜索空间中的任意一个位置,甚至是一个远离p点的位置。这样一个位置可能比当前群体中的最佳位置具有更好的适应值。

2 改进的QPSO算法

与标准的PSO一样,QPSO同样存在着早熟的趋势。对于每个粒子来说,失去了全局搜索能力意味着它只能在一个相当小的空间运动,当单个粒子所经历的最佳位置pbest和群体的最佳位置gbest非常接近时,就会发生这种情况。在标准的PSO中,从它的进化方程可以看出pbest和gbest之间的距离接近0时,粒子的速度也接近0。在QPSO算法中,pbest和gbest很接近时意味着粒子的参数L很小,于是,粒子的搜索范围也变得很小,这样,粒子群的进化就会停滞。如果此时粒子群的当前最佳位置gbest处于一个局部最优解,那么由于所有的粒子越来越失去活力,整个粒子群就会趋于早熟。

在QPSO算法中,只有一个收缩扩张系数β,对于这个参数的选择和控制是非常重要的,它关系到整个算法的收敛性能。文献[9]已经证明当β≤1.7时,粒子收敛,靠近粒子群的当前最佳位置gbest;当β≥1.8时,粒子发散,远离粒子群当前最佳位置gbest。

文献[9]是针对每个粒子所经历的最优位置与当前种群的全局最优位置之间的距离而为每个粒子设定一个参数值;文献[10]是分群组和分阶段地为一个群组的一个阶段的所有粒子赋一个参数值。本文在两个文献基础上提出一种新的参数自适应方法对QPSO进行改进。具体方法如下:

a)因为随时间t增长,粒子所经历的个体最优位置pbest就越接近群体的最佳位置gbest,mbest与每个粒子的位置的差距也越来越小,这样粒子的搜索范围非常小,导致粒子群进化停滞。为此,并不像传统的QPSO算法那样将参数β随时间从1线性减小到0.5,而是将参数β随时间作线性增长,将β从0.6增加到0.9,明显延缓了整个粒子群陷入早熟。

β=0.3×(maxiter+t)/maxiter+0.3

(8)

其中:maxiter是迭代的最大次数。

b)即便β增长到0.9,但在算法搜索后期,仍然有粒子所经历的个体最优位置pbest与群体的最佳位置gbest非常接近,导致参数L非常小。为此,本文针对每个粒子,采用文献[9]的第二种改进办法,对每个粒子的参数L进行改进。

ifL(i)<ε

L(i)=A*rand(0,1)end

本文取ε=0.0005,A=0.5。

3 基于改进的QPSO算法训练BP网络

3.1 算法描述

BP网络是一种多层前馈网络,含有输入层、隐层和输出层。这里采用三层网络结构,即单隐层结构、其隐含层和输出层神经元的激活函数均选用S型函数:

f(x)=1/(1+e-x)

(9)

其中:x是神经元的加权输入值。

因为采用梯度下降法训练BP网络常会使网络陷入局部极小,降低网络的性能,采用改进的QPSO算法来训练BP网络。将网络的权值与阈值编码成粒子群的位置向量,每个粒子代表网络的一组权值和阈值。将误差函数作为改进的QPSO算法的适应度函数,搜索到的适应度函数值最小的一组粒子就是网络的一组最优参数。

第1期王 鹏,等:基于改进的QPSO训练BP网络的网络流量预测

・ ・3 01

设P(t)、T(t)、D(t)分别是第t组训练样本的输入,实际输出以及目标输出,s1为输入样本维数,s2为隐层节点数,s3为输出维数;fitness为适应度函数。其中m为输入样本数。

P(t)=(pt1,pt2,pt3,…,pts)T(t)=(tot1,tot2,tot3,…,tos)1

QPSO训练BP网络在进行流量预测时,每次实验均取得很高的预测精度,且性能稳定;其他两种模型的精度普遍较低,性能并不稳定。

0.7实际流量数据练络预测数据训网表种模型预测的差比较1三MSE误3

D

(t)

=(dt1,dt2,dt3,…,ds3

)

ms3

fitness(r)=(1/m)t６=1k６=1

‖totk-dtk‖2

(10)

3.2 算法步骤

a)选定粒子数n,设置粒子向量X的长度L=(s1+s3)×(s2+1),初始化X为(-1,1)之间的随机数。设置目标适应度值fit,最大迭代次数maxiter。

b)将粒子向量解码成网络的权值和阈值,构成BP网络,输入训练样本训练网络。计算每一个网络在训练集上产生的均方误差作为适应度函数(式(10)),以此来评价每一个粒子,并不断更新pbest和gbest。

c)判断种群的最优适应度值是否满足目标适应度值或达到最大的迭代次数。若不满足,则按改进的QPSO算法继续生成新的粒子,并进入b);如果满足则终止搜索,保存当前具有最优适应值的一组粒子向量,作为网络的最优参数。

4 实验与结果分析

4.1 仿真实验

本文数据源于流量文库:http://newsfeed.ntcu.net/～news/2006,收集了自2006年12月7日～21日共15天,每天每小时网络的访问流量,得到15×24=360个数据。将这360个流量数据组成的时间序列作为BP网络的训练和预测样本,并作归一化处理,归一化式如下:

x(t)=(x(t)-min(x))/(max(x)-min(x))

(11)

BP网络采用5-9-1的结构,即网络的输入节点数为5,隐层神经元为9,输出节点数为1。采用滚动预测方式对样本空间进行重构,输入层节点的输入为连续5日第i(i=1～24)小时的实际网络流量。训练时,目标输出则为第6日第i小时的实际网络流量;预测时,网络的实际输出则为预测的第6日第i小时的网络流量。这样,将数据集划分为240个训练样本,前216个样本作为学习和训练样本;最后24个样本作为预测检验样本,最终预测出2006年12月21日全天的流量数据。

为了验证基于改进的QPSO训练BP网络这一模型在网络流量预测中的有效性,笔者共做了三个实验。实验1,采用基于PSO算法训练的BP网络作为模型;实验2,采用QPSO算法训练的BP网络作为模型;实验3,采用改进的QPSO算法训练的BP网络作为模型。每个实验分别运行10次,记录每次运行中实际流量数据与预测流量数据之间的误差MSE值,分析模型的稳定性以及精确性,最后以MSE平均值为根据比较三种模型的预测精度。在三个实验中,目标误差均为0.001,训练的最大迭代次数为200次。4.2 结果分析

图1为三种模型进行网络流量预测的比较图。从图中可见,基于改进的QPSO算法训练BP网络这一模型的预测性能明显高于其他两种模型,预测曲线与实际流量曲线的趋势几乎一致,在某些时间段,预测曲线与实际曲线几乎重合。表1为三种模型预测的MSE误差比较。从表1可以看出基于改进的

0.6PSOQPSO改进的训QPSO练BPBP训网练络BP预测网数络据0.5预测数据次数0.006实验190.005实验250.002实验3180.420.00630.00450.00300.330.00670.00510.00310.240.00650.00430.00290.150.00570.00550.0033060.00650.00620.003351015202570.00750.00570.0027图80.00690.00400.0031三预种0测模的型比进较行图网络流量90.00630.00530.0031均10值0.00600.00510.00330.00650.00510.00305 结束语

本文提出一种新的基于参数自适应的方法改进QPSO算法,明显改善了QPSO算法容易出现早熟的缺陷。使用改进的QPSO算法训练BP神经网络作为模型用于网络流量预测,仿真实验结果表明,该模型不仅取得很好的预测精度,而且稳定性很好。可见,单纯的改进QPSO算法的参数只能在一定程度上延缓QPSO算法进入早熟,为此,笔者下一步的工作是:将QPSO算法与其他智能算法混合使用以优化神经网络作为模型进行网络流量预测,以加快网络收敛速度,提高全局搜索性能,以提高预测精度。参考文献:

[1]

ELDMANNA,GILBERTAC,WILLINGERW.Datanetworksascascades:investigatingthemultifractalnatureofInternetWANtraffic[C]//ProcofSIGCOMMConferenceonApplications,Technologies,andProtocolsforComputerCommunication.NewYork:ACMPress,1998:42-45.[2]

HOTNIKK,STINCHCOMBEM,WHITEH.Multilayerfeedforwardnetworksareuniversalapproximators[J].NeuralNetwroks,19,1(2):359-366.

[3]

HUSSEIND.Anobject-orientedneuralnetworkapproachtoshort-termtrafficforecasting[J].EuropeanJofOperationalResearch,

2001,131(2):253-261.

[4]

ATIYAAF,ALYMA,PARLOSAG.Sparsebasisselection:newre-sultsandapplicationtoadaptivepredictionofvideosourcetraffic[J].IEEETransonNeuralNetworks,2005,16(5):1136-1146.

[5]

GUOWen,QIAOYi-zheng,HOUHai-yan.BPneuralnetworkopti-mizedwithPSOalgorithmanditsapplicationinforecasting[C]//ProcofIEEEInternationalConferenceonInformationAcquisition.WashingtonDC:IEEEComputerSociety,2006:617-621.

[6]

SUNWei,ZOUYing.ShorttermloadforecastingbasedonBPneuralnetworktrainedbyPSO[C]//Procofthe6thInternationalConfe-renceonMachineLearningandCybernetics.2007:2863-2866.

[7]

SUNJun,XUWen-bo,FENGBin.Aglobalsearchstrategyofquan-tum-behavedparticleswarmoptimization[C]//ProcofIEEEcon-fereuceonCyberneticsandIntelligentSystems.2004:111-116.

[8]SUNJun,FENGBin,XUWen-bo.Particleswarmoptimizationwithparticleshavingquantumbehavior[C]//PrecofCongressOilEvolu-tionaryComputation.PiscatawayNJ:IEEEPress,2004:325-331.

[9]

SUNJun,XUWen-bo,FENGBin.Adaptiveparametercontrolforquantum-behavedparticleswarmoptimizationonindividuallevel[J].IEEEInternationalConferenceonSystems,ManandCyberne-tics,2005,4(10):3049-30.

[10]张春燕,须文波,孙俊,等.一种具有多群体与多阶段的QPSO算法[J].计算机应用研究,2007,24(3):100-102.

[11]CLERCM.Theswarmandqueen:towardsadeterministicandadap-tiveparticleswarmoptimization[C]//ProcofCongressofEvolutio-naryComputation.Piscataway,NJ:IEEEPress,1999:1951-1957.