一種BP神經網絡和遺傳算法混合的云平臺負載預測方法

吳俊偉 姜春茂

摘要：在云計算提供高效，便捷等強大服務的背后，是日益攀升的能耗問題。準確的預測云平臺的負載（如CPU，內存的使用）在任務調度，云能效方面具有重要意義。在以往研究中，線性自回歸算法在預測請求資源的粒度上存在不足，本文提出一種基于BP神經網絡與遺傳算法混合的負載預測方法，結合遺傳算法良好的全局搜索能力與神經網絡強大的非線性擬合能力，建立CPU資源的請求預測模型。實驗通過Google的云平臺數據作為訓練，測試集。實驗結果表明該方法有效的預測了CPU資源請求量，進而可以在此基礎上調整服務資源，實現綠色調度。

引言

在云平臺提供的強大功能背后，是巨大的能源消耗問題。一個占地500平方米的數據中心每天消耗的電力就高達38000度，這一數字超過了3500戶歐洲家庭日用電量的總和。到2020年，預計數據中心的建設規模幾乎將是2010年的兩倍。從上述數字明顯可以看出，為云計算設計高能效的解決方案迫在眉睫。

云能耗的優化可以從云任務和云平臺的兩個角度進行研究。

從云任務的角度，主要是分析云任務的多維屬性，并利用算法來對云任務進行優化調度。云任務包括有靜態屬性和動態屬性。靜態屬性如需要的CPU數量，任務的開始時間，截止時間，任務的類型等。動態屬性如訪問頻率，存儲要求，時間分布，用戶請求模型等。挖掘出任務與能耗之間的關系將有助于提前預測負載，降低能耗。

從云平臺的角度包括服務器，軟件以及網絡。從服務器角度來看，云能耗來源于處理器與數據中心兩個層面，處理器的能耗的主要影響因素是應用程序的使用模式，而數據中心面臨的是不斷增長的主機數量與低使用率帶來的能源浪費，據統計分析，云數據中心服務器的使用率一般在11%?50%之間。因此，如果能夠較好的預測云平臺cro的使用情況對于關閉部分服務器，提高調度效率具有重要意義。本文提出了一種基于神經網絡和遺傳算法混合的云負載的預測方法，根據歷史數據預測未來短期CPU資源的需求，提高數據中心CPU的使用率，提局能效。

本文第1部分介紹相關工作的研究情況。第2部分提出基于神經網絡與遺傳算法混合的預測方法，第3部分實驗及其結果分析，最后總結與展望。

1 相關工作

在服務器領域，一臺完全空閑的服務器的能耗能達到其峰值的70%左右。處理器高能耗隨之帶來的問題是配套冷卻設施的開銷。據統計，計算資源消耗的每1瓦電能就需要額外的0.5?1瓦特進行冷卻。Bohra等人采用“主成分分析”方法對監控事件的相互關聯關系進行分析發現{CPU，Cache}對和{Disk，DRAM}

對有很高的相關性，由此把系統負載分成CPU密集負載和IO密集負載。Kaushik提出的綠色HDFS概念，將hadoop集群邏輯分為熱區和冷區，采用數據分類與節能的策略確保在冷區存儲的數據長期不被訪問，從而關閉冷區的數據節點，但當冷區節點被喚醒的頻率較高時，反而消耗更多能源。從軟件層面上看，文獻提出的一種綠色云架構實現虛機的重新配置，分配與再分配，以OPU的能耗為模型測量云平臺的能源消耗。Biirge等人在異構的數據中心處理請求的調度上，關注用戶任務布署的時間與節點，得出甚至只要運用很簡單的啟發信息都可以提高能效。在網絡方面，文獻中提出了一種域內流量工程機制GreenTE，能夠在保證用戶需求的前提下最大限度讓數據鏈路進入休眠狀態，Cianfrani等人提出一種能耗每女感的OSPF路由協議，通過優化Dijkstra算法與共享效率低的路由器最短路徑樹的方式，提供最少路徑數的路由服務。

