王曉敏，劉宏偉，李石妍

（河北工程大學(xué) 機(jī)電工程學(xué)院，河北 邯鄲 056038）

隨著計(jì)算機(jī)網(wǎng)絡(luò)的快速發(fā)展，網(wǎng)絡(luò)應(yīng)用已經(jīng)深入到生活的各個(gè)角落。必須加強(qiáng)多網(wǎng)絡(luò)的研究，以緩解網(wǎng)絡(luò)發(fā)展與網(wǎng)絡(luò)應(yīng)用不相適應(yīng)的矛盾。除了提高硬件技術(shù)來解決矛盾，加強(qiáng)網(wǎng)絡(luò)流量研究是急需解決的工程。新一代網(wǎng)絡(luò)管理的核心包括網(wǎng)絡(luò)業(yè)務(wù)管理及其支持的QoS、優(yōu)化網(wǎng)絡(luò)配置和流量工程、有效提高網(wǎng)絡(luò)運(yùn)行速度和利用率，其中網(wǎng)絡(luò)流量預(yù)測是業(yè)務(wù)管理的關(guān)鍵問題。20世紀(jì)70年代，網(wǎng)絡(luò)業(yè)務(wù)性能單一，人們主要基于泊松過程，指數(shù)分布等建立模型來進(jìn)行網(wǎng)絡(luò)流量的預(yù)測。90年代初期，leland等證實(shí)了局域網(wǎng)流量中存在自相似性[1]，paxson等證明了WWW廣域網(wǎng)流量的自相似性和突發(fā)性[2]。學(xué)者開始使用自相似性模型進(jìn)行網(wǎng)絡(luò)流量的預(yù)測研究。網(wǎng)絡(luò)流量預(yù)測的精確性、實(shí)時(shí)性直接關(guān)系到業(yè)務(wù)管理的效率和性能。目前BP神經(jīng)網(wǎng)絡(luò)是應(yīng)用最為廣泛的神經(jīng)網(wǎng)絡(luò)之一。BP神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)簡單、可塑性強(qiáng)，然而它卻存在易陷入局部收斂和收斂速度慢等特點(diǎn)[3]。差分進(jìn)化（Differential Evolution,DE）算法[4]有很強(qiáng)的全局最優(yōu)能力，不需借助問題的特征信息，并且收斂速度很快，本文利用改進(jìn)的DE算法彌補(bǔ)BP的不足，進(jìn)行網(wǎng)絡(luò)流量預(yù)測研究。

1 BP神經(jīng)網(wǎng)絡(luò)模型

1.1 BP神經(jīng)網(wǎng)絡(luò)

BP（Back Propagtion）神經(jīng)網(wǎng)絡(luò)由 Rumelhart,McClelland于1985年最早提出，實(shí)現(xiàn)了Minsky的多層網(wǎng)絡(luò)設(shè)想。BP神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)算法是一種多層網(wǎng)絡(luò)的“逆推”學(xué)習(xí)算法?；舅枷胧?，學(xué)習(xí)過程由信號(hào)的正向傳播和學(xué)習(xí)逆向反饋組成。BP神經(jīng)網(wǎng)絡(luò)的非線性擬合能力強(qiáng)，精度高，并且算法簡單易懂，應(yīng)用廣泛。但BP神經(jīng)網(wǎng)絡(luò)存在局限。國內(nèi)外學(xué)者針對BP神經(jīng)網(wǎng)絡(luò)的不足進(jìn)行改進(jìn)。

1.2 BP神經(jīng)網(wǎng)絡(luò)的標(biāo)準(zhǔn)學(xué)習(xí)算法

BP神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)算法如下：步驟1：網(wǎng)絡(luò)初始化。Xk（k=1,2,...,N）為輸入向量。N為訓(xùn)練樣本的個(gè)數(shù)。WMI（n）為第 n次迭代時(shí)輸入層與隱含層I之間的權(quán)值向量。WIJ（n）為第n次迭代時(shí)隱含層I與輸出層之間的權(quán)值。YK（n）為第n次迭代時(shí)網(wǎng)絡(luò)的實(shí)際輸出。 dK為期望輸出；步驟 2：給 WMI（n），WIJ（n）各一個(gè)較小的隨機(jī)非零值，n=0；步驟3：隨機(jī)輸入樣本Xk；步驟4：對輸入樣本Xk前向計(jì)算BP神經(jīng)網(wǎng)絡(luò)每層神經(jīng)元的輸入信號(hào)u和輸出信號(hào)v；步驟5：由期望輸出dk和上一步求得的實(shí)際輸出YK（n）計(jì)算誤差E（n）判斷其是否滿足要求，若滿足轉(zhuǎn)至步驟8，不滿足轉(zhuǎn)至步驟6；步驟6：判斷n+1是否大于最大迭代次數(shù)，若大于轉(zhuǎn)至步驟8，若不大于，對輸入樣本Xk，反向計(jì)算每層神經(jīng)元的局部梯度δ；步驟7：計(jì)算權(quán)值修正量Δw，并修正權(quán)值；n=n+1,轉(zhuǎn)至步驟4；步驟8：判斷是否學(xué)習(xí)完所有的訓(xùn)練樣本，是則結(jié)束，否則轉(zhuǎn)步驟3。

