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

四川大学锦城学院 计算机与软件学院 宋亚静 徐 艳

随着教育的不断发展，因其复杂和多样性，排课越来越成为很多学校的难题，它是一个典型的多组合优化问题，问题的解就是求出时间，教室，班级，教师，课程之间的对应关系，正常来排的话会出现多组不同的解，每组解中有时还会出现例如课程冲突，时间冲突等各种各样的问题，本文将针对这些问题利用遗传算法进行优化，得出最佳排课方案。

1 约束条件

1.1 硬约束条件

此系统的约束条件分为硬约束和软约束两种，其中硬约束具体是指由于资源的局限性而必须满足的条件，不满足这些条件该课表就会发生冲突。本文主要考虑时间、教师、班级、课程、教室五个元素，对这5个元素求笛卡儿积即D×T×C×L×R得出所有的排列组合，一种结果称为一个单元；对时间，教室求笛卡儿积得出的结果称为时间-教室对，记为D×R={d1×r1，d1×r2，...，dm1×rm5}，教师，班级，课程不变，只需要找出最佳的时间-教室对，即可满足问题最优解。如下是对元素的数学描述：

时间集合为D={d1，d2，...，dn1，dm1}，其中1 ≤n1≤m1；

教师集合为T={t1，t2，...，tn2，tm2}，{x1，x2...xm2}为所对应老师教的课程数，其中1≤n2≤m2；

班级集合为C={c1，c2，...，cn3，cm3}，{y1，y2...ym3}为所对应班级的学生人数，其中1≤n3≤m3；

课程集合为L={l1，l2，...，ln4，lm4}，其中1≤n4≤m4；

教室集合为R={r1，r2，...，rn5，rm5}，{z1，z2...zm5}为每个教室可容纳的人数，其中1≤n5≤m5。

同一时间，教师只可能教一门课程，不可能同时教两门。

将一师一课设为A，A≤1，A只能取0或1，当A=1时，意为教师tn2在dn1这个时间在rn5这个教室上ln4这门课程；当A=0时，结果不成立。

同一时间，班级只可能学一门课程，不可能同时学两门。

将一班一课设为B，B≤1，B只能取0或1，当B=1时，意为班级cn3在dn1这个时间由tn2这个教师在上ln4这门课程；当B=0时，结果不成立。

1.1.2 生态地理资料 以《云南农业地理》《云南省种植业区划》和《云南省农业气候资料集》[7-9]等资料为基础，分析整理云南128个县(市、区)的生态气候类型和稻作种植业区划。

同一时间，教室只可能上一门课程，不可能同时上两门。

将一室一课设为C，C≤1，C只能取0或1，当C=1时，意为教室rn5在dn1这个时间由教师tn2在上ln4这门课程；当B=0时，结果不成立。

每个教室能容纳的人数必须大于每个班级的学生人数，即zm5≥ym3，否则该教室不可为当时上课的班级所使用。

1.2 软约束条件

软约束指的就是对硬约束后的课表进行细化，使之更贴近现实，如：学生大多都不想每天的课集中在一起，所以排表时应该注意分散，同理教师每周的课程也应被均匀分配到周一到周五；有些课对上课环境有要求也应尽量满足；应为班级分配与之学生人数相当的教室，避免资源浪费；晚上注意力下降，尽量少安排或不安排专业课等。软约束分的情况较多，每个学校情况不同，应视具体情况而定。

2 遗传算法

2.1 基本原理

自然界有一个很神奇的现象就是生物的进化大体上都朝着好的方向发展，众所周知人类的基因组合是随机无约束的，但随机的结果却总是朝一个方向进行，遗传算法（Genetic Algorithms，GA）就是基于这样的自然现象产生的，它是一种基于自然选择，借助生物进化优胜劣汰的机制和基因重组、突变的遗传机制的全局搜索算法，从一组随机产生的初始值（种群）开始，种群中每个个体都是经编码的有特征的染色体，初始值产生后根据优胜劣汰的法则不断迭代进化，每一代都选择适应度较高的个体遗传到下一代，产生新种群，最后一代种群中最优的个体经过解码操作（基因型向表现型的映射），可以近似作为该种群的最优解。

