一種基于差分進化的BP神經網絡學習算法

王曉敏，劉宏偉，李石妍

（河北工程大學 機電工程學院，河北 邯鄲 056038）

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

1 BP神經網絡模型

1.1 BP神經網絡

BP（Back Propagtion）神經網絡由 Rumelhart,McClelland于1985年最早提出，實現了Minsky的多層網絡設想。BP神經網絡學習算法是一種多層網絡的“逆推”學習算法。基本思想是，學習過程由信號的正向傳播和學習逆向反饋組成。BP神經網絡的非線性擬合能力強，精度高，并且算法簡單易懂，應用廣泛。但BP神經網絡存在局限。國內外學者針對BP神經網絡的不足進行改進。

1.2 BP神經網絡的標準學習算法

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

2 差分進化算法

差分進化是一種新穎的進化計算方法，最初的設想是解決切比雪夫多項式問題，后來發現差分進化解決復雜優化問題的優越性，并已應用與多個學科和工程領域[5－6]。它從當前種群中提取差分信息，然后指導進一步搜索，不需要借助問題的特征信息，具有較強的全局收斂能力和魯棒性。

2.1 差分進化算法的基本步驟

步驟4：交叉。為了增加干擾參數向量的多言性，引入交叉操作。向量變為（i=1,2,...,NP;j=1,2,...,D）

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

2.2 差分進化算法的其他形式

實際應用中還發展了差分進化的幾個變形形式，并用符號DE/x/y/z加以區分，其中：x限定當前被變異的向量是 “隨機的”或“最佳的”；y是所利用的差向量的個數；z指示交叉程序的操作方法。

式中，ri為隨機整數，表示個體在種群中的序號，r1、r2、r3、r4和r5互不相同。

2.3 控制參數的選擇

控制參數對一個全局優化算法的影響很大，差分進化的控制變量選擇也有一些經驗規則[7]。

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

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

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

4）最大進化代數 它表示遺傳算法運行結束條件的一個參數，表示差分進化算法運行到指定的進化代數之后就停止運行，并將當前群體中的最佳個體作為所求問題的最優解輸出。一般取值范圍為100～200。

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

3 網絡流量預測方法

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

其中gmax為最大迭代次數，g為當前進化代數，a的取值在 0.2～0.6之間。本文設計的差分進化的BP網絡學習算法，其偽代碼如下：步驟1：初始化BP網絡隱層神經元個數s、最大迭代次數Nmax、群體數目N、交叉概率CR、變異因子F。

步驟3：把最優參向量XG作為BP網絡最佳連接權值。

步驟4：BP神經網絡前項傳播，進行預測，計算誤差。

4 實驗與結果分析

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

BP神經網絡的輸入層為5個節點，隱含層為10個節點，輸出層為1個節點。訓練是把5日每小時的流量作為輸入，第6日的流量作為期望輸出。當訓練完成。最終預測3月16日全天流量數據。

為了驗證基于改進的差分進化的訓練BP神經網絡預測的有效性。筆者做了3個實驗。實驗1采用BP神經網絡作為模型；實驗2采用差分進化訓練BP神經網絡作為模型；實驗3采用改進的差分進化訓練BP神經網絡作為模型。在3次試驗中，目標誤差均為0.001，訓練的最大迭代次數為20000次，實驗結果如圖 1，2，3所示。

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

5 結束語

本文使用一種改進差分進化算法來訓練BP神經網絡，彌補了BP神經網絡易陷入局部收斂和收斂速度慢的不足。實驗結果表明，本文方法能得到較高的網絡流量預測精度，具有較好的應用價值。

圖1 BP神經網絡模型誤差Fig.1 Model error of BP neural network

圖2 差分進化訓練BP神經網絡模型誤差Fig.2 Model error of BP neural network with differential evolution training

圖3 改進的差分進化訓練BP神經網絡模型誤差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]高雋.人工神經網絡原理及仿真實例[M].北京:機械工業出版社,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]姚峰,楊衛東,張明.改進自適應變空間差分進化算法[J].控制理論與應用,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].化工自動化及儀表,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.