基于改进遗传算法排课系统应用研究

马小姝 李芙蓉

摘要：针对复杂的排课问题，结合高校实际排课需求，本文将排课问题抽象成一个计算机可以求解的多约束多目标组合优化问题。建立排课问题数学模型，引入遗传算法，提出一种改进的算法方案来求解排课问题。同时，设计了染色体编码和适应度函数，采用自适应参数调整的交叉概率和变异概率，讨论了遗传算法在排课系统中的应用，并采用Matlab工具进行仿真实验。仿真结果表明，改进遗传算法平均适应度值高于传统遗传算法平均适应度值，收敛性好，提高了全局搜索能力，与传统的遗传算法相比，能更有效的解决高校排课问题。该研究可以较好地解决排课问题。

关键词：遗传算法; 排课问题; 多目标优化; 数学模型; 适应度函数; 自适应参数

中图分类号： TP311.52; G642.0  文献标识码： A

收稿日期： 20200114; 修回日期： 20200225

基金项目：国家自然科学基金资助项目（61461046）;甘肃省教育厅创新能力提升项目（2019B129）;甘肃省天水师范学院中青年教师科研资助项目（YB201702）

作者简介：马小姝（1979），女，甘肃天水人，硕士，讲师，主要研究方向为智能信息处理。 Email： maxiaoshu2013@163.com

随着信息技术的不断发展和教育改革的不断深入，利用信息技术实现智能化的教学管理在高校越来越有必要[1]。对于高校教学管理工作，合理的课程安排能充分体现一个学校的教学管理水平。近年来，由于国家大力投资教育事业，高等院校的招生规模不断扩大，学生数量不断增加，因此如何高效利用有限的教学资源解决排课问题，在教学管理工作中尤为重要。对于复杂的排课问题，国内外许多学者进行了研究，S.Even等人[23]证明了排课问题是一个多项式复杂程度的非确定性问题（nondeterministic polynomial complete，NP），是一个多约束多目标的组合优化问题。对于算法的研究，早期提出了整数规划算法[4]、图论法[5]和启发式算法[67]，但运用比较多的是遗传算法[810]、模拟退火算法[1112]和蚁群算法[1314]等方法。目前，遗传算法因具有并行搜索能力，可以重点集中搜索性能高的部分，在解决排课问题上得到了广泛的应用[1517]，虽然其效率较高[18]，但容易出现局部最优解的早熟现象，具有较大的改进空间。因此，本文在注重传统遗传算法的基础上，提出了改进的排课算法，建立了排课问题数学模型，并进行了仿真验证。与传统的遗传算法相比，本研究有效的解决了高校排课问题，提高了高校的教学管理水平。

1 遺传算法

遗传算法（genetic algorithm，GA）是J.H.Holland于1975年提出[19]，受生物进化论的启发，是一种模拟生物进化机制的随机搜索自适应算法。对所研究的问题先进行染色体编码，形成初始种群。按照自然界进化法则迭代进化，产生最优个体，得到问题最优解[20]。在迭代过程中，借助交叉算子和变异算子生成下一代种群个体，每次新生成的子代种群个体具有更高的适应度值，经过多次迭代进化，最终解逐步接近最优解，收敛到最适应环境的个体，对最优个体进行编码，即可认为近似最优解。

2 排课问题

要实现课程的合理安排，生成合理的课程表，就要在合理分配教学资源的前提条件下，将班级、课程、教室、教师安排在一周内的某一时间段内而不发生任何冲突，还要考虑在排课过程中出现的各种影响排课的因素，包括课程因素、教室因素、班级因素、教师因素等，根据这些因素的重要性，可理解成排课过程中需要考虑的约束条件，分为硬约束和软约束两类。

2.1 硬约束条件

硬约束条件是指必须要满足的条件，其受资源的限制，一般包括以下几点：

1） 一个时间单元内，一位教师只能讲授一门课程。

2） 一个时间单元内，一个教室只能安排一门课程。