在預測資源請求方面，文獻中通過分析主機狀態間轉換花費的時鐘頻率與電功率，提出綠色調度算法，用神經網絡作為云資源的預測原型。但實驗僅對NASA、Clark Netweb服務器url請求數作預測，粒度不夠精細。John J.Prevost等人同樣是預測url請求數，他們通過不同時間間隔模擬神經網絡與線性自回歸模型，從實驗數據來看，二者都有較理想的近似曲線，但神經網絡在90s間隔的案例中均方差值較大，預測效果不理想，分析得出神經網絡存在收斂速度慢，易陷于局部最優解等不足。

2011年google對外公布了其29天的云平臺實際數據，為進一步研究云平臺信息提供了重要的實踐依據。基于該數據，已經取得了相關的研究成果。其中，ZitaoLiu等人對此進行多方面的統計分析得出，在云計算中心任務的調度呈現周期性，其中被殺死（loll）和完成（finish）的任務（task）的數量相對穩定，而被殺死的任務占用CPU60%的時鐘周期，可成功完成的任務僅占10%?15%，結論表明合理運用啟發信息可提高完成任務所占用CPU時鐘周期的比例。文獻中提出一種預測失敗任務的普適框架。作者分析云任務屬性，以任務結束狀態作為結構體數據，選擇中長型任務，以上述的結構體作為輸入，用周期神經網絡訓練預測器，訓練完成后用該預測器對任務結束狀態作預測。但資源消耗的范化丟失了數據的一些原始特性，無法辨別任務失敗的具體原因，預測器無法在短時間內規避相同錯誤的作業。

綜上所述，國內外研究從多個方面尋求云節能方案。對于請求資源預測這一方面，資源粒度未能具體到物理或虛擬的靜態資源，而云能耗的度量大多都是以此構建模型的。算法單一，神經網絡雖具有良好的非線性映射能力，但同時它也存在收斂慢等不足；多元線性回歸可以準確地計量各個因素之間的相關程度與回歸擬合程度的高低，提高預測方程式的效果，但可能忽略了交互效應和非線性的因果關系。本文將主機的CPU作為能效的研究對象，在系統使用率層面，通過準確預測CPU的需求量來對服務平臺進行休眠，關閉等操作將極大降低云平臺的能耗水平。本文提出一種基于神經網絡和遺傳算法混合的用戶資源請求預測模型，預測未來短期CPU請求量，以此值為參照關閉閑置主機，從而提高系統使用率，降低能耗。

2 算法模型

2.1 BP神經網絡

BP（Back Propagation）神經網絡是一種按誤差逆傳播算法訓練的多層前饋網絡。從信息處理角度對人腦神經元網絡進行抽象，建立某種突觸聯系強

度可變的簡單模型，按不同的連接方式組成不同的網絡。每個節點代表一個神經元（Neuron），接受一組輸入信號，通過激勵函數生成特定輸出。神經網絡模型拓撲結構包括輸入層（inputlayer）、隱含層（hidelayer）和輸出層（outputlayer），如圖1所示：

輸入信號依次通過輸入層、隱含層、輸出層逐級前饋，直至網絡輸出。之后學習系統計算網絡的實際輸出與期望輸出的誤差，根據這個誤差逐級反饋調整網絡權值，縮小實際輸出與期望輸出的差值，完成網絡的學習過程。其具體過程如下：

（1）前饋計算

在該過程中，第層神經元的輸入為該神經元相連的第層神經元輸出的權重和，再將該和作為激勵函數的參數，計算出該神經元的輸出，設在第時刻第個神經元的輸入為，輸出為以，該神經元的輸出可表示為：

其中，表示節點到節點的輸入信號，表示節點到節點的權重，表示節點的閾值，為激勵函數。

（2）反饋傳播

反饋傳播的含義在于，第層神經元的誤差項是所有與該神經元相連的第層的神經元誤差項權重和與該神經元激活函數/梯度的乘積。

對于/為sigmoid函數，輸出層第時刻第個神經元，其誤差計算公式可表示為：

其中，表示期望輸出值，為實際輸出值。

而對于隱含層第《時刻第個神經元，其誤差計算公式可表示為：

第時刻第層第個神經元根據誤差項，調整與該神經元連接的第層所有神經元的權重值，其調整計算公式可表示為：

