摘要：遗传算法用于解决排课系统问题是目前国内外的热门研究课题。在教学资源有限的条件下，传统的遗传算法一般难以满足师生的满意度要求。本文创新地引进时间编码模式，对传统遗传算法染色体的编码模式进行了修正，并给出了以该种编码来实现排课系统的具体做法。与传统遗传算法解决排课系统的模式编码相比，该编码模式提高了模式的“灵活性”。本文对修正的编码模式进行了详细的描述，阐述了它能提高满意度的原因，并给出了具体的算法设计。实践证明：这种编码模式设计得出的课程安排可以达到了师生的高度满意。
关键词：遗传算法; 时间编码模式; 满意度; 灵活性

Application of Genetic Algorithm to the Arrangement of Curriculum Schedule
Abstract: Genetic Algorithm used to the solution of curriculum arrangement is the heat research topic domestic and abroad today. Generally, when teaching resource is limited, the curriculum derived from traditional Genetic Algorithm is hard to meet the needs of students and teaching stuff. In this paper, a kind of time code used to modify the code of traditional Genetic Algorithm chromosome is creatively designed, and the application of this code to the curriculum arrangement is presented. Compared with the solution of curriculum arrangement system which applied traditional Genetic Algorithm, this kind of time code improves the “flexibility” of the model. This paper expounds the modified code model, the reason how it improves satisfaction and the concrete algorithm design. The practice has proved that the curriculum schedule induced by the time code meet the satisfaction of students and teaching staff exactly.
Key words: Genetic Algorithm; time code model; satisfaction; flexibility

绪论：
１、 相关定义：

为了更好地阅读和理解本文，下面给出本文中的一些相关定义：
普通班级：指的是一个学校中的所有专业班级，具有如下特点：若记一个普通班级的学生集合为 　 ，若 则 并且 ，其中代表全校全体学生
。
特殊班级：指的是一个学校中所有能够上课的班级中除去普通班级的班级，如体育课的班级，英语课的班级，其他公共课的班级等。具有如下特点：若记特殊班级的集合为 ，同时全校中所有班级的集合为 ，所有普通班级的集合仍为 ，则有 并且 。

时间编码模式：指的是把一个普通班级的一个星期的排课时间划分为授课时间段的一种模式，具体可以根据不同的学校的情况由用户自定义。

２、 文献探讨：

排课问题研究：
1960 年代，开始有学者从事计算机辅助排课的研究，Appleby等人开始使用简单的经验法，来解决小规模的排课问题[1]。七十年代到九十年代，又有些学者开始了利用矩阵向量方法来对排课问题进行研究，能够解决规模稍大的问题，但是仍然存在缺陷。到了九十年代后，国内外及台湾很多学者转而采用遗传算法对排课问题进行了研究，随着遗传算法的发展，有了一定的结果，但是仍然未能解决满意度的问题，本文正是在这种情况下，通过结合前人已有的成果来研究和实现排课系统的[2]。

遗传算法：

遗传基因算法是由Holland 于1975 年所提出[3]。GA 的基本观念源自于达尔文的进化论（Darwin's Theory of Evolution）中适者生存的理论。

一般遗传算法操作伪代码如下[4]：
BEGIN
t = 0;
Initialize P(t);　　　　　　　　　　　 //初始化种群
Evaluation P(t); //评价种群
while ( NOT Terminate-Condition ) do
begin
t = t + 1;
Selection P(t) from P(t-1); //选择复制
GA-Operator P(t); //选择杂交，变异
Evaluation P(t); //评价新种群
end;
END.

从伪代码可以看出其一般步骤包括：初始化种群（Initialize P（ｔ）），评估第一代（Evaluation　P（ｔ）），当世代遗传变异结束条件不成立时，则：从上一代从复制产生下一代，进行遗传算子操作，重新评估新一代。即遗传算法就是不断地在产生新一代，遗传算子操作，评估新一代中循环直至最终达到最优解或近似最优解。

一、 染色体编码及具体实现：

１、 数据输入要求：

随着各个学校具体情况的不同，排课系统中数据的输入与格式也不一样。一般来说，系统数据的输入包括：教室统计表，班级统计表，教师统计表，课程统计表。教室统计表的主要字段有：教室编号，教室名称，教室大小，多媒体配备情况，教室功能，所属校区。班级统计表的主要字段有：班级编号，班级名称，班级人数，所属院系，所属校区。教师统计表的主要字段有：教师编号，教师姓名，教师职称，授课喜好时段。课程统计表的主要字段有：课程编号，课程名称，授课教师，上课班级，多媒体要求，课程功能，周次，周学时，所属校区。这些统计表中的字段我们的系统有些是用的着的，有些跟排课过程没有任何关联，我们结合排课要求，暂且把它们抽象地分为：硬性条件，软性条件。

