一种基于深度强化学习的调度优化方法
邓志龙;张琦玮;曹皓;谷志阳
【摘 要】深度强化学习在于将深度学习的感知能力与强化学习的决策能力相结合,可以直接根据输入进行控制,是一种更接近人类思维方式的人工智能方法.旨在二者结合基础上,研究了一种基于深度强化学习的资源调度算法的设计框架.该框架首先利用从网络节点获取的大量先验数据,训练深度学习网络;然后利用强化学习来分配网络资源;接着通过大量的自我对弈,实现基于深度强化学习的价值网络学习.最后,设计实验方案对算法的性能进行了仿真和对比验证,以验证该算法的有效性.%Depth intensive study is a combination of deep learning perceived ability and enhanced learning decision?making ability which can be controlled by the input. Depth intensive study is an artificial intelligence meth?od which is closer to human thinking. Based on the combination of the two methods, the paper studies a designed framework of resource scheduling algorithm based on depth intensive study. First, the framework utilizes a large number of priori data from the network nodes to train depth learning network. Then use the enhanced learning to al?locate network resources, Next realize the value of network learning
based on deep reinforcement learning through a lot of self?chess. Finally, the performance of the algorithm is simulated and compared, and the results confirm the effectiveness of the algorithm.
【期刊名称】《西北工业大学学报》
【年(卷),期】2017(035)006
【总页数】7页(P1047-1053)
【关键词】深度学习;调度算法;蒙特卡洛模拟;强化学习
【作 者】邓志龙;张琦玮;曹皓;谷志阳
【作者单位】西北工业大学 电子信息学院,陕西 西安 710072;西北工业大学 自动化学院,陕西 西安 710072;西北工业大学 自动化学院,陕西 西安 710072;西北工业大学 自动化学院,陕西 西安 710072
【正文语种】中 文
【中图分类】TP391.4
云计算的优势之一,在于弹性计算和资源的高效整合利用[1]。通过虚拟化技术,可将原有的物理主机的资源划分为不同的虚拟机资源,以实现资源的按需分配和使用[2-5]。但是,在实际的云环境下,由于传统的资源分配机制不能完全适应云资源动态变化和不确定等特性,容易引发负载不均衡,从而对云环境下的服务性能和资源利用效率产生影响。为了进一步改善云资源的使用性能,需要对云资源进行动态优化。解决资源分配的这类问题,通常用启发式算法。然而传统启发式算法自身的局限性,不能解决大型、复杂、动态的资源分配问题[6]。传统的启发式算法由于自身的局限性,不能圆满解决大型、复杂、动态的资源分配问题[7]。本文旨在结合云计算资源分配的实际情况,且充分考虑到云计算环境下的任务处理时间、网络带宽和网络时延等约束,设计了一种基于深度学习和强化学习的智能资源调度算法。可以验证该算法能够有效解决分布式环境下,动态资源分配问题。
如图1所示,基于深度强化学习算法设计的核心思想是,将深度学习和强化学习2种启发式算法在恰当的时机融合,汲取各自的优点,克服固有的缺陷,取长补短,在时间效率和求解精度上共同达到最优。其具体的工作原理如下:
1) 首先在分布式环境下,对各分支节点采集流量数据作为训练样本;
2) 根据样本的规模及实时性要求,确定深度学习网络的隐藏层数量及其节点数量,并初始化网络参数;
3) 用深度学习方法对数据流量进行拟合,并对拟合结果偏差进行分析;
4) 如果拟合偏差较大,说明现在的训练属于欠拟合状态,需要扩大训练次数,并转向第3)步;
5) 再次采集各个节点数据作为测试样本,并运用现有的神经网络对数据进行预测和方差分析;
6) 如果拟合方差较大,说明现在样本处于过拟合状态,需要对深度学习网络进行正则化处理,处理完成后转向第2)步;
7) 根据训练好的深度学习网络,设置相应的超参数;
8) 由于在分布式环境下,数据流量峰值较高,且流量具有动态性的特点。因此,运用蒙特卡罗模拟,来对抽样数据最大流方向进行预测,并给出预测结果;
9) 根据蒙特卡罗给出的预测结果,设置强化学习的回报函数;
10) 运用强化学习策略,对网络资源进行分配,并给出分配结果。
沿用单隐层前馈神经网络的分析,当隐藏的层数超过2层时,称为深度前馈神经网络,其网络结构如图2所示。
设输入x∈Rm,输出y∈Rs,则隐层的输出可记为:
对应的超参数为:
于是,得到输入、输出关系为:
对于训练集:
所得到的优化目标函数为:
式中，yn=f(xn,θ),且:
欲对优化目标函数公式(5)求解,需要确定目标函数的凸性,如果可行域是凸集,定义在该凸集上的凸函数为凸优化,由此可以得到全局最优解。但是,在实际问题中,深度前馈神经网络的优化
目标函数并非凸函数,于是参数的求解依赖于初始参数的选择,需要进行反复迭代。通常,可用梯度下降算法来更新参数,具体描述如下。
式中,α为学习速率,对于每一层上的参数,按下式进行更新:
式中为第l层第k次迭代的更新。对于核心梯度下降量的求解,可引入误差传播项,根据链式法则,将其展开为:
式中,传播误差项标记为:
本文采用蒙特卡罗模拟方法来降低数据的复杂度。蒙特卡罗模拟法是工程应用中的一种数学计算方法,主要用来解决降低数据复杂度问题。其基本原理是根据随机变量样本空间的概率分布,通过模拟实验的手段,计算样本某一事件发生的概率,或者样本某一事件属性的平均值,并以此作为所求事件发生的概率估计或随机变量期望的估计,能以较低的计算代价,枚举出概率值更高、更符合数据观察结论的结果。其计算公式为:
根据上面的公式进行求解,在f(x)中选取一系列独立同分布的样本x1,x2,…,xn,就可以得到
Ep(x)(f(x))=f(x)p(x)dx
同样也可以得出是无偏的。这里,f(x)服从密度为p(x)的概率分布,为了计算f(x)的数学期望,根据大数定律,只需要产生p(x)分布的随机数即可。
对J做相应的变化,即
J=f(x)p(x)q(x)dx=
f(x)q(x)dx=
我们同样在q(x)中抽取x1,x2,…,xn。令w(x)=,可以得出
产生带权值的样本。
在前面的分析中,我们对J做了相应的改进,目的是为了计算随机变量的数学期望。若注意到Eq(x)[w(x)]=1,则可将公式(13)、(14)分别改写为
和
f(x1)+f(x2)+…+f(xn)
实际上,就相当于对样本进行重新赋予权值。即利用非均匀的离散分布来近似概率密度函数f(x),再进行抽样及均匀化。归一化,从而可视为离散的均匀分布。于是,便产生了带权重的样本,其方差可以通过选择适当的q(x)来降低。
下面我们通过蒙特卡罗方法进行随机模拟来实现递归的贝叶斯估计。为此利用一系列通过抽样得到的随机样本,对它们所表示的后验概率密度函数进行加权，得到状态的估计值。这里,采用序贯重要性抽样来完成递归模式,以取得递归后的状态估计值。
根据Bayesian原理,现设系统模型为p(xk|xk-1)和p(x0k|xk),它们分别代表系统中2个方程的模型。同时,再做以下假设:
1) 系统状态符合隐马尔可夫过程;
2) 系统所得量测值之间是相互独立的;
3) 系统状态的先验概率密度函数可设为p(x0)。
根据蒙特卡罗方法,这里的后验概率密度函数的表达式为:
对于非线性系统来说,最理想的情况是样本都能从得到的。然而,要在贝叶斯估计中发现解析解和系统状态难度很大。不过由于每个样本点所对应的权值并不需要具体的数值,只需在一定的比例下,求得其值的大小即可,这就使得后验概率密度函数可以得到相应的近似。
正则化是结构风险最小化策略的实现引入相对容易进行抽样的概率密度函数通过重要性抽样可得到一系列样本它们应满足:
为了能够实现递归估计,现在假设重要性概率密度函数的分解式为:
实际上就是通过q(x0)和来构造
再假设给定的系统符合隐马尔科夫过程,又可得出:
于是要获得的样本集合便可通过将新测量值zk加入得到
我们先从第k-1层所得的概率密度函数中提取一系列的随机样本当样本很多时,概率密度函数可以表示为:
由贝叶斯估计可知,第k时刻状态对应的概率密度函数可以表示为:
即重要性密度函数可以满足:
并有则可得到校正的后验概率密度函数为:
式中
这里的权值都要经过归一化处理。在实施序贯重要性抽样时,应注意权值的变化,所产生的随机样本也应根据权值的变化进行选取,以使抽出的各个样本的权重值不会随着递归的过程,逐渐趋近于同一个样本。
强化学习是受生物能够有效适应环境的启发,以试错的机制与环境进行交互,通过最大化积累奖赏的方式,来学习最优策略。其目的是解决计算机从感知到决策的控制问题,从而实现通用人工智能。
将Q学习和深度学习相结合,可以解决高维数据的输入问题。对于基于分布式的网络资源分配问题,可将其拆分为一系列的步骤(最后一步为输出结果)。其中,每一步都包括竞技双方根据当前自己的观测所做的行动或行为,同时期望该行为带来累积奖赏(即该行为及以前行为的奖赏之和),即对方为自己最终获胜增添筹码。如果用数学分式来量化这一过程需要给出必要的假设:资源分配问题中每一步所对应的观测,可执行的行动或行为是有限的;不可能仅靠当前这一步的观察来执行某一行为,需要充分结合该布置前的观测行为来采取行动。
为了描述方便,引入下列记号:
1) 符号xt∈Rm×n为游戏进行到第t(t=1,2,…,T)步时,所对应的观测。
2) 符号at∈Λ为观测xt下所执行的动作,其中Λ为游戏规则下合理行动集合。
3) 符号rt为观测xt下执行动作at后,所获取的奖赏(或惩罚),另外:
式中，γ∈(0,1)为折扣因子,Rt为第t步到终止时刻T,所获取的累积奖赏和。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。