其中，表示學習率，為節點的輸出。

2.2 遺傳算法

遺傳算法（Genetic Algorithm）是模擬物競天擇的生物進化與自然選擇的計算模型，通過維護一個潛在解的群體執行多方向的搜索，以問題潛在解集作為初始化種群，以直接或間接的方式為該種群的每個個體進行基因編碼，實現從表現型到基因型的映射。在下一代中，根據問題域個體的適應性函數（fitness）選擇個體，并借助遺傳學的遺傳算子（geneticoperators）對染色體進行組合交叉（crossover），變異（mutation），繁衍出代表新解集的種群。這個過程將導致后代種群像生物進化一樣更加適應于環境，逐漸逼近問題的全局最優解。

2.3 混合遺傳算法

2.3.1 算法描述

通過2.1，2.2的描述可以發現，神經網絡與遺傳算法都具有自適應，自組織的特點，神經網絡雖具有良好的非線性映射能力，但易陷于局部最優解，而遺傳算法從問題解集開始搜索，覆蓋面大，易于尋找全局最優解。結合上一節的神經網絡，具體給出遺傳算法的關鍵步驟。

（1）基因編碼

遺傳算法的基因編碼有直接與間接編碼兩種方式。以直接的方式對神經網絡相鄰層的權重矩陣進行編碼，建立這樣一個神經網絡拓撲模型，3個輸入節點，4個隱含節點和一個輸出節點。如圖2所示：

其中表示節點1與節點4的連接值，表示節點2與節點4的連接值，以此類推，用權值矩陣記錄的節點間連接關系作為種群個體的遺傳信息。

（2）自然選擇

確定輸入；經過神經網絡的前饋計算，以均方誤差：

作為適應性函數（fitness），值越小表示適應性越好。其中，分別表示第n時刻輸出節點k的預測值與實際值。以輪盤賭的方式模擬自然選擇，在輪盤賭中，權重矩陣代表種群個體，用矩陣對應的適應值計算該個體在輪盤中所占據的扇形比例，以此近似該個體被自然環境所選中的概率。

（3）組合交叉

組合交叉模擬父母雙方染色體配對過程，使子類更加逼近問題的最優解。組合的方式多種多樣，這里介紹種群內部與種群間的基因重組，如圖3，圖4所示。

種群內部的重組體現在保留當前最優解的種群權值矩陣，種群間則使用的是單點組合交叉的方式組合交叉重組父母雙方權值矩陣，以產生新的解集空間。種群內部的重組體現在保留當前最優解的種群權值矩陣，種群間則使用的是單點組合交叉的方式組合交叉重組父母雙方權值矩陣，以產生新的解集空間。（4）基因變異

變異算子定義為以小概率事件修改基因重組后子類的權重矩陣，使得對問題的求解有機會從當前空間跳躍到另一個搜索空間，逼近問題的全局最優解。

（5）過渡條件

如此重復以上步驟，當達到預期的適應值或種群的適應值趨于穩定時，將適應性最好的基因作為神經網絡的權值矩陣，進入第6步。

（6）前饋傳播

對于每一組輸入，計算其實際輸出。

（7）反饋傳播

根據公式（2）（3），調整權值矩陣，當達到公式（8）小于預期的閾值或達到最大迭代次數時，結束算法。否則回到第6步。該算法的偽代碼如表1所示。

2.3.2 實例分析

以拓撲結構為3-4-1的神經網絡為例，假定初始條件下資源統計如下表2所示：

任選一組輸入數據（以編號1為例），通過前饋算，三組基因的輸出值分別為0.55，0.61，0.66，其適應值為0.013，0.005，0.001。對應的在輪盤中所占的比例為0.06，0.16，0.78。在輪盤賭中選中的基因為基因B與基因C。其基因重組，變異過程如圖7所示：

產生下一代個體，其適應值為0.0128。重復輪盤賭步驟構建新一代種群。假設圖9的基因適應值滿足迭代結束條件，則進入神經網絡訓練過程。

