基于云自適應粒子群優化算法和隨機森林回歸(CAPSO-RFR)的負載均衡預測

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

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

0 引言

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

1 隨機森林回歸

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

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

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

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

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

(1)

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

(2)

(3)

2 云自適應粒子群優化算法

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

(4)

(5)

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

(6)

(7)

(8)

(9)

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

(10)

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

3 基于CAPSO-RFR的負載均衡預測

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

(11)

式中，Yi為第i樣本點負載實際值，Xi為第i樣本點負載預測值。基于CAPSO-RFR的云計算資源負載預測算法如下：

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

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

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

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

Step5：計算適應度并更新粒子的速度和位置；

Step6：判定CPSO算法終止條件，若滿足則輸出最優解；反之，執行Step3；

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

4 實證分析

4.1 數據來源

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

圖1 云計算資源負載數據

4.2 評價指標

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

(10)

(11)

(12)

4.3 結果分析

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

圖2 對比結果

圖3 預測絕對誤差

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

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

5 結論

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