26-12-2012, 04:28 PM
Timetabling with Genetic Algorithms
Timetabling with Genetic.ppt (Size: 801 KB / Downloads: 29)
Timetabling Problem
Specifically university class timetabling
Highly complex problem (NP-Hard)
Example: School of Computing
Hundreds of interactions between students and lecturers per week
Complex set of constraints
Fixed number of rooms and timeslots (~50 rooms on different sites, 40 hours in a week)
Approaches include Tabu Search, Tiling Algorithms, Simulated Annealing and Multi-Agent Systems
GAs a good candidate
Work well on other scheduling tasks
Have previously been applied to timetabling in several different ways
Constraints
Hard constraints (weight 1.0) – if broken result in invalid timetable
All classes must be scheduled
No class/lecturers double booked
Room capacities must not be exceeded and correct room types used
Soft constraints (weight 0.01) – relate to quality of a feasible timetable
Classes scheduled within preferred hours
Hour for lunch is allowed
Bunch classes into groups
Avoid long runs of consecutive lectures
Memetic Algorithms (MAs)
Builds on the idea of a GA
GAs have static genes being passed through generations, MAs have memes which can be changed
Adds local search (hillclimbing) to algorithm; aims to reduce search space MA must cover
Could adapt either of the GAs
Initially tried both, had to drop one due to time constraints
The timetabling MA adds a local search to the genetic + greedy algorithm hybrid
Local Search
Attempts to resolve problems with the timetable
Takes classes which clashed with others and attempts to find a new timeslot where there is no clash
Optimisation
Fractional factorial screening experiment determines significant factors
Response surface experiment finds optimal values for those factors
Confirmation experiment run to check values
Comparison
Comparing number of generations to find a feasible timetable, and fitness over time
Found hybrid GA to be best approach
Faster and better quality solutions
MA performed surprisingly poorly – possible local search implementation issue