一種權重自適應的強化學習云資源調度算法

李成嚴，孫 巍，唐立民

(1.哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080；2.中國航發哈爾濱東安發動機有限公司，哈爾濱 150066)

0 引 言

云計算[1]是當前熱門的一種服務模式，為用戶提供動態可伸縮的廉價服務，同時減少與服務商之間的交互。用戶通過按需付費的方式享受到服務商通過網絡為其提供的資源共享池中的資源。

云資源調度[2]是指根據資源使用規則，不同的資源使用者按照規則在云服務平臺進行資源調整的過程。在合理的資源調度優化算法對于提高云計算系統的綜合性能是至關重要的。

調度中的服務質量約束包括運行成本、完成時間、安全性、可用性等。其中運行成本和完成時間分別是影響運營商和使用者滿意度的關鍵因素。Yao等[3]為了減少任務的完成時間，提出一種以最小化完成時間為目標的云資源調度模型。Zhang等[4]為了提高運營商的滿意度，研究了如何降低運營商的成本。Xu等[5]針對在滿足多個服務器提供高質量服務的同時，如何降低能耗這一問題，提出了一種新的數據中心調度方案，將提升服務質量與降低能源消耗這二者關系轉化為利潤與成本之間的關系。Jena等[6]通過優化任務的等待時間來最大化虛擬機的吞吐量和保持任務優先級之間的平衡。在實際需求中，將減少執行時間和降低運行成本同時作為優化目標對于調度算法來說是至關重要的。本文以減少虛擬機運行成本和任務總完成時間為優化目標，建立了多目標云資源調度模型。

近年來，為求解云資源調度問題，國內外學者提出了許多智能啟發式算法，如Zhang等[7]提出的蟻群算法，Gawanmeh等[8]提出的遺傳算法等。相較于上述算法，強化學習[9]作為一種與模型無關的具有學習能力的非監督式智能搜索算法，在云資源調度問題上具備較好的學習效果，因此嘗試使用強化學習算法解決云資源調度問題。其中，Q學習算法[10]對于調度問題表現更加穩定。Peng等[11]設計了一種基于強化學習和排隊論的任務調度方案，并在資源約束條件下優化任務調度，將強化學習應用于云工作流調度中利用狀態集結技術加快學習進度。針對算法易陷入局部最優這一缺點，Bahrpeyma等[12]將Q學習算法中的動作選擇策略選為ε-greedy算法，通過ε調節探索與利用之間的平衡，Agent以一定概率重新隨機選擇動作，跳出局部最優。Wu等[13]，以解決任務調度時間長，負載不均衡的問題，雖然算法可以尋找到最優解，但仍存在收斂速度過慢問題。Reinaldo 等[14]提出了啟發式Q學習算法，在傳統Q學習的基礎上加入一個影響行為選擇的啟發式函數，函數利用先前的經驗，指導Agent進行動作選擇，提高收斂速度，函數只改變動作的選擇，并不改變Q值。為了進一步提高算法的收斂速度，本文考慮將權重因子與啟發式函數相結合，依據Agent每次訓練后的立即回報值，自動更新不同動作執行后的權重因子，從而確定動作選擇策略，提高算法收斂速度。

本文提出一種權重自適應的啟發式動作選擇策略。在ε-greedy算法的基礎上，引入結合了權重因子概念的啟發式函數，提出基于權重自適應的啟發式Q學習算法(heuristics accelerate q-Learning based on adaptive weight，WHAQL)，并將它作用于多目標云資源調度模型的求解上。

1 多目標云資源調度模型

多目標優化的云計算資源調度問題的數學模型定義如下：

1)任務集合定義為T={t1,t2…tn}，共n個任務，其中ti表示第i個任務，且ti={ti(1),ti(2)…ti(p)}，表示第i個任務包含p個不同的屬性。

2)執行任務調度的虛擬機集合定義為VM={vm1,vm2…vmm}，共m臺虛擬機(m

3)第i個任務分配給第j臺虛擬機定義為

(1)

4)第i個任務在第j臺虛擬機的執行時間定義為

ectij=sizei/mipj

(2)

