Hybrid bee colony optimization for examination timetabling problems

doi:10.1016/j.cor.2014.09.005

2015-02-01

PRE

Malek Alzaqebah *

Salwani Abdullah

DOI：10.1016/j.cor.2014.09.005

原文链接

原文求助

摘要

En 中文

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.

Keyword:

Bee colony optimization algorithm

Examination timetabling problems

Late acceptance hill climbing algorithm

Selection strategy

Self-adaptive mechanism

Simulated annealing