How to represent a schedule for Timetabler Problem in Genetic Algorithms?

Question

For genetic algorithms usually genes symbolized like this:

PARENT1: 101101010101001001001001110011100110101011101101
PARENT2: 010100111011010101110101001001101011001010010110

so crossover, mutations may be done with this representations as like:

Choose a crossover point:

PARENT1: 1011010101010010 01001001110011100110101011101101
PARENT2: 0101001110110101 01110101001001101011001010010110

Perform crossover to produce a child:

CHILD: 1011010101010010 01110101001001101011001010010110

Which then becomes, a whole new chromosome:

CHILD: 101101010101001001110101001001101011001010010110

My problem is how to represent a weekly schedule gene in Java?

Examples are taken from this article: http://secretgeek.net/content/bambrilg.pdf

I am impelementing this timetabling problem in Java and want to represent

FIGURE 10: An Entire University Timetable

in Java.

Answer 1

The code below might give you an idea how to approach the problem. One solution (which would be the university timetable) consists out of an array of single rooms. These single rooms each have a 2dimensional array, where the columns are the days, and the rows are the hours. I set the HOURS to 16, since I think in the night time there will be no classes. So Hour Row 1 would be the first hour of the day... probably from 7 to 8 AM. The values of the array show which class is booked.

public class SingleRoom {
    static final int DAYS  = 7;
    static final int HOURS = 16;
    . . .
    private int[][] timetable = new int[DAYS][HOURS];   //0 would say room is not booked, >0 indicates the booked class (english advanced (12), object oriented programming (139), etc..)
}

public class Solution {
    static final int AVAILABLE_ROOMS = 26;
    . . .
    private SingleRoom[] university_timetable = new SingleRoom[AVAILABLE_ROOMS];    
}

mutations:

change class mutation - change the class to another random class or to zero = no booking

switch on / off class - if an hour at a day in a specific room is booked, switch it off if it is not booked, switch it on with a random class this is to give the algorithm the possibility to not book hours, since in the change class mutation the 0 has a low probability to be chosen

constraints: after creating your solutions, check against all constraints and keep the solutions that are valid the new valid solutions have to be inserted into your population (of solutions), if they are better to other solutions already in your population or if they enhance the diversity of your population

But in the document you referred to it is fairly good described how to implement a GA for this problem (starts with page 16).

I wrote a generic java framework for the multi-objective optimisation algorithm mPOEMS (Multiobjective prototype optimization with evolved improvement steps), which is a GA using evolutionary concepts.

You can find the code here, it might give you an idea how to approach your problem:

The solutions which you can find with this algorithm have been compared in a scientific work with state-of-the-art algorithms SPEA-2 and NSGA, and it has been proven that the algorithm performes comparable or even better, depending on the metrics you take to measure the performance.

You can find it here.

Further resources: My thesis which applies this framework to the project selection problem: http://www.ub.tuwien.ac.at/dipl/2008/AC05038968.pdf

The documentation of the framework: http://thomaskremmel.com/mpoems/mpoems_in_java_documentation.pdf

mPOEMS presentation paper: http://portal.acm.org/citation.cfm?id=1792634.1792653

Actually with a bit of enthusiasm you could easily adapt the code of the generic framework to your needs.

Do you write this GA in your job or as a student?