基于改进型遗传算法求解高校排课问题
龚程 陈高云 刘胤田 李代伟
摘 要：随着信息技术的不断发展和教育改革的不断深入，通过信息技术实现教学管理的智能化已经成为可能。排课作为教学管理的核心内容之一，它是衡量教学管理水平的重要指标，它是教学管理智能化的重要体现。本文的研究是通过学校的教学计划分析并建立排课的数学模型，对传统的遗传算法进行改进，设计出一种改进的自适应的遗传算法求解排课问题，改进的自适应遗传算法相对于传统的遗传算法在排课效率上有很大提高。
关键词：排课模型；遗传算法；节次；自适应
中图分类号：TP311.5 文献标识码：A
Abstract：With the continuous development of information technology and the further deepening of education reform，intelligent teaching management by means of information technology has become possible.As one of the core contents of teaching management，course scheduling is an important index to measure teaching management as well as an important evidence of intelligent teaching management.This paper has analyzed and established the mathematics model of course scheduling through the teaching plan in colleges and universities，improved traditional genetic algorithm and designed an improved self-adaptive genetic algorithm to solve the scheduling problem.Compared with traditional genetic algorithm，the improved adaptive genetic algorithm has greatly increased the efficiency of course scheduling.
Keywords：course scheduling model；genetic algorithm；section；self-adaptive
1 引言（Introduction）
随着信息技术的不断发展和教育改革的不断深入，通过信息技术实现教学管理的智能化已经成为可能[1]。排课作为教学管理的核心内容之一，它是衡量教学管理水平的重要指标，它是教学管理智能化的重要体现。排课问题的目标是在一定的约束条件下求解出较优的排课方案，使得依据此方案执行的教学计划具有学生老师合理安排，教室资源利用率高，教学质量高的特点[2，3]。
2 常见的排课模型（Common course scheduling model）
2.1 图论算法
图论中的图是由若干给定点及连接两点的线所构成的图形，这种图形通常用来描述事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系图论解决排课问题，将图论的边着色理论，对排课资源进行建模，使得排课问题得以解决[4]。但图论本身是NP完全问题，算法实现上比较繁琐。
2.2 贪心算法
贪心算法基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。贪心算法的排课系统，以资源匹配为基础，用内存动态分区分配的最佳适应法为依托解决排课问题[5]。与图论算法比较，避免了算法实现上的困难，但贪心算法在断点选择中存在缺陷。
2.3 人工智能算法
人工智能是对人的意识、思维的信息过程模拟。人工智能解决学校的排课系统，以时间因素为核心进行课程的安排符合学校教学实际情况，以影响学校课程安排中最为直接的三个因素教师。以学生和教室为核心来安排一门课程[6]。使用这种方法能够使学校管理进一步科学化，高效化。
3 基于高校的排课模型（Course scheduling model in colleges and universities）
3.1 相关术语
⑴教学班（Teaching Class）：一个教学班包含多个班级。例如：软件工程2015级1—2班包含1班和2班两个班，这样定义不需要考虑合班情况，只需要在制定教学计划时选择出需要合班的班级即可，教学班集合定义为，每个教学班对应的人数为。
⑵节次（Section）：一门课程上一节课45min所耗费的时间为一个节次，一天共有10个节次，上午四个节次，下午四个节次和晚上两个节次，节次集合定义为。
⑶课程（Course）：将课程分为公共基础必修，公共基础选修，学科基础必修，学科基础选修，专业课必修，专业课选修，实践教学环节必修，实践教学环节选修，表示课程的重要程度，即权重。课程的权重为1，2，3，…，8。
⑷教室（Class Room）：集合定义为。
⑸教师（Teacher）：集合定义为。
⑹时间间隔（Time Interval）：对于一周多学时的课程需要有时间间隔，用，表示间隔的天数。
3.2 约束条件
3.2.1 硬约束条件
3.2.2 软约束条件
⑴课程约束：课程约束包含三个约束条件，分别是：①重要的课程要安排在教学效果好的节次；②同一门课程应该安排在每周中同一个节次；③同一門课程的教室应该安排一致。对应的数学表达式如下：
⑵教师约束：教室约束包含三个约束条件，分别是：①同一个教师在一周上同一门课程是多节次，则课程的时间安排应该有时间间隔；②同一个教师在一周上两门课程，则课程的时间安排应该连排；③同一个教师在一周上两门课程，则课程的教室安排应该足够的近。对应的数学表达式如下：
⑶学生约束：学生约束包含三个约束条件，分别是：①每个学生一个周节次排课分布均匀；②每个学生一天不能排满课；③每个学生连续上两门课程，则课程教室的安排应该足够的近。对应的数学表达式如下：
其中，表示一个教学班在一个工作日所上的课程数，表示一周上课天数，表示一个教学班一天平均要上的节次。
⑷教室约束：教室约束是教室的利用率应该高。对应的数学表达式如下：
3.3 适应度函数
适应度函数的好坏决定了遗传算法的收敛性，若目标函数设计不合理会造成程序执行过早收敛，形成局部最优解，合理的目标函数可以得到全局最优解。本文所设计适应度函数如式（6）所示，目标函数适应度的函数值的解越大所求出的解越优。
3.4 排课的流程
排课是根据教务处指派的教学任务，合理的将教学任务分配教室和时间，排课流程如图1所示。
4.1 编码设计
编码方式有浮点编码、二进制编码、十进制编码等方式，本文采用十进制编码表示课表染色体的编码，如下表2所示，能更好地表示排课问题的实际特点。每一种编码对应一条染色体，则每一条染色体表示的是一种排课可能。
例如：软件学院张三教授给2012级软件工程1班上《数据结构》课程，课程每周两次，在2栋楼101多媒体教室进行，时间是第四周周一下午五六节，则可此授课事件的染色体编码为011001-1201011-1220001-22101-0413（其中011001表示教师编码，01表示软件学院，1表示教师的职称，001表示教师的编号）。
4.2 初始种群的产生
初始种群的产生一般通过随机搜索的方式产生，为后续各种操作提供初始可行解。由于初始种群中生成的个体适应度值较低，本文首先按照课程权重对课程进行排序，该操作可以避免解空间的过早压缩，同时能够尽早的产生可行解。
4.3 选择操作
根据达尔文的进化论提出的“适者生存”的原则，选择是从种群中选择出优秀的个体作为父代，并为下一代个体繁殖作基础。选择操作通常也称作再生操作。选择操作从种群中选择出适应度高的个体遗传到下代个体。种群中个体的适应度的值越大，被选择的概率则越高。fi表示种群中个体的适应度的值，n表示种群中个体的数量，则种群中个体的概率值：
4.4 自适应交叉和变异操作
交叉操作是把种群中两个个体进行随机的交叉重组，这种操作既保证的新产生的个体保留了父代个体的优良基因，又是种群的个体具有多样性。变异操作是种群中的个体根据一定的概率值做出基因位的变动。传统的遗传算法中，采用固定的交叉概率和变异概率，容易产生局部最优解，本文采用自适应的交叉和变异操作进行遗传算法的计算，具体操作如下：
其中，和分别表示交叉和变异概率，表示当前种群最优个体的适应度值，表示当前种群平均适应度值，表示进行交叉操作的个体中适应度较大的值，表示变异个体适度值，和取值均为0到1的随机数。
5 实验（Experiment）
5.1 实验数据
本文实验数据是来自软件工程学院2017年秋季课表，如表3所示。实验参数如表4所示。实验平台采用2.20GHz，Pentium i7处理器、8GB内存、700GB硬盘，操作系统为win7。所有实验均采用C#语言，在Visual Studio 2010下实现。
5.2 实验结果与分析
对于同一初始种群下，将文献[7]中（GA）方法与本文方法（MGA）进行对比。图2是10次实验两种方法不同的种群平均適度的值，MGA的平均值高于GA的平均值，图3是10次实验两种方法不同的时间值，MGA的时间值低于GA的时间值。由图2和图3可以看出，本文方法都优于文献[7]中的方法。
根据表5的评价指标分析，改进后的遗传算法MGA比传统的遗传算法GA在课程均匀度，学生课程分布，教室满意度及教室利用率方面都有明显的改善。
6 结论（Conclusion）
本文针对高校排课问题进行分析，根据教学计划对排课问题建模，通过改进的遗传算法对问题进行求解。实验结果表明，改进后的遗传算法比一般的遗传算法具有更高的效率。如何合理的解决排课中漏排课问题是下一步研究的重点。
参考文献（References）
[1] Marc Goerigk，Christian Liebchen.An Improved Algorithm for the Periodic Timetabling Problem[C].17th Workshop on Algorithmic Approaches for Transportation Modelling，Optimization，and Systems，2017（12）：1-14.
[2] H Babaei，J Karimpour，A Hadidi.A survey of approaches for university course timetabling problem[J].Computers & Industrial Engineering，2015，86（C）：43-59.
[3] G Woumans，L De Boeck，J Belin.A column generation approach for solving the examination-timetabling problem[J].European Journal of Operational Research，2016，253（1）：178-194.
[4] 崔妍，王权，王康，等.排课问题的数学模型[J].沈阳工程学院学报（自然科学版），2016，12（3）：276-278.
[5] 聂小东，李振坤，陈平华.基于贪婪算法的排课系统的探讨与实现[J].现代计算机：专业版，2007（11）：109-112.
[6] 杨斌.人工智能算法在学校排课系统中的应用[J].数字技术与应用，2015（10）：144-145.
[7] NPillay，W Banzhaf.An informed genetic algorithm for the examination timetabling problem[J].Applied Soft Computing，2010，10（2）：457-467.
作者简介：
龚 程（1990-），男，硕士生.研究领域：数据挖掘.
陈高云（1963-），女，硕士，教授.研究领域：数据挖掘，数据集成与可视化.
刘胤田（1972-），男，博士，教授.研究领域：智能信息处理，数据集成与可视化.
李代伟（1976-），男，硕士，副教授.研究领域：智能信息处理，知识工程.
摘 要：随着信息技术的不断发展和教育改革的不断深入，通过信息技术实现教学管理的智能化已经成为可能。排课作为教学管理的核心内容之一，它是衡量教学管理水平的重要指标，它是教学管理智能化的重要体现。本文的研究是通过学校的教学计划分析并建立排课的数学模型，对传统的遗传算法进行改进，设计出一种改进的自适应的遗传算法求解排课问题，改进的自适应遗传算法相对于传统的遗传算法在排课效率上有很大提高。
关键词：排课模型；遗传算法；节次；自适应
中图分类号：TP311.5 文献标识码：A
Abstract：With the continuous development of information technology and the further deepening of education reform，intelligent teaching management by means of information technology has become possible.As one of the core contents of teaching management，course scheduling is an important index to measure teaching management as well as an important evidence of intelligent teaching management.This paper has analyzed and established the mathematics model of course scheduling through the teaching plan in colleges and universities，improved traditional genetic algorithm and designed an improved self-adaptive genetic algorithm to solve the scheduling problem.Compared with traditional genetic algorithm，the improved adaptive genetic algorithm has greatly increased the efficiency of course scheduling.
Keywords：course scheduling model；genetic algorithm；section；self-adaptive
1 引言（Introduction）
随着信息技术的不断发展和教育改革的不断深入，通过信息技术实现教学管理的智能化已经成为可能[1]。排课作为教学管理的核心内容之一，它是衡量教学管理水平的重要指标，它是教学管理智能化的重要体现。排课问题的目标是在一定的约束条件下求解出较优的排课方案，使得依据此方案执行的教学计划具有学生老师合理安排，教室资源利用率高，教学质量高的特点[2，3]。
2 常见的排课模型（Common course scheduling model）
2.1 图论算法
图论中的图是由若干给定点及连接两点的线所构成的图形，这种图形通常用来描述事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系图论解决排课问题，将图论的边着色理论，对排课资源进行建模，使得排课问题得以解决[4]。但图论本身是NP完全问题，算法实现上比较繁琐。
2.2 贪心算法
贪心算法基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。贪心算法的排课系统，以资源匹配为基础，用内存动态分区分配的最佳适应法为依托解决排课问题[5]。与图论算法比较，避免了算法实现上的困难，但贪心算法在断点选择中存在缺陷。
2.3 人工智能算法
人工智能是对人的意识、思维的信息过程模拟。人工智能解决学校的排课系统，以时间因素为核心进行课程的安排符合学校教学实际情况，以影响学校课程安排中最为直接的三个因素教师。以学生和教室为核心来安排一门课程[6]。使用这种方法能够使学校管理进一步科学化，高效化。
3 基于高校的排课模型（Course scheduling model in colleges and universities）
3.1 相关术语
⑴教学班（Teaching Class）：一个教学班包含多个班级。例如：软件工程2015级1—2班包含1班和2班两个班，这样定义不需要考虑合班情况，只需要在制定教学计划时选择出需要合班的班级即可，教学班集合定义为，每个教学班对应的人数为。
⑵节次（Section）：一门课程上一节课45min所耗费的时间为一个节次，一天共有10个节次，上午四个节次，下午四个节次和晚上两个节次，节次集合定义为。
⑶课程（Course）：将课程分为公共基础必修，公共基础选修，学科基础必修，学科基础选修，专业课必修，专业课选修，实践教学环节必修，实践教学环节选修，表示课程的重要程度，即权重。课程的权重为1，2，3，…，8。
⑷教室（Class Room）：集合定义为。
⑸教师（Teacher）：集合定义为。
⑹时间间隔（Time Interval）：对于一周多学时的课程需要有时间间隔，用，表示间隔的天数。
3.2 约束条件
3.2.1 硬约束条件
3.2.2 软约束条件
⑴课程约束：课程约束包含三个约束条件，分别是：①重要的课程要安排在教学效果好的节次；②同一门课程应该安排在每周中同一个节次；③同一門课程的教室应该安排一致。对应的数学表达式如下：
⑵教师约束：教室约束包含三个约束条件，分别是：①同一个教师在一周上同一门课程是多节次，则课程的时间安排应该有时间间隔；②同一个教师在一周上两门课程，则课程的时间安排应该连排；③同一个教师在一周上两门课程，则课程的教室安排应该足够的近。对应的数学表达式如下：
⑶学生约束：学生约束包含三个约束条件，分别是：①每个学生一个周节次排课分布均匀；②每个学生一天不能排满课；③每个学生连续上两门课程，则课程教室的安排应该足够的近。对应的数学表达式如下：
其中，表示一个教学班在一个工作日所上的课程数，表示一周上课天数，表示一个教学班一天平均要上的节次。
⑷教室约束：教室约束是教室的利用率应该高。对应的数学表达式如下：
3.3 适应度函数
适应度函数的好坏决定了遗传算法的收敛性，若目标函数设计不合理会造成程序执行过早收敛，形成局部最优解，合理的目标函数可以得到全局最优解。本文所设计适应度函数如式（6）所示，目标函数适应度的函数值的解越大所求出的解越优。
3.4 排课的流程
排课是根据教务处指派的教学任务，合理的将教学任务分配教室和时间，排课流程如图1所示。
4.1 编码设计
编码方式有浮点编码、二进制编码、十进制编码等方式，本文采用十进制编码表示课表染色体的编码，如下表2所示，能更好地表示排课问题的实际特点。每一种编码对应一条染色体，则每一条染色体表示的是一种排课可能。
例如：软件学院张三教授给2012级软件工程1班上《数据结构》课程，课程每周两次，在2栋楼101多媒体教室进行，时间是第四周周一下午五六节，则可此授课事件的染色体编码为011001-1201011-1220001-22101-0413（其中011001表示教师编码，01表示软件学院，1表示教师的职称，001表示教师的编号）。
4.2 初始种群的产生
初始种群的产生一般通过随机搜索的方式产生，为后续各种操作提供初始可行解。由于初始种群中生成的个体适应度值较低，本文首先按照课程权重对课程进行排序，该操作可以避免解空间的过早压缩，同时能够尽早的产生可行解。
4.3 选择操作
根据达尔文的进化论提出的“适者生存”的原则，选择是从种群中选择出优秀的个体作为父代，并为下一代个体繁殖作基础。选择操作通常也称作再生操作。选择操作从种群中选择出适应度高的个体遗传到下代个体。种群中个体的适应度的值越大，被选择的概率则越高。fi表示种群中个体的适应度的值，n表示种群中个体的数量，则种群中个体的概率值：
4.4 自适应交叉和变异操作
交叉操作是把种群中两个个体进行随机的交叉重组，这种操作既保证的新产生的个体保留了父代个体的优良基因，又是种群的个体具有多样性。变异操作是种群中的个体根据一定的概率值做出基因位的变动。传统的遗传算法中，采用固定的交叉概率和变异概率，容易产生局部最优解，本文采用自适应的交叉和变异操作进行遗传算法的计算，具体操作如下：
其中，和分别表示交叉和变异概率，表示当前种群最优个体的适应度值，表示当前种群平均适应度值，表示进行交叉操作的个体中适应度较大的值，表示变异个体适度值，和取值均为0到1的随机数。
5 实验（Experiment）
5.1 实验数据
本文实验数据是来自软件工程学院2017年秋季课表，如表3所示。实验参数如表4所示。实验平台采用2.20GHz，Pentium i7处理器、8GB内存、700GB硬盘，操作系统为win7。所有实验均采用C#语言，在Visual Studio 2010下实现。
5.2 实验结果与分析
对于同一初始种群下，将文献[7]中（GA）方法与本文方法（MGA）进行对比。图2是10次实验两种方法不同的种群平均適度的值，MGA的平均值高于GA的平均值，图3是10次实验两种方法不同的时间值，MGA的时间值低于GA的时间值。由图2和图3可以看出，本文方法都优于文献[7]中的方法。
根据表5的评价指标分析，改进后的遗传算法MGA比传统的遗传算法GA在课程均匀度，学生课程分布，教室满意度及教室利用率方面都有明显的改善。
6 结论（Conclusion）
本文针对高校排课问题进行分析，根据教学计划对排课问题建模，通过改进的遗传算法对问题进行求解。实验结果表明，改进后的遗传算法比一般的遗传算法具有更高的效率。如何合理的解决排课中漏排课问题是下一步研究的重点。
参考文献（References）
[1] Marc Goerigk，Christian Liebchen.An Improved Algorithm for the Periodic Timetabling Problem[C].17th Workshop on Algorithmic Approaches for Transportation Modelling，Optimization，and Systems，2017（12）：1-14.
[2] H Babaei，J Karimpour，A Hadidi.A survey of approaches for university course timetabling problem[J].Computers & Industrial Engineering，2015，86（C）：43-59.
[3] G Woumans，L De Boeck，J Belin.A column generation approach for solving the examination-timetabling problem[J].European Journal of Operational Research，2016，253（1）：178-194.
[4] 崔妍，王权，王康，等.排课问题的数学模型[J].沈阳工程学院学报（自然科学版），2016，12（3）：276-278.
[5] 聂小东，李振坤，陈平华.基于贪婪算法的排课系统的探讨与实现[J].现代计算机：专业版，2007（11）：109-112.
[6] 杨斌.人工智能算法在学校排课系统中的应用[J].数字技术与应用，2015（10）：144-145.
[7] NPillay，W Banzhaf.An informed genetic algorithm for the examination timetabling problem[J].Applied Soft Computing，2010，10（2）：457-467.
作者简介：
龚 程（1990-），男，硕士生.研究领域：数据挖掘.
陈高云（1963-），女，硕士，教授.研究领域：数据挖掘，数据集成与可视化.
刘胤田（1972-），男，博士，教授.研究领域：智能信息处理，数据集成与可视化.
李代伟（1976-），男，硕士，副教授.研究领域：智能信息处理，知识工程.
