基于遗传算法的智能排课问题的探究

李俊芳 张健立

摘要：目前，随着高校在校生人数的不断增长，教学管理任务也开始变得越来越繁重，其中排课任务在教务管理中就是一项极其重要但又很繁杂的工作。所以，设计开发一个合理高效的智能排课系统从而全面提高排课管理人员的工作效率，对于各高校管理部门及其工作人员来说都是一件特别有意义的事情。

关键词：智能排课遗传算法排课变量

1.引言

近几年，随着高校教育走向大众化，学生人数急速上升，这无疑加大了排课工作的难度，而课表安排又是教务管理工作中最基础的部分。因此自动排课系统是高校教务管理系统的一个重要组成部分，自动排课系统的应用，使得管理人员可以及时掌握学生的排课情况，进一步优化指导学校的教学资源，在一定程度上提高了高校教学管理人员的工作效率及教学质量。

2.背景

随着计算机网络技术的发展和教育信息化的不断推进，信息技术和计算机网络技术对教学和管理的各个方面都产生了很深的影响。教学计划的实施是高校日常教学管理工作中最重要也是最基本的一个环节。而课程表的制定则是教学计划实施的一个根本条件，是整个教学管理工作实施的基础，对教学计划的实施与教学培养计划的落实起着至关重要的作用，在此基础上对教育教学进行科学统一的组织和管理，有助于充分整合及利用各种资源。一张好的课表不仅能给授课教师带来工作上面的便利，而且也能为学生创造好的学习环境，提高学习效率。编制课表目的在于使整个教学过程能够有计划有秩序地进行，这在高校的教务管理工作中是一项耗时巨大的工程。而这项排课工作的复杂程度与学校的规模有很大的关系，学校的规模越大，当然排课工作的复杂程度就会越高。近几年，随着高校教育走向大众化，学生人数急速上升，这无疑加大了排课工作的难度，而课表安排是又教务管理工作中最基础的部分，因此如何设计一个好的排课系统，如何把教务管理人员从复杂的排课工作中抽离出来，是每一位教务工作人员和软件开发者的希望，也是当前迫切需要解决的一个问题。

因此，自动化排课系统的广泛应用必然成为大势所趋。排课系统是高校教务管理系统的一个重要组成部分，自动排课系统的应用，使得管理人员可以及其掌握学生的排课情况，进一步优化指导学校的教学，操作方便、灵活高效。自动化排课系统实现了整个排课流程的自动化，同时还解决了多种角色以及各个部门之间的协作关系。因此自动化排课系统的应用，在一定程度上提高了高校教学管理人员的工作效率及教学质量。

3.遗传算法

1.原理

遗传算法（Genetic Algorithms，GA）通过模拟自然界的生物进化过程来寻求问题的最优解，它借鉴了生物界的自然选择机制。遗传算法被较多的用于解决排课问题，同时很多学者热衷于对它的改进与优化，从而出现了诸多基于遗传算法的排课算法。

2.遗传算法流程如下：

1）进行染色体编码；

2）随机产生初始种群，数量根据实际情况事先定义；

3）计算所有个体进行适应度函数值的计算，若某个个体适应度值已满足最优化的要求，则输出该个体及其优化解，并结束当前计算，否则转到第4）步；

4）依据适应度值的大小，从所有个体中选取出那些适应能力较强的个体成为再生个体；

5）依据预先定义的交叉概率及方法产生出新的个体；

6）依据预先定义的变异概率及方法产生出新的个体；

7）由以上两个步骤中的交叉、变异操作产生新一代种群，并返回到第3）步。

4.排课系统设计

4.1排课管理部分

包括智能排课和排课结果查询两个功能。确定专业和年级后，启动自动排课功能，即可完成自动排课功能。排课结果查询即是对前面已排好的课表，在指定了专业和年级以后进行查询。

4.2数据库设计

排课系统依赖的基本信息包括课程、教室、教师、班级等资源，求解目标即满足要求的课表安排。数据库是上述信息的载体。利用关系型数据库系统进行系统的开发，需要首先完成概念结构的设计。概念结构反映了现实世界中实体之间的联系。

4.3排课问题变量

1. 时间变量

排课时重点要注意的是时间段的划分，一般高校安排周一至周五

為课程工作日， 一天可以安排8节课（上午4节， 下午4节），上课方式一般为两节连上，一个课次为两个相邻的小节课。所以以一个课次为一个时间段，一天可以划分为4个时间段。按一周五天计算，一周可以划分为20个时间段。但是，并非20个时间段里面每一个时间段都适合排课，并且有的课程对时间可能还会有一定的要求，如：比较重要的课一般放在一二节；体育课尽量不要排在上午的时间；周五下午三四节一般不排课等等。

2. 教师变量

