基于遗传算法的大学排课系统.doc

基于遗传算法的大学排课系统.doc基于遗传算法的大学排课系统
（威客SZ2122译）
Edmund Burke, David Elliman and Rupert Weare
Department of Computer Science,
University of Nottingham,
University Park, Nottingham, NG7 2RD.
e~mai1: ******@cs. nott. qc. uk
摘要
考试时间表的年度建设是所有高等教育机构的普遍问题。它常常由手工完成或者是借助简单 有限的管理系统，通常是用上一年的时间表修改后第二年再用。许多英国大学现在都引入了 单元制学位的概念，这给学生选课带来了更多的灵活性和更宽的选择性。但这对制表人和增 长的学生数量来说，意味着时间安排将比以前更紧了，再使用前一年的时间表就不尽人意， 所以每年都要制出一个能把员工，学生和课程变动引起的大量必要管理工作都包含进去的新 表。
我们提供了一个基于用遗传算法安排大学考试和课程时间表的系统原形。它将包括一个标志 性用户界面的交互窗口，为用户工作和深入研究提供一个良好的解决办法。
引言（绪论）
时间表安排问题就是把不同的课程和考试安排在不同的时间与地点。以下是两种大学时间
表：课程表和考试表。它们相互联系又不尽相同。一般来讲，例如在特定的时间段里每个考
试大厅会安排不止一场考试，而一个学校允许一个教室同时进行两堂课的情况却极为少见。
还有学院内各个院系可以共用一个考试大厅但上课要用他们自己的教室。这意味着在实践中
考试日程要由大学集中安排。我们这篇论文的目的是考虑考试而非课程。但是描述的这种方
法也同样适用于课程安排。
遗传算法
遗传算法是一个功能强大的演示了进化原则的通用优化工具［戴维斯91.］。他们往往能找到
全局最优解即便在最复杂的搜索空间。他们运算的是一个编码方案集合，这些集合根据质量 评估选出，通过交叉和改变现有算子再生成新一代演生方案的基础算符。传统搜索机制一直 是域独立的，也就是说交叉和改变算符后将无法产生一个好的解决方案。然而事实证明：通 过使用独立的域算符至少可以达到预期的结果。
在我们的描述中，我们可以将方案当做把考试分配到合适的时间和地点的一个时间表。遗传
算法通过随机生成的一组时间表开始，然后通过某种评估标准得到评价，例如，任意一个学
生要几次坐在连续的两场考试中。然后以此评估群基础座位生成下一代时间表的母算符。经
过几轮选择有利于选出更佳的表格系统，在剔除最差表格的同时搜索将指向最佳搜索空间
域。（见图1）
交叉算符运算抓取两个集合元件，合并后以某种方式生成一到两个新元件（即后代）。传统
操作方法是随机选取一个编码点（编码因子），这个点附加在第二个方案中的一部分，两个
点之和达到这个点位，若达不到这个点位则反用之。
变异算符一次只能用于一个方案，涉及一个特定因子的随机变异。这增加了一个可搜索到的
有限随机元素，但也可能重新引入在先前搜索中遗失的潜在有用遗传因子。
时间表群集合
两个基本条件限制生成一个表格。第一是没有一个考生和监考人能同时出现在一个以上的地
方，另一个是必须有足够多的座位提供给所有在场的考生。我们把满足这些条件限制的表格
称作可行性时间表。一个时间表可行，但不是说足够好