遗传算法在排课系统中应用和设计探究

《遗传算法在排课系统中应用和设计探究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、遗传算法在排课系统中应用和设计探究　　摘要：为了方便教学管理方面的课程安排，在研究遗传算法的基础上，以软件工程的思想研究了排课系统的设计过程，并使用Java语言实现了基于遗传算法的排课系统。经过测试，该系统能自动完成自动排课和手动调整功能。关键词：遗传算法；排课系统；Java中图分类号：TP311文献标识码：A文章编号：1009-3044（2014）05-1032-04排课是教学管理中十分重要、又相当复杂的管理工作，课程表的编排是一个涉及多种因素的组合规划问题，它要保证在课程安排中教师、学生、教室不能产生冲突并且要满足教师的要求和资源限制等约束条件。8

2、为了利用计算机来解决这个实际问题，减轻工作人员的负担，自20世纪60年代起就有学者投入研究，研究者对于排课系统的解决方案大致分为以下几种：第一种是基于简单的经验法则解决教学规模不太大的问题[1]；第二类是建立排课模型，将排课问题归结为图的边染色问题[2]；第三种方式是先将固定时段的课程优先排入，然后依序填入其他课程[3，4]；第四种方法是采用模块化方式[5]；图形着色法[6]；搜索法[7]，总之这些方法适合处理小规模排课问题，当问题的约束条件增多时，问题变得相对复杂，求解过程会变得非常困难。我国在排课方面的解决方案总结为两种：一是图着色模型[8]；而是

3、数学模型[9，10]。本文在讨论遗传算法的基础上，研究了遗传算法在排课系统中的应用和设计。1遗传算法遗传算法最早于1968年由Holland教授提出，并建立了遗传算法原型，形成了遗传算法的理论基础。遗传算法是从生物进化论观点出发，用计算机模拟自然界演化的方式，对既定问题求最优解的方法，是基于自然选择和基因遗传、进化机制基础上的一种高度并行、自适应的优化算法[11]。遗传算法的操作步骤如图1所示。图1遗传算法流程图2排课系统的设计2.1总体设计在充分调研教学排课管理业务后，经过分析，总结排课系统管理的信息和完成的功能有：1）基础信息管理排课系统中所需要管

4、理的基本信息有：教室信息、教师信息、课程信息、和班级信息；对这些信息管理的主要操作有、搜索、查看、添加、修改和删除。2）学期计划管理8学期计划管理模块主要依据学生的培养方案设置课程所在的学期、对应的专业（班级）、课程的名字以及课程所需的学时数；并为每一门课程指定相关的任何教师。3）排课管理排课管理有自动排课和手动课表调整两个方面的功能。自动排课是根据遗传算法的工作原理，对排课系统所管理的基本信息和学期计划进行杂交、编译操作后得到基本满足硬约束、软约束条件的课表；然后，在自动排课的基础上，将不满足条件的部分内容进行调整，最后生成教师课表、班级课表。系统的

5、总体功能模块图如图1所示。图2系统功能模块图2.2数据库设计根据排课系统所涉及到的实体有：课程、教师、教室、班级、学期；这五个实体中教师和课程之间有授课关系；学期和课程之间有学期计划关系；班级与课程之间有班级课程关系；教室和课程之间有哪些课程在哪个教室上课的关系。关系E-R图如图3所示。图3排课系统中各实体及其关系E-R图2.3排课系统详细设计1）表示结构8在遗传算法排课系统中，一条染色体中应包含所有排课DNA分子，每个排课DNA分子又包含班级课程信息、老师信息、教室信息和时间信息，以及院系和学期信息。由于院系和学期在处理中是提前设定好的，在每次处理时

6、都是一个给定的值，所以在染色体中可以不考虑他们。2）初始种群采用系统的随机数，生成初始种群。将排课任务表示为CyKwTx，在进行排课时，初始化种群中的个体就是用随机函数生成染色体中的RzMN的组合。3）约束条件硬约束：l每个指定时间段一个班级、一个教师、一个教室分别只能对应一门课程；l要求教室的个数大于或等于指定时间段将要安排的课程数；l安排教室时，要求教室容量必须大于或等于班级人数；l教室类型与课程要求一致。软约束：l优先安排全校公共基础课；l一周内课次多于2次以上的多课时课程，在时间安排上要求尽量隔天安排；l较难课程应安排在上午第一节或下午第一节；

7、l体育课后尽量避免直接排课；8l同一门课程尽量安排在固定的教室。4）评价函数评价函数是对种群中的每个染色体设定一个概率，使得高概率地选择某染色体，适应性值高的染色体被选择产生后代的机会更大。评价函数的定义因各种问题而异，参数的个数也不一致。一般情况下，都是根据某种性的函数将各基因所获得的适应值进行统计，以求得整条染色体的适应值。5）洗牌杂交遗传算法中的杂交算法主要有：多点杂交、均匀杂交和洗牌杂交。本系统设计中使用的是洗牌杂交，即从每个父本中取它们一般的基因重组成新的个体。6）变异操作变异是随机改变一个染色体中某一基因的值，使得染色体出现新的基因特性，有

8、时候将求解过程中趋于局限制时出现新的解决方法。变异的染色体个数根据变异率而定，如果变异率过高，