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

李文蕙，刘 嵩

武汉软件工程职业学院，湖北武汉 430205

0 引言

人工编排课程表是教务科人员在进行教学管理中最为头疼的工作之一。它涉及到很多的硬软件资源和内外部因素，如：时间、地点、教师、学生以及课程等。尤其是随着高职院校的不断扩招而硬软件设备没有及时更新和增加，造成了人多教室少、课程多时间少等状况。这些问题使得学院系部的教学管理工作无法正常进行。传统的人工排课方式存在有以下几个方面的问题：1）人工编排课程表工作量大；2）人工编排课程表依赖于人为因素；3）人工编排课程表可维护性差；4）人工编排课程表安全性差。

编排课程表是一项需要认真计划，合理安排，科学部署以及没有冲突的工作。在编排课程表过程中，需要最大化的利用所有资源并充分的发挥学院所能提供的资源。这些资源包括人力、物力以及时间空间等。

1 排课算法核心属性的确定

排课问题就是指如何避免在有限的教学资源里，授课人员、班级、教室、上课时间以及课程之间发生冲突。当授课人员、班级、教室、上课时间以及课程分别能够确定时，就可以进行排课工作了。排课问题主要集合描述及核心属性为：

1）授课人员集合E={e1,e2,e3,…,ek+1,…en}。授课人员的员工号为主键。

2）班级集合C={c1,c2,c3…,cm}。其中，每个班级所对应的人数为 S={s1,s2,s3,… sn}。

班级的班级号为主键。

3）教室集合 R={r1,r2,r3…rk,…rm+1…,rn}。

4）上课时间集合T={t1,t2,t3…,tn}。其中，一周的上课时间为星期一至星期五的白天（本校晚上不排课且不考虑特殊节假日）并以2课时为1节课，一天分为4节课。

5）课程集合D={d1,d2,d3…,dn}。课程的课程号为主键。

2 排课模型的建立

一个排课算法排出了一周的课程安排，其实质就是一个包含了授课人员、班级、教室、上课时间以及课程的五维向量（a1，a2，a3，a4，a5）。

设nk为授课班级ck的一周课程的总课时数，则

一张课表可以表示为n×5的矩阵，该矩阵即为问题求解中的目标矩阵。

在实际的排课中，教务科需要按照一定要求进行排课才能使最终得到的课表正确并且合理。那么，排课里每一个要求其实就是一个约束条件。一般来说，一个恰当合理的课表需要满足以下约束条件：1）一个授课人员在同一个时间段里只能上一门课程；2）一个班级在同一个时间段里只能上一门课程；3）一个教室在同一个时间段里只能上一门课程。

为了更好的开展教学工作，保证教学质量以及便于学生对知识的吸收和理解。在排课过程中还应该注意一些软约束条件。

如：1）一个授课人员每天的课时量不建议超过3节课；2）教室的座位数建议大于在该教室上课的班级人数，但是也要尽可能的避免大教室被小班级所占用。如：35人的班级使用能容纳100人的教室；3）针对不同性质的课程建议的安排合适的教室进行。如：实训课程或侧重动手能力要求的课程最好能安排在机房上课；4）对于周课时多的课程，建议的分散排课；

5）在排课时尽量保证学生的上课时间比较平均。最好不要出现一整天没课的情况。

在实际排课中，硬性约束条件必须达到，它的精确性必须是百分之百。但是，对于上面所涉及的软约束条件，在实际操作中允许存在一定误差。不同的学校可以根据其自身特点规定这些约束条件的重要性和对它的期望值，从而决定误差大小。为此，可以通过对以上软约束的设置误差权值，则目标函数F可表示为：

这里的fi为实际值和期望值之间的误差必须取绝对值，以避免各项误差之间抵消而产生错误。且wi表示第i个约束条件的权值，0≤wi≤1。通过目标函数公式可知，F的值越小，误差也就越小。所得的解越优，即最后生成的课表更接近要求。

3 遗传算法

遗传算法是指的一种通过模拟自然界生物进化过程求解极值的自适应人工智能技术。实现遗传算法的过程为：初始种群生成；个体适应度评估；选择、交叉和变异生成新的种群。

遗传算法描述如下：

1）随机抽取课表生成一定数量的初始种群；2）如果设置了循环次数上限，则判断是否达到上限值。如果达到，则停止；3）通过公式计算F的值是否达到预期设置的值，如果达到，则转6；4）按照一定的方法对种群进行选择、交叉、变异从而生成新的种群；5）转2；6）记录种群，输出课表。

4 结论

排课作为教学管理中比较麻烦的工作，给教务科带来了很大的困难。通过利用遗传算法解决排课问题，很大程度上提高了工作效率。同时，也避免了排课中遇到的矛盾和冲突。对于整个教学管理工作来说，提供了非常大的便利。

[1]薛惠锋，许五弟.基于遗传算法的多维快速聚类算法研究.计算机应用究，2005(6)：58-60.

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

[3]王敏.基于聚类-遗传算法的文摘提取方法研究.硅谷，2008(4)：26-29.

[4]陈国龙，叶文辉.基于关联度分析的遗传算法研究及其应用.计算机应用研究，2005(9).