计算机工程与应用 ›› 2022, Vol. 58 ›› Issue (18): 304-310.DOI: 10.3778/j.issn.1002-8331.2101-0343

• 工程与应用 • 上一篇    下一篇

面向大学课程时间表的并行多视图搜索算法

宋婷,王栋,许玉龙,王昂   

  1. 1.河南中医药大学 信息技术学院,郑州 450046
    2.华中师范大学 国家数字化学习工程技术研究中心,武汉 430079
    3.河南农业大学 信息与管理科学学院,郑州 450046
  • 出版日期:2022-09-15 发布日期:2022-09-15

Parallel Multi-View Search Algorithm for University Course Timetable Problem

SONG Ting, WANG Dong, XU Yulong, WANG Ang   

  1. 1.School of Information Technology, Henan University of Chinese Medicine, Zhengzhou 450046, China
    2.National Engineering Research Center for E-Learning, Central China Normal University, Wuhan 430079, China
    3.School of Information and Management Science, Henan Agricultural University, Zhengzhou 450046, China
  • Online:2022-09-15 Published:2022-09-15

摘要: 针对大学课程时间表问题,提出一种基于改进迭代局部搜索的并行多视图搜索算法进行求解。依据课程时间表问题特性设计包含八种基础邻域的多邻域集,并根据提升速度比制定基邻域选择概率设置规则。在迭代局部搜索过程中,运用多视图学习策略对多个局部搜索步骤进行视图共享,及时调整搜索方向以提升搜索效率。通过并行计算思想对算法优化,提升多视图搜索的收敛速度。实验结果表明,提出的算法求解精度更佳,且具有优异的扩展性和并行效率。

关键词: 大学课程时间表, 迭代局部搜索, 多视图学习, 并行计算

Abstract: For the university course timetable problem(UCTP), this paper proposes a parallel iterative local search algorithm based on multi-view learning strategy to solve it. The algorithm designs a multi-neighborhood set with eight base neighborhoods according to the characteristics of UCTP, and formulates the base neighborhood selection probability setting rules based on the increase speed ratio. In the iterative local search process, a multi-view learning strategy with view pooling is presented to fuse the search results of different local search and the search direction is adjusted in time to improve the search efficiency. The algorithm is optimized through the idea of parallel computing to improve the convergence speed of multi-view search. Experimental results show that the proposed algorithm has better solution accuracy, and has excellent scalability and parallel efficiency.

Key words: university course timetable, iterative local search, multi-view learning, parallel computing