一种基于Q学习的任务调度算法的改进研究

《一种基于Q学习的任务调度算法的改进研究》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、5一种基于Q学习的任务调度算法的改进研究一种基于Q学习的任务调度算法的改进研究摘要：本文针对协同工作中的任务调度问题，提出了一种改进的基于模拟退火的Q学习算法。该算法通过引入模拟退火，并结合贪婪策略，以及在状态空间上的筛选判断，显著地提高了收敛速度，缩短了执行时间。最后与其它文献中相关算法的对比分析，验证了本改进算法的有效性。关键词：任务调度Q学习强化学习模拟退火1引言随着产品设计的复杂化和多样化，协同工作已成为设计制造领域中的必由之路。协同工作的开展，不仅加强了企业内部和企业间的交流与合作，更能够充分发挥企业自身的群组优势，从而提高产品的开发效率，增强企业在市场中的竞争力。而在产品

2、生产过程中，任务的规划和分解，子任务间的调度与优化作为协同工作的基础，就显得尤为重要。目前，有效的调度方法与优化技术的研究和应用，已经成为先进生产技术实践的基础和关键，所以对它的研究与应用具有重要的理论和实用价值[1]。任务调度问题已经被证明是一个NP完全问题[2]，不可能在多项式时间内找到问题的最优解。近年出现的一些启发式算法为求解此类NP完全问题提供了新的途径。其中遗传算法以解决大空间、非线性、全局寻优等复杂问题时具有传统方法所不具备的优越性，受到了研究人员的普遍关注[3-5]。但是遗传算法在求解大规模任务调度问题时存在的计算效率偏低、收敛于局部最优解等弊端，也不容忽视，因此有必

3、要寻求更加有效的算法来解决此问题。强化学习作为一种无监督的学习方法，它具有其他机器学习方法无可比拟的优点，它考虑的是在没有外界指导的情况下，智能体通过与不确定的外界环境进行交互，从而获得最优解的学习过程。文献[6]将Q学习应用于动态车间作业调度中，取得了较好的效果。Shah[7]等人在无线传感网络中，提出了一种基于Q学习的分布式自主资源管理框架，并通过仿真与对比试验，证明其比现存的其他方法大大提高了系统效率。文献[7]提出了一种基于多步信息更新值函数的多步Q学习调度算法，并结合实例阐明其解决任务调度问题的有效性，但其在收敛速度上还有待提高。针对此，本文改进了现有的基于Metropol

4、is原则的Q学习算法，并将其应用到协同设计的任务调度上，通过和文献[8]所示实例的对比，表明该算法具有更好的收敛速度和泛化性。2问题定义任务调度问题可以简单的描述为，由设计任务分解出的N个子任务要在M个处理机上加工，每个子任务要在某个处理机上连续加工一段时间，调度就是将各个子任务恰当的分配给处理机，使给定的目标得到最优解。下面，我们给出任务分配和调度问题的一般性定义：(1)n个子任务的集合T={T1,T2，…，Tn}，Ti为第i个子任务；(2)m个处理机的集合P={P1,P2，…，Pm}，Pi为第i个处理机；(3)一个m×n的矩阵Cm×n，Ci,j为子任务Ti在处理机Pj上的平均运行

5、时间；图1任务前驱图(4)一个任务约束关系图，由任务前驱图[10]来表示各个子任务间的时序约束关系，如图1是7个子任务的约束关系图．对于一个任务前驱图TPG，TPG=(T，L)5一种基于Q学习的任务调度算法的改进研究，其中T为子任务集，一个子任务Ti，就是图TPG中的一个节点；L是任务前驱图中的有向边集，它表示任务之间的直接驱动关系，（Ti，Tj）∈L即子任务Tj必须在子任务Ti完成之后才能执行，Ti为Tj的一个前趋，Tj为Ti的一个后驱。(4)子任务节点Ti的深度值，其中，表示的前驱节点集合，。(5)一个任务匹配矩阵TPm×n={dij

6、1≤i≤m，1≤j≤n}，若dij=1表示

7、任务Tj分配给了处理机Pi，反之dij=0。称TPm×n为一个调度策略记为s，如果满足：1)，该约束条件的意义是每个处理机至少分配一个任务，并且一个任务同时只能调度给一台处理机。2)调度在同一台处理机中的所有任务是按深度值升序排列的。(6)一个调度策略s的执行时间，其中为调度策略s中处理机Pi上最后一个任务完成的时间，t0为开始时间。现在的目标就是，寻找一个分配调度策略s，将n个子任务指派到m个处理机上，合理调度各个子任务的执行顺序，使得各个任务在满足任务前驱图TPG的约束下，整个大任务的完成时间t(s)最短．3算法描述Q学习的基本思想是根据动态规划原理，用即时回报和下一个状态的估计

8、值来更新当前状态—动作对的值函数，从估计的值函数中得到最优策略[11]。与Q学习收敛速率紧密相关的因素有：(1)状态空间；(2)动作选择；因此，要想提高Q学习的收敛速率，就需要使问题的状态空间尽可能地小，也即缩小可行解空间；以及寻找合适的动作选择策略，使得Q学习在探索和利用之间达到平衡，既避免一味的贪心利用陷入局部最优，又防止过多的探索降低学习算法的性能[12]。针对以上两点，本文提出了一种改进的基于Metropolis的Q学习，下面给出此算法描述：Ste