粒子群退火算法優化的BP神經網絡及其應用①

王 榮,白尚旺,黨偉超,潘理虎,2

1(太原科技大學 計算機科學與技術學院,太原 030024)

2(中國科學院 地理科學與資源研究所,北京 100101)

軟件老化通常是由軟件故障激活的累積效應造成的,從而導致內存泄漏、操作系統資源耗盡等系統錯誤,最終致使軟件失效或系統宕機的現象[1].隨著軟件系統的廣泛應用,研究發現在Web服務器[2]、文件服務器、數據庫管理系統[3]、DNS服務器以及虛擬化環境[4]等,出現軟件老化現象的概率會更高.隨著云計算時代的到來,提高系統可靠性的問題顯得尤為重要.因此,對軟件老化趨勢進行早期預測,在系統發生故障之前采取相應措施,能夠有效的提高軟件的可靠性與安全性.

軟件老化,受系統性能參數的相互影響和制約,呈現出一種非線性的特性.而BP神經網絡,是一種應用較廣泛的多層前饋型神經網絡,能夠擬合任意的非線性映射,是一個復雜的非線性動力學習系統[5].現有的基于BP神經網絡的軟件老化預測模型雖然在一定程度上取得了很大的進展,但仍存在一些不足之處,如BP神經網絡的初始權值和閾值都是隨機設定的[6],而粒子群算法能夠很好的解決BP神經網絡對初始參數選取比較敏感的問題.因此本文通過構建NPSOSABP神經網絡預測模型,將NPSOSA算法得到的最優解賦值給BP神經網絡的權值和閾值,并實現對軟件老化趨勢進行預測,實驗表明本文提出的NPSOSA-BP神經網絡預測模型,相比于傳統粒子群算法改進的BP神經網絡模型的預測精度更高.

1 BP神經網絡

BP (Back Propagation)神經網絡是目前應用比較廣泛的神經網絡算法,是一種誤差逆向推導的訓練模型.由輸入層、隱含層和輸出層3層組成,每一層都有大量且數量不同的神經元.BP神經網絡在學習的過程中,由數據正向傳播和誤差的逆向推導兩部分構成.正向傳播即在輸入層輸入訓練樣本后,神經元被激活,激活值由輸入層經隱含層處理后最終由輸出層輸出網絡響應;逆向傳播的過程為:如果在正向傳播過程中訓練輸出與期望輸出間存在誤差,則按照梯度下降法,經輸出層和隱含層沿著誤差減小的方向進行調整,不斷修改各個神經元的連接權值和閾值,直至滿足網絡的輸出要求.

2 NPSOSA-BP神經網絡預測模型的建立

2.1 基本粒子群算法

基本粒子群算法(Particle Swarm Optimization,PSO),具有良好的搜索機制,最早由Kennedy和Eberhart于1995年提出的.PSO算法起源于對鳥類捕食行為的研究,并將其與優化問題的求解過程進行對比及研究.該算法中每個粒子都可以看作是搜索空間中的最優解,在移動與飛行的過程中,利用適應度函數求得適應度值,用適應度值評價當前解的優劣.每個粒子由位置、速度和適應度值三項特征值進行表示.PSO算法隨機初始化一群粒子,接著在迭代搜索過程中,參照個體和群體極值的最優解,不斷調整飛行的速度和位置,以搜索到全局最優值.速度和位置更新公式如下[7]:

其中,m=1,2,···,M;i=1,2,···,N;Vim為第i個粒子在第m維的飛行速度;Xim為 粒子的位置;c1和c2為非負的常數,稱為加速度因子;r1和r2為介于[0,1]之間的隨機變量;Pim為 個體粒子經歷過自身最優位置;Pgm為種群粒子集合中各個粒子進行比較后所經歷的全局最優位置.

2.2 PSO算法的改進

PSO算法從種群的多個個體出發并行處理,具有良好的全局收斂性.但是PSO算法應用在高維復雜問題上,往往會出現迭代期間搜索不平衡,極易陷入局部極值得不到全局最優解、早熟收斂的問題.針對PSO算法的缺陷,本文提出一種NPSOSA優化算法,分別采用動態變化慣性權重法,以及引入模擬退火算法(Simulated Annealing algorithm,SA),對PSO算法進行改進.首先采用動態變化慣性權重法,使得迭代初期較大的慣性權重能夠擁有較強的全局搜索能力,而迭代后期較小的慣性權重有利于進行更精確的局部搜索,以此達到在整個迭代過程中平衡粒子的全局與局部搜索能力.其次針對粒子群算法易聚集到次優解而陷入局部最優發生早熟的情況,利用SA算法的概率突跳性來跳出局部極值,避免早熟問題.

2.2.1 動態變化慣性權重的設置

PSO算法是粒子在飛行過程中不斷尋找最優值,但是當粒子以較快速度飛向全局最優解所在的區域時,尤其是在靠近最優解時,由于飛行速度過快,缺乏有效控制與約束,粒子的移動將會超過最優解的位置,粒子只能在最優解的附近來回移動,往前一步超過最優解位置,后退一步錯過最優解位置,使得粒子陷入局部優化的狀態.