其中，sizei為第i個任務的大??；mipj為第j臺虛擬機的處理速度。

5)第j臺虛擬機的總運行時間定義為

(3)

一個完整的調度方案Pi的總執行時間定義為

(4)

執行任務所消耗的總運行成本定義為

(5)

其中，cstj表示在單位時間內，第j臺虛擬機執行任務所消耗的資源成本。

多目標云資源調度的目標是使任務總執行時間更短，同時所需的運行成本更低。則云計算資源調度的多目標優化問題可以表示為

min[Time(Pi),Cost(Pi)]

(6)

針對多目標優化問題，本文引入一種通過控制權值的方法求解多目標優化問題的函數。考慮到任務的執行時間和運行成本在數據規模上不統一，因此使用取對數的方法對數據進行標準化處理，最終調度Pi評價函數定義為

est(Pi)=ωlogTime(Pi)+(1-ω)logCost(Pi)

(7)

其中：ω∈[0,1]，表示用戶對執行時間和運行成本的關注度，通過調整ω的大小來滿足用戶對執行時間和運行成本的不同需求。

虛擬機的最短執行時間與最長執行時間的比值定義為系統的負載均衡函數，公式如下

(8)

根據式(8)可知，Load值越接近1，系統的負載越均衡，對資源的利用率越高。

在改進Q學習算法中，將針對多目標云資源調度模型中的優化目標進行合理的算法設計，使改進后的Q學習算法更適用于解決此問題模型。

2 WHAQL算法設計與分析

2.1 強化學習

強化學習(Reinforcement learning，簡稱RL)是機器學習領域的一種通用算法，主要思想是 Agent通過一個“試錯”的過程，與環境進行交互得到回報值，以最大化回報值為目標進行學習。

Agent通過執行動作與環境進行交互，當Agent執行一個動作后，會使得狀態按某種概率轉移到另一個狀態；同時，環境會根據回報函數反饋給Agent回報值。過程如圖1所示，其中，t為時間(t=0,1,2,3...)；St∈S，S為狀態空間；At∈A(St)，A(St)為在狀態St時的動作集；Rt為t時刻的立即回報。

圖1 Agent與環境交互圖Fig.1 Interaction between agent and environment

2.2 云資源調度的馬爾科夫決策模型

2.2.1 馬爾科夫決策優化方法

云資源調度問題可以用馬爾科夫決策過程[15](Markov decision process，MDP)來描述。MDP用五元組可以表示為{S,A,Q,R,γ}。

S：表示狀態集，狀態空間。

A：表示動作集，動作空間。

Q：表示狀態轉移函數，Q(st,at)表示在t時刻執行動作at后，狀態在t+1時刻由st轉移為st+1所得到的Q值函數。

R：表示立即回報函數。r(st,at)表示在狀態st下執行動作at得到的立即回報值。

γ：表示折扣因子，用于權衡長期回報與立即回報之間的重要程度。其中γ∈[0,1]，當γ=0時，代表只考慮立即回報，不考慮長期回報；當γ=1時，代表將長期回報與立即回報看得同等重要。

2.2.2 云資源調度的MDP模型

傳統的云資源調度問題中，狀態空間中的每一個狀態會定義為一個任務匹配矩陣Matrixm×n；動作空間中，每個狀態對應的動作與任務數相對應。比如說，第i個任務分配給第j臺虛擬機，在任務匹配矩陣中，mij=1。

由于上述狀態是定義為矩陣的形式，因此存在搜索空間過大問題。為了減少算法搜索空間，本文將狀態空間中的每一個狀態定義為數組形式，提高算法性能。本文云資源調度的MDP模型定義如下：

1)狀態空間由不同的狀態s構成，由一個動態數組表示，其中狀態s用一維數組表示，s的下標表示任務序號，s的值表示虛擬機序號，數組的維數為任務的個數，數組數值的最大值為虛擬機序號的最大值。比如5個任務分配3臺虛擬機，則是一個維數為5的整形數組，每個元素的值表示任務分配到哪個虛機上執行。

2)動作空間。將動作定義為整型變量，當執行將第i個任務分配給第j臺虛擬機這一動作時，則將整型變量j賦值給狀態s數組中第i個值。

