基于改進的ＱＰＳＯ訓練ＢＰ網(wǎng)絡(luò)的網(wǎng)絡(luò)流量預測

（江南大學 a.信息工程學院；b.數(shù)字媒體創(chuàng)意中心， 江蘇 無錫 214122）

摘 要：為了提高網(wǎng)絡(luò)流量預測的精度，采用一種改進的QPSO算法訓練BP神經(jīng)網(wǎng)絡(luò)對網(wǎng)絡(luò)流量數(shù)據(jù)的時間序列進行建模預測。針對標準的QPSO算法不可避免地出現(xiàn)早熟的不足，提出一種新的基于參數(shù)自適應的QPSO算法，較好地避免了粒子群的早熟，提高了算法的全局收斂性能。仿真實驗結(jié)果表明，與PSO訓練的BP網(wǎng)絡(luò)、QPSO訓練的BP網(wǎng)絡(luò)作為預測模型相比，該模型具有更高的預測精度及很好的穩(wěn)定性。

關(guān)鍵詞：量子粒子群優(yōu)化算法；粒子群優(yōu)化算法；早熟；神經(jīng)網(wǎng)絡(luò)；網(wǎng)絡(luò)流量預測

中圖分類號：TP39301 文獻標志碼：A

文章編號：10013695(2009)01029903

Network traffic prediction based on BP neural network trained by improved QPSO

WANG Penga，LIU Yuana，b

(a.School of Information Engineering，b.Digital Media Research Center， Jiangnan University， Wuxi Jiangsu 214122， China)

Abstract:In order to improve the precision of the network traffic prediction，proposed the BP neural network(BPNN)trained by an optimized QPSO algorithm to model and predict the time series of network traffic data. Proposed a new adaptive parameter control method for QPSO to avoid the particle prematurely and improved the ability of global convergence. The experimental results prove that， compared with the model of BPNN trained by PSO， and BPNN trained by QPSO， this model is more efficient in network traffic prediction with higher precision and better stability.

Key words:quantumbehaved particle swarm optimization (QPSO); particle swarm optimization (PSO); particle prematurity; neural network; network traffic prediction

網(wǎng)絡(luò)流量預測在網(wǎng)絡(luò)設(shè)計、管理、控制以及最優(yōu)化等方面均起到重要的作用，因而一直備受關(guān)注。流量預測問題可定義為：給定當前時刻的一組觀測流量數(shù)據(jù)Xn-i(i=0，1，2，…，n)則未來某一時刻的流量Xn+k可由Xn-i給出，這里k是預測步長。大量研究發(fā)現(xiàn)，網(wǎng)絡(luò)流量的某些特性已遠遠超出了傳統(tǒng)隊列論中泊松和馬爾可夫流量模型的框架[1]，用線性方法來預測非線性的網(wǎng)絡(luò)流量在理論上就存在不足，其預測精度不高。科研人員早已證明具有非線性結(jié)構(gòu)的神經(jīng)網(wǎng)絡(luò)系統(tǒng)可以逼近任意的非線性函數(shù)[2]。由于神經(jīng)網(wǎng)絡(luò)具有自學習能力，它可以只通過輸入輸出數(shù)據(jù)構(gòu)建出非線性模型，因而被廣泛用于計算機網(wǎng)絡(luò)的流量控制和流量預測[3，4]。目前BP網(wǎng)絡(luò)是應用最廣泛和成功的神經(jīng)網(wǎng)絡(luò)之一，它結(jié)構(gòu)簡單、可塑性強，然而BP網(wǎng)絡(luò)卻存在著易陷入局部極小和收斂速度慢等缺陷。進化算法具有較強的全局收斂能力和較強的魯棒性，且無須借助問題的特征信息，如導數(shù)等梯度信息。因此，將其應用于神經(jīng)網(wǎng)絡(luò)學習算法，不僅能發(fā)揮神經(jīng)網(wǎng)絡(luò)的泛化映射能力，而且能夠提高神經(jīng)網(wǎng)絡(luò)的收斂速度及學習能力。已經(jīng)有許多學者將粒子群算法(PSO)應用到BP網(wǎng)絡(luò)的訓練中并用于預測，均取得了較好的效果[5，6]。量子粒子群算法(QPSO)是在對 PSO收斂性基礎(chǔ)上提出的一種全新的群體智能優(yōu)化算法。QPSO算法[7，8]具有模型簡單、收斂速度更快以及收斂性能更好的優(yōu)點。雖然QPSO能夠保證算法的全局收斂性，并且算法中用來控制算法收斂速度的惟一參數(shù)易于控制，但是在收斂的情況下，由于所有的粒子均向最優(yōu)解的方向飛去，導致粒子不可避免地趨向同一化（多樣性損失），使得后期收斂速度明顯變慢；同時算法收斂到一定精度時，無法繼續(xù)優(yōu)化，進而陷入局部最優(yōu)解。這是群體智能算法包括PSO算法所固有的缺點。孫俊等人[9，10]已經(jīng)提出了一些關(guān)于參數(shù)自適應的QPSO改進方法。文獻[9]提出了兩種改進方法：a）根據(jù)每個粒子所經(jīng)歷的最佳位置與當前全局最佳位置之間的距離來確定每個粒子的參數(shù)值；b)為參數(shù)設(shè)定一個閾值，若參數(shù)小于這個閾值，則將參數(shù)設(shè)為一個在[0，1]的隨機值。文獻[10]將粒子群分成多個群組、多個階段進行搜索，每個群組的不同階段β值分別選為小于1.7和大于1.8的值，保證在一個群組中，一階段的粒子擴張時，另一個階段的粒子就收縮，避免了粒子趨于早熟收斂。

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