硬性条件包括：

(1). 时间要求：同一个教师，一个时间只能分配一门课；同一个班级，一个时间只能上一门课；

(2). 教室要求：教室容量应该大于学生数；教室特定要求，实验课要求；教室特定要求，多媒体要求

(3). 同一门课程不要重复在同一天上课

软性条件包括：

(1). 尽量提高教师对课程表的满意度，即提高其课程表与他的喜好时段的吻合度。

(2). 尽量提高班级学生对课程表的满意度，即提高课程表中课程的均匀度。

２、 排课数据分流：

根据以上的输入分析，结合遗传算法的特点，我们确定以班级为单位来进行课程的安排。首先根据上课班级的特点把一个学校的所有班级划分为普通班级和特殊班级。排课首先安排特殊班级所属的特殊课程，然后再安排普通班级的普通课程。根据我们对某高校的统计，发现特殊班级的课程最多只占整个学校课程的20%，我们即使用普通的算法先对特殊班级的课程进行安排，资源对那些课程来说总是足够的，于是那些课程的满意度总是可以保证很高的水平，然后再利用遗传算法对普通班级的课程进行安排。

３、 染色体编码前的准备数据：

如上所述，我们虽然采用了普通的算法与遗传算法相结合的方法来处理排课问题，但是由于资源是统一的，故复杂班级和普通班级的染色体编码是统一的。由输入的数据我们可以对遗传操作中所需的染色体结构作如下编码：

首先扫描所有的普通班级，根据其班级的课程特点确定时间编码模式。这种时间编码模式根据具体的应用而具体确定，在我们实现了的中山大学排课系统中，我们根据普通班级一个星期所含有的连续3节课的次数来确定模式。如下所示：

扫描过程即判断所属该普通班级的课程中到底有多少连上3节课的课程，具体得出结果后就给各个普通班级的时间编码模式按上面的表格定义下来，其中有多个的选项的，则必须使用Rand()随机确定。当然这些在这种情况下确定的模式是可以改变的。

然后根据模式给每个普通班级的时间划时段编码。例如，04计算机A班的模式为3135
则我们有下面的时段编码：

上表说明如下，一天分4个时段，上午两个，下午两个。如上表，周一周三周五的上午第二个时段即2，10，18分别是从3-5节的，说明是上3节课的。其它时段全部供上2节课。
这种遗传编码方式的优点如下：

1．这种编码方式可以为各个专业的班级安排一种或者几种模式，进行杂交时，可以达到更优秀的遗传效果。

2．这种编码模式可以为各个班级指定不同的设计模式，并在遗传的过程中受到变异的影响，这样可以达到更优
秀的遗传结果。

3．这种编码方式可以很容易地对染色体编码进行改变，有多种可供选择的模式，扩展性强，从而提高该算法的通用性。

4．这些3节课的分布尽量达到了均匀，达到了普通班级上课时间尽量均匀的要求。

模式确定后，就可以确定每一个班级的编码了.

这里就涉及到编码解码问题， 这种算法不难，只要建立一个对应表就可以了。

教师编号编码：
就是用一个UINT代表的6位正整数来表达任意一个教师的基本信息，这样就可以在一个整
数中表达很多信息，具体如下所示：
教师的编码，统一采用6位来编号，具体的编码及相应的意义如下

课程编号编码：
类似于教师编号编码，用一个UINT代表的10位正整数来表达任意一个课程的基本信息，这
样可以在一个整数中隐藏很多遗传算法所需的课程相关的信息，具体如下所示：

课程的编号，课程统一采用10位数来编号，具体编码及相应的意义如下

普通班级编号编码： < 类似于课程编号编码，也是用一个UINT代表的10位正整数来表达任意一个普通班级的信息，
这样可以在一个整数中隐藏很多遗传算法所需的班级相关的信息，具体实现如下所示：

班级的编号，统一采用10位来编号， 具体的编码及相应的意义如下：

这里用到了几个假定：假定一个大学专业总数不超过299个，假定学院总数不超过
99个，假定最多只有九个年级，最多只有9999个基本班级，等等，这些假定都是合理的。

染色体的编码实现：

