Academic course scheduling using a genetic algorithm

Abstract

Genetic algorithms are known for their good performance m finding near-optimal solutions for problems that are typically hard to solve due to their intrinsic combinatorial nature. Such NP-hard problems, as they are better known, are characterised by solutions that lie in a large, multidimensional search space, one which is so strewn with local maxima and minima that it is somehow difficult, if not impossible, to traverse using conventional, heuristic or hill-climbing techniques. Genetic algorithms, which are loosely based on the Darwinian theory of natural selection, perform well in such cases due to their inherent ability to investigate multiple solutions in the search space simultaneously. They encode candidate solutions to the problem into a chromosome structure, and through genetic recombination operators manage to promote those solutions whose chromosome is genetically fit and lie closer to a better solution in the search space. However, if the genetic algorithm is allowed to search across the entire search space examining every possible solution, it will end up examining also those solutions that somehow violate the hard constraints (i.e. constrains that cannot be violated at all costs), rendering the solutions invalid and thus not worth considering. It follows that if those areas of the search space that contain invalid solutions are excluded, then the genetic algorithm will search through a delimited space that contains only valid candidate solutions. This is known as pre-satisfying the search space, and in so doing, the algorithm will only have to search for a solution in a search space containing exclusively valid solutions, and not waste time validating every solution it encounters. In this way, most of the processing time taken by the genetic evaluation function is drastically reduced. The primary objective of this project was to develop a genetic algorithm that searches through a pre-satisfied search space for an optimised solution to the academic timetabling problem (TTP). It will be shown that the chromosome encoding scheme for a timetable, together with genetic recombination operators, play major roles in pre-satisfying the TTP search space. The implemented artefact is made up of three distinct components: the course database that holds resource information on the B.Sc.(Hons.) I.T. degree program (which was used as an example throughout the project), the genetic algorithm that uses this information to evolve a genetically robust population of candidate solutions, and a user interface that unifies and provides access to the two and also displays the results of the genetic algorithm.