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

1、5一种基于Q学习的任务调度算法的改进研究一种基于Q学习的任务调度算法的改进研究*基金资助：国家自然科学基金(60673028), 合肥市科研计划项目(2008-1004).作者简介：杜琳(1985-), 女, 河南南阳人, 硕士研究生, 研究方向为计算机图形学与计算机辅助设计; 石慧(1980-), 女, 安徽合肥人, 硕士, 助教, 研究方向为CSCW和CAD; 刘晓平(1964-), 男, 山东济南人, 教授, 博导, 研究方向为建模、仿真和协同计算.杜琳 石慧 刘晓平合肥工业大学计算机与信息学院，安徽合肥 230009摘 要：本文针对协同工作中的任务调度问题，提出了一种改进的基于模拟退火

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

3、技术实践的基础和关键，所以对它的研究与应用具有重要的理论和实用价值1。任务调度问题已经被证明是一个NP完全问题2，不可能在多项式时间内找到问题的最优解。近年出现的一些启发式算法为求解此类NP完全问题提供了新的途径。其中遗传算法以解决大空间、非线性、全局寻优等复杂问题时具有传统方法所不具备的优越性，受到了研究人员的普遍关注3-5。但是遗传算法在求解大规模任务调度问题时存在的计算效率偏低、收敛于局部最优解等弊端，也不容忽视，因此有必要寻求更加有效的算法来解决此问题。强化学习作为一种无监督的学习方法，它具有其他机器学习方法无可比拟的优点，它考虑的是在没有外界指导的情况下，智能体通过与不确定的外界环境

4、进行交互，从而获得最优解的学习过程。文献6将Q学习应用于动态车间作业调度中，取得了较好的效果。Shah7等人在无线传感网络中，提出了一种基于Q学习的分布式自主资源管理框架，并通过仿真与对比试验，证明其比现存的其他方法大大提高了系统效率。文献7提出了一种基于多步信息更新值函数的多步Q学习调度算法，并结合实例阐明其解决任务调度问题的有效性，但其在收敛速度上还有待提高。针对此，本文改进了现有的基于Metropolis原则的Q学习算法，并将其应用到协同设计的任务调度上，通过和文献8所示实例的对比，表明该算法具有更好的收敛速度和泛化性。2 问 题 定 义任务调度问题可以简单的描述为，由设计任务分解出的N

5、个子任务要在M个处理机上加工，每个子任务要在某个处理机上连续加工一段时间，调度就是将各个子任务恰当的分配给处理机，使给定的目标得到最优解。下面，我们给出任务分配和调度问题的一般性定义：(1) n个子任务的集合T=T1, T2，Tn，Ti为第i个子任务；(2) m个处理机的集合P=P1, P2，Pm ，Pi为第i个处理机；(3) 一个m n的矩阵Cmn，C i,j 为子任务Ti在处理机Pj上的平均运行时间；图1 任务前驱图(4) 一个任务约束关系图，由任务前驱图10来表示各个子任务间的时序约束关系，如图1是7个子任务的约束关系图对于一个任务前驱图TPG，TPG=(T，L)，其中T为子任务集，一个

6、子任务Ti ，就是图TPG中的一个节点；L是任务前驱图中的有向边集，它表示任务之间的直接驱动关系，（Ti，Tj）L即子任务 Tj 必须在子任务 Ti 完成之后才能执行，Ti 为 Tj 的一个前趋，Tj 为 Ti 的一个后驱。(5) 子任务节点Ti的深度值 ，其中，表示的前驱节点集合，。(6) 一个任务匹配矩阵TPmn = dij | 1im，1jn ，若dij =1 表示任务Tj 分配给了处理机Pi，反之dij = 0。称TPmn 为一个调度策略记为s，如果满足：1) ，该约束条件的意义是每个处理机至少分配一个任务，并且一个任务同时只能调度给一台处理机。2) 调度在同一台处理机中的所有任务是按