為了使PSO算法在迭代周期內達到局部與全局搜索的有效平衡,并實現對粒子飛行速度的有力控制,本文引入了“動態變化慣性權重”參數.實驗表明,在慣性權重?不變的情況下PSO算法擁有較快的收斂速度,但容易出現在最優解的位置來回反復移動,陷入局部最優的問題.而采用“動態變化慣性權重法”優化的PSO算法,具有比固定值更為良好的搜索結果,使得迭代初期較大的慣性權重能夠在全局搜索范圍內得到較好的粒子,且搜索后期較小的慣性權重能夠在極值點的周圍做精細的搜索[8],有效提高了算法的求解精度.本文采用的動態變化慣性權重法公式如下,對應的曲線如圖1所示.

圖1 動態變化慣性權重

其中,ωstart為 PSO算法迭代初期時的慣性權重值;ωend為最大迭代次數時的終止權重值;k為當前迭代數;Tmax為最大迭代數.從圖1可以看出,迭代初期慣性權重變化較慢,粒子可以進行較大范圍的搜索,隨著迭代次數的增加,慣性權重下降的速度也逐漸加快,較好的局部搜索能力展現出來.該策略下的粒子速度更新公式如下:

2.2.2 模擬退火算法的引入

SA算法,主要源于熱力學的理論,通過研究熱平衡問題,將其應用在優化問題的求解過程中.在模擬高溫物體退火過程中尋找優化問題的全局或者近似全局最優解[9].因此如何有效的調整溫度成為SA算法最重要的問題,在算法中溫度是一個很重要的參數,一方面,溫度可以限制SA的搜索范圍;另一方面,溫度決定了算法在運行過程中以多大的概率接受劣于當前解的新解.其中,SA算法采用Metepolis準則作為接受新解的概率.公式如下:

其中,x為當前解;x′為新解;f(·)代表解的目標函數值;T為溫度.

本文提出的NPSOSA算法以NPSO算法為主要的流程,是在繼承NPSO算法優點的基礎上,引入SA算法.該算法的思想是:在更新個體和種群極值時加入SA算法,對NPSO算法的適應度值和位置按照Metropolis準則接受最優解的同時以一定的概率接受惡化值.該過程不斷迭代進行,開始時溫度較高,接受劣解的概率相對較高,使得粒子有很高的機率跳出局部最優解,隨著溫度的逐步下降,能量降低,粒子接受較差解的概率變小,最終收斂至全局最優解,避免早熟問題.pi存儲的是各個粒子的位置和適應值,Pg存儲種群最優粒子的位置和適應值.計算各粒子接受概率公式如下:

2.3 構建NPSOSA-BP神經網絡

NPSOSA-BP神經網絡其本質是利用NPSOSA算法尋優能力強,收斂速度快的優勢,獲得最優的初始權值和閾值,并將最優值賦值給BP神經網絡,應用在軟件老化預測趨勢上.實驗表明,利用NPSOSA算法優化BP神經網絡能有效提高網絡的性能,預測精度也相對提升.

2.3.1 NPSOSA-BP神經網絡結構的確定

本文實驗的輸入層與輸出層節點數分別為3、10.隱含層節點數按照傳統的計算公式a∈(1,10),得出適宜的節點數值范圍為3～12.經過仿真實驗,驗證得出當隱含層節點數為10的時候,模型能達到最佳軟件老化預測狀態.于是本文搭建了具有3-10-1結構的NPSOSA-BP神經網絡預測模型.實際上,除了選取最佳隱含層神經元個數以外,也可以通過增加隱含層數來提高神經網絡的學習能力,但后者方法使網絡結構復雜化,訓練時間增長,因此本文采用單隱含層BP神經網絡.

2.3.2 NPSOSA-BP神經網絡預測模型的訓練與預測

NPSOSA-BP神經網絡預測模型的訓練與預測流程如下:

① 數據預處理.由于原始數據數量級差別較大,對BP神經網絡訓練過程產生較大的影響,加大訓練難度.因此為了提高神經網絡的訓練效率,在對數據進行分析之前,需要對數據進行歸一化處理,將輸入層數據和輸出層數據歸一化到[–1,1]之間.

② NPSOSA-BP算法參數的設定.本實驗NPSO算法參數設定:加速度因子c1=c2=1.49445,ωstart=0.9,ωend=0.4,迭代次數為1000次,種群規模為60.SA算法參數設置:初始溫度為10 000,溫度下降速率采用公式:T=T0(0.9j?1),其中T0為 初始溫度,j為迭代次數.BP算法初始參數設置:學習速率為0.05,期望誤差為1×10–6.

③ 初始化粒子群.NPSO算法需要對BP神經網絡中所有權值和閾值的集合進行優化.粒子的速度和位置向量的維數等于BP神經網絡中所有權值和閾值的數量之和,即3×10+10×1+10+1=51.采用算法開發與分析工具Matlab 2016a,其內部函數rands(1,51)隨機初始化粒子的位置和速度.

