Hybrid bee colony optimization for examination timetabling problems

被引:34
作者
Alzaqebah, M. [1 ]
Abdullah, S. [2 ]
机构
[1] Jadara Univ, Fac Sci & Informat Technol, Dept Software Engn, Irbid, Jordan
[2] Univ Kebangsaan Malaysia, Ctr Artificial Intelligence Technol, Data Min & Optimizat Res Grp DMO, Bangi 43600, Selangor, Malaysia
关键词
Bee colony optimization algorithm; Examination timetabling problems; Late acceptance hill climbing algorithm; Selection strategy; Self-adaptive mechanism; Simulated annealing; ALGORITHM;
D O I
10.1016/j.cor.2014.09.005
中图分类号
TP39 [计算机的应用];
学科分类号
081203 ; 0835 ;
摘要
Swarm intelligence is a branch of artificial intelligence that focuses on the actions of agents in self-organized systems. Researchers have proposed a bee colony optimization (BCO) algorithm as part of swarm intelligence. BCO is a meta-heuristic algorithm based on the foraging behavior of bees. This study presents a hybrid BCO algorithm for examination timetabling problems. Bees in the BCO algorithm perform two main actions: forward pass and backward pass. Each bee explores the search space in forward pass and then shares information with other bees in the hive in backward pass. This study found that a bee decides to be either a recruiter that searches for a food source or a follower that selects a recruiter bee to follow on the basis of roulette wheel selection. In forward pass, BCO is supported along with other local searches, including the Late Acceptance Hill Climbing and Simulated Annealing algorithms. We introduce three selection strategies (tournament, rank and disruptive selection strategies) for the follower bees to select a recruiter to maintain population diversity in backward pass. The disruptive selection strategy outperforms tournament and rank selections. We also introduce a self-adaptive mechanism to select a neighborhood structure to enhance the neighborhood search. The proposed algorithm is evaluated against the latest methodologies in the literature with respect to two standard examination timetabling problems, namely, uncapacitated and competition datasets. We demonstrate that the proposed algorithm produces one new best result on uncapacitated datasets and comparable results on competition datasets. (C) 2014 Elsevier Ltd. All rights reserved.
引用
收藏
页码:142 / 154
页数:13
相关论文
共 44 条
[1]  
Abdullah S, 2006, P INT C AUT PLANN SC, P334
[2]   Investigating Ahuja-Orlin's large neighbourhood search approach for examination timetabling [J].
Abdullah, Salwani ;
Ahmadi, Samad ;
Burke, Edmund K. ;
Dror, Moshe .
OR SPECTRUM, 2007, 29 (02) :351-372
[3]   On the use of multi neighbourhood structures within a Tabu-based memetic approach to university timetabling problems [J].
Abdullah, Salwani ;
Turabieh, Hamza .
INFORMATION SCIENCES, 2012, 191 :146-168
[4]  
Abdullah S, 2009, LECT NOTES COMPUT SC, V5818, P60, DOI 10.1007/978-3-642-04918-7_5
[5]  
Alzagebah M, 2011, LECT NOTES COMPUT SC, V6831, P31, DOI 10.1007/978-3-642-22616-8_3
[6]  
[Anonymous], 2006, P PATAT
[7]  
[Anonymous], 2008, PATAT 2008 C MONTR C
[8]  
Atsuta M, 2007, IBARAKI TITC2007 TRA
[9]  
Baker J., 1987, P 2 INT C GEN ALG, P14, DOI DOI 10.1007/S10489-006-0018-Y
[10]  
Blickle T, 1995, P 6 INT C GEN ALG SA, P2