例如一維數組[1, 0, 0, 2, 1]，則表示第0個任務分配給1號虛擬機，第1個任務分配給0號虛擬機，完整對應關系如下：

TaskID=0 VmID=1

TaskID=1 VmID=0

TaskID=2 VmID=0

TaskID=3 VmID=2

TaskID=4 VmID=1

3)立即回報定義了一種立即啟發式回報函數，能夠較精確的評價動作的好壞，為學習系統直接及時地提供回報信息，從而引導強化學習算法更快的學會最優策略。此處將回報函數定義為

r=ωr_ect+(1-ω)r_cst

(9)

其中，r_ect和r_cst分別定義為

r_ect=Ect-Ti

(10)

r_cst=Cst-Ci

(11)

Ti和Ci分別表示當前狀態下已經分配的任務的總執行時間和執行任務的總成本。Ect和Cst都表示較大常數，此處將Ect設置為所有任務在所有虛擬機上的總執行時間，Cst設置所有任務在所有虛擬機上的總成本。用Ti和Ci來評價當前狀態下任務分配給第i臺虛擬機這一動作的好壞。式(10)和式(11)將Ti和Ci最小化問題轉化為回報值最大化問題，將任務調度的目標最小化完成時間與Q學習中最大化Q值函數聯系起來。

4)狀態轉移函數通過2.3節中Q學習算法中的Q值更新公式進行計算。

2.3 云資源調度的Q學習算法

Q學習算法作為一種基于值函數的離線學習算法，其核心是建立一個Q表，表的行和列分別表示狀態和動作，Q表的Q值是用來衡量在當前狀態下執行該動作的價值。主要通過迭代下述步驟進行訓練學習。

1)觀察當前狀態st，選擇合適的動作at。

2)狀態st轉移到下一狀態st+1，同時更新立即回報值r(st,at)。

3)在狀態st下執行動作at的Q值函數定義為Q(st,at)，更新公式如下：

(12)

其中，α∈(0,1)，表示學習速率。

Q學習算法動作選擇策略一般選用ε-greedy算法，Agent以ε的概率隨機選取動作，即探索過程，以1-ε的概率選擇Q值最大的動作，即利用過程。策略概率分布定義為

(13)

其中，arandom表示隨機選擇一個動作；p,q∈[0,1]，p值決定Agent進行探索概率，p值越大，Agent進行探索的概率就越小。

Q學習算法的目標是形成一個策略π:S→A，通過Agent反復的訓練過程實現Q值的最大化。

Q學習算法(q-learning，QL)偽碼如算法1所示。

算法1 Q學習算法偽碼

① Initializeω,ε,α,γ

② Initialize Q table

③ Repeat(for each episode):

④ Initialize statest

⑤ Repeat(for each step)

⑥ Select an action a using policy(13)

⑦ Execute actionatobserverandst+1

⑧ Update the values ofQ(st,at) according to equation(12)

⑨s=st+1

2.4 WHAQL算法設計

2.4.1 啟發式Q學習

針對Q學習算法收斂的速度慢這一問題，啟發式學習算法在傳統Q學習算法的基礎上，通過提供先驗知識去指導Agent進行動作選擇，動作選擇策略如下所示：

(14)

其中啟發式函數H(st,a)的更新公式定義為

(15)

其中：πH(st)表示狀態為st時，在啟發式函數H的指導下選擇的最優動作；Δ表示啟發系數。

啟發式Q學習算法(heuristics accelerate Q-learning，HAQL)偽碼如算法2所示。

算法2 啟發式Q學習算法偽碼

① Initializeω,ε,α,γ

② Initialize Q table, H table

③ Repeat(for each episode):

④ Initialize statest

⑤ Repeat(for each step)

⑥ Update the values ofH(st,at) according to equation (15)

⑦ Select an action a using policy (16)

⑧ Execute actionatobserverandst+1

⑨ Update the values ofQ(st,at) according to equation (12)

在啟發式Q學習算法中，Δ為固定值，不隨著不同的動作進行自動更新，為了進一步加強不同動作反饋得到的回報值對動作選擇的指導，進而達到提高算法的收斂速度的目的，本文采用一種權重自適應的啟發式動作選擇策略。