11 粒子群算法

PSO是在1995年由美國社會心理學家J. Kennedy和電氣工程師R. Eberhart 共同提出的，其基本思想是受他們早期對鳥類群體行為研究結(jié)果的啟發(fā)，并利用了生物學家F. Heppner的生物群體模型。目前，有關(guān)PSO算法的研究大多以帶慣性權(quán)重的PSO算法為基礎(chǔ)進行擴展和修改，為此將帶慣性權(quán)重的PSO算法稱之為標準PSO算法。該算法將每個粒子看做是在n維搜索空間中的一個沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。其飛行速度由粒子的飛行經(jīng)驗和群體的飛行經(jīng)驗進行動態(tài)調(diào)整。標準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]內(nèi)變化的隨機變量；pi是粒子i的最佳位置；pg是群體中所有粒子的最佳位置；ω是慣性權(quán)重因子；c1、c2為加速常數(shù)。

根據(jù)文獻[11]關(guān)于粒子收斂行為的分析，要保證算法的收斂性，每個粒子必須收斂于各自的p點，這由粒子的追隨性和粒子群的聚集性決定。第i個粒子p點的第j維坐標為

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

φ1j+φ2j)(3)

其中：φ1j=c1r1j；φ2j=c2r2j。

從動力學的角度看，粒子群算法中的粒子收斂過程是以p點為吸引子，隨著速度的減小不斷接近p點，最后收斂到p點。整個過程中，在p點處實際上存在某種形式的吸引勢能場吸引著粒子，這正是整個粒子能保持聚集性的原因。但由于在標準PSO系統(tǒng)中，粒子的收斂以軌道的形式實現(xiàn)，并且又由于粒子的速度總是有限的，在搜索過程中粒子的搜索空間是一個有限的區(qū)域，不能覆蓋整個可行空間。PSO算法不能保證以概率1收斂到全局最優(yōu)解，這正是其最大的缺點。

12 量子粒子群算法

2004年，Sun等人在研究了Clerc等人的關(guān)于粒子收斂行為的研究成果后，從量子力學的角度出發(fā)提出了一種新的PSO算法模型。這種模型是以DELTA勢阱為基礎(chǔ)，認為粒子具有量子的行為，并根據(jù)這種模型提出了量子粒子群算法（QPSO）[7]。

在量子空間中粒子滿足聚集態(tài)的性質(zhì)完全不同，它可以在整個可行解空間中進行搜索，因而QPSO算法的全局搜索性能遠遠優(yōu)于標準PSO算法。在量子空間中，粒子的速度和位置是不能同時確定的，因此文獻[12]通過波函數(shù)ψ(x，t)（其物理意義為：波函數(shù)的平方是粒子在空間某一點出現(xiàn)的概率密度）來描述粒子的狀態(tài)，并通過求解薛定諤方程得到粒子在空間某一點出現(xiàn)的概率密度函數(shù)，隨后通過蒙特卡羅隨機模擬的方式得到粒子的位置方程為

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

