李雨泰, 李偉良, 尚智婕, 王洋, 董希杰

(國家電網(wǎng)有限公司 信息通信分公司, 北京 100761)

0 引言

云計算資源負載均衡預(yù)測的預(yù)測精度直接影響云計算系統(tǒng)的服務(wù)質(zhì)量、安全性和經(jīng)濟性，其是云計算系統(tǒng)平臺規(guī)劃的重要構(gòu)成部分[1]。根據(jù)歷史負載數(shù)據(jù)，建立云計算資源負載之間的定量關(guān)系，從而實現(xiàn)云計算資源負載的預(yù)測，為云計算資源的規(guī)劃、調(diào)度以及云計算平臺的性能優(yōu)化提供決策依據(jù)。由于云計算數(shù)據(jù)量的幾何級數(shù)倍增以及其復(fù)雜性和非線性，傳統(tǒng)的ARMA模型、ARIMA模型和FARIMA模型[2]已經(jīng)無法保證云計算資源負載預(yù)測的精度。神經(jīng)網(wǎng)絡(luò)雖然適合非線性資源負載預(yù)測，但其預(yù)測精度易受其權(quán)值和閾值的影響，存在收斂速度慢和局部最優(yōu)的問題。支持向量機[3]雖然適合短期資源負載預(yù)測，但其預(yù)測結(jié)果易受其參數(shù)選擇的影響。隨機森林[4](Random Forest，RF)是將隨機子空間和Bagging集成學習理論結(jié)合提出的一種機器學習方法，其具有預(yù)測精度高、收斂速度快、穩(wěn)健性好和調(diào)節(jié)參數(shù)少的優(yōu)點。文獻[5]為解決大部分虛擬機上任務(wù)不均衡和等待時間過長的問題，選擇虛擬機的CPU和內(nèi)存等資源的利用率為目標函數(shù)，提出一種基于粒子群算法優(yōu)化隨機森林的用于解決負載均衡問題。研究結(jié)果表明，PSO-RFR算法可以有效解決負載均衡問題，提高虛擬機的CPU和內(nèi)存的資源利用率。針對其預(yù)測結(jié)果易受森林中樹的數(shù)量Ntree、候選特征子集Mtry和葉節(jié)點的樣本數(shù)Nodesize等參數(shù)影響，提出一種云自適應(yīng)粒子群算法(cloud adaptive particle swarm optimization, CAPSO)優(yōu)化RF參數(shù)的負載均衡高精度預(yù)測方法，并實現(xiàn)RF算法參數(shù)的自適應(yīng)選擇。

1 隨機森林回歸

隨機森林回歸[6](Random Forest Regression，RFR)算法是基于決策樹分類器的組合算法，其利用bootstrap重抽樣方法從原始樣本中抽取多個樣本，對每個bootstrap樣本構(gòu)建決策樹，然后將所有決策樹中出現(xiàn)最多的投票結(jié)果最為最終預(yù)測結(jié)果。假設(shè)隨機參數(shù)向量θ對應(yīng)的決策樹為T(θ)，其葉節(jié)點表示為l(x,θ)，RFR算法步驟如下：

Step1：利用bootstrap方法重采樣，隨機產(chǎn)生k個訓練集θ1,θ2,…,θk；利用每個訓練集生成對應(yīng)的決策樹集{T(x,θ1)},{T(x,θ2)},…,{T(x,θk)}；

Step2：假設(shè)特征有M維，從M維特征中隨機抽取m個特征作為當前節(jié)點的分裂特征集，并以m個特征中最好的分裂方式對該節(jié)點進行分裂；

Step3：每個決策樹均得到最大限度的生長，在此過程中不進行剪枝；

Step4：對于新的數(shù)據(jù)，單棵決策樹T(θ)的預(yù)測可以通過葉節(jié)點l(x,θ)的觀測值取平均獲得，其中權(quán)重向量為wi(x,θ)；

(1)

Step6：運用公式(7)通過對決策樹權(quán)重wi(x,θt)(t=1,2,…,k)取平均得到每個觀測值Yi(i=1,2,…,n)的權(quán)重wi(x)如式(2)、式(3)。

(2)

(3)

2 云自適應(yīng)粒子群優(yōu)化算法

粒子群優(yōu)化(particle swarm optimization, PSO)算法是受鳥群覓食行為啟發(fā)的研究，其算法更新式如下[7-8]如式(4)、式(5)。

(4)

(5)

更新公式中的w和c1，c2均為常數(shù)，尋優(yōu)過程中，所有粒子的移動方向趨于一致性，使得粒子群體慢慢失去多樣性，導(dǎo)致算法容易陷入局部最優(yōu)和“早熟”問題。為了提高PSO算法的收斂速度和尋優(yōu)精度，將云模型[10]的隨機傾向性和穩(wěn)定性引入PSO算法，提出云自適應(yīng)粒子群優(yōu)化算法，通過云算子對PSO算法的慣性權(quán)重w進行自適應(yīng)改進，云算子的穩(wěn)定性可以保證全局最優(yōu)值，而隨機性可以避免PSO算法陷入局部極值，云算子的調(diào)整方法可以詳細描述如下：

