適應遺傳退火算法優化BP神經網絡及其應用①

裴 瑞,白尚旺,黨偉超,潘理虎

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

在一個長期運行的系統中,軟件的退化和意外中斷被稱為軟件老化現象,軟件老化表現為系統的狀態異常、性能退化、軟件的掛起和失效[1].已經證明了幾種類型的系統遭受到軟件老化,包括:Web 服務器[2],操作系統[3],數據庫管理系統[4],云計算[5]和虛擬化環境[6]等.因此,對軟件老化的趨勢進行早期預測,并在系統崩潰之前采取有效的預防措施,有助于提高軟件的可靠性和可用性,減少軟件失效的發生和一些不必要的資源浪費及財產損失.本文通過對TPC-W 基準測試標準的在線售書網站注入一段內存泄漏代碼,收集JVM 在120 s內的平均內存變化數據作為實驗的訓練集和測試集.

由于BP 神經網絡獨特的誤差逆向傳播算法不斷的修正權值和閾值,不僅可以縮短訓練時間還能提高擬合精度的特點,自適應遺傳算法有著全局搜索能力和自適應優化方法,當種群規模較大時遺傳算法可以在全局搜索范圍內找到最優解,該過程簡單易實現且求解快速的特點.

在此基礎上提出了一種新型自適應遺傳退火算法(NAGSA)優化BP 神經網絡模型,采用輪盤賭選擇法和精英保留策略相結合的選擇操作對種群中個體進行篩選,之后通過新型自適應遺傳算法優化交叉概率和變異概率,由于遺傳算法在運行后期個體的適應度逐漸趨于一致,優秀個體優勢不足,這時需要通過模擬退火算法對適應度進行拉伸,之后將得到的種群中個體的解碼賦值給BP 神經網絡的權值和閾值進行預測.實驗表明本課題提出的NAGSA-BP 神經網絡模型,相比傳統遺傳算法改進的BP 神經網絡模型的預測精度更高、收斂性更好.

1 BP 神經網絡

BP(Back Propagation)神經網絡是目前應用較廣泛的一種多層前饋型神經網絡,其網絡訓練采用誤差逆傳播算法[7],它可以擬合任意的非線性映射從而降低預測誤差.現有的基于BP 神經網絡模型雖在一定程度上取得了進展,但是依舊存在一些不足需加以改進.

2 自適應遺傳退火算法優化BP 神經網絡

2.1 遺傳算法優化BP 神經網絡模型

遺傳算法的優點是全局式搜索,并且它可以利用歷史信息來指導搜索進入到搜索空間內性能更好的區域,BP 神經網絡的優點是局部尋優,因此可結合兩者優勢進行改進.遺傳算法對BP 神經網絡有兩方面的優化:權值優化和結構優化.權值優化:先通過遺傳算法縮小搜索范圍,再用BP 算法使其快速收斂尋找最優解,以此來實現權值的優化.結構優化:通過形成不同長度的種群和不同結構的網絡,各個種群經過進化之后選擇一個最優個體,可確定各權值的初始值.但是傳統的自適應遺傳算法(AGA)隨著進化的進行,一般先執行交叉操作后執行變異操作,這時種群的多樣性不豐富并且進化速度很慢,最終導致收斂過慢或者不易收斂的后果.因此,本文采用閆春等人[8]提出的新型自適應遺傳算法,結合了模擬退火算法共同優化BP 神經網絡模型,該模型根據優化遺傳算法的選擇算子、交叉算子、變異算子克服了傳統遺傳算法易陷入“早熟收斂”的缺點,平衡了種群的多樣性并且提高了收斂精度.

2.2 新型自適應遺傳退火算法

2.2.1 編碼

首先初始化種群,種群中的個體采用實數編碼方式將神經網絡中的權值和閾值進行優化,編碼所得長度H為:

其中,n為輸入節點個數,l為隱含層節點個數,m為輸出層節點個數,n×l為 輸入層與隱含層之間的權重 ωij的編碼長度,l×m為 隱含層與輸出層之間的權重 ωjk的編碼長度,n為隱含層閾值 α的編碼長度,m為輸出層閾值β的編碼長度.