其中:u為[0，1]內(nèi)變化的隨機數(shù)。文獻[17]中L被定義為

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

mbest=Mi=1Pi/M(6)

其中:β為收縮擴張系數(shù);M為粒子的數(shù)目；D為粒子的維數(shù)；Pi為第i個粒子的pbest。最后得到粒子的位置方程為

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

在QPSO算法中，粒子的狀態(tài)只需用位置向量來描述，并且算法中只有一個控制參數(shù)β，對這個參數(shù)的選擇和控制是非常重要的，它關(guān)系到整個算法的收斂速度。在傳統(tǒng)的PSO算法中，有限的搜索范圍將粒子限制在一個固定的區(qū)域；而在QPSO算法中，粒子能夠以某一確定的概率出現(xiàn)在整個可行搜索空間中的任意一個位置，甚至是一個遠離p點的位置。這樣一個位置可能比當前群體中的最佳位置具有更好的適應值。

2 改進的QPSO算法

與標準的PSO一樣，QPSO同樣存在著早熟的趨勢。對于每個粒子來說，失去了全局搜索能力意味著它只能在一個相當小的空間運動，當單個粒子所經(jīng)歷的最佳位置pbest和群體的最佳位置gbest非常接近時，就會發(fā)生這種情況。在標準的PSO中，從它的進化方程可以看出pbest和gbest之間的距離接近0時，粒子的速度也接近0。在QPSO算法中，pbest和gbest很接近時意味著粒子的參數(shù)L很小，于是，粒子的搜索范圍也變得很小，這樣，粒子群的進化就會停滯。如果此時粒子群的當前最佳位置gbest處于一個局部最優(yōu)解，那么由于所有的粒子越來越失去活力，整個粒子群就會趨于早熟。

在QPSO算法中，只有一個收縮擴張系數(shù)β，對于這個參數(shù)的選擇和控制是非常重要的，它關(guān)系到整個算法的收斂性能。文獻[9]已經(jīng)證明當β≤1.7時，粒子收斂，靠近粒子群的當前最佳位置gbest；當β≥1.8時，粒子發(fā)散，遠離粒子群當前最佳位置gbest。

文獻[9]是針對每個粒子所經(jīng)歷的最優(yōu)位置與當前種群的全局最優(yōu)位置之間的距離而為每個粒子設(shè)定一個參數(shù)值；文獻[10]是分群組和分階段地為一個群組的一個階段的所有粒子賦一個參數(shù)值。本文在兩個文獻基礎(chǔ)上提出一種新的參數(shù)自適應方法對QPSO進行改進。具體方法如下：

a)因為隨時間t增長，粒子所經(jīng)歷的個體最優(yōu)位置pbest就越接近群體的最佳位置gbest，mbest 與每個粒子的位置的差距也越來越小，這樣粒子的搜索范圍非常小，導致粒子群進化停滯。為此，并不像傳統(tǒng)的QPSO算法那樣將參數(shù)β隨時間從1線性減小到0.5，而是將參數(shù)β隨時間作線性增長，將β從06增加到0.9，明顯延緩了整個粒子群陷入早熟。

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

其中:maxiter是迭代的最大次數(shù)。

b)即便β增長到0.9，但在算法搜索后期，仍然有粒子所經(jīng)歷的個體最優(yōu)位置pbest與群體的最佳位置gbest非常接近，導致參數(shù)L非常小。為此，本文針對每個粒子，采用文獻[9]的第二種改進辦法，對每個粒子的參數(shù)L進行改進。

ifL(i)<ε

L(i)=A*rand(0，1) 

end 

本文取ε=0.000 5，A=0.5。

3 基于改進的QPSO算法訓練BP網(wǎng)絡(luò)

31 算法描述

BP網(wǎng)絡(luò)是一種多層前饋網(wǎng)絡(luò)，含有輸入層、隱層和輸出層。這里采用三層網(wǎng)絡(luò)結(jié)構(gòu)，即單隱層結(jié)構(gòu)、其隱含層和輸出層神經(jīng)元的激活函數(shù)均選用S型函數(shù)：

f(x)=1/（1+e-x）(9)

