《毕业设计基于遗传算法的自动排课系统设计.doc》由会员分享，可在线阅读，更多相关《毕业设计基于遗传算法的自动排课系统设计.doc（23页珍藏版）》请在三一办公上搜索。
1、摘 要随着科学技术和社会信息技术的不断提高，计算机科学的日渐成熟，其强大的功能已为人们深刻认识，它在人类社会的各个领域发挥着越来越重要的作用，给人们的生活带来了极大的便利，成为推动社会发展的首要技术动力。排课是学校教学管理中十分重要、又相当复杂的工作之一。解决好教学工作中的排课问题对整个教学计划的进行，有着十分重要的意义。首先对排课的已有算法作了相关的调查研究，决定采用遗传算法。通过设计实现基于遗传算法的自动排课系统，研究了遗传算法在排课系统中的应用。关键词：遗传算法、自动排课、Java。 AbstractAlong with science technical and community i
2、nformation 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 i
3、s 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 adopt genetic algorithm. Through Design Implementation the Auto Course Arrangement Management System Base on Geneti
4、c Algorithm, researched the application of genetic algorithm in the Course Arrangement Management System.Keywords: Genetic Algorithm Auto Course Arrangement Management Java.第一章 绪论1.1排课系统研究背景排课是学校教学管理中十分重要、又相当复杂的管理工作之一，其实质就是为学校所设置的课程安排时间和地点，从而使整个教学能够有计划有秩序的进行。迄今为止，对课程表的研究工作已经进行了长达四十多年之久，取得了丰硕的成果。但是，仍
5、然存在许多不足之处，例如规模大、约束(条件)复杂以及规律不断变化等，因此课程表问题至今仍未完全解决。课程表的编排是一个涉及多种因素的组合规划问题，它要保证在课程安排中教师、学生、教室不能产生冲突(所谓冲突，就是将需上不同课程的两个或多个班安排在了同一时间、同一教室，或为同一教师在同一时间段安排了多门课程等情况)，并且要满足教师的要求和资源限制等约束条件。目前，国内的大部分学校仍然采用手工排课的方法。手工排课工作的主要手段是“摆牌”，就是在一个画有空课表的版面上将有课名的小牌摆在适当的位置上，边摆边观察，边调整，凭借经验将各门课摆在合理的位置上，最后形成一个有效的课程表。这种办法没有一定的规律，
6、没有理论指导，更没有数据模型，具有很大的盲目性。所以，要为上千名学生和上百名教师安排出合理的课程表，往往需要花费教务处人员很多的时间，工作量大，排出的课程表不宜调整。随着中国教育体制改革的不断深入，学生人数的不断上升，课程设置不断向深度和广度发展，手工排课的缺点就越来越突出。由于计算机具有运算速度快、处理能力强等特点，很自然地就进入到这一应用领域中。用计算机进行排课能够快速地得到满足约束条件的可行结果，具有排课时间短、省人力和质量高的优点，不但能使教务人员从繁杂的排课任务中解脱出来，而且对于推动教学的发展也起到非常重要的作用。每个学期开学时，教务管理工作中的课程表安排问题，都是教务处面临的一项
7、艰巨任务。排课问题是一个非常棘手却又亟待解决的问题，通常都是使用传统的人工手动排课方法。手工排课不仅劳动强度大，而且排课效率低，很难排出一个让人满意的课程表。时间，教师，教室，班级，课程等限制问题更是难以解决，使用计算机进行自动排课已经成为近年来的热点话题。教学管理的信息化需要计算机辅助排课，而排课理论的研究和软件技术的成熟己为我们提供了计算机自动排课的重要手段，研究一种准确、高效、实用、自动化程度高的排课系统己经成为可能。1.2排课系统国内外现状排课问题是NP完全问题，许多学者分别在理论、启发式搜索技术应用求解、专家系统应用求解和遗传算法应用求解上作了很多研究。国外从20世纪50年代末就对排
8、课问题展开了研究。1963年Gotlieb在他的文章中提出了排课问题的数学模型2，它标志着排课问题的研究正式跨越了科学的殿堂。之后，人们对排课问题的算法做了许多探索，但由于排课问题是NP完全问题，并且易受实际问题边界的影响，大多数求解结果都不够理想。Ferland3等人和吴金荣4把排课问题化成整数规划来解决，但计算量很大，其仅仅适用于规模很小的课表编排，对于大规模复杂的排课情况，至今没有一个切实可行的算法;何永太5和胡顺仁6等人试图用图论中的染色问题来求解排课问题，可惜图的染色问题本身也是NP完全问题。由于问题的复杂，许多文章利用启发式函数来解决排课问题，大多数启发方法都是模拟手工排课的过程来
9、实现的。由于实际的排课问题存在各种各样的限制条件与特殊要求，对这些因素处理的好坏就显得尤为重要。进入20世纪90年代，国外对排课问题的研究仍然非常活跃。如印度Vastapur大学管理学院的Arabinda Tripathy、加拿大Montreal大学的Jean Aubin和JacqueSA Ferland以及Charles Fleutent等。Arabinda Tripathy的工作是针对以“人”为单位进行课表编排的。他运用拉格朗日松弛法和分支定界技术求解，这种方法的缺点是为了减少变量的个数，人为造成科目间的冲突。A.Tripathy还研究了研究生课表编排问题，他采用多重课组的方法来处理冲突(
10、即根据学生选课的矛盾情况，将人数多的课程在一星期内开多次)。JacQuesA.Ferland等人则把排课问题分成两个子问题:时间表问题和分组问题。在时间表问题中，根据学生注册情况、教师和教室的可利用情况形成一个主时间表。对于选课人数较多的大课，一个星期要分成几个时间段来上，分组问题就是将学生分给各时间段。两个问题相关联，通过惩罚因子来构造启发函数。他们研制的SAPHIR课程调度决策支持系统分为数据处理、自动优化、交互优化等几个模块。该系统解决矛盾的主要方法也是采用多重课组。在国内，对于排课系统的研发，林漳希和林尧瑞1984年发表了该课题上的实验性研究成果。成形的系统有大连理工大学1998年推出
11、的教学调度系统版本3.00和由清华大学计算机与信息管理中心开发的综合教务管理系统TISER。这些应用界面很友好的排课软件己经可以帮助排课人员大大提高工作效率。这些系统大多数都是模拟手工排课，以“班”为单位，只能在排课过程中辅助工作人员进行排课，并没有一套完善有效的自动排课算法。当人工输入的条件达到一定的限制程度时，软件运行就有可能出现死锁现象，使得系统的实际应用非常困难19。后期人工调整的工作量并不比重新排课的工作量小很多。一旦出现了这种现象，就要把所有的数据作废或者打乱重排，之前做的工作都付诸东流。高校的课程、教室、教师等因素都十分复杂，排课所需数据量也十分庞大，所以造成的时间、人力损失也非
12、常巨大。课程表问题又称时间表问题，是一个多因素的优化决策问题，也是组合规划中的典型问题，是NP完全的1。对于排课问题的解决，研究人员己经使用了各种不同的算法，但由于该问题的复杂性，所求解也只能是较为合理、较为满意的解。随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进化思想和遗传算法，由于其超强的并行搜索能力，以及在解决优化问题中表现出来的高度鲁棒性，它已经被广泛应用于各个领域。目前，很多研究人员已使用遗传算法来求解排课问题，如文献20使用遗传算法优化教室的合理利用，文献21的用自适应的遗传算法求解大学课表安排问题，文献22的基于遗传算法排课系统的设计与实现等等。这些应用说明，使用
13、遗传算法来解决排课问题，其结果还是令人较为满意的。教学排课问题是学校每个排课人员最头痛的问题。短时间内没有一个方法来达到学校教师满意的结果。其最大的困难是硬件资源的限制。排课人员在硬件资源兼顾的条件下难于短时间内排出教师满意的课表。“穷举法”可将所有的方式列出然后找出最佳解，但成本太高，时间太长。如一个星期有n个时段可排课，有m位教师需要参与排课平均每位教师一个星期要上i堂课。其排课的组合数有nm*i次。可见穷举法的复杂度有多高。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。本文试图以遗传算法来实现排课问题的最佳解。本课题研究的目的就是实现基于遗传算法的排课系统，并在VB下具体实现，满足
14、日常需求。1.3排课常用算法比较1.3.1贪心算法贪心法(greedy method)是一种改进了的分级处理方法，逐步构造最优解。它从问题的某一个初始解出发，在一定的标准下做出一系列的贪心选择(选择一旦做出，就不可再更改)，即当前状态下看上去最优的选择逐步逼近给定的目标以尽可能快的速度求得更好的解 当达到算法中的某一步不能再继续前进时则停止。贪心算法的核心是在所选择的策略中，选一个权值最优的策略作为当前策略。因此贪心算法的好坏主要决定于权值的确定。在排课系统中，贪心算法是从排课问题的某一初始状态出发依据给出的贪心策略朝最终排好全部课程这个目标前进一步，判断是否可以求出可行解的一个解元素如果可以
15、则继续依据贪心策略向给定目标前进求出下一个解元素。直到前进不能再继续时停止。最后由所有得到的解元素组成问题的一个可行解。此时算法结束。贪心算法的缺点在于解的效果比较差而最大优势在于极低的时间复杂度。能做到某种意义上的局部最优。它具有不可后撤性，可以有后效性一般情况下不满足最优化原理。并且不适用于解决可行性问题仅适用于较容易得到可行解的最优性问题。为了尽量减小贪心算法带来的副作用。使得最后得到的解更接近最优解。可以在算法尽可能多的地方使用有效的最优化算法(如动态规划)。贪心算法还可以为搜索算法提供较优的初始界值。1.3.2回溯算法回溯算法也叫试探法它是一种系统地搜索问题的解的方法，可以被认为是一
16、个有过剪枝的DFS(深度优先搜索)过程。它按优先条件向前搜索，以达到目标，但当搜索到某一步时发现原先的选择并不优或达不到目标。就退回一步重新选择。而满足回溯条件的某个状态点称之为回溯点。具体到计算机智能排课系统中，选优条件即为排课数学模型中的约束条件群(需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系)若不满足约束条件群，该选择即为不优或达不到目标 当遍历该步骤的所有可能仍未满足约束条件群则该状态满足了回溯条件，该状态点即为回溯点。回溯算法解决排课问题时首先要描述解的形式，定义一个解空间它包含问题的所有解：其次构造状态空间树，这棵树的每条完整路径都代表了一种解的可能：再次是构造约束
17、函数，通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分：然后通过深度优先搜索完成回溯。设置初始化的方案(给变量赋初值，读入已知数据等)；变换方式去试探。若全部试完则转 ； 判断此法是否成功(通过约束函数)，不成功则转 ； 试探成功则前进一步再试探；正确方案还未找到则转 ； 已找到一种方案则记录并打印；退回一步(回溯)，若未退到根则转 ； 已退到根节点则排课结束或打印无排课结果。回溯法适用于解的组合数相当大但仍然有限的那一类问题。它的一个有重要的特性是在搜索执行的同时产生解空问。在搜索期间的任何时刻仅保留从开始节点到当前节点的路径。因此回溯算法的空间需求为一个
18、常数，即从开始节点起最长路径的长度。这个特性非常重要因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话。再多的空间也不够用。其缺点是时间复杂度较大因此在采用时还需要谨慎。最好是和其它的算法结合使用。1.3.3遗传算法遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著Adaptation in Natural and Artificial Systems，GA这个名称才逐渐为人所知，J.Hilland教授所提出的
19、GA通常为简单遗传算法（SGA）。 遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，
20、逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点：1、 遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决
21、策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。2、 遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。3、 遗传算法使用多个点的搜索信息，具有隐含并行性。4、 遗传算法使用概率搜索技术，而非确定性规则。根据其算法特点，遗传算法非常适合于应用到排课处理中。具体应用方式将在后面设计部分详细说明。1.4遗传算法国内外现状进入90年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域
22、扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能
23、计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用，五是遗传算法和进化规划（Evolution Programming,EP）以及进化策略（Evolution Strategy,ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独
24、立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，即同遗传算法具有相同之处，也有各自的特点。目前，这三者之间的比较研究和彼此结合的探讨正形成热点。1991年D.Whitey在他的论文中提出了基于领域交叉的交叉算子（Adjacency based crossover），这个算子是特别针对用序号表示基因的个体的交叉，并将其应用到了TSP问题中，通过实验对其进行了验证。D.H.Ackley等提出了随即迭代遗传爬山法（Stochastic Iterated Genetic Hill-climbing，SIGH）采用了一种复杂的概率选举机制，此机制中由m个“投票者”来共同决定新
25、个体的值（m表示群体的大小）。实验结果表明，SIGH与单点交叉、均匀交叉的神经遗传算法相比，所测试的六个函数中有四个表现出更好的性能，而且总体来讲，SIGH比现存的许多算法在求解速度方面更有竞争力。H.Bersini和G.Seront将遗传算法与单一方法（simplex method）结合起来，形成了一种叫单一操作的多亲交叉算子（simplex crossover），该算子在根据两个母体以及一个额外的个体产生新个体，事实上他的交叉结果与对三个个体用选举交叉产生的结果一致。同时，文献还将三者交叉算子与点交叉、均匀交叉做了比较，结果表明，三者交叉算子比其余两个有更好的性能。国内也有不少的专家和学者
26、对遗传算法的交叉算子进行改进。2002年，戴晓明等应用多种群遗传并行进化的思想，对不同种群基于不同的遗传策略，如变异概率，不同的变异算子等来搜索变量空间，并利用种群间迁移算子来进行遗传信息交流，以解决经典遗传算法的收敛到局部最优值问题。2004年，赵宏立等针对简单遗传算法在较大规模组合优化问题上搜索效率不高的现象，提出了一种用基因块编码的并行遗传算法（Building-block Coded Parallel GA，BCPGA）。该方法以粗粒度并行遗传算法为基本框架，在染色体群体中识别出可能的基因块，然后用基因块作为新的基因单位对染色体重新编码，产生长度较短的染色体，在用重新编码的染色体群体作
27、为下一轮以相同方式演化的初始群体。2005年，江雷等针对并行遗传算法求解TSP问题,探讨了使用弹性策略来维持群体的多样性,使得算法跨过局部收敛的障碍,向全局最优解方向进化。1.5研究目标及内容1.5.1研究目标对遗传算法进行研究，进而将其应用到排课系统中，利用计算机来模拟手工排课工作，可以抽象问题中的各个要素，数学表达各种约束条件，并根据课表的组织形式和普遍存在的规律，缩减了问题空间的搜索范围，有效组织了排课知识，使其在一定程度上呈现智能化。1.5.2研究内容学校排课问题本质上是时间表问题的一类典型应用实例，是为了解决课程安排对时间和空间资源的有效利用并避免相互冲突。在排课过程中需要考虑课程教
28、学效果、满足教师特殊要求等多项优化指标，将各门课程安排到相应的时间和教室。1）排课问题具体研究的内容如下：（1）遗传算法的理论（2）排课问题的建模（3）遗传算法在自动排课中的应用方法（4）排课算法的实现2）排课问题具体研究的重点和难点如下：（1）深入理解遗传算法理论。（2）排课问题的建模，包括排课问题的要素以及排课过程的约束条件等。（3）遗传算法在排课问题中的应用方法，包括基因编码、初始种群的产生、适应度函数、控制参数的设定等。（4）排课问题本身的求解规模过于庞大，各要素之间的关联层出不穷，以及人们对多个课表优劣评定的准则存在差异，在求解排课问题的过程中，会面对难以穷尽的组合和多个模糊目标的优
29、化问题，实际解决时会受到一些制约。3）排课问题具体研究方法如下：采用循序渐进的方法进行研究，首先必须要学习遗传算法，在学习的基础上进行深入研究，对现行的遗传算法进行一些改进，然后对排课问题进行建模，分析排课问题的要素和约束条件。最后将遗传算法应用到排课系统中，提出一种具体的应用方法并实现排课算法。研究过程中要借助于大量的文献资料，必须要先学习理论，在理论的基础上再进行实践。4）排课问题具体研究步骤如下：（1）大量阅读关于遗传算法的相关文献，理解算法原理。（2）研究排课问题，对排课问题进行建模。（3）对遗传算法进行一些改进。（4）提出遗传算法在自动排课中的应用方法。（5）进行系统的概要设计和详细
30、设计。（6）编码实现排课算法。（7）对系统进行测试和运行。（8）对系统进行回归测试和功能完善。5）排课问题研究用到的工具与框架如下：（1）MyEclipse6.0；（2）开发的环境：JDK1.5；（3）UML建模工具：PowerDesigner12.5；（4）MS SQL Server 2000；1.5.3研究意义排课系统是教学管理系统中的一项重要内容，排课结果的优劣直接影响到学校的正常教学秩序，甚至影响教学质量。排课管理的主要任务是把全校各年级所开设的课程进行汇总，然后根据教学计划和教学资源制订全校各班级的课程表，优化配置各种教学资源，使教学工作科学、高效顺利的进行。研究的意义就在于设计一个
31、好的智能排课系统，从而减轻了教学管理工作者的劳动强度，提高了工作效率，规范了教学管理工作流程。第二章 相关技术基础本章介绍开发中用到的相关技术。2.1 MyEclipse Enterprise Workbench 介绍MyEclipse企业级工作平台（MyEclipse Enterprise Workbench ，简称MyEclipse）是对Eclipse IDE的扩展，利用它我们可以在数据库和JavaEE的开发、发布，以及应用程序服务器的整合方面极大的提高工作效率。它是功能丰富的JavaEE集成开发环境，包括了完备的编码、调试、测试和发布功能，完整支持HTML, Struts, JSF, C
32、SS, JavaScript, SQL, Hibernate。Eclipse是著名的跨平台的自由集成开发环境（IDE）。最初主要用来Java语言开发，但是目前亦有人通过插件使其作为其他计算机语言比如C+和Python的开发工具。Eclipse的本身只是一个框架平台，但是众多插件的支持使得Eclipse拥有其他功能相对固定的IDE软件很难具有的灵活性。许多软件开发商以Eclipse为框架开发自己的IDE。Eclipse 最初由OTI和IBM两家公司的IDE产品开发组创建，起始于1999年4月。IBM提供了最初的Eclipse代码基础，包括Platform、JDT 和PDE。目前由IBM牵头，围绕
33、着Eclipse项目已经发展成为了一个庞大的Eclipse联盟，有150多家软件公司参与到Eclipse项目中，其中包括Borland、Rational Software、Red Hat及Sybase等。Eclipse是一个开发源码项目，它其实是 Visual Age for Java的替代品，其界面跟先前的Visual Age for Java差不多，但由于其开放源码，任何人都可以免费得到，并可以在此基础上开发各自的插件，因此越来越受人们关注。近期还有包括Oracle在内的许多大公司也纷纷加入了该项目，并宣称Eclipse将来能成为可进行任何语言开发的IDE集大成者，使用者只需下载各种语言的插件即可。2.2.1 Eclipse开发环境
