A comparison of genetic algorithms and genetic programming in solving the school timetabling problem

摘要

In this paper we compare the performance of genetic algorithms and genetic programming in solving a set of hard school timetabling problems. Genetic algorithms search a solution space whereas genetic programming explores a program space. While previous work has examined the use of genetic algorithms in solving the school timetabling problem, there has not been any research on the use of genetic programming for this domain. The GA explores a space of timetables to find an optimal timetable. GP on the other hand searches for an optimal program which when executed will produce a solution. Each program is comprised of operators for timetable construction. The GA and GP were tested on the Abramson set of school timetabling problems. Genetic programming proved to be more effective than genetic algorithms in solving this set of problems. Furthermore, the results produced by both the GA and GP were found to be comparative to methods applied to the same set of problems.