基于遗传算法的自动排课系统毕业设计

摘要

随着科学技术和社会信息技术的不断提高，计算机科学的日渐成熟，其强大的功能已为人们深刻认识，它在人类社会的各个领域发挥着越来越重要的作用，给人们的生活带来了极大的便利，成为推动社会发展的首要技术动力。排课是学校教学管理中十分重要、又相当复杂的工作之一。解决好教学工作中的排课问题对整个教学计划的进行，有着十分重要的意义。首先对排课的已有算法作了相关的调查研究，决定采用遗传算法。通过设计实现基于遗传算法的自动排课系统，研究了遗传算法在排课系统中的应用。

关键词：遗传算法、自动排课、Java。

Abstract

Along with science technical and community information technical increases continuously, calculator science is gradually mature, its mighty function has behaved deep cognition, and it has entered the human social each realm erupts to flick the more and more important function, bringing our life biggest of convenience. Curriculum arrangement is an important and complicated working in school,so solving the problem is of great importance for teaching programming.Investigated and studied the algorithm existed, determine that adoptgenetic algorithm. ThroughDesign Implementation theAuto CourseArrangementManagement System Base onGenetic Algorithm, researched the application of genetic algorithmin theCourseArrangementManagement System.

Keywords: Genetic Algorithm Auto Course Arrangement ManagementJava.

第一章绪论

1.1排课系统研究背景

排课是学校教学管理中十分重要、又相当复杂的管理工作之一，其实质就是为学校所设置的课程安排时间和地点，从而使整个教学能够有计划有秩序的进行。迄今为止，对课程表的研究工作已经进行了长达四十多年之久，取得了丰硕的成果。但是，仍然存在许多不足之处，例如规模大、约束(条件)复杂以及规律不断变化等，因此课程表问题至今仍未完全解决。课程表的编排是一个涉及多种因素的组合规划问题，它要保证在课程安排中教师、学生、教室不能产生冲突(所谓冲突，就是将需上不同课程的两个或多个班安排在了同一时间、同一教室，或为同一教师在同一时间段安排了多门课程等情况)，并且要满足教师的要求和资源限制等约束条件。

目前，国内的大部分学校仍然采用手工排课的方法。手工排课工作的主要手段是“摆牌”，就是在一个画有空课表的版面上将有课名的小牌摆在适当的位置上，边摆边观察，边调整，凭借经验将各门课摆在合理的位置上，最后形成一个有效的课程表。这种办法没有一定的规律，没有理论指导，更没有数据模型，具有很大的盲目性。所以，要为上千名学生和上百名教师安排出合理的课程表，往往需要花费教务处人员很多的时间，工作量大，排出的课程表不宜调整。

随着中国教育体制改革的不断深入，学生人数的不断上升，课程设置不断向深度和广度发展，手工排课的缺点就越来越突出。由于计算机具有运算速度快、处理能力强等特点，很自然地就进入到这一应用领域中。用计算机进行排课能够快速地得到满足约束条件的可行结果，具有排课时间短、省人力和质量高的优点，不但能使教务人员从繁杂的排课任务中解脱出来，而且对于推动教学的发展也起到非常重要的作用。

每个学期开学时，教务管理工作中的课程表安排问题，都是教务处面临的一项艰巨任务。排课问题是一个非常棘手却又亟待解决的问题，通常都是使用传统的人工手动排课方法。手工排课不仅劳动强度大，而且排课效率低，很难排出一个让人满意的课程表。时间，教师，教室，班级，课程等限制问题更是难以解决，使用计算机进行自动排课已经成为近年来的热点话题。教学管理的信息化需要计算机辅助排课，而排课理论的研究和软件技术的成熟己为我们提供了计算机自动

排课的重要手段，研究一种准确、高效、实用、自动化程度高的排课系统己经成为可能。

1.2排课系统国内外现状

排课问题是NP完全问题，许多学者分别在理论、启发式搜索技术应用求解、专家系统应用求解和遗传算法应用求解上作了很多研究。

