This paper investigates a number of approaches to encoding and crossover to support timetable design using gnetic algorithms, thus extending the range of techniques available for solving such problems. Timetabling is used in this paper to refer to organising a weekly lecture timetable, as used in unviersities. In addition the algorithm is designed to produce a `good' timetable as defined by a fitness function rather than merely a legal solution. The first approach to encoding timetabling dealt with in this paper uses a 'greedy algorithm' variant and a variety of standard crossover methods. The second encoding method searches a wieder space of solutions but requires a new adaptation of existing order and position-based corssover algorithms. Results are compared with a traditional search technique and timetables provided by lecturers. These results demonstrate the effectiveness of genetic algorithms when used to optimise a timetable and introduce a combinatorial crossovar operator which can deal with a more general class of problem than the normal order and position based operators. The greedy algorithm version of the genetic algorithm outperformed the other methods, despite the fact it cannot search the whole of the legal solution space.
展开▼
