一种权重自适应的强化学习云资源调度算法

李成严，孙 巍，唐立民

(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种算法迭代过程的对比图。总迭代次数设置为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学习算法中的状态空间进行整合优化，使其更适用于解决未来更大规模的云资源调度问题。