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

发布时间：2022-06-15 发布人：admin 分类：说明书资料大小：4.79M 资料格式：doc 举报版权申诉

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第1页.png

第1页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第2页.png

第2页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第3页.png

第3页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第4页.png

第4页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第5页.png

第5页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第6页.png

第6页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第7页.png

第7页 / 共60页

281c2b1e-a6a2-486a-8e6d-bc421eee4e5a.doc.pdf-第8页.png

第8页 / 共60页

摘要

Abstract

第一章绪论

1.1排课系统研究背景

1.2排课系统国内外现状

1.3排课常用算法比较

1.3.1贪心算法

1.3.2回溯算法

1.3.3遗传算法

1.4遗传算法国内外现状

1.5研究目标及内容

1.5.1研究目标

1.5.2研究内容

1.5.3研究意义

第二章相关技术基础

2.1 MyEclipse Enterprise Workbench 介绍

2.2.1 Eclipse开发环境

2.2.2 Eclipse的主要特点

2.2 SQL Server 2005

第三章系统分析与初步设计

3.1系统分析的工作步骤

3.2问题提出即需求提出

3.3系统的可行性分析

3.4系统功能目标

3.5系统总体结构设计

第四章数据库设计

4.1数据库设计原则

4.2数据库E-R图

4.3数据库物理结构设计

4.3.1特殊教室信息表 ClassRoomTb

4.3.2课程信息表 CourseTb

4.3.3教师信息表 TeacherTb

4.3.4班级信息表 ClassTb

4.3.5学期课程计划表 TermPlan

4.3.6班级课程信息表 ClCo

4.3.7学期信息表 Term

4.3.8课表信息表 CourseInfoTb

第五章自动排课系统的设计与实现

5.1登陆模块设计

5.2网站布局设计

5.3基础信息管理模块设计

5.3.1特殊教室管理模块实现

5.3.2课程信息管理模块实现

5.3.3教师信息管理模块实现

5.3.4班级信息管理模块实现

5.4排课设置管理模块设计

5.4.1学期课程计划管理模块实现

5.4.2班级课程及任课教师管理模块实现

5.5基于遗传算法的自动排课设计

5.5.1排课问题的分析

5.5.2排课约束

5.5.3排课问题的数学分析

5.5.4算法设计-编码及初始种群

5.5.5算法设计-确定适应度

5.5.5.1课程离散度期望值

5.5.5.2特殊课程期望值

5.5.5.3理论课程期望值

5.5.5.4冲突的检测与消除

5.5.5.6选择运算和变异运算

5.5.6排课处理流程图

5.5.7自动排课窗口的界面设计

5.6排课管理模块设计

5.6.1手工排课及课表调整模块设计

5.6.2教师及班级课表打印模块设计

第六章全文总结

感想及致谢

参考文献

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

Abstract 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 adopt genetic algorithm. Through Design Implementation the Auto Course Arrangement Management System Base on Genetic Algorithm, researched the application of genetic algorithm in the Course Arrangement Management System. Keywords: Genetic Algorithm Auto Course Arrangement Management Java. II

第一章绪论第一章绪论 1.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 年发表了该课题上的 2

第一章绪论实验性研究成果。成形的系统有大连理工大学 1998 年推出的教学调度系统版本 3.00 和由清华大学计算机与信息管理中心开发的综合教务管理系统 TISER。这些应用界面很友好的排课软件己经可以帮助排课人员大大提高工作效率。这些系统大多数都是模拟手工排课，以“班”为单位，只能在排课过程中辅助工作人员进行排课，并没有一套完善有效的自动排课算法。当人工输入的条件达到一定的限制程度时，软件运行就有可能出现死锁现象，使得系统的实际应用非常困难[19]。后期人工调整的工作量并不比重新排课的工作量小很多。一旦出现了这种现象，就要把所有的数据作废或者打乱重排，之前做的工作都付诸东流。高校的课程、教室、教师等因素都十分复杂，排课所需数据量也十分庞大，所以造成的时间、人力损失也非常巨大。课程表问题又称时间表问题，是一个多因素的优化决策问题，也是组合规划中的典型问题，是 NP 完全的[1]。对于排课问题的解决，研究人员己经使用了各种不同的算法，但由于该问题的复杂性，所求解也只能是较为合理、较为满意的解。随着人工智能的发展，特别是在计算智能领域的拓展，借鉴于生物界进化思想和遗传算法，由于其超强的并行搜索能力，以及在解决优化问题中表现出来的高度鲁棒性，它已经被广泛应用于各个领域。目前，很多研究人员已使用遗传算法来求解排课问题，如文献[20]使用遗传算法优化教室的合理利用，文献[21]的用自适应的遗传算法求解大学课表安排问题，文献[22]的基于遗传算法排课系统的设计与实现等等。这些应用说明，使用遗传算法来解决排课问题，其结果还是令人较为满意的。教学排课问题是学校每个排课人员最头痛的问题。短时间内没有一个方法来达到学校教师满意的结果。其最大的困难是硬件资源的限制。排课人员在硬件资源兼顾的条件下难于短时间内排出教师满意的课表。 “穷举法”可将所有的方式列出然后找出最佳解，但成本太高，时间太长。如一个星期有 n 个时段可排课，有 m 位教师需要参与排课．平均每位教师一个星期要上 i 堂课。其排课的组合数有 nm*i 次。可见穷举法的复杂度有多高。遗传算法是一种通过模拟自然进化过程搜索最优解的方法。本文试图以遗传算法来实现排课问题的最佳解。本课题研究的目的就是实现基于遗传算法的排课系统，并在 VB 下具体实现，满足日常需求。 3

