利用改进遗传算法破解排课难题

董玉锁+贺波+尹迎+胡海琴+李铁梅

摘 要 针对当前学校排课的实际问题，在传统遗传算法的基础上做了一系列改进。设计专门的染色体结构，优化初始種群的生成过程，并在标准遗传算法的基础上对选择算子、交叉算子和变异算子等多方面进行改进。目前，该算法已成功应用在东华博育云有限公司的排课产品中，实验表明，改进后的算法能得到较满意的课程安排方案，运行效率高，课表中出现资源冲突现象显著减少，极大地缩短了学校教务管理人员排课工作消耗的时间。

关键词 数学模型；遗传算法；排课；教务管理；教学班

中图分类号：G434 文献标识码：B

文章编号：1671-489X（2018）01-0016-04

1 引言

中小学校的教务管理部门在整个教学过程中起着组织、协调、管理及服务的作用，而排课又是教务工作中最基础、最重要的组成部分，也是工作量最大、最烦琐、难度最大的一项任务。排课工作的核心就是为学校所有的课程安排合适的教师、教学时间和地点，使学校的各项教育教学工作能够稳步推进、相互衔接。排课问题是困扰各学校的主要难题之一。近年来，国家大力推行课程和教学改革，实施“分层走班”等试验教学，这种走班模式下的排课难度更大。

所谓“走班制”，是指学校开设教学内容和程度要求不尽相同的各种层次班，教师、班级、学生并不固定，学生需要根据自己的能力和爱好选择进入不同的层次班上课学习。这种模式下学生的学习课程和上课班级都不相同，打破了原来固有的行政班授课模式，更增大了学校排课工作的难度。

S.Even等人于20世纪70年代论证了排课问题为NP完全问题（Non-deterministic Polynomial complete Problem，

NP-C，即多项式复杂程度的非确定性问题，是世界七大数学难题之一），由此奠定了其理论深度和难度。由于NP完全问题的特殊性，到现在为止，业界对其还没有通用的解决方案和算法。为了解决排课这类复杂的NP完全问题，本文立足实践提出排课问题的数学模型，并专门对传统遗传算法操作进行一系列的改进来求解，依托模型和算法降低运算的复杂度，力争使求解问题的时间大大减少。

排课问题描述 排课问题属于复杂的动态组合规划问题，由于限制因素较多且求解复杂性大，使求解计算所消耗时间成指数级增长。课表由教师、学生、课程、教室、上课班级和上课时间等元素构成，排课的过程是把这些课表元素进行排列组合规划，保证教师、学生、班级、课程和教室等资源在课表中的任何上课时间里都不会发生冲突。为了使排出的课表更人性化、用户满意度高，同时要考虑另外一些因素，例如：每门课程的上课时间要分布均匀、间隔合理；根据不同课程的特点安排合适的上课时间，如语文、英语不适合在下午排课，足球课、游泳课不适合在上午第一节排课等。

在对排课模型进行分析之后，本文抽象出一个“教学班”的概念。所谓教学班，指的是在相同时间、相同地点（教室）学习，由相同教师讲授同一门课程的一定数量的学生组成，便于教学和课堂活动的学生集体。在多个教师任同一门课程，或一门课程开设多个班级时，按课程和任课教师将学生分配到多个教学班（必修课可以在排课前确定教学学生分班情况，选修课教学班分班情况在选课完成后才能确定）。采用教学班的概念之后，无论传统的行政班授课，还是走班制授课，都可以很好地转换和对应起来，可以实现各种模式下的排课场景和需求。

排课的约束条件 排课不仅要考虑课表各元素在时间、空间上存在的合理性，同时要满足学校自身的各种约束条件（如教师不排课时间、课程不排课时间、固定课安排和课程互斥等），从而保证学校教学工作正常进行。排课中设置约束条件是为了避免课表中出现冲突。为了保障学校教育教学工作顺利进行，排出的课表必须不违反任何约束条件，也不允许出现任何课表元素冲突。同时，对课表各元素资源进行最优化组合配置，也有利于学校发挥资源优势、提高教学质量。有鉴于此，本文定义了三种排课约束条件。

