A genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem

R Raghavjee, N Pillay

Abstract


Research in the domain of school timetabling has essentially focused on applying various techniques such as integer programming, constraint satisfaction, simulated annealing, tabu search and genetic algorithms to calculate a solution to the problem. Optimization techniques like simulated annealing, tabu search and genetic algorithms generally explore a solution space. Hyper-heuristics, on the other hand, search a heuristic space with the aim of providing a more generalized solution to the particular optimisation problem. This is a fairly new technique that has proven to be successful in solving various combinatorial optimisation problems. There has not been much research into the use of hyper-heuristics to solve the school timetabling problem. This study investigates the use of a genetic algorithm selection perturbative hyper-heuristic for solving the school timetabling problem. A two-phased approach is taken, with the first phase focusing on hard constraints, and the second on soft constraints. The genetic algorithm uses tournament selection to choose parents, to which the mutation and crossover operators are applied. The genetic algorithm selection perturbative hyper-heuristic (GASPHH) was applied to five different school timetabling problems. The performance of the hyper-heuristic was compared to that of other methods applied to these problems, including a genetic algorithm that was applied directly to the solution space. GASPHH performed well over all five different types of school timetabling problems.

Full Text:

PDF


DOI: https://doi.org/10.5784/31-1-158

Refbacks

  • There are currently no refbacks.





ISSN 2224-0004 (online); ISSN 0259-191X (print)

Powered by OJS and hosted by Stellenbosch University Library and Information Service since 2011.


Disclaimer:

This journal is hosted by the SU LIS on request of the journal owner/editor. The SU LIS takes no responsibility for the content published within this journal, and disclaim all liability arising out of the use of or inability to use the information contained herein. We assume no responsibility, and shall not be liable for any breaches of agreement with other publishers/hosts.

SUNJournals Help