遗传算法在排课问题中的改进研究

刘二钢 黄荣芳 龙映宏

关键词：排课；遗传算法；智能排课；交叉；变异

0 引言

排课问题本质上是时空排列组合问题，即将教学中的班级、教师、课室等元素在时间上进行有序组合，从而使整个教学活动正常有序高效运行。近年来，由于高校办学规模不断扩大，课程安排规模逐年递增，给课表的编排带来一定困难。并且高校课表在编排过程中受到教室类型、专业要求等限制条件较多，结构更为复杂。因此编排出合理、科学的课表难度较大，需要花费大量的时间和精力，以往完全依靠人工的排课方式已不合时宜。

遗传算法本身是一种仿生算法，算法是在达尔文的生物进化论和孟德尔的遗传变异理论基础上，通过模拟生物进化过程而构造的一种自适应启发式全局优化搜索算法[1]。遗传算法最早是由美国密歇根大学的约翰·霍兰德（John H.Holland，1929-2015） 教授创建的，约翰教授也因此被称为遗传算法之父。遗传算法除了结构简单之外还具有全局搜索能力强、信息处理过程可以隐形鲁棒性和并行性等特殊优势，在数据挖掘、图像处理、机器学习、自动控制、组合优化以及模式识别等领域有着非常广泛的应用[2]。

近年来随着信息技术及人工智能的不断发展，计算机应用技术已经逐步深入人类社会的各个领域，起到极其重要的作用。通过计算机自动排课，本身具有手工排课无法比拟的诸多优点，例如：排课过程速度快、省时省力，排课结果查找方便、检索迅速、可靠性较高。另外计算机存储还可以保证保密性好、存储量大，最终使得整个排课过程人工成本降低、使用寿命加长[3]。通过上述优点，不仅可以相应提高排课效率，还可以使管理人员更加有效地看到各种资源的使用情况，从而更好地分配和利用教学资源，也便于解决教室临时借用、教师调停课等实时问题。因此计算机智能排课能够推动教学活动良性循环，从而提高教学质量。

1 排课问题

实际过程中，排课规则需要受到各种条件约束，因此随机产生的排课结果不可避免会产生大量冲突。一个好的课表必须做到统筹兼顾，既要满足教学需要，又要为管理者提供决策依据，使排课结果满足大多数师生的要求。

对上述问题进行归纳，主要解决两类问题：一是解决教师、课室、班级等在时间上的冲突，此类问题必须解决，通常称之为硬约束；二是解决教师个性需求、教学效果等特殊要求，使得课表编排能够更加合理，此类问题应尽量满足，通常称之为软约束。

硬约束主要包括：

1） 同一个时间一名教师只能在一个课室上课；

2） 同一个时间一个班级只能在一个课室上课；

3） 同一个时间，一间课室不能同时上一门以上的课程[4]；

4） 课室提供的座位数要大于或等于班级学生数。

軟约束主要包括：

1） 个别教师（如外聘教师）提出对于上课时间的特殊需要；

2） 同一个班级在一周内的同一门课程在时间安排上能够有一定的间隔；

3） 同一个班级或同一名教师在一天内相邻时间片所安排的课室能够尽量相同或接近，以避免师生远距离地更换课室；

4） 重要课程能够尽量安排在较好的时间节次。

2 排课过程当中的相关遗传算法设计

2.1 编码与染色体设计

编码与染色体是设计算法的两个关键因素，染色体就是构造编码之后生成的编码串。染色体中的每一位称之为基因，多个基因构造的有效信息段称之为基因组。染色体不断进化，最后需要的结果就是得出相对适宜的染色体。在算法实现过程中，通常以一周作为基本单位，整个学期可以看作是一周课程的多次重复。

根据上述的分析过程，首先将排课过程中的多个元素相互结合起来，根据办学规模进行编码，其中主要元素包括：