1）排课硬约束条件。硬约束条件代表课表各元素在时间和空间概念上不能成立的情形，是排课过程中要遵守的最基本的约束条件。评价一张课表是否合理、可行，首先要看它是否满足所有的硬约束条件：教师不能冲突，如一个教师既不能同时教授两门或更多课程，也不能同时在多个教室上课；学生不能冲突，如一个学生既不能同时上两门或更多课程，也不能同时在多个班上课；教室不能冲突，如一间教室内不能同时安排两门及以上课程；班级不能冲突，如一个班级不能同时安排两门及以上课程；每门课程安排的授课教室座位数不得少于该课程的上课人数。

2）用户自定义约束条件：教师不排课时间要求；课程不排课时间要求；班级不排课时间要求；教室不排课时间要求；年级不排课时间要求；固定课要求；教师互斥要求；课程互斥要求。

3）排课软约束条件。评价一张课表优秀质量高，不仅必须满足上述硬约束条件和用户自定义约束条件，还需要考虑一些额外的软约束条件。软约束条件不是排课中必须遵守的规则，虽然这些规则并不会影响排课的成功或失败，但它们会对课表的合理性和用户满意度产生较大影响。硬约束条件和用户自定义约束条件是评价一张课表是否合理有效的标准，而软约束条件则是评价一张课表质量好坏的标准。软约束条件在排课问题中要尽量遵守、满足，一般的软约束条件有：班级课程尽量均匀分布；教案对齐；教师连续长时间上课的情况要尽量避免；班级不同课程上课地点尽量靠近；同一门课程的不同上课时间间隔要合理；上课学生人数和教室容量尽量匹配，提高教室利用率。

排课的求解目标 排课问题是一个含多约束条件的多目标的组合规划问题，按照多目标优化的方法与理论，在可行解域中找到的解将是一系列的解集合。如何从排课问题的众多求解空间中找到一套完整的包含课表所有元素的信息组合，并且不违背任何硬性约束和用户自定义约束的课表，是排课的最基本要求。在此基础上，课表质量的高低还需要通过其他指标来评价。本文中确定了两个排课目标：endprint

1）课表方案中不存在任何的硬性冲突，即课表必须满足所有硬约束条件和用户自定义约束，如同一个学生在同一时间不能上多门不同的课程，或者不能违背课程的不排课时间约束等，这是评价课表是否合理可行的基本条件；

2）课表质量高，即对课表各元素资源的分配合理、优化，尽可能多地满足各种软约束条件。

2 基于改进遗传算法的排课问题求解

遗传算法（Genetic Algorithm，GA）也叫基因进化算法，或进化算法，是由美国人J.Holland在20世纪60年代提出来的。遗传算法属于启发式搜索算法，它模拟自然界生物的进化过程，试图应用生命进化的规律找到一条有效解决实际问题中组合爆炸问题的途径。遗传算法提供了一种求解非线性、多模型、多目标等复杂系统优化问题的通用框架，它不依赖于问题具体的领域，已在很多领域得到广泛应用[1-2]，用于求解各种组合优化问题，为求解排课问题提供了有效的手段。

染色体（Chromosome）结构 使用遗传算法来求解排课问题的时候，首先必须把问题解的参数形式转换成由基因编码按一定结构组成的遗传染色体或个体[3]。遗传算法运算的起点和对象是种群（population），而种群是由大量经过基因编码的离散个体（individual）所构成的。初始化种群以后，算法依据适者生存的生物进化理论迭代进行，进化过程中的每一代，算法通过交叉操作和变异操作，诞生出下一代种群，并根据适应度大小选择优秀的后代个体，淘汰较差的个体，从而使整个种群保持稳定。经过多次迭代运算之后，遗传算法将逐渐收敛于最好的个体[4]。

应用遗传算法首先要对个体染色体进行基因编码，将排课问题中的课表转化为算法可操作的染色体编码。染色体编码方式设计至关重要，它不仅要能记录表达种群个体的各种特征信息，而且决定了遗传操作算子的设计和计算规模，直接影响了整个算法的收敛和搜索速度。

通过对常见遗传算法编码方案进行分析比较后，鉴于它们在实际求解排课问题时存在表示问题本身较为困难、排课效率较低、求解结果不理想的问题，本文针对排课问题专门设计一种优化改进的染色体编码方案，使其更适合于表示和求解排课问题。排课一般按排课周期来进行，以中小学来说是按周排课，每周周一至周五共五天上课，每天上七节课（上午两节课，下午三节课，晚上两节课）。这样，每周就会构成35个课节次，用T1，T2，T3，T4，T5，

