This is project done at my University. The team was me Sanka Darshana and Lasindu Charith . This blog post also written as team. We used Genetic Algorithm, Java Genetic Algorithm Package - JGAP for our project.
Making Timetables for an institution,
considering the resources of that institution so that the resources will not be
clashed on the usage with one another is NP complete task. But here we tried to
implement a solution for that using Genetic Algorithms.. If we take our
scenario as an example, our department needs to schedule its lecture slots so
that no clashes are happening between the availability of the resources of the
department. As department’s resources, we have considered lecturers’, rooms’
and students’ availabilities. If a lecture is to be held, all those who are
conducting, those who are attending and the rooms where the lecture is going to
held must be free at that time. So the problem is to find a way to generate a
timetable.
What is Genetic Algorithms (GA)
Genetic Algorithm (GA) is a type of Evolutionary Algorithms which adapts the evolutionary process of the genetic chromosomes into some computational problems. It has been widely used in optimization problems. In Genetic Algorithms there are basically two major components.
- Population
- Fitness function
The population is which the evolution is applied on. With the evolution and the correct Fitness function which measures the fitness of a given individual entity in a population, the following generations will have better members than the earlier generation. An individual element of the population is named a Chromosome following the chromosomes in the natural genetic process. A chromosome is consisted of Genes which are in-turn consists of the data which we want the chromosome to have. Within each iteration many genetic operators are applied to the population so the next generation will be different from the current one. There are basic operators we have used in our attempt.
- Cross-over
- Mutation
In cross-over operation, genes from 2 chromosomes are combined to make other new chromosomes. And in mutation, some genes of a chromosome are mutated in a way that the random behaviors can be generated. This randomness important because as the iterations happen, the population tends to converge to some solution while there may be some solutions which can be more acceptable. As GA doesn’t generate the best solution but an acceptable one we have to optimize the evolution process due to the fact that an inefficient application of GA could get long time before making an acceptable solution
Application Of Genetic Algorithms
The most
difficult and challenging task of the project was the application of GA into
our problem. The way of application could affect the amount of resources
required by the program.
We considered
the lecturers, students and rooms as constraints which will be needed to be
satisfied. Each constraint contains a representation of which time slots they
are available and the other time slots are considered unavailable. Each subject
will have the identifications of the lecturers, students and the rooms involved
with the subject and lecture slots will contain the subject and the time slots
which the lecture is to be held.
In genetic
algorithms the base elements of the algorithm are Chromosomes and Genes. So
here we had to choose them. We will explain how we did it in next section. Also
to run the algorithm we have to check the appropriateness of those genes and
chromosomes. To do it we have to run a check to get the fitness for the
solution. That check is run by the fitness function. We will explain it also in
the next section
Implementation
For the
implementation we have used Java language for programming. We used a framework
named JGAP (Java Genetic Algorithm and Genetic Programming framework) for the
implementation of the Genetic Algorithm. We used Java Swing framework for
implementing the GUIs and data was stored in a XML file for manipulation. To represent
the data used for the algorithm, we used a XML file. Following XML examples
will show we did it,Each start
time and other time are represented in this format,
If the time
is Monday at 8 am = we represent it as 8
If the time
is Monday at 1 pm = we represent it as 13
If the time
is Tuesday at 8 am = we represent it as 24+8 = 32
If the time
is Thursday at 3 pm = we represent it as 24+24+24+15 = 87
All the
length of time slots is given in hours.
Lecturer Entity
Lecturer Entity
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<lecturers count="1" >
<lecturer id="0" >
<name>Dr_Chandana_Gamage</name>
<availableSlots count="5" >
<slot>
<start>8</start>
<length>8</length>
</slot>
<slot>
<start>32</start>
<length>4</length>
</slot>
<slot>
<start>56</start>
<length>8</length>
</slot>
<slot>
<start>80</start>
<length>8</length>
</slot>
<slot>
<start>104</start>
<length>8</length>
</slot>
</availableSlots>
</lecturer>
</lecturers>
Student Entity
<students count="1" > <student id="0" > <name>Sanka</name> <level>2</level> <availableSlots count="5" > <slot> <start>8</start> <length>10</length> </slot> <slot> <start>32</start> <length>10</length> </slot> <slot> <start>56</start> <length>10</length> </slot> <slot> <start>80</start> <length>10</length> </slot> <slot> <start>104</start> <length>10</length> </slot> </availableSlots> </student> </students>
Subject Entity
Here
each lecturers and students who are related the subject is represented
by their id number. The potential lecture rooms for this subject is also
represented by their id. Also another important thing here is lectures
and practicals of subject considered as two different subject in this
implementation. That why there is a tag called isPractical.
<subjects count="1" > <subject id="0" > <name>TOC</name> <isAPractical>0</isAPractical> <lecturers count="2" > <id>0</id> <id>1</id> </lecturers> <students count="2" > <id>0</id> <id>1</id> </students> <rooms count="3" > <id>0</id> <id>1</id> <id>2</id> </rooms> </subject> </subjects>
Lecture Room Entity
Here the lecture rooms and labs are identified by the tag iLectureRoom.
<rooms count="1" > <room id="0" > <name>CSLR</name> <seatCount>20</seatCount> <isLectureRoom>1</isLectureRoom> <availableSlots count="9" > <slot> <start>8</start> <length>4</length> </slot> <slot> <start>13</start> <length>5</length> </slot> <slot> <start>37</start> <length>5</length> </slot> <slot> <start>56</start> <length>4</length> </slot> <slot> </slot> <slot> <start>80</start> <length>4</length> </slot> <slot> <start>85</start> <length>5</length> </slot> <slot> <start>104</start> <length>4</length> </slot> <slot> <start>109</start> <length>5</length> </slot> </availableSlots> </room> </rooms>
Lecture Entity
This
is the most important entity in the XML representation. Here the data
in side lecture tag represent the time table. At the beginning, before
the time table generating algorithm runs we have add lecture entity. But
the start time of the lecture,venue cant be said at the beginning. So
we used the following approach to represent the lecture data,
<lectures count="1" > <lecture id="0" level="2" > <subject>0</subject> <room>0</room> <slot> <start>0</start> <length>2</length> </slot> </lecture> </lectures>
Here
the room,start tags cant be finalized at the beginning. Because they
change while the time table algorithm runs. So at the beginning we set
them to default value of 0. All the lecture entries will be same as that
at the beginning. But after the time table algorithm runs, those tags
will be change like this,
<lectures count="1" > <lecture id="0" level="2" > <subject>0</subject> <room>3</room> <slot> <start>15</start> <length>2</length> </slot> </lecture> </lectures>
We followed five basic steps to implement the Algorithm.
- Plan the Chromosome.
We
have decided following structure of chromosomes and genes. We choose
the four time tables set as a chromosome and each one time table as a
gene. For each evolving iteration those genes and chromosomes are
changed by crossover and mutation.
- Implement a "fitness function".
To Implement a fitness function in this problem. We have to add constrains to be checked in the fitness function. So following structure we implemented for the constrains.
At the concrete implementation of these constrains we follow the following structure,
- Setup a Configuration object.
- Create a population of potential solutions.
- Evolve the population
Generating a good solution set from the initially created solution set is process of evolution in genetic algorithms. To evolve a population of solutions we took two approaches. One is changing a chromosome Little bit by changing a lecture time or venue and checking it with the fitness functions to check the fitness. If the fitness is up to some value it will put to the next population. This process is called the mutation process.
Other process is called the cross over process. In it we took one part form one chromosome and other part form other chromosome. Then we join it to have a new solution. Then we check with the fitness functions to check the fitness. If the fitness is up to some value it will put to the next population.
So in the evolution process these two happens for the population to get the next population. So what we did was evolving the initial population for number of iteration to get the new populations. At each evolution the population move towards the optimal solution. The number of evolutions is proportional to the correctness of the population. So following graph will show how our implementation behaves with respect to the number of evolutions. Here the y axis gives the fitness value of the population,
So like wise doing number of evolutions we can deduce a good timetable according to our given constrains. We have created a GUI also so user of this solution can change those constraints easily.