2.2 遗传算法流程

首先随机初始化一批可行解，计算每个个体的适应度，然后判断当前迭代次数是都达到最大，若达到最大迭代数，输出最优解，结束；若还没有达到，就利用选择，交叉，变异等操作产生新一代种群，迭代数加1，再去判断当前迭代数是否达到最大，依此类推。

2.3 染色体编码

对排课问题，所有可能的排课结果组成的空间称为问题空间，每一条结果的基因型组成的空间称为编码空间，由问题空间向编码空间的映射称为编码，反之称为解码，解码一般用于末代种群的最优个体。传统的编码方式有浮点数编码和二进制编码。因二进制编码会导致染色体串过长，所以本文利用十进制编码方式，简单易懂且不存在进制转化问题。

2.4 适应度

通俗来讲，适应度就是为使结果不冲突而把约束条件根据一定规则转化成数字的形式，适应度函数是用来评估每一条产生的结果好坏的函数。函数值越大说明个体的适应能力越强，反之说明越弱。选择适应力较强的个体遗传到下一代，使其优秀基因能够迭代下去。现为其制定评分体系来计算个体的适应度：若满足一条硬约束+10，反之，-10；满足一条软约束+5；每个教室的资源利用率（班级总人数/教室总座位数*100%）若大于70%，+10，若资源利用率大于100%，则-10，该结果不成立；学生每天的课分散均匀（上下午都有）+5，教师每周的课分散均匀（不在同天或两次课间差2天）+5，反之，-5。

设置初始化适应度F为20，最终的结果适应度为F(i)，硬约束和教室资源为f1，不满足记为f2，软约束条件即课是否分配均匀为f1’，不满足记为f2’，公式即为：F(i)=F+f1+f2-f1’-f2’。当最终结果F(i)>20时，即为一个新的个体，大于20的值离20越远，越接近最优值，反之，当F(i)＜20时，即为冲突，小于20的值离20越远，被抛弃的概率就越大。

2.5 遗传算法的操作

（1）初始化种群

本文采用随机生成一批可行解的方式初始化种群，这种方式的好处是随机可以使初始种群分布更均匀，但产生的种群中有可能会有些不满足硬约束的结果，因此需对每一个结果筛选，不满足条件的直接舍弃，再重新随机生成，再筛选，直到种群中所有的结果都满足条件。

（2）选择

选择操作用来确定哪些个体可以遗传到下一代，遗传算法使用选择算子对种群中的个体进行选择，适应度较高的被遗传到下一代的概率较大，较低的被遗传到下一代的概率较小，选择的目的是为了避免基因缺失。本文采用轮盘赌法，也称比例选择方法进行选择，其思想就是每个个体被选中到下一代的概率与它的适应度成正比。

（3）交叉和变异操作

交叉操作是生成新个体的主要方式，其思想就是将两个个体的部分基因互换产生新基因个体，交叉算子分为很多种，本文采用的是单点交叉算子，如图1所示。变异操作是指将染色体编码中的某些基因用该基因的等位基因代替，形成一个新个体，变异操作是产生新基因的辅助方法，以较小的概率存在于遗传算法中，保证了种群的多样性，防止出现过早收敛。

图1 单点交叉算子示例图

（4）搜索终止条件

计算出一轮染色体的适应度后，利用轮盘赌法选出概率较高的个体，概率较低的个体可以通过交叉和变异重新产生新个体，再计算，直到遗传达到最大迭代数或当连续多次前后两代个体最佳适应度的值相差很小，终止执行。

总结：本文详细介绍了遗传算法在排课系统中的应用。排课问题是一个复杂的多目标优化问题，而遗传算法在不断的迭代之后会产生出近似最优解，收敛性较好，其次，它基于随机概率规则，可以使搜索更为灵活，再者它的扩展性较好，可较容易的与其他方法混合使用以达到一个综合优化的效果。在智能化的今天，越来越多求最优解的问题被大众关注，遗传算法也越来越被广泛使用，它解决了数学理论很难解决的问题，是一个很不错的求最优值的算法。