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 *