3） 同一时间单元，一个班级只能安排一门课程。

4） 每个教室的座位数都应满足在此教室上课的班级人数。

5） 每门课程的课时总量应严格按照教学计划规定。

6） 对于特殊岗位的教师，某些时间段不能排课。

7） 需要特殊时间安排的课程，必须安排在预订的时间段内。

2.2 软约束条件

软约束条件是课表优化的方向，满足效果较佳，是不满足也不会产生影响的条件，根据我校实际情况，一般包括以下几点：

1） 一门课程在一周内的安排时间尽量分散，不要连续。

2） 黄金时段尽量安排高难度的专业课程。

3） 尽量避免一个班级全天空课和满课的情况。

4） 教学资源要尽可能的充分利用，对于采用专用教室的特殊课程，尽最大可能安排。

5） 尽量避免同一门课程在一天时间内多次授课。

6） 考虑老师的特殊情况，安排是否需要连排课时。

由于每所学校都有各自的实际情况，软硬约束条件不尽相同，其界定相对困难。因此，只要在定义约束范围内，给出一个新的遗传算法，对此问题进行优化处理。

3 建立排课问题数学模型

3.1 数学模型描述

排课问题中，会涉及课程、教师、教室、班级和时间5个因素，对5个因素分别进行如下数学描述：

时间段集合为T={T1，T2，…，Tnt}。

课程集合为M={M1，M2，…，Mnm}，{z1，z2，…，znm}为每门课程开课班级数。

式中，βi表示每位教师的满意度权值;m为教师总数。

4） 教室利用率。由于教室的人数容量有限，首先要考虑教室容纳的人数和上课学生的人数，如果学生人数与教室可容纳人数之比越大，说明此教室的利用率就越高，其值小于等于1。教室利用率为

f4=1r∑ri=1kcyr（4）

式中，kc表示班级对应人数;yr表示教室可容纳的人数。

对求得的适应度函数值进行修正，即

f=f+f-favgfmax-fminf

式中，favg表示种群个体适应度函数值的平均值;fmax表示最大适应度函数值;fmin表示最小适应度函数值。

4.3 初始种群

采用随机生成方式产生初始种群，但种群中也会产生一些不满足排课模型硬约束条件的个体。本文方法是对初始种群中的个体逐一进行筛选，将不能满足硬约束条件的个体丢弃，并重新生成新个体。反复操作，使其初始种群中的个体都尽可能的满足硬约束条件。

4.4 选择操作

选择操作经常使用的方法是轮盘赌选择算法，从上一代种群中选出适应度值较高的个体，并将其放到配对池中，剔除适应度值较低的个体，保留适应度值较高的个体，形成新的种群，从而进行下一步交叉、变异操作。本文在采用轮盘赌选择算法的基础上进行改进，选择个体进入下一代种群的概率为

pi=fi/∑Mi=1fi

式中，fi为個体适应度值;M为种群大小。

当每次产生N个随机数后，再从中选择一个个体，并不是产生一个随机数就选中一个个体，这样循环M次后会产生M个个体，可以保证每次都能选择最高适应度值的个体，提高下一代种群个体的更优性。

4.5 交叉和变异操作

交叉操作是利用交叉算子得到新一代个体，将种群内两个个体根据交叉概率随机交换其部分基因，产生新的基因组合，构成新个体。通过交叉操作，可提高算法的搜索能力，是生成新个体的主要方法，通常有单点交叉、多点交叉等方法。变异操作可以使局部搜索范围增加，提高算法局部搜索能力，依据变异概率，将个体中的某些基因组进行替换，形成新个体，是产生新个体的辅助方法，保持了种群的多样性。交叉概率pc的值决定了种群的空间搜索区域，但如果pc取值太大，会破坏个体的优良特征;若取值太小，也会使最优解出现过早的收敛。变异概率pm的取值保持了种群的多样性，但是pm过大，会使算法变成随机搜索算法，取值过小时也可避免某种单个基因的丢失。本文引入一种改进的自适应调节思想，使交叉概率和变异概率随迭代情况和个体适应度函数值进行自我调整更新。基于pc的变化，当pc增大时，pm减小;当pc减小时，pm增大，这样可以使交叉和变异操作共同保证了遗传算法的全局搜索能力。