在排课操作前，首先考虑学校的多种元素。设有R间教室，一周有T（每天上课节次×一周上课天数）个时间段上课时间，则一周的教学任务就可以安排于R×T个时空单元内。如果将所有时空单元按照一定序列排序，就可以构成一个有序的时空数组。然后考虑每门课程的课程ID，教师ID和班级ID。由于课程对于同一个教学班也会存在重复的现象，比如一个班级一周上课多次，因此必须考虑主键，否则会有重复记录产生。将上述要素设定好后进行组合，构建的基因序列如图1所示：

基因序列构建完成之后，通过算法的演化过程，适应度高的基因能够留下，适应度差的基因相应去除，随后进入下一轮演化过程。如此反复循环，直到遗传算法整体终止或满足所设定的结束条件，整个算法即表示完成。

多个基因组合之后构造成为染色体，染色体构造完成后生成一条排课记录，将所有的排课记录在数据库二维表中，就构成了一种排课方案。有了排课方案，后续就可以根据适应度函数对排课方案进行评估。

2.2 适应度评估

适应度评估实际上是对排课结果的一种判断，一般用函数值来评估排课结果的优劣。适应度函数（Fit?ness Function）的选取将会直接对遗传算法的收敛速度及能否找到最优解产生影响[5]。由于遗传算法在搜索进化中基本不利用外部信息，仅以适应度函数作为依据，利用种群个体的适应度来进行搜索[6]。并且遗传算法需要得到非负的可比较结果，从而进行优劣比较，这也是遗传算法能够量化并广泛应用的主要原因，因此适应度函数设计非常关键。

通常来讲，适应度函数需要满足下述条件：其本身是一个连续的实函数，其上每个点与之相匹配的适应度值和染色体好坏成反比。函数对可导并无要求，但设计应尽量简单，参数尽可能少。

排课过程中，需要满足硬约束和软约束两个指标。硬约束在上述方案中已经得到满足，但课室的座位数并不一定能够满足学生的选课人数，因此在适应度函数计算时必须加以考虑，而软约束主要考虑以下几个指标：

1） 班级课程分散程度，用指标u1表示；

2） 课程时段优度，用指标u2表示；

3） 教师课时分散程度，用指标u3表示。

则整体的适应度函数可以设计如下：

其中，? 表示教室座位数满足容纳学生选课人数的平均值，α 是班级课程分散程度的全校平均值，β 表示课程时段优度平均值，γ 表示教师课程分散程度平均值。

2.3 初始种群的生成改进

初始种群创建之后，遗传算法才能开始进行演化。通常初始种群的创建都是随机生成，如果创建的初始种群搜索空间越大，在空间上分布得越均匀，就越有利于全局最优解的寻找[7]。

种群的生成改进则是在此基礎之上，根据每次随机产生的新个体与已存在的个体进行比较，如果相关排列顺序与已存在个体排列顺序相同，则需要弃用此产生个体，重新生成新个体。这样就能限制初始种群中相似个体总数。

2.4 遗传操作

遗传主要包含选择、交叉和变异三种操作方式，对于各种方式都可进行改进。主要改进方法包括：

1） 选择操作的改进

在排课过程中，衡量排课结果优劣的主要参数是适应度。在种群选择中初期采用赌轮选择法比较合适。该方法使得适应度高的个体更容易被选中，从而更容易产生优质的后代。赌轮选择法每次从轮盘中的较大区域通过随机选择若干个遗传样本到下一代。在进化过程中，该算法能够保证种群中最优个体被保留，最差个体被淘汰，从而使得种群整体被优化[8]。

考虑到初始种群适应度参差不齐，适应度低的个体也并非毫无价值，在算法演算的初始阶段采用赌轮方式比较适宜，可以有效地保留各类个体。但在算法演化过程的后半阶段，种群发展已经比较成熟，适应度高的个体普遍已经缺陷较少，质量较好，此时已经没有必要保留所有个体，可以将适应度差的个体放心淘汰。此时应对算法改进，将赌轮算法修改为锦标赛选择法，即将种群个体随机分组，并按适应度大小排名，每个组排名靠前的个体将直接进入下一轮[9]。锦标赛选择法更容易淘汰劣质个体，保留优质个体，使得算法演化速度更快。

