Journal of Computer Applications ›› 2019, Vol. 39 ›› Issue (6): 1760-1765.DOI: 10.11772/j.issn.1001-9081.2018102183

• Advanced computing • Previous Articles     Next Articles

Automated course arrangement algorithm based on multi-class iterated local search

SONG Ting, CHEN Mao, WU Chao, ZHANG Gongzhao   

  1. National Engineering Research Center for E-Learning(Central China Normal University), Wuhan Hubei 430079, China
  • Received:2018-10-31 Revised:2018-12-03 Online:2019-06-17 Published:2019-06-10
  • Supported by:
    This work is partially supported by the National Key R&D Program of China (2017YFB1401300).

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

宋婷, 陈矛, 吴超, 张龚钊   

  1. 国家数字化学习工程技术研究中心(华中师范大学), 武汉 430079
  • 通讯作者: 陈矛
  • 作者简介:宋婷(1982-),女,河南永城人,博士研究生,主要研究方向:智能优化算法、资源调度;陈矛(1975-),男,湖北孝感人,副教授,博士生导师,博士,主要研究方向:几何定理自动推理、优化算法设计;吴超(1992-),男,湖北咸宁人,博士研究生,主要研究方向:教育数据挖掘、知识图谱;张龚钊(1995-),男,湖北孝感人,硕士研究生,主要研究方向:数字化学习技术。
  • 基金资助:
    国家重点研发计划项目(2017YFB1401300)。

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

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

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

CLC Number: