基于遺傳算法的改進時序預測模型研究

李思莉，楊井榮

(成都理工大學 工程技術學院 電子信息與計算機工程系，四川 樂山 614000)

0 引 言

互聯網技術的發展帶來了電子商務等業務的迅猛發展，用戶請求和互聯網環境越來越復雜，服務器負載急劇增加，為互聯網應用的高可用性、高性能和服務質量帶來了嚴峻的挑戰。傳統的Web集群模式由于集群規模固定的問題，無法應對突發性訪問激增帶來的負載壓力。

云計算技術的出現使得集群規模可以隨工作壓力變化而動態調整，資源按需獲取成為可能。云計算中的彈性伸縮是一種云計算系統根據系統需求變化而自動調整的技術。它能有效提高用戶滿意度，特別是當系統需求不穩定時，能很好地調度資源，避免資源分配不足或資源浪費。其組織分類如圖1所示。

對于資源的伸縮，一般分為水平伸縮和垂直伸縮。在水平伸縮(伸/縮)過程中，以虛擬機為最小資源單位按需要添加或釋放虛擬機；在垂直縮放(上/下)過程中，通過改變分配給已經運行的虛擬機的資源來實現，例如增加(或減少)分配的CPU或內存。對于彈性伸縮的實現機制，目前比較流行的是反饋觸發策略[1]和提前預測。反饋觸發策略是根據一些性能指標和預定義的閾值來觸發伸縮，也就是說，系統將根據用戶負載是否達到某個確定的閾值來決定增加或減少資源。但是，需要精確的定量值，通常容易出現不確定性[2]。同時，如果用戶負載非常不穩定，就會造成系統資源的頻繁伸縮，這本身也會給系統帶來很大的負擔。加之，這種反饋觸發策略在資源分配部署過程中存在較大的延時問題，在用戶負載大規模增加的情況下，處理能力有限。

圖1 彈性云服務組織分類

預測模式以時間序列方法[3]、控制理論[4]、增強學習(RL)[5]和隊列模型[6]為主，但單純的時間序列方法難以預測峰值和工作負載真實變化。隊列模型只適用于靜態環境。此外，隊列模型的現有方法(QM)對彈性系統有不切實際的假設，并且這些假設在云計算環境中并不適用，因為在云環境中，動態工作負載是一種常態。

該文利用遺傳算法改進時序預測模型，結合當前資源使用率，對未來趨勢進行預測，從而實現了資源動態快速伸縮。通過實驗表明，該預測模型在同等虛擬用戶請求的時序下，虛擬機數量在滿足SLA的情況下較少，并且響應速度下降。

1 相關工作

1.1 排隊論

排隊論是排隊等待中的概率處理最優化設計問題。排隊論(QT)被廣泛用于表示基于internet的應用程序和傳統服務器性能指標，如隊列長度和平均等待時間請求的時間。云應用程序場景使用一個簡單的QM對于在“n”個虛擬機之間分配請求的負載平衡器?，F實云環境中的自動縮放問題是通過周期性地改變傳入的到達和無限服務器容量的假設。排隊理論包括到達過程、排隊規則、服務機制，如隊列長度和平均等待時間請求的時間。文獻[7]中使用排隊論對工作負載和服務平均響應時間進行預測，從而實現資源的動態分配。目前，被廣泛使用的排隊模型是M/M/1和G/G/1[8]，M/M/1將用戶服務請求過程看作為是一個參數為λ的泊松流，其中到達時間和服務時間是基于指數分布的，而G/G/1到達時間和服務時間是基于一般分布的,這種模型最大的問題是當面對峰值負載時，可能造成大量的資源浪費。排隊論適用于結構相對固定的系統，如果系統結構發生變化，需要重新建模。因此，排隊論在云計算資源動態伸縮的管理中代價很高，通常不是一個太好的選擇。

1.2 時間序列分析預測模型

基于時間序列分析的彈性策略是實現資源彈性管理的常用方法。它能夠預測應用程序的未來需求，所以通常用來提前申請資源，從而有效避免了在虛擬機啟動和應用程序部署上花費時間。這一策略具有巨大的潛力，在金融、工程、經濟和生物信息學等領域有著廣泛的應用。其獨特的特性也決定了該方法同樣適用于云計算環境下的資源預測。

目前，時間序列預測分析方法的主要模型有樸素模型(Native)、自回歸預測模型(AR)、自回歸滑動平均模型(ARMA)、差分自回歸滑動平均模型(ARIMA)以及擴展指數平滑模型(ETS)和神經網絡預測模型等[7]。樸素模型非常簡單，它假設最后一次的觀測值將出現在下一個時間間隔內。這個模型只需要單個時間點序列。

自回歸預測模型可以根據最近幾個時間段的負載值預測下一個時刻的負載。其線性表達式為：

yt=c+φ1yt-1+φ2yt-2+…+

φpyt-p+εt

(1)

其中，c是常量，εt是獨立的誤差項，φ1是自相關系數，該系數如果小于0.5，其預測結果將極不準確。

自回歸滑動平均模型ARMA(p,q)包含了兩個多項式的平穩隨機過程，一個用于自回歸，另一個用于移動平均線。其模型可以表示為：

(2)

其中，p和q是模型的自回歸階數和移動平均階數；φ和θ是不為零的待定系數；εt是獨立的誤差項；Xt代表平穩、正態、零均值的時間序列。ARMA模型適用于預測在一定趨勢內變化的時間序列。

差分自回歸滑動平均模型ARIMA(p,d,q)是ARMA模型的擴展，它不直接考慮其他相關隨機變量的變化，其模型可以表示為：

(3)

其中，p是自回歸項數，q是滑動平均項數，d是使之成為平穩序列所做的差分次數(階數)。該模型的缺點是參數選取困難。

神經網絡預測模型適用于非線性時間序列的預測，它采用梯度下降法來計算閾值和權值，并通過不斷修正網絡權值和閾值使誤差函數沿負梯度方向下降，逼近期望輸出。誤差函數表達式為：

(4)

其中，ti為期望的輸出，oi為網絡實際輸出。但是，神經網絡預測模型容易導致神經網絡陷入局部最優解，降低預測精度。

1.3 時間序列預測算法

目前，時間序列預測算法主要以差分自回歸滑動模型(ARIMA)[9]為基礎，這些算法對于時間有較強依賴性的線性數據有較好的預測效果，但對于非線性數據，如果數據波動過大，將對非平穩序列差分進行平穩化處理，變成平穩序列之后再進行移動回歸，這將會導致預測誤差增大。在實際云環境中，單一的ARIMA算法很難準確預測工作負載。因此，目前有些研究人員已經對ARIMA算法進行了改進，如文獻[10]用傅里葉變換提高預測準確度；文獻[11]中引入平均誤差提高預測精確度；文獻[12]對下一個預測周期進行預測誤差補償，防止誤差進一步擴大；文獻[13]對歷史窗口大小進行動態調整。這些算法是以ARIMA算法為基礎進行的改進，對提高預測準確度有一定的幫助。

2 改進的時序預測算法

2.1 資源分配彈性伸縮框架

由于并發或重復的請求是從多個客戶機發出的，因此到達間隔時間成為一個隨機變量，又由于到達的請求遵循具有無限計算能力的泊松過程，所以系統使用M/M/m隊列模型來處理到達的服務請求，m是提供的服務器數量。仿真結果表明，穩態下隊列長度等待的平均時間會隨平均間隔時間的增加而降低，如果增加服務器m(虛擬機)的數量，等待時間會降低。但是，在云計算環境下，需要通過負載平衡策略和時間預測算法計算出在不違反SLA原則的基礎上，最小化資源的占用率，即m的值。其框架示意圖如圖2所示。

圖2 資源分配彈性伸縮框架

從圖2可以看出，彈性分配策略主要分為兩個階段，第一階段負責預測下一個時間間隔的需求，第二階段根據改進的基于時間序列的算法求取最小資源數，動態調整調度資源。

2.2 改進的基于遺傳算法時序的預測算法GA-ARIMA

本算法是對ARIMA基本算法的改進，因此在設計時首先使用了arima()函數創建自回歸模型，接著使用auto.arima()函數根據確定的時間間隔調整參數，最后使用ets()函數調整平滑指數，使之與數據的擬合度最高。其具體算法偽代碼如下：

input:client request //用戶請求

output:next point //下一個時間間隔需求預測

1:init();

2:foreach timeInterval do

3:TS<-read(information); //將用戶請求轉換為時序

4: foreach m do

5:value[m]<-predictAhead(m);

6: end

7:nextValue<-UsingPerviousValue(value);

8:end

該算法首先完成初始化的工作，然后對于每個時間間隔(這個值可以設定)，將用戶請求(可以多個，高并發)轉換為時序，根據時序選擇適用的參數及模型，得到需求值。最后根據前一個需求值等到下一個預測值。

UsingPerviousValue函數需要用到遺傳算法[14]，該算法模擬達爾文的進化論，其具體描述如下所示：

input：perviousValue

output：nextValue

1:Initializate ();

2:While(not Terminate-Condition) do

3:evalPopulation();

4:select();

5:crossSelected();

6:mutateResultValue();

7:evaluateResultValue();

8:updatePopulation();

9:end

10:outputNextValue;

11:end

2.3 資源分配

根據2.2描述的預測算法得到的結果，使用M/M/m隊列模型[15]來分配資源，其系統資源利用率根據等式(5)來計算。

(5)

其中，ρ是系統利用率，λ是到達率，μ為處理率，m為服務器的數量。文中的目標是找到滿足用戶需求的m的最小值。因此變換式(5)得：

(6)

M/M/m模型中，系統利用率ρ和響應時間t密切相關，響應時間t計算如下：

(7)

將式(5)和式(7)帶入式(6)得：

(8)

根據式(8)就可以計算出所需資源，要使m值最優，采用如下算法：

輸入：預測值(算法2的結果)

輸出：m

初始化;

1：foreach(TS) do

2：λ<-getForecastPrevious(model);

3：μ<- getProcessingRate();

4：sla<-getMaxRT();

5：m<-calculateResources(λ,μ,sla);

6：end

通過預測獲得了下一個時序的到達率后，每個虛擬機和最大響應時間的μ值可以計算出來，最后帶入式(8)得m的值。

3 仿真實驗分析

為了驗證提出的基于遺傳算法改進時序預測的云計算彈性伸縮策略的有效性，利用基于OpenStack[16]開源項目搭建云平臺，將CPU需求(虛擬機數量)作為實驗數據，在Matlab上進行仿真，初始參數設置如表1所示。

表1 參數設置

圖3模擬了400秒內虛擬用戶的隨機請求時序。

圖3 時序圖

根據計算公式和實驗數據得出的誤差率如表2所示。

表2 各模型誤差值

由實驗結果可以看出，在同一時序下，利用遺傳算法改進的預測模式平均絕對誤差、均方根誤差等都有一定程度的降低。

根據式(8)計算所需虛擬機數量，在一周的時間內，相同負載下的不同模型實驗結果如圖4所示。

圖4 虛擬機數量對比

4 結束語

首先介紹了云計算彈性伸縮策略的必要性和現存策略的弊端，對目前現有的預測模型進行了相關的介紹，指出它們的優劣。在此基礎上利用遺傳算法對ARIMA模型進行改進，并對未來一段時間的虛擬機需求做預測，從而決定是否需要伸縮。通過實驗表明，提出的基于遺傳算法的預測模型在一定程度上減少了CPU使用率，減少了預測誤差，有一定的優越性。