We have a set of teachers who needs a schedule for a set of subjects over a set of periods, this schedule must take into account characteristics of periods of week, the limited availability of teacher and rooms, and some constraints which should be fulfilled.
The problem of assigning teachers to subjects and groups for timetabling problem has been studied by many authors. Tillet (1975) was the first to address it, using an integer linear programming model.
Then other authors like Shih and Sullivan (1977), Schniederjans and Kim (1987) and also Badri et al. (1998) developed linear programming models a different approach is followed by Dyer and Mulvey (1976), Bloomfield and McSharry (1979), Mulvey (1982) and Dinkel et al. (1989) who developed capacitated flow models for the problem.
Our timetabling problem has the following elements:
In a course timetabling problem, generally, constraints are considered in two types. One of them is called hard constraints. Every acceptable timetable must satisfy these Constraints, they are:
The other type of constraints is the soft type, without those constraints an acceptable solution will be generated but the more we stick to those constraints the higher quality of the solution will be fulfilled.
Those soft constraints are:
Here you can find the description of the programming elements used in the implementation of the Genetic Algorithm on the problem of Time-Tabling. To support the implementation we have used the OOP approach in our implementation, so the classes where organized into a specific hierarchy to make it easier and more organized, thus producing cleaner and faster implementation.
Harshly saying, the classes are organized into the following hierarchy:
Each of the above stated classes are described below in detail:
Buffer is a static class that is used in order to communicate with the database and buffer some data. This will speed up the performance and make communication with the database easier.FetchData() – method fetches the data from the database by executing the “SELECT ALL” query, in order to speed up performance of the systemgetRandomCell() – fetches random cell, which should be validgetRandomGCCell() – fetches the random cell, according to the provided groupid argumentWriteChromosome() – saves the provided chromosome to the specified text fileReadChromosome() – reads a saved into text file chromosome and returns it as a result of the method.
Cell class represents the smallest building block of the chromosome. If we want to define the chromosome as a schedule, than we can define a cell as a one-slot entry, which specifies the slot number, teacher, room and subject and group to be taught.We provided the cell object with a copy construct, to return a new instance copy of the same cell. Also as we can notice from the above description, GenerateValidCell() will perform a call to the getRandomCell() / getRandomGCCell() of the Buffer static class in order to make current cell as a generated random valid cell, with or without the pre-specified groupid value.MutatedBy() method will accept a value, indicating what is the mutation performed by, and perform a mutation on the cell, executing the corresponding query. The available mutation types are: mutate by all (new generated random cell), mutate by group, mutate by period, mutate by room and mutate by teacher. Notice that the result of the mutation will be a valid cell._cumul property is very important when counting the fitness function. As the fitness function iterates through the current cell, the _cumul property will record the cumulative impact of the current cell on the fitness function total value._tillnow property will be also important as it also record the cumulative impact, but not totally cumulative, but just on the period of last genAlgoSettings.CrossOverCellNumbers number of cells. Then it can be used in future to define which interval of chromosome had the greatest impact on the total fitness function value.f – the flag which will indicate if the current cell has any contribution on worsening the fitness function value. Can be helpful in drawing the chromosome and coloring the bad cells.
As we said before, a Cell is the smallest building block of the chromosome, so the chromosome is the schedule itself, defined by a set of Cells. Chromosome is the item within the population, an item which will be evaluated by the fitness function, and finally, the output of the program.elements property – is an array of cells, which define the chromosome itselfff – defines the latest fitness function value, which is saved for faster access to avoid evaluating chromosome each timefv – fitness values, which assess the compliance on the chromosome to each of the 4 hard constraintsnumber – number of elements within the chromosomecopy() – the same copy constructor to copy the chromosome as a whole producing a new instance, and new instances of the contained cells
FF() – evaluate the chromosome using the fitness function – this will update the ff and fv properties of the current chromosome
GenerateChromosome() - will generate a totally random chromosome of number number of cells and is used to introduce the initial random population
MarkUsed() – will mark the current chromosome as used, by activating the used property / flag. This will be helpful to avoid the chromosomes that were already chosen as parents in the iteration through the present population. This way we can ensure that in the next iteration the chromosomes used will be not identical to the same parents already chosen.
clearFlags() – clears all the flags f of a cell
clearTillNow() - clears all the _tillnow and _cumul properties of the cells to be reused when transferring from the current population to the new population.
UpdateGroups() – retrieves and updates the groupid’s values of each cell in the chromosome, according to the _subject and _groupnumber properties. This will ensure the consistency of data, when the chromosome of some old data was saved, and need to be retrieved, but the values of the groupid’s has been changed.
Mutation() – mutates the chromosome, using the procedure defined in the Reproduction.Mutation.Run() static method.
Fitness function is a very important static class, which defines the procedures and heuristics for counting the fitness function value. Actually the main methods for counting the fitness function values are the count() and countSoft() method. These methods accept a chromosome as an input parameter, and return the total fitness function value as a result of execution.The interesting thing about the fitness function class that it is designed to operate in 2 modes: soft mode and hard mode. Depending on the current stage value, defined by the HeuristicSwitcher.Stage property the fitness function will decide whether to count its value based on the soft or hard constraints. the chromosome function FF() (Chromosome.FF()) will check for the value of HeuristicSwitcher.Stage to match Stages.Hard or Stages.Soft, and will choose to correspondingly return FitnessFunction.count() or FitnessFunction.countSoft() for the current chromosome.The constraints and their weights are multiplied correspondingly to show the impact of the constraint of the fitness function. They are organized as follows:Hard Constraints / Weights:
HC1() / hc1w, HC2() / hc2w, HC3() / hc3w, HC4() / hc4w
Soft Constraints / Weights:
SC1() / sc1w, SC2() / sc2w, SC3() / sc3w, SC4() / sc4w
This is considered as the main class of our implementation. The GeneticAlgorithm class is responsible for the main code flow management. The class contains several essential properties, which contribute to the work of the algorithm:
The algorithm consists of the three major parts: init() – initialization, connection to the database, and preprocessing of the data, input() – generating first random PresentPopulation, which will be the initial seed of the program, and run() – implementation of the algorithm itself to obtain the ResultChromosome using the PresentPopulation seed.
Heuristic Controller – this class is responsible for monitoring the performance of the currently used heuristic of reproduction and changing it to obtain better results. This way we ensure that the program will not enter the infinite loop and will try to reproduce in different types of defined techniques to reach better results. In order to monitor the performance of currently active heuristic, several properties are needed to be recorded and constantly reviewed:This is done by two methods of the static class: checkPerformance() – which will check the performance of the current heuristic based on some specific metrics, and takeAction() – takes some specific appropriate heuristic modification action, in case the performance using the active heuristic is unsatisfactory. Check performance works in the following way:
The algorithm checks for the number of consequent bad results. If it is more than GenAlgoSettings.SteppingNumberThreshold, than the whole heuristic after several number of chances is considered as bad, and a next heuristic is executed within the takeAction() method.
Heuristic Switcher checks for the currentHeuristic number and redirect the program to the next heuristic using the NextHeuristic() method. A heuristic within our implementation is defined as a set of values for optional attributes, such as mutateby, CrossOverNumber, MutationNumber, SteppingNumberThreshold, SmartCrossOver and CrossOverCellNumbers. Using these parameters we will be able to define specific heuristic, way of reproduction that can be used by the parent chromosomes to reproduce in different ways. The Stage parameter saves the value, defining if the program is current running in the hard or soft stage.
A male and a female chromosome is considered as parent, which will in future reproduce to obtain a better population. This parent object has a copy() constructor, which will call the copy constructors of both the chromosomes to produce a completely new copy of the parent instance.CrossOver() is a method which will recall the Reproduction.CrossOver.Run() in order to following the specific procedure for the current parent chromosomes. MarkUsed() will mark both the parent chromosomes, male and female as used.
Population is a set of chromosomes, which should be used to reproduce and obtain better population through evolution. The population contains the property number, which is the pointer to the last filled chromosome in the population. The count property returns the total number of chromosomes within the current population.This class contains several assisting methods to assist the work of the population in an easier way:
getAllFitness() – perform fitness function execution FF() for all the chromosomes in the population.
Reproduction class performs the actual reproduction, corresponding to the two methods: CrossOver and Mutation. The two methods of reproduction are defined as classes within the static reproduction class.
Stages Enumerator – indicates the HARD and SOFT stage of the running the algorithm. This will determine the fitness function count method chosen and the heuristics and their order.