国外从20世纪50年代末就对排课问题展开了研究。1963年Gotlieb在他的文章中提出了排课问题的数学模型[2]，它标志着排课问题的研究正式跨越了科学的殿堂。之后，人们对排课问题的算法做了许多探索，但由于排课问题是NP完全问题，并且易受实际问题边界的影响，大多数求解结果都不够理想。Ferland[3]等人和吴金荣[4]把排课问题化成整数规划来解决，但计算量很大，其仅仅适用于规模很小的课表编排，对于大规模复杂的排课情况，至今没有一个切实可行的算法;何永太[5]和胡顺仁[6]等人试图用图论中的染色问题来求解排课问题，可惜图的染色问题本身也是NP完全问题。由于问题的复杂，许多文章利用启发式函数来解决排课问题，大多数启发方法都是模拟手工排课的过程来实现的。由于实际的排课问题存在各种各样的限制条件与特殊要求，对这些因素处理的好坏就显得尤为重要。

进入20世纪90年代，国外对排课问题的研究仍然非常活跃。如印度Vastapur 大学管理学院的Arabinda Tripathy、加拿大Montreal大学的Jean Aubin和JacqueSA Ferland以及Charles Fleutent等。Arabinda Tripathy的工作是针对以“人”为单位进行课表编排的。他运用拉格朗日松弛法和分支定界技术求解，这种方法的缺点是为了减少变量的个数，人为造成科目间的冲突。A.Tripathy还研究了研究生课表编排问题，他采用多重课组的方法来处理冲突(即根据学生选课的矛盾情况，将人数多的课程在一星期内开多次)。JacQuesA.Ferland等人则把排课问题分成两个子问题:时间表问题和分组问题。在时间表问题中，根据学生注册情况、教师和教室的可利用情况形成一个主时间表。对于选课人数较多的大课，一个星期要分成几个时间段来上，分组问题就是将学生分给各时间段。两个问题相关联，通过惩罚因子来构造启发函数。他们研制的SAPHIR课程调度决策支持系统分为数据处理、自动优化、交互优化等几个模块。该系统解决矛盾的主要方法也是采用多重课组。

在国内，对于排课系统的研发，林漳希和林尧瑞1984年发表了该课题上的

实验性研究成果。成形的系统有大连理工大学1998年推出的教学调度系统版本3.00和由清华大学计算机与信息管理中心开发的综合教务管理系统TISER。这些应用界面很友好的排课软件己经可以帮助排课人员大大提高工作效率。这些系统大多数都是模拟手工排课，以“班”为单位，只能在排课过程中辅助工作人员进行排课，并没有一套完善有效的自动排课算法。当人工输入的条件达到一定的限制程度时，软件运行就有可能出现死锁现象，使得系统的实际应用非常困难[19]。后期人工调整的工作量并不比重新排课的工作量小很多。一旦出现了这种现象，就要把所有的数据作废或者打乱重排，之前做的工作都付诸东流。高校的课程、教室、教师等因素都十分复杂，排课所需数据量也十分庞大，所以造成的时间、人力损失也非常巨大。

课程表问题又称时间表问题，是一个多因素的优化决策问题，也是组合规划中的典型问题，是NP完全的[1]。对于排课问题的解决，研究人员己经使用了各种不同的算法，但由于该问题的复杂性，所求解也只能是较为合理、较为满意的解。

随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进化思想和遗传算法，由于其超强的并行搜索能力，以及在解决优化问题中表现出来的高度鲁棒性，它已经被广泛应用于各个领域。目前，很多研究人员已使用遗传算法来求解排课问题，如文献[20]使用遗传算法优化教室的合理利用，文献[21]的用自适应的遗传算法求解大学课表安排问题，文献[22]的基于遗传算法排课系统的设计与实现等等。这些应用说明，使用遗传算法来解决排课问题，其结果还是令人较为满意的。