7、深度值升序排列的。(7) 一个调度策略s的执行时间 ，其中为调度策略s中处理机Pi上最后一个任务完成的时间，t0为开始时间。现在的目标就是，寻找一个分配调度策略s，将n个子任务指派到m个处理机上，合理调度各个子任务的执行顺序，使得各个任务在满足任务前驱图TPG的约束下，整个大任务的完成时间t(s)最短3 算 法 描 述 Q学习的基本思想是根据动态规划原理，用即时回报和下一个状态的估计值来更新当前状态动作对的值函数，从估计的值函数中得到最优策略11。与Q学习收敛速率紧密相关的因素有：(1) 状态空间；(2) 动作选择；因此，要想提高Q学习的收敛速率，就需要使问题的状态空间尽可能地小，也即缩小可行

8、解空间；以及寻找合适的动作选择策略，使得Q学习在探索和利用之间达到平衡，既避免一味的贪心利用陷入局部最优，又防止过多的探索降低学习算法的性能12。针对以上两点，本文提出了一种改进的基于Metropolis的Q学习，下面给出此算法描述：Step1：初始化所有，情节数k=0和情节设定值K，以及t；Step2：随机初始化状态S，并使其满足，的原则，步骤数i =1和步骤设定值I;Step3：根据贪婪策略，从动作集A中选取当前状态S的值函数最大的动作ap，若为最大的数量超过2，则随机从对应的几个动作中选取一at作为ap；Step4：从动作集A中随机选取一动作ar；Step5：若，则a=ap；否则，产生0

9、 , 1之间的随机数；如果，则a=ar，反之a=ap。Step6：执行动作a，进入下一状态S，若此S不满足，则返回Step3，反之继续；Step7：由式（1）更新；Step8：，如果步骤数i达到设定值I，返回Step2，并令k=k+1，；若情节数k也达到设定值K，算法结束；否则，返回Step3继续。算法描述中Step3至Step5是Metropolis原则的应用，其中加入了贪婪策略，试图利用已学习到的信息采用当前最优的动作，而随机数的存在，又使得算法不放弃探索，以exp(Q/t)的概率接受新的动作尝试。随着温度t的降低，探索成分将极大减少，最终几乎不存在探索。在探索中，算法采用随机选取相同最大

10、Q值动作的做法，旨在保证每步训练动作完全随机选择，使得结果训练序列无限频繁的访问每个动作状态转换对，确定学习到Q函数，以及最优策略12。Step2和Step6意在缩小状态空间，对于图1所示的7个任务和3个处理机的任务调度问题，总的状态空间为221，但采用了Step2和Step6的限定，状态空间为37-273+3=1806个，不足211，使得状态空间达到了指数级的下降。虽然算法在状态判断中会花费时间，但相比于在KI步循环中更新所有状态空间的Q值时所花费的时间，可忽略不计。4 实验对比与分析为了验证和比较本文算法，我们采用文献8中的调度实例进行试验。该设计任务由7个子任务节点组成，任务之间的约束关

11、系如图1所示；3个处理机，Cmn矩阵如表1所示。表1 子任务i在处理机j上的平均运行时间T1T2T3T4T5T6T7P12314254P24231723P31426122算法中用到的主要参数均采用文献8所用参数：折扣因子，权重参数，学习率，初始温度t=500，K=30。本算法最终收敛于8，也即最好调度策略的执行时间为8。并且找出了所有解，其对应的TPmn为：或表2给出了本算法在取不同步骤时收敛到最优解8的平均执行时间。图2所示的是本文算法与文献8给出的两种Q学习算法的性能比较，从中可以很明显的看出本文的改进Q算法在时间效率和收敛速度上的较大优势（实验在普通PC上运行，CPU2.6GHZ，内存7

12、68M，VC 6.0）。作者猜想算法间如此大的差别可能是状态空间不同，文献8中的两种算法状态空间均为221，这就意味着Q学习几乎要更新221个Q值，并在此庞大的状态空间中不断搜索查询，而本文的算法加入了状态判断，使状态空间缩小到1806个，从而大大减少了搜索时间，也使得算法的执行时间获得了指数性的下降。从图2还可以看出文献8中的两种算法均随着步骤数的增加，收敛速度加快，执行时间变短。这一点在本文的改进Q中也有体现出来，如图3所示，随着步骤数的增大（从200到1000），情节数递减，收敛速度加快，但执行时间并没有相应的变短，原因在于步骤数i =200时，Q学习已经在情节数平均k =25处收敛于最