毕业设计论文 1.3 排课常用算法比较 1.3.1 贪心算法贪心法(greedy method)是一种改进了的分级处理方法，逐步构造最优解。它从问题的某一个初始解出发，在一定的标准下做出一系列的贪心选择(选择一旦做出，就不可再更改)，即当前状态下看上去最优的选择．逐步逼近给定的目标．以尽可能快的速度求得更好的解当达到算法中的某一步不能再继续前进时则停止。贪心算法的核心是在所选择的策略中，选一个权值最优的策略作为当前策略。因此贪心算法的好坏主要决定于权值的确定。在排课系统中，贪心算法是从排课问题的某一初始状态出发．依据给出的贪心策略朝最终排好全部课程这个目标前进一步，判断是否可以求出可行解的一个解元素．如果可以则继续依据贪心策略向给定目标前进．求出下一个解元素。直到前进不能再继续时停止。最后由所有得到的解元素组成问题的一个可行解。此时算法结束。贪心算法的缺点在于解的效果比较差．而最大优势在于极低的时间复杂度。能做到某种意义上的局部最优。它具有不可后撤性，可以有后效性．一般情况下不满足最优化原理。并且不适用于解决可行性问题．仅适用于较容易得到可行解的最优性问题。为了尽量减小贪心算法带来的副作用。使得最后得到的解更接近最优解。可以在算法尽可能多的地方使用有效的最优化算法(如动态规划)。贪心算法还可以为搜索算法提供较优的初始界值。 1.3.2 回溯算法回溯算法也叫试探法．它是一种系统地搜索问题的解的方法，可以被认为是一个有过剪枝的 DFS(深度优先搜索)过程。它按优先条件向前搜索，以达到目标，但当搜索到某一步时．发现原先的选择并不优或达不到目标。就退回一步重新选择。而满足回溯条件的某个状态点称之为回溯点。具体到计算机智能排课系统中，选优条件即为排课数学模型中的约束条件群(需求集中的元素特征与资源集中的元素特征相互作用形成的数学关系)若不满足约束条件群，该选择即为不优或达不到目标当遍历该步骤的所有可能仍未满足约束条件群．则该状态满足了回溯条件，该状态点即为回溯点。回溯算法解决排课问题时首先要描述解的形式，定义一个解空间．它包含问 4

第一章绪论题的所有解：其次构造状态空间树，这棵树的每条完整路径都代表了一种解的可能：再次是构造约束函数，通过描述合法解的一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余部分：然后通过深度优先搜索完成回溯。 ①设置初始化的方案(给变量赋初值，读入已知数据等)； ②变换方式去试探。若全部试完则转⑦ ； ③ 判断此法是否成功(通过约束函数)，不成功则转② ； ④ 试探成功则前进一步再试探； ⑤正确方案还未找到则转② ； ⑥ 已找到一种方案则记录并打印； ⑦退回一步(回溯)，若未退到根则转② ； ⑧ 已退到根节点则排课结束或打印无排课结果。回溯法适用于解的组合数相当大但仍然有限的那一类问题。它的一个有重要的特性是在搜索执行的同时产生解空问。在搜索期间的任何时刻．仅保留从开始节点到当前节点的路径。因此．回溯算法的空间需求为一个常数，即从开始节点起最长路径的长度。这个特性非常重要．因为解空间的大小通常是最长路径长度的指数或阶乘。所以如果要存储全部解空间的话。再多的空间也不够用。其缺点是时间复杂度较大．因此在采用时还需要谨慎。最好是和其它的算法结合使用。 1.3.3 遗传算法遗传算法是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它是有美国 Michigan 大学 J.Holland 教授于 1975 年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA 这个名称才逐渐为人所知，J.Hilland 教授所提出的 GA 通常为简单遗传算法（SGA）。遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产 5

毕业设计论文生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小挑选（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。遗传算法是一类可用于复杂系统优化的具有鲁棒性的搜索算法，与传统的优化算法相比，主要有以下特点： 1、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际植本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。 2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。 3、遗传算法使用多个点的搜索信息，具有隐含并行性。 4、遗传算法使用概率搜索技术，而非确定性规则。根据其算法特点，遗传算法非常适合于应用到排课处理中。具体应用方式将在后面设计部分详细说明。 1.4 遗传算法国内外现状进入 90 年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。遗传算法的应用研究已从初期的组合优化求解扩展到了许多更新、更工程化的应用方面。随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习，这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其它智能计算方法相互渗透和结合，这对开拓 21 世纪中新的智能计算技术将具有重要的意义。 6

分享到：

赞收藏

资料库

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

相关推荐

后端

热门标签

最新资料