T6，...，T35表示。其中，T1，T2，...，T7为周一的课节次，T8，T9，...，T14为周二的课节次，以此类推。如果全校有S个教学班，那么该学校课表可表示为以35个课节次为列、每个“教学班”为行组成的一个S*35二维矩阵。

基于这个设计，本文开创性地采用二维布尔矩阵（Boo-

lean Matrix）的方式来对课表染色体进行基因编码。该矩阵的所有元素取值均为1或0，横坐标为课节次，纵坐标为教学班。其中，值为0表示没有安排课程，值为1表示已经安排了课程。任何一种排课方案都可以在设计的编码空间中找到对应的解。

约束的处理 排课问题中的各类约束条件在设计的算法中都要得到对应和处理。本文采用惩罚函数法来处理约束。惩罚函数法是解非线性约束优化问题常用的一种方法[5-6]，

它根据约束的特点构造某种惩罚函数，并把它加到目标函数中去，使约束问题的求解转化為一系列无约束问题的求解。对无约束问题求解过程中违反约束的迭代点给予很大的目标函数值，从而迫使这一系列无约束问题的极小点逐渐收敛于约束问题的极小点。本文具体做法：如果一个种群个体染色体对应的解违反了某个约束条件（包括硬性约束条件、用户自定义约束条件），算法将根据其违反约束的程度给予一定的惩罚，使该个体具有较小的适应度值。这种处理方式可以保证在不损失种群数目的前提下，随着种群的进化，使不可行解的数量在整个种群中所占的比例越来越小，而可行解的数量则越来越多，并逐步趋向于最优解。

初始种群生成 初始种群是遗传算法迭代的起点，它选择的好坏将直接影响算法的效率[7]。在遗传算法中，要求初始种群内个体多样化，以保证较高的进化效率[8-9]。根据前文介绍，每个个体的染色体是行为40个时间片（即一个教学班一周的课表），列为教学班组成的二维数组。对每一个教学班来说，根据课程的周任课数，随机初始化到这一行中，用1表示，其他位数用0填充。所有的教学班均按此办法操作，就可以形成一个个体。按照种群的大小，产生一定数量的个体构成初始种群。对于固定课和预排课，初始化的时候要特别注意。

适应度函数设计 在遗传算法体系中，适应度是描述种群中个体优劣的主要指标，进化时根据个体适应度的大小优胜劣汰。参照以自然选择学说为核心的现代生物进化理论，遗传算法中的适应度对应着生物界中物竞天择、适者生存的物种生存能力，在算法执行过程中起到极其重要的作用。为了使用遗传算法来表示和求解排课问题，需要将排课问题的目标函数与种群个体适应度建立一种映射关系，从而在群体进化过程中实现对排课问题目标函数的寻优。

前文提到排课问题中，对一种排课方案的好坏评价是很复杂的，包含各课表元素的规则和要求——硬约束条件、用户自定义约束条件和软约束条件。使用遗传算法求解排课问题时，适应度函数的构造和设计尤为关键，是不可或缺的一步。综合考虑三类约束条件，本文提出适应度函数由两部分组成：不可违反代价f1（违反硬约束条件、用户自定义约束条件产生的代价）和可违反代价f2（违反软约束条件产生的代价）。本文设计的适应度函数的特点：当有违反硬性约束时（即使只违反了一个），那么个体的适应度将主要由f1决定；只有在没有违反硬性约束的情况下，个体适应度主要由f2决定。适应度函数为：

其中：

ρ是一个0～1之间的小数，用于条件f1和f2间的权重比例；αi为第i个硬约束条件、用户自定义约束条件的权重；βi为第i个软约束条件的权重。endprint

遗传算子设计 遗传操作是遗传算法的核心处理过程，是算法实现迭代寻优功能的最主要工具。在标准遗传算法中，遗传操作包括三种基本遗传算子，即选择算子、交叉算子、变异算子。

1）选择算子（Selection）。生物界进化机制中的选择操作能够实现个体染色体的复制延续，使各种生物能够保持各自性状，从而保证物种种群稳定。遗传算法也引入选择操作方式，选择的目的是优胜劣汰，它根据种群中个体适应度的大小，将适应度高的个体挑选出来，使其染色体有更高机率往下一代遗传，而逐步将适应度低的个体淘汰。因此，选择操作的实质是挑选，其作用是定向优化。在种群进化迭代的过程中，由于选择算子的定向优化作用逐代叠加，使整个种群个体都朝着适应度高的方向进化，从而使种群的品质越来越高。选择算子决定了种群中哪些个体染色体可以遗传复制到下一代，直接影响到种群的多样性。