2 差分進(jìn)化算法

差分進(jìn)化是一種新穎的進(jìn)化計(jì)算方法，最初的設(shè)想是解決切比雪夫多項(xiàng)式問題，后來發(fā)現(xiàn)差分進(jìn)化解決復(fù)雜優(yōu)化問題的優(yōu)越性，并已應(yīng)用與多個(gè)學(xué)科和工程領(lǐng)域[5－6]。它從當(dāng)前種群中提取差分信息，然后指導(dǎo)進(jìn)一步搜索，不需要借助問題的特征信息，具有較強(qiáng)的全局收斂能力和魯棒性。

2.1 差分進(jìn)化算法的基本步驟

步驟4：交叉。為了增加干擾參數(shù)向量的多言性，引入交叉操作。向量變?yōu)椋╥=1,2,...,NP;j=1,2,...,D）

步驟 6：G=G＋1，重復(fù)步驟 2到步驟 5，直到滿足算法的終止條件或G＞Gmax。以上是最基本的DE操作程序。

2.2 差分進(jìn)化算法的其他形式

實(shí)際應(yīng)用中還發(fā)展了差分進(jìn)化的幾個(gè)變形形式，并用符號(hào)DE/x/y/z加以區(qū)分，其中：x限定當(dāng)前被變異的向量是 “隨機(jī)的”或“最佳的”；y是所利用的差向量的個(gè)數(shù)；z指示交叉程序的操作方法。

式中，ri為隨機(jī)整數(shù)，表示個(gè)體在種群中的序號(hào)，r1、r2、r3、r4和r5互不相同。

2.3 控制參數(shù)的選擇

控制參數(shù)對一個(gè)全局優(yōu)化算法的影響很大，差分進(jìn)化的控制變量選擇也有一些經(jīng)驗(yàn)規(guī)則[7]。

1）種群數(shù)量 種群數(shù)量NP的合理選擇在5D～10D之間，必須滿足NP≥4以確保DE具有足夠的不同的變異向量。

2）變異算子 變異算子F∈[0，2]是一個(gè)實(shí)常數(shù)因數(shù)，它決定偏差向量的放大比例。研究表明，小于0.4和大于1的，值僅偶爾有效，F(xiàn)=0.5通常是一個(gè)較好的初始選擇。若種群過早收斂，那么F或NP應(yīng)該增加。

3）交叉算子 交叉算子CR是一個(gè)在[0，1]的實(shí)數(shù)，它控制著一個(gè)試驗(yàn)向量參數(shù)來自于隨機(jī)選擇的變異向量而不是原來向量的概率。CR的一個(gè)較好的選擇是0.1，但較大的CR通常加速收斂，為了看是否可能獲得一個(gè)快速解，可以首先嘗試CR=0.9或 CR=1.0。

4）最大進(jìn)化代數(shù) 它表示遺傳算法運(yùn)行結(jié)束條件的一個(gè)參數(shù)，表示差分進(jìn)化算法運(yùn)行到指定的進(jìn)化代數(shù)之后就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問題的最優(yōu)解輸出。一般取值范圍為100～200。

5）終止條件 除最大進(jìn)化代數(shù)可作為差分進(jìn)化的終止條件，還需要其他判定準(zhǔn)則。一般當(dāng)目標(biāo)函數(shù)值小于閥值時(shí)程序終止，閥值常選為10－6。上述參數(shù)中F，CR與NP一樣，在搜索過程中是常數(shù)，一般F和CR影響搜索過程的收斂速度和魯棒性，它們的優(yōu)化值不僅依賴于目標(biāo)函數(shù)的特性，還與NP有關(guān)。通常可通過在對不同值做一些試驗(yàn)之后利用試驗(yàn)和結(jié)果誤差找到F，CR和A的合適值。

3 網(wǎng)絡(luò)流量預(yù)測方法

差分進(jìn)化算法在搜索過程中F取一個(gè)0到2之間的固定實(shí)數(shù)，F(xiàn)不好確定成了差分進(jìn)化的一個(gè)缺點(diǎn)。若取值太大，最優(yōu)解易遭到破壞，求出最優(yōu)解的概率下降。若取值太小，種群的多樣性低，出現(xiàn)“早熟”收斂現(xiàn)象。本文采用變化的變異因子F。

其中g(shù)max為最大迭代次數(shù)，g為當(dāng)前進(jìn)化代數(shù)，a的取值在 0.2～0.6之間。本文設(shè)計(jì)的差分進(jìn)化的BP網(wǎng)絡(luò)學(xué)習(xí)算法，其偽代碼如下：步驟1：初始化BP網(wǎng)絡(luò)隱層神經(jīng)元個(gè)數(shù)s、最大迭代次數(shù)Nmax、群體數(shù)目N、交叉概率CR、變異因子F。

