基于分布式势博弈算法排课方法研究.docVIP

基于分布式势博弈算法排课方法研究 　　摘要：排课问题已被证明是NP完全问题，排课问题的难度随课表规模的增大而增加。通过对排课问题建立图形着色模型，采用分布式?莶┺乃惴ㄇ蠼狻７植际绞撇┺乃惴ù泳植孔钣湃胧郑?最终形成全局最优，适用于排课问题求解；同时势博弈算法对排课问题中课表微调问题的响应是高效的。实践表明，相较于遗传算法、模拟退火算法，分布式势博弈算法对解决排课系统问题具有独特优势。 　　关键词：NP完全问题；势博弈；分布式势博弈算法；图形着色 　　DOIDOI：10.11907/rjdk.171696 　　中图分类号：TP319 　　文献标识码：A 文章编号：1672-7800（2017）012-0152-03 　　Abstract：Scheduling Problem has been proved to be an NP-complete problem， the difficulty of scheduling problem increases with increasing size of the curriculum. Through establishing graphics rendering model and applying to scheduling problem， a distributed potential algorithm is introduced. Distributed potential game algorithm starts to solve the problem from local optimum， which eventually forms the global optimum for the Scheduling Problem. At the same time the potential game algorithm is efficient in response to the course arrangement where there is a micro change in timetable. Practice shows that compared to genetic algorithms， simulated annealing algorithm， distributed game algorithm is unique and effective to solve the Scheduling Problem. 　　Key Words：scheduling problem； distributed； potential game； graphics rendering 　　0 引言 　　早在20世纪70年代，排课问题就被证明是NP完全问题[1]。排课问题的复杂度随问题规模的增大而剧烈增加。目前，对于NP完全问题求解主要是通过寻找一些降低计算复杂度的近似算法，没有通用算法，因而诸如动态规划[2]、遗传算法[3]、模拟退火算法[4]等用于近似求解NP完全问题的算法都可以用于解决排课问题。这类算法的共同特征是集中式处理，如果已排好的课表出现了某些变动而需要重排，则算法对这种动态变化响应并不及时。针对上述问题，建立排课问题的图论模型，提出使用多代理系统的分布式博弈算法[5]对课表进行编排。使用多代理系统的分布式博弈学习算法对课表进行编排的优点是：对于已经编排好的课表，如果某一部分课表发生变动，只需进行局部调整便可生成新的课表，效率得到极大提高。 　　1 问题描述 　　影响排课的因素是多方面的，主要是由教师、教室、课程、班级和时间组成的五元组，排课目标是实现这5个元素配置的最优化，使得教学资源得到合理分配及利用。这是一个多约束的组合优化问题，此类问题一般不存在唯一最优解，找到其中一种近似最优解即可。排课问题有两种类型约束。 　　1.1 基本约束条件 　　排课的实质是资源分配，解决排课问题的基本要求是基础教学资源分配在时间、空间上无冲突。将教学资源的 　　分配原则称为约束，对基础教学资源分配的原则称为基础约束。通常情况下，这些基础约束条件是固定的。例如：同一时间，同一教师不能讲授一门以上的课程；同一时间，同一班级不能开展一门以上的课程；同一时间，同一教室不能开展一门以上的课程等。 　　1.2 扩展约束条件 　　排课问题要求基本约束条件必须得到满足，但并非所有约束条件都需要得到满足，称此类约束为扩展约束。扩展约束一般用于保证课程质量，使得课程安排合理、科学。属于扩展约束的条件如下：某课程一周内有几次课应不在一天进行；英语、语文等记忆性课程应放在上午；同一教师的同一课程应尽量安排在同一地点等。 　　2 模型设计 　　2