2.2.2 選擇算子

基因選擇遵從“優勝劣汰,適者生存”的原則進行基因選擇.選擇算子在整個種群中尋找適應度較高的個體去生成初始的交配池.本文選用輪盤賭法和精英保留策略相結合的方法計算個體的選擇概率,將父代個體中適應度值最高的個體保留至下一代,剩下的個體按輪盤賭方法選擇個體.

2.2.3 適應度

遺傳算法通常采用評估函數——適應度函數來評估個體或者解的優劣,適應度越高的個體遺傳給下一代的概率就越大,適應度越低的個體遺傳給下一代的概率就越小.但是遺傳算法容易在早期使個別優良的個體后代充斥整個種群,從而造成“早熟收斂”,而后期適應度函數基本趨于一致,使得優良個體后代優勢不足造成種群進化停滯.本文引入模擬退火算法對適應度函數進行拉伸,在遺傳算法前期溫度較高,適應度相似的個體產生后代的概率近似,到了遺傳算法后期也就是溫度逐漸下降之后,適應度相似的個體通過拉伸作用,放大了它們的適應度差值,使得優秀個體的優勢更明顯,可幫助算法跳出局部最優解.拉伸方法如下:

其中,fi為第i個個體的適應度函數值,M為種群個數,T為退火溫度,T0為初始退火溫度,g為遺傳迭代次數.

2.2.4 交叉、變異操作

傳統AGA 算法思想是在個體適應度值高于平均適應度值時自適應的調節交叉概率、變異概率,反之則采用固定值的交叉概率、變異概率,所帶來的不足是一些較差的個體中攜帶的較為優良的個體會遭到破壞.因此,本文采用非線性自適應交叉概率PC和變異概率Pm:

其中fa是 種群個體平均適應度,fm是種群個體適應度最大值,當fa變 化時,a rcsin(fa/fm)會隨之快速變化,因為sin(π/6)=1/2,當a rcsin(fa/fm)≥π/6時 自變量fa/fm≥1/2.經過反復多次實驗,通過NAGSA 算法和NGSA 算法中的PC、Pm取值對訓練誤差精度的影響,當滿足設置條件π /12 ≤arcsin(fa/fm)≤π/3時,NAGSA 算法優先執行交叉操作再執行變異操作,則精度高于NGSA 算法25%；當滿足設置條件 arcsin(fa/fm)≤π/12 且arcsin(fa/fm)≥π/3時,NAGSA 算法優先執行變異操作再執行交叉操作,則精度高于NGSA 算法22%.得出設置條件π/12 ≤arcsin(fa/fm)≤π/3,若滿足則NAGSA 算法優先執行交叉操作,反之則優先執行變異操作.

將NAGSA 算法訓練后的權值和閾值作為BP 神經網絡的初始權值和閾值,用實驗獲得的樣本數據建立BP 神經網絡模型.

3 實驗驗證

3.1 數據獲取

造成軟件老化的一個重要因素是由于內存的泄漏,本課題在服務器端使用符合 TPC-W 基準測試標準的在線售書網站,為其注入一段內存泄漏代碼以加速老化.實驗平臺模擬了一個電子商務 Web 服務系統,其中包括運行在同一臺物理機的虛擬機中的一個Web服務器,一個數據庫服務器以及一組模擬的客戶端,如表1實驗配置所示.

表1 實驗配置

在符合TPC-W 規范的在線售書網站中,每一個網頁頁面都使用單獨的Servlet 實現,這些類都工作在同一個Java 虛擬機(JVM)中.JVM 是Java 技術體系的核心,操作系統為JVM 的進程分配內存,并由JVM 進行儲存和管理.其中Java 堆是運行時的數據區域并隨著JVM 的啟動而創建,所有實例類型和數組的內存均從此處分配.程序運行時,對象的堆內存由稱為垃圾回收器(GC)的自動內存管理系統回收.由于內存的泄漏大多發生在Java 堆,所以GC 主要針對Java 堆進行[9].當JVM 內存使用量持續增加并達到最大值時,GC 將自動啟動以釋放內存,但是如圖1JVM 中的內存泄漏所示,GC 僅回收無用和未引用的對象,而無用且引用的對象無法從占用的內存區域釋放,從而導致內存泄漏.同時,由于系統資源是有限的,垃圾收集器在內存釋放期間將占用大量的CPU 和系統資源.因此,連續出現的內存泄漏問題的累積效應將直接導致可用內存不足和與老化相關的系統故障.

