Title: An adaptive coevolutionary memetic algorithm for examination timetabling problems

Authors: Yu Lei; Maoguo Gong; Licheng Jiao; Jiao Shi; Yu Zhou

Addresses: Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi 710071, China ' Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi 710071, China ' Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi 710071, China ' Key Laboratory of Intelligent Perception and Image Understanding of Ministry of Education, International Research Center for Intelligent Perception and Computation, Xidian University, Xi'an, Shaanxi 710071, China ' Department of Computer Science, City University of Hong Kong, Kowloon Tong, Kowloon, Hong Kong

Abstract: In this paper, we present an adaptive coevolutionary memetic algorithm (ACMA) for examination timetabling problems. In our proposed algorithm, the evolutionary search is conducted in two spaces: the heuristic space and the solution space. In the heuristic space, a hyper-heuristic approach is utilised to generate the initial population, and then basic evolutionary operators are used to find the potential heuristic lists. The evolutionary strategy in the heuristic space is regarded as a global search procedure. In the solution space, according to the solution structure, some specific evolutionary operators are designed for expanding the scope of search in solution space. This scheme can be viewed as the local search procedure. By combining two different strategies, the cooperation between them will eventually increase the diversities in the population. In order to determine which space should be selected at each generation, an adaptive parameter is designed based on the proportion of feasible solutions in the current population. Experimental results demonstrated that ACMA obtains competitive results and outperforms the compared approaches on some benchmark instances.

Keywords: evolutionary algorithm; memetic algorithm; hyper-heuristic approach; examination timetabling problem.

DOI: 10.1504/IJBIC.2017.087918

International Journal of Bio-Inspired Computation, 2017 Vol.10 No.4, pp.248 - 257

Received: 24 Jan 2015
Accepted: 09 Apr 2015

Published online: 10 Nov 2017 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article