其中：x是神經(jīng)元的加權(quán)輸入值。

因為采用梯度下降法訓練BP網(wǎng)絡(luò)常會使網(wǎng)絡(luò)陷入局部極小，降低網(wǎng)絡(luò)的性能，采用改進的QPSO算法來訓練BP網(wǎng)絡(luò)。將網(wǎng)絡(luò)的權(quán)值與閾值編碼成粒子群的位置向量，每個粒子代表網(wǎng)絡(luò)的一組權(quán)值和閾值。將誤差函數(shù)作為改進的QPSO算法的適應度函數(shù)，搜索到的適應度函數(shù)值最小的一組粒子就是網(wǎng)絡(luò)的一組最優(yōu)參數(shù)。

設(shè)P(t)、T(t)、D(t)分別是第t組訓練樣本的輸入，實際輸出以及目標輸出，s1為輸入樣本維數(shù)，s2為隱層節(jié)點數(shù)，s3為輸出維數(shù)；fitness為適應度函數(shù)。其中m為輸入樣本數(shù)。

P(t)=(pt1，pt2，pt3，…，pts1)

T(t)=(tot1，tot2，tot3，…，tos3)

D(t)=(dt1，dt2，dt3，…，ds3)

fitness(r)=(1/m)mt=1s3k=1‖totk-dtk‖2(10)

32 算法步驟

a)選定粒子數(shù)n，設(shè)置粒子向量X的長度L=(s1+s3)×(s2+1)，初始化X為(-1，1)之間的隨機數(shù)。設(shè)置目標適應度值fit，最大迭代次數(shù)maxiter。

b)將粒子向量解碼成網(wǎng)絡(luò)的權(quán)值和閾值，構(gòu)成BP網(wǎng)絡(luò)，輸入訓練樣本訓練網(wǎng)絡(luò)。計算每一個網(wǎng)絡(luò)在訓練集上產(chǎn)生的均方誤差作為適應度函數(shù)(式（10）)，以此來評價每一個粒子，并不斷更新pbest和gbest。

c)判斷種群的最優(yōu)適應度值是否滿足目標適應度值或達到最大的迭代次數(shù)。若不滿足，則按改進的QPSO算法繼續(xù)生成新的粒子，并進入b)；如果滿足則終止搜索，保存當前具有最優(yōu)適應值的一組粒子向量，作為網(wǎng)絡(luò)的最優(yōu)參數(shù)。

4 實驗與結(jié)果分析

41 仿真實驗

本文數(shù)據(jù)源于流量文庫：http://newsfeed.ntcu.net/~news/2006， 收集了自2006年12月7日～21日共15天，每天每小時網(wǎng)絡(luò)的訪問流量，得到15×24＝360個數(shù)據(jù)。將這360個流量數(shù)據(jù)組成的時間序列作為BP網(wǎng)絡(luò)的訓練和預測樣本，并作歸一化處理，歸一化式如下：

x(t)=（x(t)-min(x)）/（max(x)-min(x)）(11)

BP網(wǎng)絡(luò)采用591的結(jié)構(gòu)，即網(wǎng)絡(luò)的輸入節(jié)點數(shù)為5，隱層神經(jīng)元為9，輸出節(jié)點數(shù)為1。采用滾動預測方式對樣本空間進行重構(gòu)，輸入層節(jié)點的輸入為連續(xù)5日第i(i=1~24)小時的實際網(wǎng)絡(luò)流量。訓練時，目標輸出則為第6日第i小時的實際網(wǎng)絡(luò)流量；預測時，網(wǎng)絡(luò)的實際輸出則為預測的第6日第i小時的網(wǎng)絡(luò)流量。這樣，將數(shù)據(jù)集劃分為240個訓練樣本，前216個樣本作為學習和訓練樣本；最后24個樣本作為預測檢驗樣本，最終預測出2006年12月21日全天的流量數(shù)據(jù)。

