遗传算法在排课系统中的应用

遗传算法在排课系统中的应用

[摘要] 排课问题是学校教务管理的一个重要环节，排课方法有很多种。一般常见的排课方法是穷举法，即将教师、班级、课程在特定的时间安排到符合要求的教学地点。但是用穷举的办法排课，其效率十分低的，时间复杂度相当高。遗传算法是一种模拟自然进化过程搜索最优解的方法。本文结合遗传算法课程的学习浅谈使用遗传算法解决排课问题的一些思路。

[关键词] 遗传算法 穷举法 排课

一、引言

在教学管理工作中，每学期排课是一个十分繁琐的工作。排课设计到大量的数据信息，如课程、班级、教师、教学地点等等。排课过程实质上就是将班级、课程和教师在特定的时间安排到特定的教学地点（如机房、体育馆、教室等等）。如果涉及到的信息比较少，通常使用人工排课就可以快速完成。但是如果一个学校的班级、课程、教师等数据量非常大，这时再使用人工完成就十分困难了。随着各个学校相继采用信息化管理，采用计算机排课成为必然趋势。

使用计算机排课，首先要解决的问题就是采用什么样的算法，如果很多算法都能解决问题，则选择一种效率最好的算法。排课问题中，我们通常会首先考虑使用穷举的方法。如果使用穷举法为某个班级排课，则先找出该班级的所有课程，再找可以讲授这门课的所有教师并选择其中一位教师，然后再考虑某个时间段有无空余教室，最后选择其中的一间空余教室安排该班级上课。

事实上，很早以前就有许多研究人员对排课问题做过分析。S.Even等人在1975年的研究中就已经证明排课问题是一个NP难问题，即若使用穷举法之外的算法找出最佳解是不可能的。假设某个学校一个星期有n个时间段可以排课，该校有m位教师需要参与排课，平均每位教师一个星期要上k节课，那么在不考虑其他条件的情况下，则能够得出的可能组合就高达种。可想而知，如此高的复杂度，是目前计算机无法承受的。因此我们必须寻求其他优秀的算法来解决排课问题。

二、遗传算法

遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，它最初由美国Michigan大学J.Holland教授于1975年首先提出来的，并出版了颇有影响的专著《Adaptation in Natural and Artificial Systems》，GA这个名称才逐渐为人所知，J.Holland教授所提出的GA通常为简单遗传算法（SGA）。

遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。每个

个体实际上是染色体(chromosome)带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现（即基因型）是某种基因组合，它决定了个体的形状的外部表现，如黑头发的特征是由染色体中控制这一特征的某种基因组合决定的。因此，在一开始需要实现从表现型到基因型的映射即编码工作。由于仿照基因编码的工作很复杂，我们往往进行简化，如二进制编码，初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解。

与传统的优化算法相比，遗传算法主要有以下特点：

1、遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接决策变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学中的染色体和基因的概念，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便的应用遗传操作算子。

2、遗传算法直接以适应度作为搜索信息，无需导数等其它辅助信息。

3、遗传算法使用多个点的搜索信息，具有隐含并行性。

4、遗传算法使用概率搜索技术，而非确定性规则。

遗传算法提供了一种求解复杂系统问题的通用框架，它不依赖于问题的具体领域，广泛应用于许多科学，例如函数优化、组合优化等等。随着问题规模的增大，组合优化问题的搜索空间也急剧增大，有时在目前的计算上用枚举法很难求出最优解。对这类复杂的问题，人们已经意识到应把主要精力放在寻求满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法对于组合优化中的NP难问题非常有效。因此采用遗传算法来解决排课问题是一种有效的方法。

三、问题描述

实际排课时，通常会考虑到各门课程教学大纲和教学进度教学计划，特别是高校理工科学生每学期有一到两周时间搞生产实习。本文这里所论述的算法只考虑通常情况，即通用性。也就是说本文论述的算法只考虑一般情况下安排教师、课程、班级、上课时间段和上课教室这五个要素，而不考虑教学进度和教学计划。

在排课时，主要任务是将班级、课程、教师安排在一周内，而且不发生冲突，即不存在同一间教室同时安排两个班级学生上课或者同一个老师在同一个时间段内上两个班的课程。因此，这里首先给出如下问题描述：

假设某学校有C个班级，S门课程，T位教师，R间教室和P个教学时间段，给出以下五个集合：

教室集合集合R(R1、R2、…、Rn)，其中每间教室分别可以容纳（X1，X2，…,Xr）人；

班级集合C(C1,C2,…,Cn),其中每个班级分别有（K1,K2…Kc）人，其中有x各班级合班上课；

课程集合S(S1,S2…,Sn),每门课程对应Ci个班级、1位教师（1<=ci<=cn）；

教师集合T(T1,…,Tn),每位教师对应Sm门课程、Cn各班级,在初始是设定每个教师的排课要求，即每个教师所教授的课程事先设定。

时间段集合P(P1,…,Pn),这里是假设每周周一到周五上课，每天分成五个教学单元，每个单元2课时。例如，周一上午第12两节课用“11”表示，周一上午第34节课用”12”表示，周一下午总第56节课用”13”表示，以此类推，则每周所有的教学时间单元可构成时间集合P(11,12,13,…,,55)，总共为25个元素。

由于遗传算法中是以个体适应度大小来评定每个个体的优劣程度，从而决定其遗传机会的大小。为配合适应度的计算，必须给出一定的约束。这里考虑一般情况下，最基本的排课中所涉及到的约束条件或约束规则如下：