前面研究了很多染色体编码实现前的一些准备，就是为了现在这里更好地进行染色体编码服务的。具体来说，我们的染色体编码采用如下格式：
struct GenoType{//染色体的数据结构
ClassType *commonclass;//普通班级信息编码数组，数组大小为普通班级总数
TeacherTime *teacherTime;//教师授课时间编码数组，数组大小为教师总数
double fitness;//该个体的绝对适应值，由教师,班级课程满意度决定
double rfitness;//该个体的相对适应值，由绝对适应值得到
double cfitness;//该个体的累加适应值,由相对适应值相加而得
};
其中ClassType和TeacherTime是两个预定义的数据结构，我们给出如下：
struct ClassType{//普通班级的课程编号编码实现
UINT ClassId;//班级编号?Time_Mode?ClassMode;Time_Mode ClassMode;//时间编码模式
UINT CourseIdTimeArray[20];//这个数组的元素是课程编号
};
struct TeacherTime{//教师的时间编码
UINT TeacherId;//教师编号
int TeacherTimeBit[45];//教师授课时间表
};
具体的还有其他的辅助数据结构，限于篇幅，我们不在此一一给出。

遗传操作的实现：

遗传算法的精髓在于染色体编码和遗传操作的具体实现，在排课系统中更加如此。不同于其他研究人员的遗传操作实现，我们给出了特殊的实现方法。具体如下：

初始化：首先，我们确定每一个普通班级的时间编码模式，具体根据不同的实际情况而定。然后根据普通算法中已经安排的特殊课程的信息结合时间编码模式，我们对整个种群进行初始化，即给GenoType染色体填充相应的数据。

对种群的评价，我们采用了教师满意度结合班级课程的均匀度来综合评价，如我们上面的染色体可以看出，这个是不难给出的，我们的teacherTime里面保存了一个个体中所有教师的时间分配情况，只要和教师的喜好时段进行比较，我们就可以得出教师的满意度，为了达到满意度的要求，我们的状态评价函数中采取了以下措施：当老师的教学方案有冲突时，我们给出的了一个很低的评价值，这样这种状态被采纳的可能性就很低。我们的commonclass这个数组保存着普通班级的编码信息，可以根据里面有的CourseIdTimeArray来具体实现班级课程的均匀度判断。结合这两点，我们的种群中所有个体的适应值即可以由满意度结合均匀度来给出。
对种群的筛选，我们采用了效果较好的轮盘赌的方案来进行，这个和其他研究人员所采用的方案是一样的。

杂交的实现：杂交和变异是遗传操作的重点，我们根据自己的染色体编码中的时间编码
模式所确定的结果，我们规定如下杂交实现的原则，必须把两个个体中不存在任何关联的班级信息全部交换，这样，能够成功地解决杂交过程中看似错综复杂的关系，又很好地处理了杂交算子的模式定理。而这样的做法是有一个前提的，跨班级上课只存在于相同学院的同一个年级中。

变异的实现：同上面给出的杂交实现的原则，我们也可以根据时间编码模式确定如下的变异实现原则，即对一个即将进行变异的个体，必须在这个个体内随机选择整个学院的所有年级来进行课程表的重新生成，只要保证用普通算法实现的特殊课程不变动即可。

遗传算法的具体流程我们给出如下：
void GACourse() {
generation=0;//种群代数初始化为零
initialize();//种群根据时间模式和已安排的特殊课程信息进行初始化
evaluate();//评价初始种群
keep_the_best();//保留精英，这个大部分遗传算法的应用中都会采用的
while(generation<MAXGENS)
{
generation++;//种群代数自增一
select();//从当代中选择适应能力强的个体
crossover();//随机对选择个体按如上原则进行杂交
mutate();//随机对选择个体按如上原则进行变异
evaluate();//衡量新一代种群中每个个体的性能
elitist();//保留上一代与新一代的最优个体
}
//遗传结束后的处理，记住，我们的染色体中没有教室分配的表达
AllocateRoom();//分配教室及解码返回给输出表
}

结论：

本文对使用遗传算法研究及实现排课系统的编码模式进行了深入地讨论，以“高排课满意度”为目标，对传统编码模式进行了修正和改进，并对其性能进行了分析。该方案可以在合理的时间内进行令人比较满意的排课，而且该种编码模式可以很容易的迁移和改变，具有较高的扩展性，因此具有较通用的使用价值。

参考文献：
[1] J.S.Applely, “Techniques for Producing School Timetables on a Computer and Their Application to other Scheduling Problems”, TheComputer Journal, Vol.3, pp.237-245, 1961.
[2]王富民，基因算法于排课问题上之研究，国立台湾师范大学信息教育研究所硕士论文， 2001。
[3] J.H.Holland, Adaptive in Natural and Artificial Systems, MI. Univ. Mich. Press, 1975.
[4]演化程序 遗传算法和数据编码的结合 [美] Z 米凯利维茨 著 北京 科学出版社