A memetic algorithm based on hyper-heuristics for examination timetabling problems

作者：Lei Yu^*; Gong Maoguo; Jiao Licheng; Zuo Yi

来源：International Journal of Intelligent Computing and Cybernetics, 2015, 8(2): 139-151.

DOI：10.1108/IJICC-02-2015-0005

• Crossover and mutation
• Design/methodology/approach
• Evolutionary strategies
• Examination timetabling
• Hyperheuristic
• Local search method
• Memetic algorithms
• Search strategies

<jats:sec>
<jats:title content-type="abstract-heading">Purpose</jats:title>
<jats:p> – The examination timetabling problem is an NP-hard problem. A large number of approaches for this problem are developed to find more appropriate search strategies. Hyper-heuristic is a kind of representative methods. In hyper-heuristic, the high-level search is executed to construct heuristic lists by traditional methods (such as Tabu search, variable neighborhoods and so on). The purpose of this paper is to apply the evolutionary strategy instead of traditional methods for high-level search to improve the capability of global search. </jats:p>
</jats:sec>
<jats:sec>
<jats:title content-type="abstract-heading">Design/methodology/approach</jats:title>
<jats:p> – This paper combines hyper-heuristic with evolutionary strategy to solve examination timetabling problems. First, four graph coloring heuristics are employed to construct heuristic lists. Within the evolutionary algorithm framework, the iterative initialization is utilized to improve the number of feasible solutions in the population; meanwhile, the crossover and mutation operators are applied to find potential heuristic lists in the heuristic space (high-level search). At last, two local search methods are combined to optimize the feasible solutions in the solution space (low-level search). </jats:p>
</jats:sec>
<jats:sec>
<jats:title content-type="abstract-heading">Findings</jats:title>
<jats:p> – Experimental results demonstrate that the proposed approach obtains competitive results and outperforms the compared approaches on some benchmark instances. </jats:p>
</jats:sec>
<jats:sec>
<jats:title content-type="abstract-heading">Originality/value</jats:title>
<jats:p> – The contribution of this paper is the development of a framework which combines evolutionary algorithm and hyper-heuristic for examination timetabling problems.</jats:p>
</jats:sec>

• 出版日期2015-6-8
• 单位西安电子科技大学