教学排课问题是学校每个排课人员最头痛的问题。短时间内没有一个方法来达到学校教师满意的结果。其最大的困难是硬件资源的限制。排课人员在硬件资源兼顾的条件下难于短时间内排出教师满意的课表。

“穷举法”可将所有的方式列出然后找出最佳解，但成本太高，时间太长。如一个星期有n个时段可排课，有m位教师需要参与排课．平均每位教师一个星期要上i堂课。其排课的组合数有nm*i次。可见穷举法的复杂度有多高。

遗传算法是一种通过模拟自然进化过程搜索最优解的方法。本文试图以遗传算法来实现排课问题的最佳解。

本课题研究的目的就是实现基于遗传算法的排课系统，并在VB下具体实现，满足日常需求。

1.3排课常用算法比较

1.3.1贪心算法

贪心法(greedy method)是一种改进了的分级处理方法，逐步构造最优解。它从问题的某一个初始解出发，在一定的标准下做出一系列的贪心选择(选择一旦做出，就不可再更改)，即当前状态下看上去最优的选择．逐步逼近给定的目标．以尽可能快的速度求得更好的解当达到算法中的某一步不能再继续前进时则停止。贪心算法的核心是在所选择的策略中，选一个权值最优的策略作为当前策略。因此贪心算法的好坏主要决定于权值的确定。

在排课系统中，贪心算法是从排课问题的某一初始状态出发．依据给出的贪心策略朝最终排好全部课程这个目标前进一步，判断是否可以求出可行解的一个解元素．如果可以则继续依据贪心策略向给定目标前进．求出下一个解元素。直到前进不能再继续时停止。最后由所有得到的解元素组成问题的一个可行解。此时算法结束。

贪心算法的缺点在于解的效果比较差．而最大优势在于极低的时间复杂度。能做到某种意义上的局部最优。它具有不可后撤性，可以有后效性．一般情况下不满足最优化原理。并且不适用于解决可行性问题．仅适用于较容易得到可行解的最优性问题。为了尽量减小贪心算法带来的副作用。使得最后得到的解更接近最优解。可以在算法尽可能多的地方使用有效的最优化算法(如动态规划)。贪心算法还可以为搜索算法提供较优的初始界值。

1.3.2回溯算法

回溯算法也叫试探法．它是一种系统地搜索问题的解的方法，可以被认为是一个有过剪枝的DFS(深度优先搜索)过程。它按优先条件向前搜索，以达到目标，但当搜索到某一步时．发现原先的选择并不优或达不到目标。就退回一步重新选择。而满足回溯条件的某个状态点称之为回溯点。具体到计算机智能排课系统中，选优条件即为排课数学模型中的约束条件群(需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系)若不满足约束条件群，该选择即为不优或达不到目标当遍历该步骤的所有可能仍未满足约束条件群．则该状态满足了回溯条件，该状态点即为回溯点。

回溯算法解决排课问题时首先要描述解的形式，定义一个解空间．它包含问

题的所有解：其次构造状态空间树，这棵树的每条完整路径都代表了一种解的可能：再次是构造约束函数，通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分：然后通过深度优先搜索完成回溯。

①设置初始化的方案(给变量赋初值，读入已知数据等)；

②变换方式去试探。若全部试完则转⑦；

③判断此法是否成功(通过约束函数)，不成功则转②；

④试探成功则前进一步再试探；

⑤正确方案还未找到则转②；

⑥已找到一种方案则记录并打印；

⑦退回一步(回溯)，若未退到根则转②；

⑧已退到根节点则排课结束或打印无排课结果。

回溯法适用于解的组合数相当大但仍然有限的那一类问题。它的一个有重要的特性是在搜索执行的同时产生解空问。在搜索期间的任何时刻．仅保留从开始节点到当前节点的路径。因此．回溯算法的空间需求为一个常数，即从开始节点起最长路径的长度。这个特性非常重要．因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话。再多的空间也不够用。其缺点是时间复杂度较大．因此在采用时还需要谨慎。最好是和其它的算法结合使用。

1.3.3遗传算法

遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Hilland教授所提出的GA通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代