本文采用加速退化測試[10](Accelerated Degradation Tests,ADT)實驗研究受軟件老化影響的應用程序故障,通過增加一個HeapLeak 類,讓服務器的生命周期都保持對該類的OOMObject 對象的引用,當服務器創建的實例數達到最大堆容量時,會產生JVM 堆的溢出,從而OOMObject 對象不再被GC 回收.實驗收集JVM的內存使用量,共持續14 400 s,每隔120 s 取一次平均值 .JVM 在120 s 內平均使用內存的變化趨勢圖如圖2.

圖1 JVM 中的內存泄漏

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

3.2 仿真實驗

3.2.1 數據預處理

本次實驗共獲取到3 個輸入參數,1 個輸出參數,神經網絡結構為3-10-1,每組實驗都選擇工作負載為100 個客戶端,共收集到14 281 個數據,取前7000 個作為訓練集,后7281 個作為驗證集.原始數據由于數量級差別較大,會對BP 神經網絡的收斂性產生影響,可能會加大訓練難度,耗費訓練的時間,因此為了提高網絡的訓練效率,用M a t l a b 中的歸一化函數mapminmax,將輸入層和輸出層數據歸一化到[-1,1]之間,BP 神經網絡訓練后得到的數據最后進行反歸一化處理,得到正常值.

3.2.2 建立訓練模型

本次實驗的輸入節點數為3,隱含層節點數為10,輸出層節點數為1,種群規模為60,進化次數為100 次,交叉和變異概率分別選擇0.6 和0.02.為了驗證本文提出的NAGSA-BP 算法有著更好的收斂效果和在驗證軟件老化預測上的有效性,分別與NGSA-BP、AGABP、GA-BP 算法進行比較,選取MAE、MSE作為評價標準,結果如表2所示.

表2 改進后的遺傳算法優化BP 神經網絡模型誤差對比

由表2可以看出,本文提出的NAGSA-BP 神經網絡模型,通過對交叉概率、變異概率的非線性優化,相比傳統的自適應遺傳退火算法(NGSA)優化的BP 神經網絡模型在預測精度上提高了35%,相比傳統的自適應遺傳算法(AGA)優化的BP 神經網絡模型在預測精度上提高了81%,相比傳統的遺傳算法(GA)優化的BP 神經網絡模型在預測精度上提高了97%.

由圖3、圖4可以看出,NAGSA-BP 神經網絡模型在加入了非線性自適應調整的交叉概率、變異概率之后,其算法的穩定性和收斂性都優于未改進的NGSA-BP神經網絡模型；NAGSA-BP、NGSA-BP 神經網絡模型通過后期模擬退火算法對適應度函數的拉伸作用,相比未改進的AGA-BP、GA-BP 神經網絡模型都在預測精度和擬合效果上有了顯著的提高.由此可得出,本文提出的新型自適應遺傳退火算法優化BP 神經網絡模型,無論是在預測精度上還是擬合效果上都存在明顯的優勢.

圖3 預測輸出與期望輸出對比圖

圖4 誤差對比圖

4 結束語

本文通過建立一個軟件老化測試平臺,通過內存泄漏代碼的注入,使得原本正常工作的在線書店網站出現老化現象,收集反應網站老化的系統參數,選取JVM 在120 s 內平均使用的內存作為預測的數據集.實驗表明,NAGSA-BP 神經網絡模型相比于幾個傳統遺傳算法改進的BP 神經網絡模型,不僅提高了預測精度,還在預測結果的收斂性上有顯著成效,驗證了本文方法的有效性.