为了提高算法的全局搜索能力，改进选择算子是最重要途径之一。选择算子有很多种处理方式，常见的方法有轮盘赌选择法、随机遍历抽样法、截断选择法和锦标赛选择法等，这些方法都有各自的特点和适用范围。本文在对常见的各种选择算子进行分析研究后，决定采用轮盘赌选择策略计算概率，并在此基础上使用最优保存策略进行挑选，结合使用这两种策略，保证种群最佳个体有更高概率向子代遗传，避免其在迭代过程中损失，加快遗传算法朝最优解收敛的速度。

2）交叉算子（Crossover）。为了模拟生物界物种繁衍的机制，遗传算法引入交叉操作，从而达到基因重组的目的，使父代个体染色体中的基因片段定向遗传到子代个体中去。交叉算子是通过交换两个父代个体部分对应基因片段来进行操作的，其结果是产生两个各自遗传一部分父代染色体基因的子代个体。交叉算子在遗传算法中起着最核心的作用[10]，经过交叉操作的处理，大大提升了遗传算法的全局搜索能力。

种群初始化时，每个个体对应的布尔矩阵的每一行中数值为1的元素个数等于其对应教学班的周课时数。在遗传算法执行过程中，不论是交叉操作还是后面将要介绍的变异操作，每一代每个种群个体都要遵循这个原则。单点交叉是传统遗传算法最常用的交叉操作方式，其做法是在个体染色体上任意选择一个基因位置作为交叉点，互换待交叉的两个父代个体在该交叉点右边的染色体片段，但这种操作不能满足周课时数规则，因此不能直接使用。考虑到课表问题的特殊性，本文采用矩阵染色体对应行之间分别进行局部交叉操作，具体操作时参照单点交叉的方式并对处理过程做了改良。为了保证交叉操作后的子代个体依然满足周课时数规则，在设计交叉操作时对交叉点的选取做了限制：只有两个父代染色体在交叉点前基因值为1的个数相同时，才允许交叉。交叉得到的两个子代个体分别继承了父代的部分基因。

3）变异算子（Mutation）。选择算子和交叉算子的引入已经能够保证遗传算法逐代促进种群进化，但是并不能保证找到种群中没有出现过的优秀个体。因此，单纯通过选择操作和交叉操作有可能只能得到局部最优解，而非全局最优解。遗传算法为了解决这一问题，引入了变异算子。变异操作是根据变异率pm将个体染色体中的部分基因值换成其他基因值，其结果是产生一个全新的个体。变异操作是遗传算法中生成新个体的另一种方式，它不仅增强了遗传算法的全局搜索能力，而且能够使种群具备多样性。

变异是模拟物种繁衍过程中基因突变而引入的遗传操作。在由初始种群中代表课表的大量随机个体逐代进化为完全符合学校教学需要的有效课表的过程中，变异操作的作用也至关重要。本文中设计的变异操作过程是这样设计的：进行变异操作前，在个体染色体上任意选取两个变异点a，b，定义变异前的个体染色体为chromosome；为了保证变异产生的新个体依然满足周课时数规则，在设计变异操作时对变异点的选取做了限制，只有当chromosome[a]+

chromosome[b]=1时才能进行变异操作；通过交换chromosome

[a]、chromosome[b]的数值，就产生了全新的个体。

算法控制参数和终止条件

1）控制参数。遗传算法中控制参数（包括群体规模N、交叉率pc、变异率pm）的选取不同，对算法的性能和结果影响很大，要想得到遗传算法的最优性能，必须确定最优参数的设置[11]。这里采用自适应策略调整交叉率pc和变异率pm，不仅提高了遗传算法的搜索效率和速度，而且可以抑制未成熟过早收敛，还能防止优良个体染色体遭到破坏。为此，定义某代种群中最优个体的适应度为fmax，种群的平均适应度以表示，定义f′为k-交换变异个体的适应度，是两个待交叉父代个体中适应度较大的一个，交叉率pc、变异率pm分别通过以下公式得到：

其中，k1、k2、k3、k4为小于等于1.0的常数。对于k2、