為了驗證基于改進的QPSO訓練BP網(wǎng)絡(luò)這一模型在網(wǎng)絡(luò)流量預測中的有效性，筆者共做了三個實驗。實驗1，采用基于PSO算法訓練的BP網(wǎng)絡(luò)作為模型；實驗2，采用QPSO算法訓練的BP網(wǎng)絡(luò)作為模型；實驗3，采用改進的QPSO算法訓練的BP網(wǎng)絡(luò)作為模型。每個實驗分別運行10次，記錄每次運行中實際流量數(shù)據(jù)與預測流量數(shù)據(jù)之間的誤差MSE值，分析模型的穩(wěn)定性以及精確性，最后以MSE平均值為根據(jù)比較三種模型的預測精度。在三個實驗中，目標誤差均為0.001，訓練的最大迭代次數(shù)為200次。

42 結(jié)果分析

圖1為三種模型進行網(wǎng)絡(luò)流量預測的比較圖。從圖中可見，基于改進的QPSO算法訓練BP網(wǎng)絡(luò)這一模型的預測性能明顯高于其他兩種模型，預測曲線與實際流量曲線的趨勢幾乎一致，在某些時間段，預測曲線與實際曲線幾乎重合。表1為三種模型預測的MSE誤差比較。從表1可以看出基于改進的QPSO訓練BP網(wǎng)絡(luò)在進行流量預測時，每次實驗均取得很高的預測精度，且性能穩(wěn)定；其他兩種模型的精度普遍較低，性能并不穩(wěn)定。

5 結(jié)束語

本文提出一種新的基于參數(shù)自適應的方法改進QPSO算法，明顯改善了QPSO算法容易出現(xiàn)早熟的缺陷。使用改進的QPSO算法訓練BP神經(jīng)網(wǎng)絡(luò)作為模型用于網(wǎng)絡(luò)流量預測，仿真實驗結(jié)果表明，該模型不僅取得很好的預測精度，而且穩(wěn)定性很好。可見，單純的改進QPSO算法的參數(shù)只能在一定程度上延緩QPSO算法進入早熟，為此，筆者下一步的工作是：將QPSO算法與其他智能算法混合使用以優(yōu)化神經(jīng)網(wǎng)絡(luò)作為模型進行網(wǎng)絡(luò)流量預測，以加快網(wǎng)絡(luò)收斂速度，提高全局搜索性能，以提高預測精度。

參考文獻：

［1］

FELDMANN A，GILBERT A C，WILLINGER W.Data networks as cascades:investigating the multifractal nature of Internet WAN traffic[C]//Proc of SIGCOMM Conference on Applications，Technologies，and Protocols for Computer Communication.New York:ACM Press，1998:4245.

[2]HOTNIK K，STINCHCOMBE M，WHITE H.Multilayer feedforward networks are universal approximators[J].Neural Netwroks，1989，1(2):359366.

[3]HUSSEIN D.An objectoriented neural network approach to shortterm traffic forecasting[J].European J of Operational Research，2001，131(2):253261.

[4]ATIYA A F，ALY M A， PARLOS A G.Sparse basis selection:new results and application to adaptive prediction of video source traffic[J].IEEE Trans on Neural Networks，2005，16(5):11361146.

[5]GUO Wen，QIAO Yizheng，HOU Haiyan.BP neural network optimized with PSO algorithm and its application in forecasting[C]//Proc of IEEE International Conference on Information Acquisition.Washington DC:IEEE Computer Society，2006:617621.

[6]SUN Wei，ZOU Ying.Short term load forecasting based on BP neural network trained by PSO[C]//Proc of the 6th International Conference on Machine Learning and Cybernetics.2007:28632866.

[7]SUN Jun，XU Wenbo，F(xiàn)ENG Bin.A global search strategy of quantumbehaved particle swarm optimization[C]//Proc of IEEE confereuce on Cybernetics and Intelligent Systems.2004：111116.

[8]SUN Jun，F(xiàn)ENG Bin，XU Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Prec of Congress Oil Evolutionary Computation.Piscataway NJ:IEEE Press，2004:325331.

[9]SUN Jun，XU Wenbo，F(xiàn)ENG Bin.Adaptive parameter control for quantumbehaved particle swarm optimization on individual level[J].IEEE International Conference on Systems，Man and Cybernetics，2005，4（10）:30493054.

[10]張春燕，須文波，孫俊，等.一種具有多群體與多階段的QPSO算法[J].計算機應用研究，2007，24(3):100102.

[11]CLERC M.The swarm and queen：towards a deterministic and adaptive particle swarm optimization[C]//Proc of Congress of Evolutionary Computation.Piscataway， NJ:IEEE Press，1999:19511957.