遗传算法在高校排课管理子系统中的应用

《遗传算法在高校排课管理子系统中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、http://www.paper.edu.cn遗传算法在高校排课管理子系统中的应用曹萍，石浩男辽宁工程技术大学研究生学院管理科学与工程，辽宁葫芦岛（125105）E-mail:corsacfox@126.com摘要：随着信息时代的到来，将信息系统应用于学校日常工作已势在必行。学校教育信息管理的核心是资源的统筹利用，它包括人力资源、物力资源以及时间资源等。本文通过对高校排课所需所有信息的遗传算法模型分析，构建了基于数据库字段的结构化遗传编码，提出了利用遗传算法解决信息管理问题的方法，为高校管理信息化提供了一种

2、有效的技术手段。关键词：遗传算法，管理信息系统，排课1.引言随着现代信息技术在教育领域的普遍应用，我国高校教学系统的管理模式已逐步进入了网络化和信息化时代。近几年我国高等教育的快速发展及高校办学规模的不断扩大，本科学分制、选课、试听制度以及双专业辅修学制的进一步推行，使得高校排课的工作量成倍增长，工作难度进一步加大。传统手工排课模式已不能适应这一挑战，这就向教学排课管理子系统提出了新型化和多元化的要求。教学管理现代化、信息化是高校的必然选择。2.问题描述2.1排课问题基本描述排课问题就是将课程、任课教师以及

3、学生在合适的时间段内分配到合适的教室中。在高校中排课工作更加的复杂，会涉及任课教师、学生班级、学生人数、教室容量、教室类型等硬性要求条件以及单双周、课程均匀分布、授课时间分布、教室之间间距等其他软性要求条件。排课问题的本质就是时间表问题TTP(TimetablingProblem)。TTP问题是一类多元受限的不确定性问题，它决定一个从项目到资源的最优分配，使得总的代价最小且能满足K个条件。早在1975年，ShimonEven等人就证明了TTP问题是NP-Complete问题。而遗传算法具有良好的并行性、很强

4、的通用性、良好的全局优化和稳定性等优点。对于传统优化方法无法或很难解决的非线性、不可微分问题，遗传算法都能很好地解决。遗传算法的特点使其解决时间表问题成为可能。此外，排课所需的各种信息可以存储在计算机中的数据库内。所以可以设计基于遗传算法的学校排课管理子系统。2.2课表优化的约束条件(1)一个教师或者一个班级或者一个教室在同一时间段内只能安排一个课程；(2)一个教室可容纳人数应该大于上课学生数。除上述硬约束，还有些软约束，这些软约束使得课表更加合理，更加人性化。这些软约束条件可能是；(1)教室容量的利用率尽

5、量高一些；(2)晚上和周末尽量少排课；(3)尽可能满足个别教师的特殊授课时间、地点要求；(4)单门课程在一周中应尽量分散分布，这样教师有充足的时间备课和批改作业，学生也有时间做作业和复习消化；-1-http://www.paper.edu.cn(5)单个教师的所有课程在一周中应分散分布，避免一个教师的课排满一整天；(6)学生的上课时间在周一至周五尽量均匀分布，应避免一天课程很满而另一天却一整天没课的情况。软约束条件各个学校情况都有所不同，将根据自行定义的约束范围，利用遗传算法进行优化操作。2.3课表优化的目

6、标(1)时间表优化最为重要的目标是使得教育、教学效果更好，也就是将较重要的教学任务安排在合适的时间进行。(2)在考虑教学效果的基础上，第二个重要的目标就是资源的利用率问题，一个良好的安排结果可以节省大量的资源。(3)其他优化目标还有时间分布均匀度、人力偏好满足程度等。3.遗传算法简介遗传算法是模拟自然界自然选择与进化机制求解极值问题的一类自适应人工智能技术，它以生物群体的观点看待优化问题。所求问题解空间中的一点为一个个体，一定数量的个体结合起来构成一个群体，群体中的每一个个体都代表了问题的一个可能解，处于某

7、一时段的群体称为代。在遗传算法中，待优化参数通常用符号串来表示，这一过程称为编码。反之，由某一符号串求得其表示的具体参数值的过程称为解码。符号串也称为染色体，染色体的基本组成单位称为基因。针对具体问题，遗传算法通过定义一个适应度函数来模拟生物界环境，而每个个体所对应的适应度函数值代表该个体对环境的适应程度，适应度函数值越高表明该个体适应环境的能力越强。初始群体确定后，在选择、交叉、变异等遗传算子的作用下，按[1]照类似于自然选择的过程逐代进化，最终获得问题的满意解。4.基于遗传算法的模型分析时间表问题求解需

8、要解决的问题有两个，一个是随机建立初始时间表，另一个是在初始[2]时间表的基础上进行优化。利用遗传算法求解主要是后者，初始时间表种群的建立是为遗传算法的优化提供处理的基础，我们采用随机的方法产生初始时间表。4.1参数编码遗传算法的编码是为了把问题的可行解从解空间转换到算法能处理的搜索空间。编码是遗传算法首先要解决的问题，编码的好坏直接影响到后面的遗传运算。对于存储于数据库中的教学基本信息，我们提出基于数据库字段的