2） 交叉操作的改进

在算法演算过程中，将随机产生的交叉点已经产生的染色体分成两个基因片段，形成左右两个子染色体，然后将左右两个子染色体进行对调，形成了新染色体，这就是交叉算法的本质。鉴于此过程会产生重复课程，因而交叉算法不能随意对调，必须进行改进。如果在交叉过程中采用多个交叉点，就构成了多点交叉。

目前遗传算法在排课问题中对于交叉操作都是基于单点交叉或多点交叉的一种交叉方式，这两种方式各有特点。单点交叉容易破坏优秀基因，而多点交叉又不利于优秀基因的扩散。因此，本文采取将两种理论进行结合，即前期使用多点交叉，便于优秀基因扩散；后期采用单点交叉，此时的迭代过程已经使得优秀基因比较稳定，单点交叉已不易破坏其完整性。

3） 变异操作的改进

交叉和变异是影响算法搜索最优解质量的关键要素，尤其是在算法的收敛性方面。算法的变异因子在演化过程中可以有效防止过早收敛而无法得到全局最优解的局面，可以据此对算法进行变异改进。

首先需要对种群中的大多数基因进行变量优化。由于此类基因本身适应度小，通过优化后再进行迭代，就会使得最终结果发生改变，从而趋向于最优解。但是由于早熟发生，需要进行变异操作，才能产生比剩余基因更好的基因，这样算法的搜索空间变得更小，寻优速度更快，进而解决原来遗传算法的早熟问题和易陷入局部最优解的问题。通过变异操作还可以相应减少遗传算法的进化迭代次数，并更早得到最优解[11]。

2.5 算法的终止条件

遗传算法由于客观条件限制，可能会产生无限循环的情况，因此一般需要设定算法终止条件。一般来讲，算法迭代次数设置为300～500次。如果在迭代次数到达之前，已经出现了满足条件，则算法可以提前结束，此时得到的就是最优解；如果达到了设定的循环条件仍没有满足约定结果，则将此时的最优解作为问题最终解。

2.6 对于冲突检测方法的优化

由于排课问题本身属于NP（Nondeterministic Poly?nomially，非确定性多项式）问题，因此排课冲突无法避免，例如一个班级可能在相同时间段内被安排了多门课程，又或者是一间教室被安排了多个班级同时上课[12]。解决的方法是引入冲突检测函数，通过冲突检测函数防止冲突发生。所有排课过程结束之后，利用冲突检测函数判断排课结果是否有冲突，并对结果进行相应调整。

2.7 排课改进算法流程

通过上述讨论，排课问题改进算法流程如图2所示。

3 算法仿真实验及结果分析

为检测改进算法的性能，以某高校机电工程学院2021—2022 年第1 学期的排课过程为例进行分析。实验过程对使用遗传算法和改进的遗传算法进行编程测试，在内存8.0 G和CPU3.8 GHz的计算机运行结果。实验中将种群设置为120，实验主要考察算法出现较优解的次数和平均运行时间两个指标。

实验结果中采用两种方式后，采用同样的算法及同样的适应度函数。假设迭代次数分别为50、100、150、200、250、300、350，即每次运行50次迭代步数，分别记录算法的平均运行时间和最优解运行次数两个运算指标，实验结果如图3、图4所示。

从实验结果可以看出，本文提出的办法在一定程度上解决了传统遗传算法所带来的随机早熟收敛问题，并在此基础上提升了算法的寻优能力和收敛速度，使得遗传操作更具有规律，整个运行过程也更平稳，并且适应度方面及操作收敛效果上略有提高，后续可以在此基础上进一步完善。

4 总结

本文在介绍遗传算法的基础上，对初始种群的生成方法以及选择、交叉、变异等操作进行解析，通过结合多种方法的优缺点后，对相应的步骤提出改进方法，最后将结论应用到实际问题中。实验证明上述方案使得算法的收敛性和寻优能力在一定程度上都有了相应提升，运算过程也更加平稳，提升了运算精度。结论证明本文算法具有更好的可行性和实用性，可以加以推广和使用。