1、不能出现学生上课冲突，一位教师或者一个班级或者一个教室在同一时间段内只能安排一门课程，即同一间教室在某个时间段不允许多个班级上课，同一个教师不允许在某个时间段同时上两门课，同一个班级不允许出现某个时间段有两门课程同时进行；

2、分配的教室可容纳人数应该大于学生数。但是要避免资源浪费情况，比如一个只有30个学生的班级被安排到能容纳250人的阶梯教室上课，这类情况尽可能避免。

3、尽量在早上安排必修课，而下午安排选修课，晚上尽量不排课；

4、尽可能满足个别教师的特殊上课时间要求；

5、一门课尽量分散在一个星期中，即某天上完某一门课后，要隔一天以上再上这门课，以使教师有充足的时间备课和批改作业，而学生也有足够的时间复习消化；

6、一个教师的课不能排满一整天；

7、学生课表中的上课时间不能过分集中，应避免一天课程很满而另一天却一整天没课的情况。

四、排课算法设计

（一）染色体编码

编码是应用遗传算法时要解决的首要问题，也是设计遗传算法时的一个关键步骤。编码方法影响到交叉算子、变异算子等遗传算子的运算方法，大很大程度上决定了遗传进化的效率。在本算法中，我们可以采用教师、班级、课程以及教室、和教学时间段的组合作为染色体，即使用每个教师的课表作为染色体：

教师ID 班级ID 课程ID 教室ID 时间ID

初始，可以为所有教师、班级、课程、教室和时间段分别给出唯一的编号，并存放到数据库的5个表中。例如，张老师编号为1012，他所带的班级08级计算机2班和3班编号分别为0802和0803，他所讲授的课程《操作系统》编号为2307，若设可以容纳这两个班上课的教室编号分别为3312和3314，若假设0802班有两次课安排在周三上午三四节和周五下午一二节，则可以得到一个组合为“1012 0802 2307|3312 3253”，即得到一条有20为十进制数表示的染色体。每条染色体代表一种可能的排课结果，至于排课结果的优劣，则由适应度函数评估染色体适应值来决定。

（二）初始群体的产生

初始群体的产生，可以采用随机选取上课时间和随机选择符合要求的教室的办法。由于本算法中每位教师可以教授的课程，以及每个班级每学期要学习的课程是事先设定的值，因此就很容易得到由若干染色体组成的初始群体。

（三）适应度计算

本算法的适应度函数如下所示：

本算法适应度函数设计的思想，是对每条染色体中存在的冲突类型进行加权求和。其中权值为代表了如前所述的第i条约束规则的重要程度。表示某条染色体是否违反了第i个约束规则，如果违反了该规则用1表示，否则用0表示。最后求和加1再取倒数，得到某条染色体的适应值。染色体适应值越大，表示其拥有较好的授课时间段和教室，那么它在下一代演化中生存的概率就比较大。

(四)选择

选择运算是把当前群体中适应度较高的个体按某种规则或模型遗传到下一代群体中。一般要求适应度较高的个体将有更多的机会遗传到下一代群体中。选择操作的方法有许多，如轮盘赌选择法（roulette wheel selection），局部选择法（local selection），锦标赛选择法（tournament selection）等。

本算法中采用局部选择法的一种即截断选择法。在截断选择法中，染色体按适应值由高到低排序，只有最优秀的个体才能被选作父个体。其中，用于决定染色体被选作父个体的百分比的参数称为截断阀值Trunc，其取值范围为50%~10%。在该阀值之外的个体不能产生子个体。

（五）交叉

交叉运算是遗传算法中产生新个体的主要操作过程，它以某一概率相互交换某两个个体之间的部分染色体。本算法的交叉操作，是根据选择操作的结果选取两个较好的排课结果作为父体，将两个染色体的上课教师和上课时间段进行交叉。如以下两条染色体代表的是编号为1012的老师教授0802班的编号分别为2307和2312的两门课程，上课教师分别为3312和4207，上课时间段分别为周三34节周五56节和周二56节和周二78节。则可以对这两条染色体做交叉操作。

1012 0802 2307|3312 3253

1012 0802 2312|4207 2324

（六）变异

变异运算是对个体的某一个或某一些基因座上的基因值按某一较小的概率进行改变，它也是产生新个体的一种操作方法。本算法的变异操作，是先随机改变染色体的任一授课时段，授课时段抽取设定在一定范围之内。设定一个变异概率p，在变异是产生一个随机数r,当r结论

排课问题一直是一个困扰教学管理人员的十分繁琐的问题，通常情况下排课采用回溯穷举的办法实现，但是这种方法复杂度相当高。遗传算法作为一种对生物遗传和进化过程的计算机模拟，使得各种人工系统具有良好的自适应能力和优化能力。本文正式在这一基础上提出了一种能够有效解决和优化排课问题的方法。

参考文献：

[1]唐勇,唐雪飞,王玲.基于遗传算法的排课系统. 计算机应用.2002(1):93-94,97.

[2]H.L.Fang,”Genetic Algorithms in Timetabling and Scheduling”,Ph.D. Thesis,Department of Artificial Intelligence, University of Edinburgh, UK,1994.

[3]E.K.Burke,D.G.Elliman,R.F.Weare,”A Genetic Algorithm Based

UniversityTimetabling System”, East-West Conference on Computer Technologies in Education, Crimea, Ukraine, 1994, pp. 35-40.

[4]王小平,曹立明.遗传算法——理论、应用与软件实现.西安：西安交通大学出版社，2002:31-33.