基于多类迭代局部搜索的自动化排课算法

宋婷 陈矛 吴超 张龚钊

摘 要：针对局部搜索算法容易陷入局部最优，无法自适应多种约束条件下排课的问题，提出一种基于多类迭代局部搜索的自动化排课算法。首先，通过多类分类器依据排课问题特征对排课问题进行分类，指导迭代局部搜索的邻域选择及参数设置。然后，在迭代局部搜索的过程中，使用基于序列的贪婪算法获得可行解。最后，采用以问题特性为导向的双温控制模拟退火算法在邻域中搜索局部最优解，并通过特定的扰动策略对当前最优解进行扰动后作为新的初始解进行迭代，最终达到全局最优。该算法在两个国际著名的数据集，即第二届国际时间表大赛基于课程的时间表数据集和Lewis 60数据集上进行了测试。实验结果表明，与当前文献中求解该问题的其他性能较优算法相比，所提出的算法具有更高的求解效率和质量。

关键词：自动化排课;多类;迭代局部搜索;模拟退火;最优化

中图分类号：TP301.6（算法理论）

文献标志码：A

Abstract： Focusing on the issue that local search algorithm is prone to fall into the local optimum and does not adapt to the course arrangement under multiple constraints， an automated course arrangement algorithm based on multi-class iterated local search was proposed. Firstly， the course arrangement problems were classified by the multi-class classifier according to the characteristics of the problems to guide the neighborhood selection and parameter setting of the iteration local search. Then， in the process of iterated local search， the sequence-based greedy algorithm was used to obtain the feasible solutions. Finally， the problem characteristics oriented two-temperature control simulated annealing algorithm was used to search for local optimal solution in the neighborhood and the current optimal solution was perturbed by a specific strategy and iterated as the new initial solution to achieve global optimization. The proposed algorithm was tested on two internationally famous datasets， which are the second international timetabling competition dataset and Lewis 60 dataset. The experimental results show that， compared with the existing efficient algorithms in current literatures， the proposed algorithm has higher efficiency and solution quality.

Key words： automated course arrangement; multi-class; Iterated Local Search （ILS）; Simulated Annealing （SA）; optimization

0 引言

自动排课问题是一个包含教室、课程、时间、班级、教学资源等多种因素的组合优化问题，已被证明是一个非确定多项式（Non-deterministic Polynomial， NP）完全問题[1]。由于该类问题的复杂性，引起了越来越多学者的关注和研究。2002年，英国和意大利合作组织了五年一届的国际时间表竞赛（International Timetabling Competition，  ITC）[2]，旨在为研究者提供一个可以普遍接受的基准来缩小研究与实践之间的差距。排课问题通常被定义为在特定约束条件下，尽可能合理地安排有限的教育资源。其约束可被分为两类：在任何情况下都不能违反的约束称为硬约束;而那些可以违反，但应尽可能地减少违反值的约束被称为软约束。满足了所有硬约束的课程表被称为可行解，而最优的课程表（最优解）则是指在满足所有硬约束的条件下，最小化软约束的违反值。

对于这类NP难问题，确定型算法只适用于在合理的时间内解决小规模问题实例。因此，ITC竞赛及其后大多数的相关研究都集中在快速近似启发式算法和元启发式算法上，以寻求在给定的时间范围内获取可行的最优解决方案。典型的算法有基于图着色的方法[3]、模拟退火（Simulated Annealing， SA）算法[4]、禁忌搜索算法[5]、变邻域搜索算法[6]、遗传算法[7]、蚁群算法[8]、蜂群算法[9]、和声搜索算法[10]等。但所有方法都还未能达到所给定问题解的下界，对问题最优解的进一步探讨仍在进行。在这些算法中，虽然模拟退火（SA）算法是一个简单且易于实现的通用框架，但它对于排课这类组合优化问题的求解确实非常有效。例如，第一届国际时间表竞赛的冠军和第二届国际时间表竞赛的三个类别组的冠军均采用了基于SA的算法。

解决排课问题的算法通常由两阶段组成：首先构建一个可行的排课方案，然后尽可能地减少软约束违反值。通常，时间表问题可以等同于一个图着色问题，对于大多数ITC竞赛的排课问题实例而言，获得可行的排课方案几乎不能构成挑战。 因此参赛算法的主要焦点都集中在最小化软约束违反值上。

近年来，Lewis等[11]创建了一组60个仅包含硬约束的测试数据集，其创建目的在于将注意力聚焦于寻求可行解，以对不同算法进行更公平的比较。而传统基于序列的技术只能为一小部分测试实例找到可行解。针对该问题，已经有多种不同的算法提出来求取这些测试实例的可行解。包括混合模拟退火算法[12]、基于团的算法[13]、基于事件插入的启发式算法[14]、基于模拟退火的元启发式算法[15]、memetic算法[16]等。迄今为止，这些方法依然无法完全解决所有样本。因此，Lewis等[11]的这组测试实例，直到今天仍然是评估不同方法的一个具有挑战性的基准数据集。

