A memetic algorithm based on MOEA/D for the examination timetabling problem

被引：9
作者：
Lei, Yu [1 ]
Shi, Jiao [1 ]
Yan, Zhen [2 ]
机构：
[1] Northwestern Polytech Univ, Sch Elect & Informat, Xian 710072, Shaanxi, Peoples R China
[2] China Univ Geosci, Sch Comp Sci, Wuhan 430074, Hubei, Peoples R China
来源：
SOFT COMPUTING | 2018年 / 22卷 / 05期
基金：
中国国家自然科学基金; 中国博士后科学基金;
关键词：
Uncapacitated examination timetabling problem; Multiobjective optimization; MOEA/D; Local search; MATCHING-BASED SELECTION; EVOLUTIONARY ALGORITHM;
D O I：
10.1007/s00500-017-2886-y
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
A memetic algorithm based on MOEA/D is presented to deal with the uncapacitated multiobjective examination timetabling problem in this paper. The examination timetabling problem is considered as a two-objective optimization problem in this paper, while it is modeled as a single-objective optimization problem generally. The framework of a multiobjective evolutionary algorithm with decomposition (MOEA/D) is first employed to guide the evolutionary process. Two special local search operators are designed to find better individuals. The proposed algorithm is tested on 11 benchmark examination timetabling instances. Experimental results prove that the proposed algorithm can produce a promising set of nondominated solutions for each examination timetabling instance.
引用
收藏
页码：1511 / 1523
页数：13
相关论文
共 27 条
[1]  
Asmuni H, 2005, LECT NOTES COMPUT SC, V3616, P334, DOI 10.1007/11593577_19
[2]  
Burke E., 1995, Evolutionary Computing. AISB Workshop. Selected Papers, P75
[3]  
Burke E., 1996, Practice and Theory of Automated Timetabling. First International Conference. Selected Papers, P76
[4]  
Burke E. K., 1996, Practice and Theory of Automated Timetabling. First International Conference. Selected Papers, P241
[5]  
Burke E.K., 2004, Studies in fuzziness and soft computing: Cilt 166. Recent advances in memetic algorithms and related seach Technologies ss, P289
[6]   A multistage evolutionary algorithm for the timetable problem [J].
Burke, EK ;
Newall, JP .
IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, 1999, 3 (01) :63-74
[7]   A SURVEY OF PRACTICAL APPLICATIONS OF EXAMINATION TIMETABLING ALGORITHMS [J].
CARTER, MW .
OPERATIONS RESEARCH, 1986, 34 (02) :193-202
[8]  
Carter MW, 1996, J OPER RES SOC, V47, P373, DOI 10.1057/jors.1996.37
[9]  
Chan C. K., 2002, Proceedings of the 2002 Congress on Evolutionary Computation. CEC'02 (Cat. No.02TH8600), P1946, DOI 10.1109/CEC.2002.1004541
[10]   Solving the exam timetabling problem via a multi-objective evolutionary algorithm - A more general approach [J].
Cheong, C. Y. ;
Tan, K. C. ;
Veeravalli, B. .
2007 IEEE SYMPOSIUM ON COMPUTATIONAL INTELLIGENCE IN SCHEDULING, 2007, :165-+
123