2.4.2 權重自適應的啟發式動作選擇策略

權重自適應的啟發式動作選擇策略設計如下。

設計G表存儲有權重因子的相關數據，元素為四元組〈si,ai,f(si,ai),rmax〉。si和ai分別表示需要更新權重因子的狀態和動作；f(si,ai)表示在狀態si下執行動作ai的權重因子；rmax表示狀態si下的最大回報值。更新規則為：

(16)

其中：at表示Agent在當前周期中在狀態si下選擇的動作；rt表示當前周期在狀態si下執行動作at反饋的回報值。f(si,ai)的值由rmax和rt共同決定。當rt>rmax時，即當前動作的回報值更大，該動作為目前最優選擇，因此按式(17)對權重因子f(si,ai)進行更新。通過對權重因子的不斷更新，記錄下不同動作的重要性。

為了使權重因子的大小對Agent的動作選擇做出進一步的指導，將f(si,ai)與啟發式函數相結合，將啟發式函數的更新規則定義如下：

(17)

改進后的Q學習動作選擇機制定義為

(18)

2.5 WHAQL算法偽碼

算法3 改進Q學習算法偽碼

① Initializeω,ε,α,γ,U

② Initialize Q table, G table

③ Repeat(for each episode):

④ Initialize statest

⑤ Repeat(for each step)

⑥ Select an action a using policy (18)

⑦ Execute actionatobserverandst+1

⑧ Update the values ofQ(st,at) according to equation (12)

⑨ Update the values off(st,at) according to equation (16)

2.6 WHAQL算法收斂性分析

本節針對在WHAQL算法啟發式動作選擇策略的收斂性進行分析。

假設動作a1是在狀態s*下記錄的初始最優動作，Agent通過學習得到了具有更大回報值的動作a2，根據式(16)可知：

f(s*,a1)

根據式(17)可知：

情況1：當a=a2時，

(19)

情況2：當a=a′時，其中a′表示包括a1在內，但a1≠a2的其他動作。

G(s*,a′)=0

(20)

根據式(18)和式(19)可知：

Q(s*,a2)+G(s*,a2)=Q(s*,a2)+

(21)

根據式(21)可知：

Q(s*,a′)+G(s*,a′)=Q(s*,a′)+0=Q(s*,a′)

(22)

對比式(21)和式(22)，顯然

即

Q(s*,a2)+G(s*,a2)>Q(s*,a′)+G(s*,a′)

根據式(18)可知

π(s*)=a2

通過上述證明可知，基于權重自適應的啟發式動作選擇策略收斂在權重因子大的策略；再通過魏英姿等[16]已證明過的啟發式Q學習算法的最優策略不變性以及Q值迭代收斂性，可以證明WHAQL算法最終必將收斂于最優策略。

3 仿真實驗

為測試本文所提出改進Q學習算法在解決本文所設計的多目標云資源調度模型的效率，將模型與算法在Cloudsim仿真平臺進行實驗。

利用Cloudsim仿真平臺隨機生成數據集，將任務大小定義在區間 [60000，120000]之間，虛擬機的處理速度定義在[400，1200]之間，通過式(2)可計算得到任務在不同虛擬機上的執行時間，虛擬機單位時間內的運行成本通過隨機生成的虛擬機處理速度進行規則計算得到，在根據式(5)到虛擬機的運行成本。

本文測試的任務規模從10個開始依次遞增10個，最多達到50個；虛擬機的數量設置為5個。實驗中的主要參數設置如表1所示。

表1 實驗參數設置Tab.1 Experimental parameter setting

WHAQL算法的參數設置如表2所示。

表2 算法參數設置Tab.2 Algorithm parameter setting

在相同數據集和算法參數設置下，本文從3個方面對改進后的算法WHAQL在求解多目標云資源調度問題上進行驗證。

3.1 算法尋優能力

在尋優能力方面，比較了以下4種算法：

1)按順序執行的調度方案，將任務按順序依次分配在每個虛擬機上，即第一個任務分配給第一臺虛擬機，第二個任務分配給第二臺虛擬機等，用Equ表示。