任選一組輸入（以編號2為例），經過網絡傳播，輸出值為0.63，根據實驗誤差與函數梯度調整矩陣，設學習率為0.25，閾值b設置為0。過程如圖8所示：

重復網絡訓練過程，直到達到最大迭代次數或均方差小于閾值，結束程序。

3 實驗及其數據分析

3.1 實驗環境與參數設置

本文實驗是在單機環境下完成的。華碩AllSeries臺式電腦，CPU為InterCorei5-4590

3.30GHz，8GB內存，1TB硬盤，主板集成聲卡和網卡，獨立顯卡。編程平臺為java環境。文獻使用了神經網絡和線性回歸模型對服務器資源的請求數做出預測，而神經網絡的預測效果相比下并不理想。實驗主要目的是測試神經網絡結合遺傳算法是否能突破局部最優解，更加逼近全局最優解的非線性曲線。因此設計了以下實驗。

實驗1GA擴大搜索范圍，尋找全局最優解區間。對谷歌數據的分析得出，集群的資源請求數據具有周期性，且一周為一個周期，換言之，上周一與這周一在請求值上具有相似性，所以我們明確以上周一與這周一的數據作為訓練樣本，預測下周一的請求數據。以上周一的數據作為網絡的輸入，這周一同一時刻的數據作為輸出，這樣就可以在夜間輕量負載的時間段執行預測程序。

初始化一個3-7-1的網絡拓撲結構，分別對應于輸入層，隱藏層和輸出層。輸入層3個節點分別是時間戳，CPU請求核數，任務請求量，輸出層為CPU的預測值。基于此拓撲的權值矩陣構建GA的編碼基因，首先隨機初始化矩陣集合，接著確定輸入值，每隔5mini己錄一次{timestamp，request Core，request Tasknum}結構數據，以24小時為整個時間跨度，可得到容量為288的數組。通過神經網絡前饋傳播輸出預測值，以均方差：

作為個體的適應性函數值，遵循優勝劣汰的規則，將適應值最高的個體基因直接遺傳給下一代，接著用輪盤賭的方式在種群中選擇待交配的雙方，采用單點基因重組構造新的權值矩陣。其變異率設置為0.05，變異區間[-0.5，0.5]。實驗中設置的參數如表4所示。實驗2BP神經網絡再訓練，逼近全局最優解。由實驗1訓練的適應值最大的編碼基因，作為BP神經網絡的權值矩陣，進入神經網絡訓練過程，得出逼近全局最優解的權值矩陣。設定sigmmd函數為激活函數，學習率為0.5。實驗中設置的參數如表5所示。

3.2 實驗分析

統計下周一的CPU資源請求數據，如圖9所示。使用神經網絡，以上周與本周的數據樣本作為訓練集，輸出結果如圖10所示。

混合算法，訓練集同上，測試結果如圖11所示。BP神經網絡與混合算法預測值與實際值差值樣本抽樣，如表6，表7所示。

如圖10所示，除個別數據節點，其它節點預測值與實際值相差較大，曲線逼近程度不理想。出現這種過擬合現象的主要因素是BP算法本身易陷于局部最優解。而在圖11中，除去少數節點，二者曲線波形相似，預測值曲線逼近實際值。表7中，混合算法均值為正數，說明該算法預測值平均高于集群的實際值，從而保證集群的SLA。本文提出的混合算法，在查找全局最優解方面借鑒遺傳算法，以面的方式搜索解集空間，尋找全局最優解區間，再用神經網絡逼近該區間的最優解，二者的混合更適用于復雜的非線性曲線問題求解。

4 總結和進一步研究

云數據中心的高能耗與低使用率的巨大反差催生了綠色節能的槪念。麵艮務器，網絡，軟件為提高能效的三大研究目標。針對服務器領域，本文提出的基于神經網絡與遺傳算法混合預測模型，自身具#轍子的學習能力，搜索全局最優解的能力較強，對云資源請求量的逼近效果較為理想，可為數據中心資源分配與任務調度提供參考。但該模型輸入參數類型較為局限，僅為timestamp、core、tasknum，且本文中該模型僅用于預測CPU資源，未來將考慮基于此構建云平臺資源請求的普適框架。