一个教师可能只带一门课，也可能带多门课，但是一个教师在某一个时间段，在某一个教学地点只能上一门课；另外，一个教师可能带一个班级的课程也可能带多个班级的课，如果一个教师在某一时间段内被安排在多个班级上课，同样会造成教学活动的混乱。

3. 课程变量

一门课程可以由一位教师任教也可以由多位教师任教，而且每位教师可能对应了个班级的学生。

4. 班级变量

同一时间段内一个班级只能在一个教室里面上课，并且只能是一门课程。

5. 教室变量

学校里通常有多个教学楼，每个教学楼又会有若干个教室可供选择，在某个时间段内只能有一名教师在此教室授课，可以有多名学生，但是学生的课程必须相同，所选教师必须相同。

4.4排课问题约束

排课问题涉及到两种约束，分别是基本约束和模糊约束。其中，基本约束又称硬约束，是指在排课过程中必须要遵循的原则。而模糊约束又称软约束，是要尽量满足的原则。

一个正确的课表要遵循的基本约束条件：

1. 同一时间段内不能给一位教师安排两门不同的课程上课；

2. 同一时间段内一个班级只能安排一门课程；

3. 同一时间段内一个教室只能安排一门课程；

4. 教室的最大容量应不小于上课的学生人数；

除上述的基本约束外，还有一些模糊约束，这些模糊约束可以使课表更加合理、更加人性化。

模糊约束条件有：

1.根据课程类型以及学生接受程度，来为这类课程安排最合适的时间段；如：专业课、必修课一般安排在早上，而文体类的课程通常安排在下午；

2.理论性课程尽量分散安排，即一门课尽量分散在一周的某几天，并且中间尽量隔开，以便教师能够有充足的时间备课，而学生也有足够的时间消化已学到的知识；理论与实践并重的课程最好将理论与实践课穿插安排，可以在学生学习完理论课程后及时通过动手操作加以巩固，有利于学生对知识的理解、掌握；

3.学生的上课时间不能过分集中，应尽量避免某一天课程安排的很满而另一天却没课的情况；

4.排课时，应尽量把知识性强的和趣味性强的、理论性的和理解性的课程交叉安排；

5.考虑教师的工作负荷，一天内上课一般不超过四节；

6. 同一教师，同一门课程可以尽量安排在相对固定的教学场所，不但方便记忆， 还有利于教师和学生的适应；

7.教师或学生接连两门课程地点尽量比较接近；

8.对于教师、学生可能提出的一些特殊要求，根据情况安排，如若合理，尽量满足。

另外，对于其它特殊情况，如分单、双周上的课程，不确定周次的课程等，也需要综合考虑，合理安排。此外对于计算机预排的结果，还可以根据实际情况，通过人工交互的方式进行修改。

4.5基于遗传算法的智能排课算法

1.连接数据库获得课程信息，班级信息，教室信息，公共课程信息，系别信息；

2.根据多媒体教室资源数据生成空白时间安排表；

3.按照群体中个体数量，随机地将课程序号数据装入到时间安排表中；

4.计算每个个体的适应度向量，即个体染色体适应度函数值；

5.若适应度达到事先设定的进化结束要求（无继续收敛），或进化代数达到最大代数，则跳转到9；

6.根据4所得适应度值，计算交叉、变异和选择概率，根据概率选择优秀的时间安排方案，并淘汰掉适应度值低的方案；

7.应用交叉、变异算子与染色体；

8.继续循环，跳到5；

9.从较优群体中选择一个最优方案，生成最优时间安排表。

5.结束语

本文中的自动排课算法实现了教师、教室、课程、时间等资源在教学活动中的合理配置与安排，把教学工作者从繁杂的手工排课工作中解脱出来。同时，也减少了排课过程中可能出现的冲突错误，保证了教学秩序的正常运行，大幅度的提高了教务教学管理水平以及教务人员的工作效率。虽然实现了自动排课功能，而在实际应用中，还应该考虑到因为一些特殊原因导致的需要手工调节课表安排的情况，所以在今后还需要改善这方面的功能。

参考文献：

[1]修磊， 杨社堂. 高校排课管理系统的设计与实现[J].太原理工大学学报，2006， 37（5）：75-77.

[2]张海涛， 刘万军. 高校计算机排调课算法研究[J].辽宁工程技术大学学报，2005，24（1）： 110-111.

[3]袁宏武， 薛模根， 姚翎. 基于规则的个性化课表生成算法[J].计算机工程，2006，32（4）， 194-224.

[4]蘇仰娜. 基于遗传算法的优化排课系统[J].河南大学学报（自然科学版），2005， 35（1）， 75-78.

[5]魏敏.基于遗传算法电大排课系统的设计与实现[J].复旦大学，2011.

课题信息：课题名称：遗传算法在高等学校智能排课问题方面的研究，课题类别： 内蒙古自治区高等教育科学“十二五”规划课题课题，批准号：NGJGH2014083。