k4，因为或者，个体适应度低于种群平均适应度，于是给予较大的pc、pm，加大适应度差个体染色体被破坏的概率；而k1、k3可根据需要动态调节。pc一般在

0.75～0.95之间，pm 一般为0.005～0.01。

2）终止条件。遗传算法本质是模拟生物的进化与遗传，依据“生存竞争”和“优胜劣汰”的原则，借助选择、交叉和变异等操作，使所要解决的问题经过多次迭代计算，从初始解一步步逼近最优解[12]。这些操作使得遗传算法具备很强的全局搜索能力，同时造成其结果受到随机性的干扰。为避免算法缺乏有效的迭代停止条件，本文设计几种终止条件：如果种群进化至1000代，则终止算法；如果某代种群中个体的平均适应度与当代最优个体适应度的比值大于0.9时，则终止算法；如果最优个体持续保持10代，则终止算法。

以上设计的三种终止条件，遗传算法执行过程中如果符合其中任意一个条件，即认为算法达到收敛，可终止算法并返回排课结果。

3 结语

本文结合新形势下排课的实际问题，立足工作实践经验，总结抽象构建出排课问题的数学模型，并在传统遗传算法的基础上做了一系列改进来求解排课问题。本文针对排课数学模型设计了专门的染色体结构，优化了初始种群的生成过程，并在标准遗传算法的基础上对选择算子、交叉算子和变异算子等多方面进行改进，采用自适应策略调整交叉率pc和变异率pm，并借鉴模拟退火算法的思想调整个体适应度，根据适应度，按轮盘赌法和最佳个体保存选择策略复制子代染色体。目前，該算法已成功应用在东华博育云有限公司的排课产品中，实验表明能得到较满意的课程安排方案，运行效率高，课表中出现资源冲突现象显著减少，极大地缩短了学校教务管理人员排课工作消耗的时间。endprint

博育云是上市公司东华软件股份公司旗下的智慧教育服务平台，由东华博育云有限公司负责研发和运营，致力于为全国教育行业用户提供优质的信息化产品。博育云教育产品以国家政策为依据，以“博创治教、智慧育人”为核心理念，应用系统贯穿教育活动中教、学、研、评、考、管等多个环节，并基于大数据、云计算、虚拟化、移动互联等技术，为用户提供区域智慧教育综合解决方案、数字化校园解决方案，打造云时代以新高考解决方案为核心的教育服务商。

参考文献

[1]Saleh H A， Chelouah R. The design of the global navigation satellite system surveying networks using genetic algorithms[J].Engineering Applications of Artificial Intelligence，2004，17（1）：111-122.

[2]Tao Q， Liu X， Xue M. A Dynamic genetic algorithm based on continuous neural networks for a kind of nonconvex optimization problems[J].Applied Mathematics and Computation，2004，150（3）：811-820.

[3]贺波.基于带时间窗集送货双需求巡回车辆路径优化问题研究[D].北京：北京科技大学，2011：27-28.

[4]陈冬亮.排课的数学模型和算法在教务管理系统中的应用研究[J].电脑知识与技术：学术交流，2006（6）：12.

[5]席少霖.非线性最优化方法[M].北京：高等教育出版社，1992.

[6]Coello C A C. Theoretical and numerical constrainthandling techniques used with evolutionary algorithms： a survey of the state of the art[J].Computer Methods in Applied Mechanics & ngineering，2002，191（11）：1245-1287.

[7]郭建蓬，王可人，海磊.MANET中基于遺传算法的带宽计算[J].计算机工程与应用，2005，41（26）：154-157.

[8]Nandakumar P， Rummel J L， Hartvigsen D， etc. A Subpath Ejection Method for the Vehicle Routing Problem[J].Management Science，1998，44（10）：1447-1459.

[9]Angel E， Bampis E， Pascual F. An exponential （matching based） neighborhood for the vehicle routing problem[J].Journal of Combinatorial Optimization，2008，15（2）：179-190.

[10]潘正君，康立山，陈毓屏.演化计算[M].北京：清华大学出版社，1998.

[11]吴少岩，许卓群.遗传算法中遗传算子的启发式构造策略[J].计算机学报，1998（11）：1003-1008.

[12]云庆夏，黄光球，王战权.遗传算法和遗传规划：一种搜索寻优技术[M].北京：冶金工业出版社，1997.endprint