高校排课问题的元启发算法外文翻译资料

英语原文共 30 页，剩余内容已隐藏，支付完成后下载完整资料

高校排课问题的元启发算法

学科类别：

计算机：元启发算法，随机式；

数学：组合

本文介绍了模拟退火，禁忌搜索和改进的遗传算法，并应用三种算法解决实例排课问题，并对计算结果进行了比较和讨论。

其他关键词：课表问题，禁忌搜索，模拟退火，遗传算法

摘要

本文介绍了三种已知的元启发算法为解决时间表问题、多约束、NP难问题、组合优化问题所提供的可能性的研究结果。首先, 我们提出了问题的模型, 包括目标函数的层次结构的定义, 以及我们应用于表示时间表的矩阵的邻域搜索算子。然后, 我们总结所实施系统的使用结果对学校时间表的产生的具体情况，对遗传算法进行了模拟退火、禁忌搜索和两种不同版本的搜索结果的比较。结果表明, 基于当前问题的局部搜索和禁忌搜索的遗传算法均优于模拟退火和手工制作的时间表。

1.介绍

元启发算法[23]构成了一类对函数有用的计算范例，优化往往受到自然过程研究的启发。 他们通常更新可能解决方案，一次一个或一整套，以找到给定问题的最佳解决方案; 在这个意义上命名演化算法在文献中很常见。 特别有效的实例化的演化算法是模拟退火[21]，其中自然类比是金属的退火过程，或遗传算法（GA）[19]，其中自然类比是群体遗传学，或禁忌搜索[15,16]。 这个类的其他几种算法已经提出，但提到的三个是获得最多研究人员的注意力的，并已成功应用于更广泛的各种各样的优化问题。

我们工作的主要目标是将这些元启发算法与困难的现实世界的组合优化问题实例进行比较，从而评估它们的相对优点。作为一个测试问题，我们选择了时间表问题（TTP），即已知的NP困难问题 [12]，但由于其具有重要的实际意义[1,2,3,4,5,9，10,13,14,17,18,20,28]。

我们将用意大利高中的时间表或时间表作为我们调查的基准。当然，本文介绍的观点可以应用于解决时间表问题的其他可能非常不同的事例。现场测试的可能性一直是选择这个特殊问题例子的主要原因。意大利高中时间表必须符合以下指令。在一所典型的意大利高中中，一个班级接受每天五个小时的课程，每周六天，为期五年的高中课程。教师可以教授一门或多门科目，通常是教两个或更多的班级。正如本文所述，除了每周18小时的教学外，他们还有其他活动。此外，除周日外，每位教师都有权每周只进行一次休息日。

意大利高中的课程时间表的结构可能会被分解，制定成若干相互关联的时间表。这可以减少实例问题的大小，并通过我们的算法进行有效管理测试。事实上，分组总是配对的，一对分组共享许多老师、学生和资源（例如实验室）。因此两个配对的部分可以作为“原子单位”来处理，由10个类组成，由于内部依赖性高，不能进一步分解，但与其他部分相对隔离。

鉴于这些前提，问题描述如下：

bull;个教师名单（本例为20-24个）;

bull;所涉及的类课程清单（10个两两配对分组）;

bull;每个班级每周有个教学时间（30个）;

bull;每个班的课程表，即在该班工作的教师频率列表;

bull;一些外部条件（例如一些教师参与其他部门或活动的时间）。

请注意，括号中的值是一对分组的典型值，仅作为我们将要处理的实例的大小的例子呈现。这里对问题维度没有限制意义。

课程表问题的正式表示如下。给定5元组，其中

是个资源（教师）的有限集;

是由教师完成的一组工作（在班和其他活动中教学）;

是个时间间隔的有限集合（小时）;

是的矩阵（时间表）;

是要被最小化的函数，；

我们要计算，其中

是如下所定义的不可数变量，;

是教学成本的集合（例如，在一周的几天内同一科目的小时数总和）;

是一组组织成本（例如，没有可用于临时教学职位的教师）;

是一组人员成本（例如，在一周的不期望的一天中休息）。如果它满足以下约束条件，那么我们的算法生成的每个解决方案（时间表）都是可行的：

bull;每个老师和每个班级必须在预定的时间内出席时间表;

bull;同一小时内同一班的教师人数不得超过一名;

bull;同一老师在同一小时内只能上一堂课;

bull;不可能有“未被覆盖的时间”（即没有教师被分配到班级的时间）。

以前对这个问题的研究主要集中在启发式方法[10]。事实上，如果用标准算法逼近，即定义二元变量（根据先前指定的参数，其中表示教师，表示时间间隔，表示一种分类），问题将由6000个变量，数百个约束和一个非常复杂的目标函数构成，这使得它难以在有限的CPU时间内解决优化问题[2,8,22]。我们决定除了产生可行的时间表外，通过演化算法来接近它，并尝试着优化下一节介绍的目标函数。

本文结构如下：在第2节中，我们介绍用于解决方案展示和局部搜索过程的编码，它构成了我们测试的所有启发式方法的基础。第3节详细描述了我们最小化的目标函数。 第4节介绍了算法我们已经实现结果，并在第5节展示计算结果。 最后，我们在第6节中得出一些结论。

2.元启发算法和局部搜索排课问题

现在描述我们如何通过使用三种不同的超启发式方法来解决第一部分中所描述的为意大利高中的分组创建学校时间表的问题。我们首先定义一个解决方案的编码，它允许应用一个有效的局部搜索过程，它是禁忌搜索和模拟退火的基本组成部分，它大大提高了遗传算法的性能。

解码编码

我们选择的字母表是教师必须完成的工作的集合：它的元素是涉及到的班级和其他活动。我们表明：

bull;带有这些字符的课程必须被教授;

bull;字符表示临时教学岗位的处理时间;

bull;字符表示专业发展的时间;

bull;字符表示在与所考虑的两部分不同的部分的课程中教授课程的时间;这些小时在手动初始化阶段或先前的算法运行中被固定，并被称为固定小时;

bull;老师不需要工作的时间;

bull;老师的休息日的特性。

因此我们的字母表是。这个字母表允许我们将问题表示为矩阵（的矩阵），其中每行对应一位老师，每列对应一个小时。矩阵的每个元素都是一个变量，其值可以在对应于包含该基因的行的教师特定的的子集上变化。

因此，该问题由与图1中提出的矩阵类似的矩阵表示（相同的表示法也已在[30]中使用过）。为了得到一个可行的时间表，矩阵必须满足第1节中讨论的约束条件。

搜索时间表被操纵，可能导致不可行的情况。但是，需要特别关注的是要满足约束条件。约束条件可如下管理：

bull;通过社区定义，以便每个教师在初始化阶段分配的小时数不能通过识别当前解决方案的邻域算子的应用来改变;

bull;通过过滤算法，以便通过过滤部分或全部消除算子应用导致的不可行性;

bull;通过目标函数，使用选择性压力来惩罚具有不可行性的解决方案（在目标函数中通过高罚分明确考察不可行性）。