(6)

(7)

(8)

(9)

式中，k1，k2為控制系數(shù)。第k代慣性權(quán)重wk計算式為[11]式(10)。

(10)

式中，wmin，wmax分別為慣性權(quán)重w的最小值和最大值。

3 基于CAPSO-RFR的負載均衡預(yù)測

針對RFR預(yù)測結(jié)果易受森林中樹的數(shù)量Ntree、候選特征子集Mtry和葉節(jié)點的樣本數(shù)Nodesize等參數(shù)影響[12]，在保證云計算資源負載預(yù)測誤差最小情況下，實現(xiàn)森林中樹的數(shù)量Ntree、候選特征子集Mtry和葉節(jié)點的樣本數(shù)Nodesize等參數(shù)的自適應(yīng)選擇，其適應(yīng)度函數(shù)如式(11)。

(11)

式中，Yi為第i樣本點負載實際值，Xi為第i樣本點負載預(yù)測值?；贑APSO-RFR的云計算資源負載預(yù)測算法如下：

Step1：歸一化云計算資源負載數(shù)據(jù)，并將數(shù)據(jù)劃分為訓練樣本和測試樣本，訓練樣本用于RFR模型的建立，而測試樣本則用于驗證RFR模型的效果；

Step2：CAPSO算法參數(shù)初始化：種群的規(guī)模N，最大迭代次數(shù)Tmax，學習因子c1和c2，慣性權(quán)重w，控制系數(shù)k1、k2；森林中樹的數(shù)量Ntree、候選特征子集Mtry和葉節(jié)點的樣本數(shù)Nodesize參數(shù)范圍的初始化；

Step3：初始化粒子的位置和速度：輸入訓練樣本，根據(jù)適應(yīng)度函數(shù)(11)計算每個粒子的適應(yīng)度；

Step4：更新粒子的速度和位置；

Step5：計算適應(yīng)度并更新粒子的速度和位置；

Step6：判定CPSO算法終止條件，若滿足則輸出最優(yōu)解；反之，執(zhí)行Step3；

Step7：輸出RFR模型的最優(yōu)參數(shù)：森林中樹的數(shù)量Ntree、候選特征子集Mtry和葉節(jié)點的樣本數(shù)Nodesize，并將這三個最優(yōu)參數(shù)用于云計算資源負載的預(yù)測。

4 實證分析

4.1 數(shù)據(jù)來源

為了驗證CAPSO_RFR進行云計算資源負載預(yù)測的有效性，選擇2018年7月16日-2018年7月26日11天的廣東某運營商云計算平臺提供的歷史云計算資源負載數(shù)據(jù)為研究對象[13-14]，其中每天每間隔1小時采集一點云計算資源負載數(shù)據(jù)，一共采集264組云計算資源負載數(shù)據(jù)，云計算資源負載數(shù)據(jù)如圖1所示。

圖1 云計算資源負載數(shù)據(jù)

4.2 評價指標

為評價云計算資源負載的預(yù)測結(jié)果，選擇MAE、RMSE和nRMSE作為云計算資源負載預(yù)測的評價指標[15-16]如式(10)—式(12)。

(10)

(11)

(12)

4.3 結(jié)果分析

為了證明本文算法CAPSO-RFR進行云計算資源負載預(yù)測的優(yōu)越性，將其與PSO-RFR、和RFR進行對比，對比結(jié)果如圖2和圖3以及表1所示。

圖2 對比結(jié)果

圖3 預(yù)測絕對誤差

方法RMSEMAEn RMSECAPSO-RFR0.30940.18442.2032%PSO-RFR0.37340.24204.8478%RFR0.81260.62657.3074%

結(jié)合圖2和圖3以及表1不同算法進行云計算資源負載預(yù)測結(jié)果可知，在RMSE、MAE和nRMSE三個評價指標上，與RFR和PSO-RFR相比較，CAPSO-RFR具有更高的預(yù)測精度；其次，PSO-RFR的預(yù)測精度優(yōu)于RFR；最后，RFR的預(yù)測精度最差，RMSE、MAE和nRMSE分別比CAPSO-RFR低0.5032、0.4421和5.1042%，通過對比可知，本文提出的算法CAPSO-RFR可以有效提高云計算資源負載預(yù)測的精度，同時實現(xiàn)RFR參數(shù)的自適應(yīng)選擇，為云計算資源負載預(yù)測預(yù)測提供新的方法和途徑。

5 結(jié)論

針對傳統(tǒng)的云計算資源負載預(yù)測算法存在精度低和誤差大的缺點，提出一種基于CAPSO -RFR的云計算資源負載預(yù)測算法。在RMSE、MAE和nRMSE三個評價指標上，與RFR和PSO-RFR相比較，CAPSO-RFR具有更高的預(yù)測精度。研究結(jié)果表明，本文提出的算法CAPSO-RFR可以有效提高云計算資源負載預(yù)測的精度，為云計算資源的規(guī)劃、調(diào)度以及云計算平臺的性能優(yōu)化提供決策依據(jù)。