步驟3：把最優(yōu)參向量XG作為BP網(wǎng)絡(luò)最佳連接權(quán)值。

步驟4：BP神經(jīng)網(wǎng)絡(luò)前項(xiàng)傳播，進(jìn)行預(yù)測，計(jì)算誤差。

4 實(shí)驗(yàn)與結(jié)果分析

本 文 把 http://newsfeed －0.progon.net/innreport/收 集 的2006年3月1日到3月16日共16天的訪問流量，作為本文的數(shù)據(jù)源與流量文庫。其中，3月1日到3月15日的數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)；3月16日的數(shù)據(jù)作為預(yù)測數(shù)據(jù)。數(shù)據(jù)做歸一化處理，歸一化公式如下：

BP神經(jīng)網(wǎng)絡(luò)的輸入層為5個(gè)節(jié)點(diǎn)，隱含層為10個(gè)節(jié)點(diǎn)，輸出層為1個(gè)節(jié)點(diǎn)。訓(xùn)練是把5日每小時(shí)的流量作為輸入，第6日的流量作為期望輸出。當(dāng)訓(xùn)練完成。最終預(yù)測3月16日全天流量數(shù)據(jù)。

為了驗(yàn)證基于改進(jìn)的差分進(jìn)化的訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)預(yù)測的有效性。筆者做了3個(gè)實(shí)驗(yàn)。實(shí)驗(yàn)1采用BP神經(jīng)網(wǎng)絡(luò)作為模型；實(shí)驗(yàn)2采用差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)作為模型；實(shí)驗(yàn)3采用改進(jìn)的差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)作為模型。在3次試驗(yàn)中，目標(biāo)誤差均為0.001，訓(xùn)練的最大迭代次數(shù)為20000次，實(shí)驗(yàn)結(jié)果如圖 1，2，3所示。

從圖1～3可以看出：圖1采用BP神經(jīng)網(wǎng)絡(luò)作為模型的誤差收斂，其最終誤差比較大；圖2采用差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)模型誤差，其最終誤差比較??；圖3采用本文改進(jìn)的差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)模型誤差，其最終誤差最小。另外，改進(jìn)的差分進(jìn)化精度提高很多，但是收斂速度比差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)模型的稍微慢一些。

5 結(jié)束語

本文使用一種改進(jìn)差分進(jìn)化算法來訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)，彌補(bǔ)了BP神經(jīng)網(wǎng)絡(luò)易陷入局部收斂和收斂速度慢的不足。實(shí)驗(yàn)結(jié)果表明，本文方法能得到較高的網(wǎng)絡(luò)流量預(yù)測精度，具有較好的應(yīng)用價(jià)值。

圖1 BP神經(jīng)網(wǎng)絡(luò)模型誤差Fig.1 Model error of BP neural network

圖2 差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)模型誤差Fig.2 Model error of BP neural network with differential evolution training

圖3 改進(jìn)的差分進(jìn)化訓(xùn)練BP神經(jīng)網(wǎng)絡(luò)模型誤差Fig.3 Model error of BP neural network with novel differential evolution training

[1]Leland,Taqqu M S,Willinger W,et al.On the self-similar nature of ethernet traffic （extended version）[J].IEEE Trans on Networking,2009,32（3）:1－15.

[2]Paxson V,Fbyd S.Wide-area traffic:the failure of Poisson.modeIing[J].IEEE/ACM Transaction on Networking,2009,32（5）:226－244.

[3]高雋.人工神經(jīng)網(wǎng)絡(luò)原理及仿真實(shí)例[M].北京:機(jī)械工業(yè)出版社,2009.

[4]Price K,Storn R,Lampinen J.Differential evolution:a practical approach to global optimization[M].Berlin:Springer,2005.

[5]MAYER D G,KINGHORN B P,ARCHER A A.Differential evolution：an easy and efficient evolutionary algorithm for model optimisation[J].Agricultural Systems,2004,83 （5）:315－328.

[6]姚峰,楊衛(wèi)東,張明.改進(jìn)自適應(yīng)變空間差分進(jìn)化算法[J].控制理論與應(yīng)用,2010,27（1）:32－38.

YAO Feng,YANG Wei-dong,ZHANG Ming.Improved spaceadaptive-based differential evolution algorithm [J].Control Theory&Applications,2010,27（1）:32－38.

[7]周艷平，顧幸生.差分進(jìn)化算法研究進(jìn)展[J].化工自動(dòng)化及儀表,2007,34（3）:12－19.

ZHOU Yan-ping,GU Xing-sheng.Development of differential evolution algorithm[J].Control and Instruments in Chemical Industry,2007,34（3）:12－19.