基于云自適應(yīng)粒子群優(yōu)化算法和隨機(jī)森林回歸(CAPSO-RFR)的負(fù)載均衡預(yù)測(cè)

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

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

0 引言

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

1 隨機(jī)森林回歸

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

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

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

Step3：每個(gè)決策樹均得到最大限度的生長(zhǎng)，在此過程中不進(jìn)行剪枝；

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

(1)

Step6：運(yùn)用公式(7)通過對(duì)決策樹權(quán)重wi(x,θt)(t=1,2,…,k)取平均得到每個(gè)觀測(cè)值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òng)方向趨于一致性，使得粒子群體慢慢失去多樣性，導(dǎo)致算法容易陷入局部最優(yōu)和“早熟”問題。為了提高PSO算法的收斂速度和尋優(yōu)精度，將云模型[10]的隨機(jī)傾向性和穩(wěn)定性引入PSO算法，提出云自適應(yīng)粒子群優(yōu)化算法，通過云算子對(duì)PSO算法的慣性權(quán)重w進(jìn)行自適應(yīng)改進(jìn)，云算子的穩(wěn)定性可以保證全局最優(yōu)值，而隨機(jī)性可以避免PSO算法陷入局部極值，云算子的調(diào)整方法可以詳細(xì)描述如下：

(6)

(7)

(8)

(9)

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

(10)

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

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

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

(11)

式中，Yi為第i樣本點(diǎn)負(fù)載實(shí)際值，Xi為第i樣本點(diǎn)負(fù)載預(yù)測(cè)值。基于CAPSO-RFR的云計(jì)算資源負(fù)載預(yù)測(cè)算法如下：

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

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

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

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

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

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

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

4 實(shí)證分析

4.1 數(shù)據(jù)來(lái)源

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

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

4.2 評(píng)價(jià)指標(biāo)

為評(píng)價(jià)云計(jì)算資源負(fù)載的預(yù)測(cè)結(jié)果，選擇MAE、RMSE和nRMSE作為云計(jì)算資源負(fù)載預(yù)測(cè)的評(píng)價(jià)指標(biāo)[15-16]如式(10)—式(12)。

(10)

(11)

(12)

4.3 結(jié)果分析

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

圖2 對(duì)比結(jié)果

圖3 預(yù)測(cè)絕對(duì)誤差

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

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

5 結(jié)論

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