交叉概率为

pc=k1-（k1-k2）（f′-favg）fmax-favg， f′≥favgk1， f′

变异概率为

pm=k3-（k3-k4）（f-favg）fmax-favg， f≥favgk3， f

式中，fmax是种群最大个体适应度值;favg为种群个体平均适应度值;f′为要交叉的两个个体中较大个体的适应度值;f为变异个体的适应度值;0

交叉操作，本文采用一种混合杂交算子的方法，利用交叉概率pc在种群中选取两个父代个体x=（x1，x2，…，xm）∈[L，U]，y=（y1，y2，…，yn）∈[L，U]，两个杂交点i1和i2进行两点凸杂交，得到两个子代个体分别为

x′=（x1，…，xi1-1，x′i1，yi1+1，…，yi2-1，x′i2，xi2+1，…，xm）

y′=（y1，…，yi1-1，y′i1，xi1+1，…，xi2-1，y′i2，yi2+1，…，ym）

其中

x′i1=axi1+（1-a）yi1，x′i2=axi2+（1-b）yi2

y′i1=ayi1+（1-a）xi1，y′i2=ayi2+（1-b）xi2

式中，[L，U]={（x1，x2，…，xm）|li≤xi≤ui，i=1，2，…，m}表示可行解空间;a和b是[0，1]中的随机数，反复操作，得到后代集合。交叉操作获得的子代个体方法和传统遗传算法相比，在进化前期可以提高进化速度。变异操作，根据变异概率，随机选取排课方案中的两列，并将其交换，判断是否满足各约束条件，如发生冲突，则再次随机选择交换，直到不冲突为止，产生一个新个体。

4.6 算法描述

Step1 随机生成初始种群p（t），令t=0。

Step2 计算当前种群中个体适应度函数值，并加以修正。

Step3 根据个体适应度值及轮盘赌选择算法进行选择操作。

Step4 进行交叉、变异操作，产生新的种群p（t+1），并且t=t+1。

Step5 若t

5 仿真实验

采用Matlab工具进行仿真实验，实验数据为15个班级，20间教室，26名教师，46门课程，每周上课的时间单元为25个，每个时间单元为2 h。设置初始种群个体数为40个，取参数k1=09，k2=06，k3=01，k4=001，进化代数最大为1000。分别采用传统遗传算法和改进遗传算法迭代1000代，每进化100代记录一次种群最佳适应度值，做15次实验，这样每隔100代进化会记录到15个最佳适应度值数据，取平均值作为实验结果，改进遗传算法与传统遗传算法对比如图1所示，由图1可以看出，改进遗传算法平均适应度值高于传统遗传算法平均适应度值，收敛性好，本文排课算法对解决排课问题效果较好。

6 结束语

本文建立了排课问题数学模型，引入改进的遗传算法求解排课问题，设计了算法的改进方案。仿真结果表明，该算法能够在一定程度上解决排课问题，提高了算法的收敛速度和寻找最优解的能力，但排课冲突率还有待降低。下一步研究还需对各个约束条件进行细化，根据学校特定的教学资源环境，完善算法自动化，排出相对优化的课表。

参考文献：

[1] 潘以锋. 高校智能排课系统的算法[J]. 上海师范大学学报： 自然科学版， 2006， 35（5）： 3137.

[2] Even S， Itai A， Shamir A. On the complexity of timetable and multicommodity flow problems[J]. SIAM Journal of Computing， 1976， 5（4）： 691703.

[3] Carter M W， Tovey C A. When is the classroom assignment problem hard？[J]. Operations Research， 1992， 40（S1）： 2839.

[4] McClure R H， Wells C E. A mathematical programming model for faculty course assignment[J]. Decision Sciences， 2007， 15（3）： 409420.