2)遺傳算法[8](GA)。

3)Q學習算法[17](QL)。

4)基于自動更新權重的啟發式Q學習算法(WHAQL)。

圖2～圖4分別表示當ω=0.5、ω=1、ω=0時，使用上述4種算法對不同任務規模下的模型進行多次求解取平均值的結果。

圖2 ω=0.5時，算法尋優能力對比圖Fig.2 ω=0.5 Comparison chart of algorithm′s optimization ability

圖3 ω=1時，算法尋優能力對比圖Fig.3 ω=1 Comparison chart of algorithm′s optimization ability

圖4 ω=0時，算法尋優能力對比圖Fig.4 ω=0 Comparison chart of algorithm′s optimization ability

其中，橫坐標表示任務規模，縱坐標表示評價函數值，評價函數值越小，算法的尋優能力越強。

通過圖可以看出，當時間因子和成本因子均為0.5時，WHAQL所得到的調度方案可以得到最小化的評價函數；而當單獨考慮時間或成本時，WHAQL也能夠在時間或成本的最小化上獲得更好的結果。

3.2 算法收斂速度

在算法收斂速度方面，本文將基于權重自適應的啟發式Q學習算法(WHAQL)與Q學習算法[17](QL)和啟發式Q學習算法[18](HAQL)進行對比。

圖5表示當任務規模為20，ω=0.5時，3種算法迭代過程的對比圖?？偟螖翟O置為5 000次，每迭代500次為一個學習階段，記錄一次結果，共10個學習階段。其中，橫坐標表示任務規模，縱坐標表示評價函數值。

圖5 ω=0.5 20task-5vm 收斂過程對比圖Fig.5 ω=0.5 20task-5vm Comparison of convergence process

觀察圖5中3種算法的迭代曲線可知，3種算法在經歷不同的迭代次數后均可達到收斂；WHAQL和HAQL算法在啟發式函數指導下，兩者都較QL算法學習能力更強，更快達到收斂，而WHAQL算法在啟發式函數中引入自動更新的權重因子，對動作的指導能力得到加強，使其在3個算法中收斂速度最快；此外，WHAQL在引入自動更新的權重因子后，將每次動作反饋的回報值更好地用于指導下一次動作的選擇，使Agent更好地權衡了不同動作的重要程度，因此WHAQL相較于HAQL和QL算法，收斂到的評價函數值也更小?？梢?，改進后的算法WHAQL尋找最優解的能力也更強。

3.3 算法負載均衡

在算法負載均衡方面，將WHAQL算法與Equ、GA[8]和QL算法[17]進行對比。

圖6表示當ω=0.5時，不同任務規模的情況下，4種算法的負載均衡對比圖。

其中，橫坐標表示任務規模，縱坐標表示負載均衡值，負載均衡值越接近1，系統的負載越均衡。

圖6 不同任務規模下的負載均衡程度Fig.6 Load balancing degree under different task scales

由圖6可知， WHAQL的負載均衡程度相較于其他3種算法效果更好，這證明WHAQL不僅對資源有更高的利用率，還可以有效減輕虛擬機的工作負載。

通過上述實驗可知，本文提出的WHAQL在尋優能力上優于其他幾種算法，相較于QL和HAQL也具備更快的收斂速度。將WHAQL應用于多目標云資源調度模型，使任務的完成時間更短、虛擬機的運行成本更低，同時有效減輕虛擬機工作負載。從整體上提高了云資源調度的綜合性能。

4 結 論

本文將任務的完成時間和虛擬機的運行成本同時作為優化目標，建立了多目標云計算資源調度模型，提出了一種基于權重自適應的啟發式Q學習算法(WHAQL)。WHAQL在啟發式強化學習的基礎上引入了權重因子，進一步加強了對Agent動作選擇的指導，提高算法的收斂速度的同時，也提高了算法的尋優能力。實驗證明WHAQL有效地提高了云資源調度的整體性能。

在未來研究工作中，主要研究如何對Q學習算法中的狀態空間進行整合優化，使其更適用于解決未來更大規模的云資源調度問題。