13、优值。因此，随着步骤数的提高，虽然收敛速度在加速，理论上出现最优解的时间变短，但增大的步骤数所带来的搜索空间变大，各状态Q值更新增多的时间花费淹没了上述改变，所以从整体上看执行时间反而有增加的趋势。 表2 不同步骤收敛到最优解的平均执行时间步骤数5001000150020002500300035004000执行时间(s)1014201616192416图2 本算法与其它算法性能比较图3 不同步骤数算法收敛速度比较5 结 语本文针对协同工作中的任务调度问题，提出了一种改进的基于Metropolis 规则的Q学习算法。该算法通过引入Metropolis 原则，并结合贪婪策略，既考虑了当前最优，又根

14、据温度随机地选取其他解以增加探索的机会，确保了算法能够尽快在全局寻得最优解。为提高Q学习的收敛速度，算法加入了特定状态的筛选，使得状态空间达到了指数级的下降，从而大大加快了收敛速度，缩短了执行时间。最后本文通过和文献8中实例的对比分析，验证了算法的有效性和优越点。由于本文提出的改进Q学习算法属于静态调度算法，因此下一步的研究方向将着重于如何有效解决动态任务调度问题。参 考 文 献1 冷晟, 魏孝斌, 王宁生. 柔性工艺路线蚁群优化单元作业调度J. 机械科学与技术, 2005, 24(11): 1268-1271.2 RongXie, DanielaRus, CliffStein. Schedu

15、ling multi-task agentsC. Proceedings of the 5th International Conference on Mobile Agents, 2001: 260 - 276.3 耿汝年, 须文波. 基于自适应选择遗传算法的任务调度与分配J. 计算机工程, 2008, 34(3): 43-45.4 Deepa, R. Srinivasan, T. Miriam, D.D.H. An Efficient Task Scheduling Technique in Heterogeneous Systems Using Self-Adaptive Selecti

16、on-Based Genetic AlgorithmC. Parallel Computing in Electrical Engineering, 2006: 343-348.5 Loukopoulos, T. Lampsas, P. Sigalas, P. Improved Genetic Algorithms and List Scheduling Techniques for Independent Task Scheduling in Distributed SystemsC. Parallel and Distributed Computing, Applications and

17、Technologies, 2007: 67-74.6 Yingzi Wei, Mingyang Zhao. Composite rules selection using reinforcement learning for dynamic job-shop scheduling RoboticsC. Automation and Mechatronics, 2004 IEEE Conference on, 2004(2): 1083-1088.7 Shah, K. Kumar, M.Distributed Independent Reinforcement Learning(DIRL)Ap

18、proach to Resource Management in Wireless Sensor NetworksC. Mobile Adhoc and Sensor Systems, 2007. MASS 2007. IEEE International Conference on, 2007: 1-9.8 陈圣磊, 吴惠中, 肖亮, 朱耀琴. 系统设计任务调度的多步Q学习算法J. 计算机辅助设计与图形学学报, 2007, 19(3): 398-402。9 Xiaoping Liu, Hui Shi, Qiang Lu, Zhengqiang Mao. Visual Task-driven

19、Based on Task Precedence Graph for Collaborative DesignJ. Computer Supported Cooperative Work in Design, 2007. CSCWD 2007. 11th International Conference on, 2007: 246-251.10 王雪松, 田西兰, 程玉虎, 易建强. 基于协同最小二乘支持向量机的Q 学习J. 自动化学报, 2009, 35(2): 214-219.11 CHRISTOPHER J.C.H. WATKINS. Q-learningJ. Machine Learning, 1992, 8: 279-292.12 Tom M. Mitchell著, 曾华军, 张银奎等译. 机器学习. 北京: 机械工业出版社, 2003.Research on Improvement of Task Scheduling Based on Q-LearningDu Lin Shi Hui Liu Xiao-pingSchool of Computer and Information, Hefei University of Technology, AnHui 230009,ChinaAbstract: In this pape