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

• 作者: 吴超 宋婷 张龚钊 陈矛
• 来源期刊: 计算机应用
• 学科: 工学
• 关键词: 自动化排课 多类 迭代局部搜索 模拟退火 最优化
• 年，卷（期）: 2019,（6）
• 所属期刊栏目: 先进计算
• 页码范围: 1760-1765
• 页数: 6页
• 分类号: TP301.6
• 字数: 7251字
• 语种: 中文
• DOI: 10.11772/j.issn.1001-9081.2018102183

摘要

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