④ 更新粒子的速度和位置.將所有粒子放置在預測模型中進行訓練,通過適應度函數式(7)計算適應度值,以此作為評價粒子的優劣,適應值越小,表示適應度越高.此外根據式(2)和式(4),更新粒子的速度和位置,本文采用BP神經網絡的輸出均方根平均誤差和作為神經網絡的適應度值,公式如下:

⑤ 迭代輸出最優值.粒子在每次更新時,采用Metropolis準則計算適應度值,隨著溫度的降低,收斂得到全局最優解.

⑥ NPSOSA-BP神經網絡模型訓練.獲得最優解并確定BP神經網絡的權值和閾值,輸入訓練數據來訓練模型.用訓練好的模型對軟件老化趨勢進行預測.

3 實驗與結果分析

3.1 軟件老化加速壽命實驗

為研究與內存泄漏相關的軟件老化現象,本文以一個符合TPC-W基準測試規范的Web應用服務器為研究對象,在其后臺程序中注入關于內存泄漏的代碼加速其老化,從而設計出加速壽命測試實驗[10],并收集老化數據作為實驗的訓練集和測試集.TPC-W的組成在邏輯上分為3層:一個Web服務器,一個數據庫,以及一定量的模擬瀏覽器.三者之間的流程為:數據庫存儲售書網站的數據;模擬瀏覽器以會話的形式并發訪問網站頁面;當請求發送給Web服務器查詢相應網頁和圖像時,Web服務器緊接著與數據庫通信,傳輸數據并動態生成響應頁.實驗配置如表1所示,三者間的工作原理如圖2所示.

表1 實驗配置

圖2 三者間工作原理

本文選取了內存消耗速率作為加速壽命測試中的加速壓力,對Java虛擬機的內存管理進行研究.由于所有的Servlet運行在同一個JVM中,因此所有對象的數據都存儲在JVM堆中[11].為了模擬軟件老化現象,實驗修改了購書網站中的Search Request Page這個頁面,對應TPCW_search_request_servlet這個Servlet,為其注入一段內存泄漏代碼.由于JVM有垃圾回收器(GC),程序在運行時,對象的堆內存由GC的自動內存管理系統回收,當JVM內存使用量逐漸增加并達到最大值時,GC將自動啟動并釋放內存.GC回收任何不再被引用的對象,其占用的內存也會被釋放.為了模擬軟件老化現象,本文增加一個HeapLeak類,使服務器整個生命周期都保持對該類對象的引用,且HeapLeak類對象在程序運行期間不會被GC回收,當創建的實例數量達到最大堆容量時,會產生JVM堆溢出.運行客戶端,每隔1 s采集一次JVM內存使用量,共持續14 400 s,采集樣本14 281個.每隔120 s取一次均值,實驗數據圖如圖3所示.

3.2 實驗分析

為了證明模型的有效性,使用Matlab 2016a編程實現了NPSOSA算法優化的BP神經網絡模型,以及與其對比分析的傳統PSOSA-BP、PSO-BP,BP預測模型.神經網絡結構采用3-10-1,每組實驗的工作負載為100個客戶端.實驗共收集到14 281個數據,取前7000個作為訓練集,后7281個作為預測集.不同的預測模型在實驗訓練過程中采用的是相同的老化數據,實驗結束后分別得到4個模型的預測與期望輸出的對比曲線,如圖4至圖7所示.本文選取MAE (平均絕對誤差),MSE (均方誤差)作為評價標準,公式如下.4種不同預測模型的評價指標對比如表2所示.

圖3 JVM在120 s內平均使用內存變化趨勢

圖4 BP神經網絡預測

從圖4到圖7可以看出本文提出的NPSOSA-BP神經網絡預測模型,經引入動態變化慣性權重法,SA算法的優化后,預測輸出曲線與期望輸出曲線的擬合效果越來越好,預測精度也明顯提高.從表2可以得出NPSOSABP神經網絡模型相比PSOSA-BP神經網絡模型預測精度提高了8%,相比PSOBP神經網絡預測模型提高了10%,相比BP神經網絡模型提高了30%.由此可以得出,本文提出的基于新型粒子群退火算法優化的BP神經網絡模型相比于其他優化算法在預測精度、擬合效果方面存在明顯的優勢.

圖5 PSO-BP神經網絡預測

圖6 PSOSA-BP神經網絡預測

圖7 NPSOSA-BP神經網絡預測

表2 神經網絡模型誤差對比圖

4 結束語

軟件老化是影響軟件系統性能的重要因素,本文通過建立一個軟件老化測試平臺,為其注入一段內存泄漏代碼加速老化,收集系統老化數據,根據獲取的老化數據構造NPSOSA-BP神經網絡預測模型.NPSOSA算法不僅解決了BP神經網絡對初始權值和閾值依賴性的問題,而且克服了PSO算法全局與局部搜索不平衡、早熟收斂相關問題,提高了神經網絡的預測精度.使得BP神經網絡擁有良好的學習能力和泛化能力,能夠很好的應用在軟件老化趨勢預測方面.