Creating Timetable Using Genetic Algorithms - Java & JGAP

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. 

Related Posts : http://crypt-sdk.blogspot.com/2012/04/timetabling-using-genetic-algorithm.html?utm_source=feedburner&utm_medium=feed&utm_campaign=Feed%3A+blogspot%2FIgiiX+%28Crypt+Blog%29

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

<?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.

1. 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.

 

2. 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,

3. Setup a Configuration object.

4. Create a population of potential solutions.

5. 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.