Timetable Generator Using Genetic Algorithms 1

CHAPTER 1

INTRODUCTION
Paradigms of design theory are defined for the GA by natural selection as a quantitative
measurement of life and ability to contribute to the reproduction process. The second
property is the random genetic difference – mutation of the genetic information (this is
important for small populations. The third typical property is the process of reproduction,
which is the opportunity for genetic information exchange – crossing, which is how the
algorithm to be effective. The basic properties of design algorithms are defined as follows:
Algorithm design can be an effective tool for optimization of processes. (They are used in
cases, in which the aim is a searching of global extreme with a lot of several local extremes
of the same type exists). Design algorithms give the tools for monitoring of properties of k
-time generation. It can be monitored some changes, which are made by the changes, and by
this way of comparison of results of experiments without the changes, and with the change of
information in “chromosome”. Design algorithms give the opportunity to “social relations”
monitoring between the generations on the basis of information changes of “chromosome”.

1.1 Previous Work

The initiator of research in GAs is John Holland. Holland published the book "Adaptation in
Natural and Artificial Systems", and then on many dissertations and papers began to be
published by different researchers. In 1985 the general approach began to receive wide
attention. Two formal conferences on GAs: "Proceedings of the International Conference on
Genetic Algorithms and their Applications" It is held in odd years from 1985 in United States
and "Parallel Problem Solving from Nature" It is held in even years from 1990 in Europe. In
addition, the theory-oriented workshop "Foundations of Genetic Algorithms and Classifier
Systems" It is held every two years from 1990; the term classifier system denotes a simple
kind of GA based machine learning system. A well organized GA-List digest news list and
another EP-List digest are available via e-mail, while major journals publishing GA-related
papers are Evolutionary Computation, Machine Learning, Neural Networks, Artificial Life,
Adaptive Behaviour, and other Artificial Intelligence based journals.

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 2

CHAPTER 2

THE STRUCTURE OF E-LEARNING

TIMETABLE GENERATOR

The structure of e-learning timetable generator consist of four main modules, a top level of
this system structure is shown in figure 2.1. The major system modules are:
 Input Data module,
 Connection and relation between the input data module,
 Time interval and time slots module
 Applying GA module then extract the reports.

Fig 2.1: Structure of timetable generator

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 3

CHAPTER 3

INPUT DATA MODULE

The input data module is described by the CVS. CVS is a type of data from the database. The
data contains:

 Person: data describe the name of lecturers in the university.

 Subject: data describe the name of courses in the class in the university.

 Room: data describe the name of classes in the university and the capacity of each it.

 Time interval: is a time slot with a starting time and duration. It has a subject and
room where it takes place.
Structure of the input data in the generator is shown in figure 3.1.

Figure 3.1: The Structure of the input data in the generator

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 4

CHAPTER 4

CONNECTION BETWEEN INPUT DATA MODULES

The relation between the inputs is the main problem, because if the relation is true, it will
extract a good timetable and you can control the entity of it. The relations between the input
objects are shown in figure 4.1.

Figure 4.1: The relation between the input objects in the timetable problem

We show Person Object that has two attributes ID number and the name of the lecturers in
the university and Subject Object that has two attributes ID number and the name of the
courses will be studied in this class and Room Object has two attributes ID number and the
name of the classes in the university and Time interval Object have five attributes ID
number, Start time, Duration, Room_fk and Subject_fk. The Time interval Object is a time
slot with a starting time and duration and. It has a subject and a room where it takes place in
the time slot. The PERSON_SUBJECT Object is done to make a combination between the
Person Object and the Subject Object, because the Person Object has more than one time
interval for each person so to solve this problem. The object was done in the generator.

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 5

CHAPTER 5

APPLIED GA MODULE

The GA in the timetable problems process and optimize the gaps where the conflicts between
the time slots are depending on these constraints:
• Teacher cannot give more the one lecture at the same time.
• Teaching group cannot learn more subjects at the same time.
• Room can be devoted to only one subject at the same time.
• Room must be sufficient for the maximum number of students.

The structure of the genetic algorithm is consisting of five sub modules; a top level of this
system structure is shown in figure 5.1.

Figure 5.1 The Structure of the genetic algorithm

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 6

CHAPTER 6

SELECTION AND REPRODUCTION SUB-MODULES

A lot of strategies were used for parents’ selection for crossing and for selection of
individuals, which are active in the next generation. The best selection is as follows:
Tournament of parents
The new generation is created by crossing of individuals selected from the original
generation by the tournament method. In other words, the two parents are selected for the
new individual by the tournament method.

Tournament of parents + children

The temporary set of individuals is created. Parents of each individual are randomly selected
from original generation. To the next generation, individuals are selected by tournament form
set of both parents and their children.

6.1 INFLEUENCE PARAMETERS FOR GA RUN

The main aim of measurement was to know what parameter influences the tendency to
searching the time of processing. The speed of solving was evaluated by the number of
generations needed to create a “good” timetable. Cases were considered when the algorithm
did not finish the timetable in the declared number of generations. In the tests, mutation
probability was changed from 0.0 through 0.5 to 1.0. The size of tournament was 3, the size
of population 80, and selection tournament methods were used, such as parents + children,
and tournament parents as shown in table 6.1.

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 7

Table 6.1: The influence of parameters

Here startTime, (0.1 and 1) #parents (80 and 120), #TI's (80 and 120) have no tendency for
roomRate (0.1, 1, and 10) it seems to be that smaller values are better. The implementation of
mutation is very variable compared to the mutation of classic GA. In any case, it has the
function of normal mutation (with random change of chromosome part). The general
property of mutation is its ability to correct any error as a part of chromosome by the random
value (of suited values). The generalization of mutation is done by the tests, the strongest tool
in timetable searching. The probability of mutation is very low value (from 0.01 to 0.2) in
classical GA. The results of testing bring the conclusion that it suits to use the bigger value of
probability of mutation. The combination of antagonistic influences gives the best results
(lower number of generations). From the tests, it is clear that the higher probability of
mutation gives the higher speed of tendency of algorithm if we consider both of the number
of generation and the total time of computation. The above parameters were chosen in the
generator in table 6.2.

Table
6.2: The GA Parameters in the timetable generator

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 8

6.2 GENETIC ALGORITHM

The algorithm for GA in the e-learning timetable generator is as the follows:

Algorithm: Apply GA in the generator

Input: import de.data.IRoom: The list of rooms in the database.
import de.data.ISubject: The list of subjects in the database.
import de.data.IPerson: The list of persons in the database.
import de.data.TimeFormat: The themes of the timetable.
import de.data.ITimeInterval: The relation between the input data.
Output: The best individual to extract the timetable reports.
Step1: Define some variables in the algorithm:
private static final EvalComparator evalComparator = new EvalComparator ();
private Individuum originalIndividuum;
private Individuum bestIndividuum;
private int generation = 1;
Step2: Set the initial parameters to do GA: Size of Population, Number of Generations,
Crossover Probability, Mutation Probability, Number of Children and Parents.
Step3: Generate the individuals.
Step4: Store the best individuals in a variable to restore from it.
Step5: Produce new generation.
Step6: The time is enough go step 7 else go step 4.
Step7: Recombination of individuals to produce children.
Step8: Evaluate the individual.
Step9: Crossing the individual.
Step10: Mutate the individual.
Step11: If the individual is the best go step 12, else go step 8.
Step12: Select the best individual for the next generation.
Step13: Update the initial time intervals to the best time intervals.
Step14: Perform some changes on the time intervals.

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 9

Step15: Mutate the genes of all individuals.

Step16: Calculates and determine the gaps and the collision of each individual.
Step17: Choose the best evaluation of the individuals.
Step18: Extract the reports
Step19: End.

Pseudo Code of Function Generate the individuals

Input: Number of parents, Number of children, First evaluation.
Output: All individuals.

int noOfParents = privateProperties.getNoOfParents ();

int noOfAll = noOfParents + privateProperties.getNoOfChildren();
List<Individuum> allIndivid = new ArrayList<Individuum>(noOfAll);
for(int i = 0; i < noOfAll; i++) {
allIndivid.add(new Individuum(originalIndividuum)); }
generation = 1;
float firstEval = allIndivid.get(0).getEval() * 0.95f;
float secEval = firstEval;
while(generation < privateProperties.getMaxGeneration() && !finishIfRequested() &&
allIndivid.get(0).getEval() > targetValue) {
maxDelayInMin = privateProperties.getDelayInMinutes() * 1000 * 60;
currentMilliDelta = System.currentTimeMillis() - firstMillisForStatus;
if(currentMilliDelta > maxDelayInMin) {break; }
generation++;
//allow changing of parameters
int oldNoOfParents = noOfParents;
noOfParents = privateProperties.getNoOfParents();
noOfAll = noOfParents + privateProperties.getNoOfChildren();
allIndivid = ensureSize(allIndivid, noOfAll);
// recombination of individuals to 'produce' some children
for(int i = oldNoOfParents; i < noOfAll; i++) {
int i1 = random.nextInt(oldNoOfParents / 4);

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 10

int i2 = random.nextInt(oldNoOfParents);
allIndivid.set(i, new Individuum( allIndivid.get(i1), allIndivid.get(i2),
random.nextInt(allIndivid.get(i1).size()))); }
assert allIndivid.size() == noOfAll : "" + allIndivid.size();

6.3 STATISTICS IN THE GENERATOR

Before knowing the results of the statistics, we must know the main parameters to make
them, there are:
• #children should be more than 20
• roomRate should be less than 50
• dayRate should be more than 5
The parameters: #TI's, startTimeRate, mutationRate and #parents have no tendency.
The Statistics was made [mean, RmsError] at the following table 6.3.

Table 6.3: Statistic parameters in the generator

The mean values of all good values of every column were found in table 6.4.

Table 6.4: The best evaluation in the generator

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 11

Here the value in brackets was the rms error. In this section, we applied timetable generator
in a University. The fetcher study in the university is assumed to have two semesters; every
semester will last for 16 weeks. The week will start on Saturday and ends on Wednesday
from 8:00 am until 7:00 pm. The time slot is various from 60 to 240 minutes. There are four
types of the timetables in the university:
• Timetable for the lectures in the university.
• Timetable for virtual rooms that depend on the conference program between the lecturer
and the students.
• Timetable for the lab.

First Example
The input data needed to insert in the generator in the table 6.6. has a list of lecturer, classes
and rooms.

Input Data Assign Values

List of lecturer 56
List of Subjects(include the number of sections) 147
List of rooms 19

Table 6.5: Example parameters in the timetable Generator

Now we want to make relation between the inputs data. The first relation is between lecturer
and subjects by using the icon add subject and the results will be saved in the database as
shown in figure 6.5, we show how many subjects are chosen for every lecturer in this class.
However, there are many errors in the relation between the inputs data. Therefore, we want to
correct and optimize the errors found in the timetable. The genetic algorithm was build in the
E-learning timetable icon that makes the steps was explained in bravoes sections. In practice,
we can found collision between two subjects in the same time, we will use the genetic
algorithm to solve this problem.

Second Example

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 12

Timetable for virtual rooms that depend on the conference program between the lecturer and
the students and specific rooms that have special techniques to deal with conference program
for example pc device, internet, amplifier, …etc. this type is combination between the first
and second example, where the lecture is want a room that students still in it and a virtual
room to contact the lecturer by using the conference programming. This type of the timetable
is applied in the Cairo program in the University of Graduate Studies. The first relation is
between lecturer and subjects by using the icon add subject and the results will be saved in
the database. After that, we will make the relationship between subjects and rooms and insert
it in the timeslots depending on the university fetchers, so we will make relation between
rooms and time intervals and the relation between subjects and time intervals. After that we
want to view the input data and the relation between them, the icon execute make this
statement for the list of persons, subjects and rooms Now we will in every room join with a
virtual room.
Third Example
In this type of the timetable is similar in first 8 example but we want remember that in this
type the main constraint is order constraint, that means the theoretical subject is must be
before the lab subject. In the university in this semester, it has two labs and the colleges will
study are IT and Software Engineering. If we want to view the input data and the relation
between them, the icon execute make this statement for the list of persons, subjects and
rooms.
The optimal parameter values in E-learning timetable generator are very important to extract
the reports, so we want to consider the three criterions in the generator:
• Size of population: it is better to start with the low, but important size of population. Thirty
individuals are sufficient for deadlock prevent.
• Probability of mutation: the higher is better. Of course, the mutation of all individuals is
very far from classical GA, the optimal value of probability of mutation 0.8 is chosen.
• The number of individuals in a tournament: high number of individuals causes very
frequent deadlock in the local minimum. Suited value is 2 or 3, which give the higher
selection gradient.

CHAPTER 7

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 13

CONCLUSIONS

We have shown that a Genetic Algorithm approach is very effective and useful on the lecture
time tabling problems. Using the methods we have described shows great potential for
leading to timetables in future which are fairer to students. The framework seems directly
applicable to a very wide variety of other timetabling problems. For example, experimental
results show that a key aspect towards its success is the employment of the mutation
operators described. As we have shown, extensions of the basic technique to handle room
constraints. The GA in timetabling framework has been shown to be successful on several
real problems of 'University Department size', and so it seems we can justify the expectation
for it to work very well on most other problems of similar size and nature. That is, there is no
reason to suspect that there is anything particularly easy about the problems it was tested on,
in comparison to other real problems. Much work remains to do to see how performance
scales to larger and otherwise different kinds of timetabling problems. In summary, we have
shown that GA in timetabling framework, involving a good solution to correct and
optimization the errors and give the reports about the lecturers, classes and rooms.

CHAPTER 8

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 14

FUTURE ENHANCEMENTS

Future work is under way to more thoroughly test the performance of our technique on a
wider variety of timetabling problems. A GA based timetabling system very similar to the
one we describe could arrange for parallel sessions to be organized such that delegates are
collectively satisfied as far as possible, in terms of minimizing the degree to which two
presentations a delegate wishes to see are scheduled to occur at the same time. Further work
is wanted to perform comparisons in terms of speed and quality between the individuals.
Considering details of the GA in timetabling framework itself, the reason why not that is so
far we have used the GA mainly to resolve important stated constraints, but not for aesthetic
and similar issues which often concern humans. So, there might be some value in a post-
processing module that can:
• Move events from one slot into an adjacent slot, subject to not violating any additional
constraints, with the goal of packing the rooms more completely so as to reduce room
bookings and invigilation requirements.
• Assess the average spread of the events in some way, that is, if we have 2 timetables that
satisfy all of the constraints, the one with the larger average event spread is the better. This
gives the students more time between events.
• Insert more constraints to extract the excellent results for the timetable, for example the
level of the students is very important in the timetable.

BIBLIOGRAPHY

DEPT OF CSE, Dr. AIT 2010-2011

Timetable Generator Using Genetic Algorithms 15

URL’s:-

1. For Information:

 http://www.public.ccsds.//genetic%algorithm%timetable.com
 http://www.genetic%20algorithm%colomigroup.edu

References
1. Alberto Colorni, “A Genetic Algorithm to solve the time table problem”, Centre for
Emergent Computing, UK, 2000.
2. N.R. Jennings, “Coordination Techniques for Distributed Artificial Intelligence”,
University of London Mile End Rd.London E1 4NS UK, 1995.
3. Adrian Hooke, “Meet the Area Directors”, Pearson, 2007
4. Narayan Naik, “ Timetable Generation Technique”, McGraw Hill,1998

DEPT OF CSE, Dr. AIT 2010-2011