本文提出了一种多类迭代局部搜索（Multi-class Classification Iterated Local Search， MC-ILS）算法，该算法分别针对ITC竞赛数据集和Lewis60数据集寻找可行的排课方案。该算法经过测试，并与当前文献中成绩较好的算法进行了比较。计算结果表明，所提算法具有优异的性能和更强的适应性，无论是在最小化软约束违反值的ITC竞赛数据集，还是在更难的硬约束条件下寻找可行解，均优于其他对比算法。

1 自动化排课问题模型

1.1 问题定义

排课问题的求解本质上是一个解决教室R={r1， r2，…， rm}、课时P={p1， p2，…， pn}、课程C={c1， c2，…， ct}等教育资源矛盾的多因素优化决策过程。

在模型中，定义X为候选解课表，每周d天，每天h节，一周总时段数n=d×h。xij为安排在ri教室pj时段的课程，事件G={g1，g2，…，gs}是绑定了教师、学生和第几次课信息的课程集合，|G|=∑ti=1cli，cli为第i个课程每周需上的次数。conij为课程ci和cj的冲突情况，有冲突为1，无冲突為0。exclij为课程ci是否可安排到时段pj，可安排为1，不可安排为0。stui为课程ci的学生数，rmi为教室ri的座位数，rni为课程ci分配的房间数。dmi为课程ci要求的最小工作日，dni为X中课程ci的实际工作日。Cri为专业i的课程集合，Cr={Cr1，Cr2，…，Crs}为专业的集合，cpi， j为Cri里的课程是否被安排在pj时段，安排为1，未安排为0。

根据要解决的问题及参数定义，具体的硬约束和软约束描述及相应的数学表达式如下。

1.2 硬约束及其数学表达

2 基本迭代局部搜索算法

局部搜索算法的基本思想是首先找到一个或一组初始解，然后按照一定的策略在邻域中搜索新的可行解，并根据特定的接受准则更新当前解，最终找到最优解。局部搜索算法具有结构简单，易理解易实现的优点，但由于其搜索性能过于依赖邻域结构和初始解，容易陷入局部最优。

模拟退火算法作为一种经典的局部搜索算法，其灵感源自物理中固体退火原理，固体的结晶状态通常是内能最小的状态。将固体加温至充分高，此时，固体内部粒子呈随机排列状态，内能增大;再让其逐步降温冷却，此过程使得粒子趋于有序，每个温度都能达到平衡态，最后常温时达到内能最小的基态。根据Metropolis准则，粒子在温度T下趋于平衡的概率为exp（-ΔE/（kT）），其中：E是温度T处的内能，ΔE是变化量，k是玻尔兹曼常数。与之相对应，模拟退火算法的过程是首先找到一个初始解作为当前解，并设定一个初始温度值T，然后按照一定的策略在邻域中搜索新的候选解，计算候选解与当前解之间的差值ΔE，按照概率exp（-ΔE/（kT））接受候选解为新的当前解。在不断迭代的过程中对温度T逐步降温，不断减少差解的接受概率，最终找到近似解。

迭代局部搜索算法是对局部搜索算法的一种改进，通过对局部寻优策略的迭代调用来跳出局部最优。在每次迭代中使用前面局部搜索得到的最优解作为本次搜索的初始解，以此反复来获取全局最优解。

3 多类迭代局部搜索求解排课问题

基本迭代局部搜索算法主要用于函数优化，将其应用于自动化排课问题，需要在算法框架、初始化方法、邻域设计、模拟退火等方面进行改进。

3.1 算法主框架

在启发式算法的设计中，待解决问题自身的特征往往决定了算法的具体设计细节，需要对每一个具体问题设计专门的解决办法，很难用一个通用算法解决所有问题。本文提出一种多类迭代局部搜索（MC-ILS）算法来求解排课问题，通过对各种排课问题特征的分析抽取并用多类分类器进行分类，指导迭代局部搜索过程，实现自动化排课。具体步骤如下：

3.2 多类分类器

不同的排课问题具有不同的条件和约束，需要依据是否有软冲突、房间数、时段数、课时约束等特征条件，对算法步骤中的实现进行参数调整和过程选择。针对该问题，采用超启发算法虽然可以提高排课算法的适应度，但也带来算法和时间复杂度的提升。本文采用基于决策树的多类分类器实现局部搜索算法的选择和参数的设定，简化算法结构和运行时间。决策树构造如图1所示。

决策树第一层节点（问题类型）根据软硬约束构造，判别仅存在硬约束还是软硬约束均存在，第二层节点（问题难度）根据房间数和事件数等条件构造。为简单起见，计算所有样例事件数与房间数的比值，依据中值分为难易两类，在实践中此种划分并不总是精确，因此需要再通过第三层节点（问题特征）对问题进行更精确的划分。当决策树构造完毕后，就采用决策树算法对不同算例进行分类。