高校排课系统的遗传算法 埃德蒙·伯克，大卫· 诶雷曼和鲁珀特·威尔

《高校排课系统的遗传算法 埃德蒙·伯克，大卫· 诶雷曼和鲁珀特·威尔》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、高校排课系统的遗传算法埃德蒙·伯克，大卫·诶雷曼和鲁珀特·威尔计算机科学系，诺丁汉大学，诺丁汉大学科技园，NG72RD.邮箱:ekb@cs.nott.ac.uk摘要：年度考试时间表的设计是一个所有高等教育机构的常见问题。往往是由手工或一个简单的管理系统帮助完成，通常包括修改上年的时间表，所以它将在新一年的工作.。英国的许多机构正在引进模块化程度的概念。这样给了学生更大的灵活性，他们采取什么课程被给予了更大的选择。对于时间表，近期学生数量增加意味着时间表设计受到的约束比任何时候都大。这样再使用前一年的时间表就不在适用。考虑到工作

2、人员、学生及课程变化的大量管理需求，每年都必须要有新的时间表出示。1、引言时间表安排有课程、考试期间教室分配的问题。这有大学时间表中的两种：课程时间表及考试时间表。这些都是相互联系的，但也可以完全不同。例如，一般多个考试将在一个特定时间在同一考试大厅举行时，任何制度都将不可能允许两个课程采用同一个教室考试。此外，考场在该系统内各部门之间是共享的，而不是每个部门用其自己的教室。这就意味着，实际上考试顺序表必须由大学集中安排。对于本文我们将只考虑考试不考虑课程。但是描述的方法将同时适用于课程安排。发现每次考试期间已被证明没有两个冲

3、突相当于分配到图中的顶点的颜色，使相邻的顶点总是有不同的颜色[Welsh+Powell67].这意味着，反过来已被证明的NP完全问题，进行穷举搜索的时间表是不是在合理的时间可能在撒谎。提出了许多启发式考试排课算法，主要用于彩色图形的方法。这些往往能产生良好的时间表，但通常忽略有可能没有足够的空席分配一个特定时期的所有考试和不可能搜索任何时间表解空间的可能性。2、遗传算法遗传算法是具有强大的演化规律模式的通用的优化的工具[DavisL.91].。他们即使在最复杂的搜索空间往往也能发现全局最优解。他们经营上人口根据其质量，作为新一

4、代的组合（交叉）或改变（变异）个人找到解决方案的基础上再使用选择的编码解决方案。传统上，搜索机制一直是独立域名，也就是说，交叉和变异算子有没有什么好的解决办法是知识。然而事实证明，如果没有更好的通过使用域依赖于良好的运营商结果可能会实[Bruns93][Burkeetal.94]。在我们的例子中，一个解决方案是一个考虑到考试期间房间分配的时间表。一个遗传算法的启动时间表随机生成一个集（人口）。这些都是根据某种标准评估。例如，任何学生有多少同时参加两次考试。评估入口成员（列表）的依据是被选择的下一代时间表。有权重的选择过程有利于

5、更好的时间表，更糟糕的时间表被淘汰，同时搜索趋向于搜索空间最有利的方向（见图1）。初始化评估每个时间表根据一套标准进行评估，例如长度时间表，有多少学生坐着连续两个考试或多少没有使用的座位。创建一个随机人口使用的时间表，上图用着色算法表示变化。时间表是以随机选择下一代为基础，好的时间表很可能选择坏的结果。f（）=x选择随机变化更改考试教室，始终保持可行的时间表。算子交叉算子对时间表，从最初的考试到最后的考试产生一个时间表。任何不可能被放置在最早时期。×一个新的人口由此产生。这个过程将反复进行，直到找到一个很好的解决方案。图1遗传

6、算法的过程交叉算子被两个群体运用并以某种方式将他们结合产生一或两个产物。传统来说这是解决方案中的随机选择编码的一个点（基因），然后追加这一点解决方案后的一部分第二个解决方案，反之亦然。变化的算子仅适用于一次性的解决方案，并涉及特定的随机变化基因。增加了一个搜索的随机限制元素，并可能重新引入潜在的有用的遗传物质已经失去了最早的搜索。3、时间表代两个基本约束支配产生一个时间表。没有学生或监考人可能在多于一个地方同一时间，并必须有足够的座位在教室里。我们称一个时间表的满足因素为可行性时间表的约束。正是由于时间表是可行的，不幸的，这不

7、意味着他是可用的。很多其他可能用于评判时间表质量的标准存在。通常一个学生不可能在同一时间参加两场考试。一个特殊的制度可能希望这样，仅有相同时间长度的考试被安排在相同的时间相同的教室或较长时间的考试首先被标注允许更多的时间。最后，仅实现的方法判断即将使用的时间表是好或不好。本文我们将描述一个遗传算法原型建立的时间表系统，该系统允许通过用最适合的图形用户界面选择最适合特殊制度的可行性时间表。遗传算法已经成功应用于大量考试时间表方案中。其他人用十分的传统的方法。如上所述每一个基因代表其特殊的考试时间及交叉的地方和变异算子。这个系统可

8、以节省时间，该系统当前正在英国爱丁堡大学使用。采用不同的方法.，当如果交叉导致考试冲突后采取何种方法寻找一个新的时期时每次考试的基因没有指定。如果考试不得不放置在任何时期，那么他就不会像以前留在被不定期系统允许的不可行的时间表里。我们使用的方法采用特定领域的知识以确保没有任何