[5] de Werra D. An introduction to timetabling[J]. European Journal of Operational， 1985， 19（2）： 151162.

[6] Junginger W. Timetabling in germanya survey[J]. Interfaces， 1986， 16（4）： 6674.

[7] Lee Y， Chen ChuenYih. A heuristic for the train pathing and timetabling problem[J]. Transportation Research Part B： Methodological， 2009， 43（8/9）： 837851.

[8] 王小平， 曹立明. 遺传算法： 理论、应用与软件实现[M]. 西安： 西安交通大学出版社， 2002.

[9] 任子武， 伞冶. 自适应遗传算法的改进及在系统辨识中应用研究[J]. 系统仿真学报， 2006， 18（1）： 4143， 66.

[10] 杨从锐， 钱谦， 王锋， 等. 改进的自适应遗传算法在函数优化中的应用[J]. 计算机应用研究， 2018（4）： 10421045.

[11] Liu Y K， Zhang D F， Leung S C H. A simulated annealing algorithm with a new neighborhood structure for the timetabling problem[C]∥Genetic and Evolutionary Computation Conterence， GEC Summit 2009， Shanghai， China： GEC， 2009.

[12] 朱颢东， 钟勇. 一种改进的模拟退火算法[J]. 计算机技术与发展， 2009， 19（6）： 3235.

[13] 孟晓琳. 蚁群算法的研究及其应用[D]. 成都： 西南交通大学， 2015.

[14] Lee hsinyun. A decision support system for exposition timetabling using ant colony optimization[J]. Intenational Journal of Information Technology & Decision Making， 2012， 11（3）： 609626.

[15] 贺毅朝， 王熙照， 李文斌， 等. 基于遗传算法求解折扣{01}背包问题的研究[J]. 计算机学报， 2016， 39（12）： 26142630.

[16] 李红婵， 朱颢东. 基于小生境遗传算法的排课问题研究[J]. 计算机工程， 2011， 37（16）： 194196.

[17] 张赫男， 张绍文. 采用改进的混合遗传算法求解高校排课问题[J]. 计算机工程与应用， 2015， 51（5）： 240246.

[18] 马玉芳， 张海娜， 邵杰. 遗传算法在高校排课系统中研究与实现[J]. 计算机系统应用， 2014， 23（5）： 112115.

[19] Holland J H. Adapatation in natural and artificial systems[J]. The University of Michigan Press， Ann Arbor， 1975（1）： 2124.

[20] 姜婧， 白似雪. 遗传算法的改进及其在排课问题中的应用[J]. 南昌大学学报： 理科版， 2018（4）： 388392.

[21] 龚程， 陈高云， 刘胤田， 等. 基于改进型遗传算法求解高校排课问题[J]. 软件工程， 2018， 21（3）： 14.

Design of Course Scheduling System Based on Improved Genetic Algorithm

MA Xiaoshu， LI Furong

（School of Electronic Information and Electrical Engineering， Tianshui Normal University， Tianshui 741000， China）

Abstract：  Aiming at the complicated problem of course arrangement， combining with the actual demand of course arrangement in colleges and universities， this paper abstracts the problem of course arrangement into a multiobjective combination optimization problem which can be solved by computer. The mathematical model of scheduling problem is established， and genetic algorithm is introduced to solve the scheduling problem. At the same time， the chromosome coding and fitness function are designed， and the crossover probability and mutation probability are adjusted by adaptive parameters. The application of genetic algorithm in the course arrangement system is discussed， and the simulation experiment is carried out with Matlab. The simulation results show that the average fitness value of the improved genetic algorithm is higher than the average fitness value of the traditional genetic algorithm， which has good convergence and improves the global search ability. Compared with the traditional genetic algorithm， it can solve the problem of university course arrangement more effectively. This research can solve the problem of course arrangement.

Key words： genetic algorithm; timetabling problem; multiobjective optimization; mathematical model; fitness function; adaptive parameter