遗传算法在排课问题上的应用研究

2019年第21期信息与电脑China Computer & Communication算法语言

基于遗传算法的排课问题研究

周　艳　邓清清

（玉林师范学院 数学与统计学院，广西 玉林　537000）

摘　要：在教学过程中，排课计划是一个非常重要的环节，只有做好该工作才能为提升教学质量奠定基础。笔者通

过研究高校中遇到的具体问题，分析了排课的顺序、约束条件和时间，确定了3个方面的遗传算法标准。关注不同类型

实验室、计算机教室、小型教室、多学科教师等复杂环境下教学管理的约束和调度过程，用遗传算法的优点解决高校排

课调度问题，能制订最佳的教学计划。关键词：遗传算法；约束条件；排课问题

中图分类号：TP301.6 文献标识码：A 文章编号：1003-9767（2019）21-059-03

Research on the Model of Course Arrangement Based on Genetic Algorithm

Zhou Yan, Deng Qingqing

(School of Mathematics and Statistics, Yulin Normal University, Yulin Guangxi 537000, China)

Abstract: In the process of teaching, course arrangement plan is a very important link. Only doing this work well can lay the foundation for improving teaching quality. By studying the specific problems encountered in Colleges and universities, the

author analyzes the sequence, constraints and time of course arrangement, and determines the three aspects of genetic algorithm

科技信息　计算机与网络　

遗传算法在萋校区排课系统巾昀应用　

黄冈师范学院计算机科学与技术学院　周芬　

［摘要ｌ辋Ｆ课是多因素决策问题，文本分析了造成多校区高校排课难的各种因素，对排课问题中的约束条件进行分析，研究了如何　

应用遗传算法来解决多校区排课问题，给出了一个基于该算法的排课模型。　

［关键词］遗传算法　多校区排课适应度函数　

排课是教务管理工作的一个重点和难点。排课涉及教师、学生人　

数、教室容量、教室类型、教室间距等诸多因素。尤其是多校区同时运行　

的高校格局增加了更多的约束条件，问题的复杂度也增加了许多。多校　

区排课是一个典型的多因素的优化决策问题，是组合规划中的ＮＰ完全　

类问题，涉及信息较多且求解复杂性为课表规模的指数量级。遗传算法　

被证明解决该类问题是最合适的。　

一　排课问题描述　

编排课表的整个过程中充满了矛盾运动，其中包括上课班级、所开　

课程、任课教师、上课时间、上课地点等方面在排列组合中所发生的冲　

突和矛盾现象。课表的编排必须精心组织，准确无误，科学合理，充分发　

挥时间、空间、人力、物力，以保证教学过程的正常运转。课表要有利于　

教学设备的充分利用，要符合教学规律。将这个原则进行细化、清晰化，　

一般可以归纳为以下具体要求。　

课表中没有硬性冲突，在排课过程中必须遵守如下约束条件：　

１．每位教师在同一时间段内只能安排一门课程；　

２．一个教室在某一时间只能安排一门课；　

３．教室的位置数量与每个自然班的人数应尽量匹配；　

４．必须根据核定的教学计划所规定的学时数排课，不得任意增减；　

５．一个教师两节课间路程不超过ｌＯ分钟，半天的工作必须安排在　同一个校区。　

课表要求有较高质量，为了使排出的课表更优化、合理、排课还应　考虑以下因素：　

１．一门课程在每个班的每两天只能安排一次；　

２．专业必修课尽量安排在上午；　

３．同一门课的上课地点尽量安排在同一教室；　

４．体育课必须排在下午或者上午３—４节，体育课后避免安排讲授　

基于遗传算法和禁忌搜索算法的排课系统研究

随着互联网和信息技术的发展，教育行业也逐渐数字化。在教育资源共享、信息透明和教育教学质量提高方面，数字化教育平台为教育行业带来了很大的变革。而在学校内部，排课系统的研发也愈发重要。传统的排课方法不仅费时费力，而且缺乏灵活性，难以适应不断变化的教育教学需求。因此，基于遗传算法和禁忌搜索算法的排课系统研究成为了现代教育领域中的热点和难点问题。

遗传算法是一种自然界中生物遗传变异、选择和适应的过程的抽象模型。它具有并行搜索、全局优化等特点，能够有效地解决一些复杂的、难以用传统算法解决的问题。利用遗传算法来解决排课问题，首先需要确定排课问题的表达方式。针对排课问题中课程的时间、地点、教师的安排等各种约束条件，可以将每一个课程看作遗传算法种群中的一个个体并进行编码。然后，通过遗传算法的选择、交叉和变异操作，不断优化种群中各个个体的适应度，从而得到排课方案。

禁忌搜索算法是另一种优化问题的常用算法，它通过设定“禁锢”规则来实现搜索过程中的局部最优的跳出。在排课问题中，可以使用禁忌搜索算法来避免陷入局部最优解，提高系统的收敛速度和求解精度。禁忌搜索算法和遗传算法的结合可以达到更优的效果，并且相对于单独使用遗传算法，禁忌搜索算法能够更快地找到解，从而减少计算时间和成本。

除了遗传算法和禁忌搜索算法之外，排课系统研究还需要考虑到课程的优先级、期望班级时间表等问题。另外，针对多种约束条件的复杂性，优化算法还需要逐步改进和完善。例如，探索新的算法结构、加强遗传算法的局部优化能力等。

在实际应用中，排课系统研究对教育行业的发展具有重要意义。一方面，它能够提高学校排课的效率和质量，为学校减少人力物力的开销，避免教师和学生排课的繁琐和浪费；另一方面，通过数字化教学平台，在确保课程规划、人力统计、教学质量控制等方面的数据化和透明化的基础上，帮助学校提高教育教学质量，推进教育信息化、数字化发展。

遗传算法在排课系统中的应用

摘 要:随着信息时代的到来, 将信息系统应用于学校日 常工作已势在必行。 学校教育信息管理的核心是资源的统筹利用, 它包括人力资源、 物力资源以及 时间资源等。 本文给出了排课问题的数学模型,提出基于遗传算法解决方案。 结果表明,

该算法能比较有效的解决排课问题。 该方法易于学习和应用, 且不必 依赖特殊的实现模式。

关键词:排课 遗传算法 优化算法

1. 引言

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

2. 遗传算法简介

遗传算法是模拟自然界自然选择与进化机制求解极值问题的一类自适它以 生物群体的观点看待优化问题。 所求问题解空间中的一点为一个个体结合起来 构成一个群体, 群体中的每一个个体都代表了问题的一个可能解群体称为代。 在遗传算法中, 待优化参数通常用符号串来表示, 这一过程由某一符号串求得其 表示的具体参数值的过程称为解码。 符号串也称为染本组成单位称为基因。针 对具体问题, 遗传算法通过定义一个适应度函数来而每个个体所对应的适应度 函数值代表该个体对环境的适应程度, 适应度函个体适应环境的能力越强。 初 始群体确定后, 在选择、 交叉、 变异等遗传照类似于自然选择的过程逐代进 化, 最终获得问题的满意解。 [1]

3. 排课问题基本描述

排课问题就是将课程、 任课教师以及学生在合适的时间段内分配到合适的 教室中。 在高校中排课工作更加的复杂, 会涉及任课教师、 学生班级、 学 生人数、