基于遗传算法的高校排课系统研究

摘? 要 为了保证教学质量，在制定规范的教学计划的同时，排课是教学计划顺利执行的重要环节，随着高校规模的急剧扩大，在有限的教学资源情况下排课问题变得越来越复杂，人工排课不仅工作量大，而且各种因素交联复杂，已不能完善的进行课表的编排工作。因此利用计算机智能排课是高校教务管理的迫切需要。排课是一个组合优化问题，它不仅要多种条件的约束、多种目标的制约，并且在70年代，排课就被证明为一个NP完全问题。 遗传算法是是一类借鉴生物界的进化规律（适者生存，优胜劣汰遗传机制）演化而来的随机化搜索方法。具有良好的并行性和更好的全局寻优能力，是目前能比较有效的解决NP完成的组合优化问题的方法。当今，排课问题影响着高校教务工作的效率，所以越来越多的研究机构和高校开始热衷于排课问题的研究。本文提出了排课问题使用遗传算法的求解求解策略，分别从以下几个方面进行了研究: 首先，本文从完整地讨论了排课问题产生的背景，该问题的影响因素、主要约束该问题的条件、以及求解该问题的难点和目标，之后完整地设计了排课问题的数学模型。接着概括说明遗传算法的结构、功能、特征，并研究其在排课系统中的应用，考虑到遗传算法很快收敛到局部最优而非全局最优解，综合各种排课方案优缺点基础上，设计更为适合的排课方法。设计了遗传算法排课问题的算法，并给出了算法的描述和流程图。 最后，结合排课问题具体数学模型，以Visual C++为主要开发工具，SQL SERVER2000为数据库实现了基于改进型遗传算法的自动排课系统。分析显示该系统达到了预期要求，结果比较满意。 关键词：排课问题；遗传算法；影响因素； v:* {behavior:url(#default#VML);} o:* {behavior:url(#default#VML);} w:* {behavior:url(#default#VML);} .shape {behavior:url(#default#VML);} 排课问题是NP完全问题，目前，许多科学家在多个方面对该问题进行了研究，比如理论、人工智能、模拟退火法、遗传算法应用求解上作了很多研究。 1.2.1排课问题的理论研究 1950年《计算机和智力》这篇论文，在世界范围内引起了关于机器能否思维的争论，并且在长时间内这个争论异常激烈，这篇论文是由英国数学家A.M.图灵发表的。到60年代初期，各个领域开始利用计算机技术来提高工作效率，工业部门、管理部门都引入了计算机，不仅工作效率得到了惊人的提高，而且工作内容准确率大大提高。因此，工作效率低、工作难度大的高校排课工作也自然而然地引起了计算机专家的重视。 国外针对排课问题的研究十分热烈。比如加拿大Montreal大学的Jacques A.Ferland和Charles Fleutent以及Jean Aubin等、印度Vastapur大学管理学院的Arabinda Tripathy [8]。Arabinda Tripathy的工作主要是运用拉格朗日松弛法和分支定界技术进行求解，它要求以“人”为基本单位进行课表的编制共组，这种方法的缺点是当变量的个数比较少时，科目间的冲突就会比较没明显，这些人为制造的因素应予以排除。Jacques A.Ferland等人是把利用分组和分解时间表来解决这个问题的，在时间表问题中，根据教师的数量，教室的实际情况，已经注册的学生人数情况排出一个主时间表。对于比较热门的课程，由于选课人数众多，可以把一个月的时间分成几个时间片段来上，然后把学生分配给某个特定的时间段。采用以上两个因素，并他们关联起来，就可以采用惩罚因子来构造一个函数，从而达到课表合理的目的。A.Tripathy在研究了许多课表的编排问题，并进行总结归纳，然后提出了一种新的方法来解决排课冲突问题，这种方法叫做多重课组的方法，即根据学生选课出现的矛盾情况，将课程比较人们、选择人数众多的课程在一星期多次开设，从而合理的分配学生。为此，他们研制出了一个新的系统来调度和决策支持，该系统名字叫做SAPHIR，系统包含了几个模块，其中比较重要的是交互优化、自动优化、数据处理等。该系统的特点是采用了多重课组来解决排课问题主要矛盾，这与西方的教学管理体制是相关的。 1.2.2排课问题的求解方法 国外从20世纪50年代末就开始展开对排课问题的研究工作。在1963年，当时著名的科学家C.C.Gotlibe发表了一篇论文，叫做《The Construction of Class-Teacher Time-Tables》[1]，该文首先提出了排课问题的数学模型，这个模型标志着科学家开始使用科学的手段来研究和解决排课问题。然而，在实际情况中遇到的困难，以及各种制约因素的交联，使人们对能否合理正确解决排课问题产生了疑问。在1976年，另一名科学家S.Even发表了一篇讨论时间表和多物流的复杂性的论文，他在论文中证明了课表问题是一个NP完全的问题，这也是第一次提出了排课问题是一个NP完全的问题。这个结论等于宣布计算机编排课表无法实现，因为这就是排课问题在实践中遇到困难的根本原因。因为之前的研究表明，科学家还没有找到解决NP完全问题的算法。从此以后，科学家对于排课问题的研究开始注重实际情况中的问题而言，大多会加入自己的经验，而不再把大量的时间花费在理论研讨的轨道。这样的结果导致了80年代的许多排课系统缺乏普适性，往往都是针对特定的环境而言。 S.Even的论证结果提高了排课问题的难度，把该问题的提高到理论的高度进行。之后，人们又开始依据该理论，设计和实验了大量的算法来研究排课问题，但是，实际情况下，影响因素对排课问题的影响特别大，而且由于排课问题是NP完全问题，所以一般情况下，求解的结果都不是最理想的。 Ferland等人[4]和吴金荣[5]在后续的研究中，把排课问题分解为整数规划问题来研究和解决，在一定程度上能实现智能排课，但是由于需要很大的计算量，所以只能适用于小规模的排课，而对于当前规模大的高校，至今还没有一个通用的、可行的算法。此外，何永太[6]和胡顺仁等人[7] 在自己的研究基础上，提出了用图论中的染色问题来求解排课问题，然而图的染色问题本身也是NP完全问题。有许多限制制约条件存在于实际的排课问题中，并且对求解目标等各种因素需要有很多特殊要求，因此，如何处理这些因素也显得特别重要。 在20世纪90年代，一批学者还利用模拟退火法来解决到排课问题 [9][10][11][12]。1983年，Kirkpatrick等人首先提出了[13]模拟退火法(Simulated Annealing)，它是一种随机优化算法，是根据人们从自然界固体退火过程中得到启发，并从中进行一定的抽象。在固体退火方法中，首先是先进行加热，使得粒子能够活跃起来，可以进行无约束的行动，后来，温度越来越低，最后形成了低能态晶格。如果控制温度的下降速率，在晶体的凝结点附近，控制温度下降的速率足够的慢，那么固体物质会形成最低能量的基态。这个过程与优化问题非常的相似。学者们提出的模拟退火算法用来解决优化问题的最基本出发点正是基于一般优化问题与物理中固体物质的退火过程的相似性。在实际情况中，模拟退火法已经应用到了许多实际的优化问题当中，并且取得了良好的效果，但是由于排课问题的复杂性，将模拟退火法应用到排课问题当中还不是特别的顺利，该项课题还处在模型试验阶段，许多问题正在面临彻底的解决。 大概在80年代初期，我国的科学家和学者才开始对排课问题进行研究，主要是针对运用人工智能的方法构建专家系统或者决策支持系统。在1984年，《清华大学学报(自然版)》[16]上发表了林漳希和林尧瑞的论文，该论文描述了对该课题的实验性研究成果。之后，当时的浙江大学、西安交通大学、四川大学等著名院校都相继开展了这方面的研究工作。 当前的一些排课软件都存在多多少少的问题。一方面，国内真正意义上的智能排课软件系统很少，大部分都是计算机排课和人工修正相辅相成，并没有实现真正意义上的自动排课，而且几乎都没有采用自动排课的相关算法。另一方面，在现有的仅仅的几套自动排课系统中，却都产生了很的程度上的不完善，比如由于无法安排合理的教师或者无法指定特定的教室或者授课时间冲突，从而不能正常的排入课表，这样就使得系统几乎没有意义，很难在实际中推广使用，由于困难太多，后期需要进行的人工调整，人为的工作量并不亚于重新排课的工作量的大小。 不过西安交大自行设计开发的排课系统以及清华大学目前正在使用的TISER系统虽然已经在排课问题应用方面很大的提高了排课人员的工作效率，但仍然有些不足之处。这些系统都只是为排课工作起到辅助作用，并没有一套可以有效的自动排课系统，因此这些系统很难真正的达到自动排课的需求，要么排完课后，会出现很多“甩课”问题，后面需要工作人员进行大量的人工调整工作，而往往由于调整一门课程会涉及到很多其它的课程、班级及代课教师，很多时候这些调整工作并不比完全人工排课的工作量小。在这种情况下，迫切需要一套完全适合排课管理应用的软件，以减轻教务人员的工作负担。智能编排的排课系统的设计应用已迫在眉睫。 排课问题实际上是一个模糊数学问题，它被多种因素约束着。目前有许多方法可以在满足各种已知约束条件的情况，仍然找到较优的时空组合问题的的解决方案，例如常见的有优先级算法、最速下降法、专家系统法、爬山法、模拟退火法、梯度法，以及遗传算法等。从生物界遗传进化机制演化而来的遗传算法，由于其在解决优化问题中表现出来的高度鲁棒性，以及超群的并行搜索能力，它己经被广泛应用于各个领域。 遗传算法具有很强的全局搜索能力，它是利用模拟自然界物种进化的规律来寻找最优解。本文所设计的排课算法，就是以遗传算法为基础，并对它进行了多方面的改进和完善，从而可以提高优化搜索的效率，以及避免过早收敛和收敛缓慢等问题。作为一种不确定性的优化方法，它在搜索的时候有着两个主要特性: 1. 并行计算。遗传算法可以在种群空间的许多不同的区域同时进行搜索，因为该算法采用的是基于生物种群的方式进行组织和搜索，并且该算法可以非常及时的交互信息，据科学家的研究表明，这种情况下，该搜索方式具有极高的效率，每次只根据生物种群规模的大小，运行成比例的计算工作量，但是实际上算法运算已进行了大约 ( )次有效的搜索。它的好处就是可以节省时间和提高效率，利用比较少的计算数据量，但是可以获取很大的计算结果，同时获得较大的收益。 2. 智能计算。遗传算法在确定了解决方案之后，根据指定的编码规则、遗传算子、适应值计算函数，算法首先获取繁衍演化过程中获得的信息，然后进行自动的组织搜索。研究表明，低生存概率的生物个体的适应值都比较小，高生存概率的生物个体的适应值都比较大，也就是说优化效果好。遗传算法是具有“潜在学习能力”的自适应搜索技术。 遗传算法的这两个特性，是它区别于其他算法的一个明显的特征，也就是这两个特性，使得遗传算法迅速被各国科学家和学者进行研究，因为组合优化的问题大多都需要遗传算法来进行解决。 1.3本文研究内容 根据以上所述，排课问题是一个涉及多种因素的的优化组合问题，它不仅要保证在课程安排中学生、教师、教室之间能够合理的进行配置，不能产生冲突，合理有效的配置资源。研究表明，排课问题采用具有智能性和并行性的遗传算法，是当今研究成果中比较优质的选择。本文的目标是在对遗传算法研究分析的基础上，对它进行扩展和优化完善，提出一个智能化的解决方案，不仅能够随机生成课表，而且能够较大程度地反映实际排课情况，降低冲突。本论文的主要研究以下几方面内容: 1. 通过排课问题的基本信息，提取出影响排课问题的元素，绘制ERD和类图，之后设计出排课系统的所需要用到的数据库结构。在对排课过程中的每个子模块进行研究之后，提出了一种基于多因素的目标最优的决策协调模型的适应度计算方法，生成可行解，产生可用来迭代进化的初始种群，形成一套多目标协同优化的排课算法。 2. 深入研究排课过程中的常用的影响因素和约束条件，分析排课问题解决的目标和可遇见的难点，利用数学工具把排课问题抽象为一个数学模型，紧接着提出本文求解方案的总体思路和技术路线。 3.根据以上设计的数学模型，以Visual C++为开发工具，设计开发一种改进型遗传算法的自动排课系统，该系统可以应用以有的编码方案以及改进的遗传算子，并且系统符合数学模型的设计要求。 4.对上述的随机生成方案算法和基于该遗传算法设计的排课系统进行测试，对一个实际问题的案例，实验并获取相关的测试数据，并对一些数据进行跟踪分析，从实验的角度论述算法的可行性。 5.根据实际排课数据测试本论文设计的智能性和并行性为基础的遗传算法的排课方案在实际排课问题中的应用可行性，从时间复杂度和排课满意度结果两个方面来进行定量、定性地分析测试结果。 通过以上五个方面的论述，根据实际的测试数据，说明遗传算法有效地解决高校排课中遇到的问题。