1.2 – Genetics Algorithm – Problem Specification

1.2.1 – Introduction

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.

1.2.2 – Problem Description

Our timetabling problem has the following elements:

• A set of groups:
• A set of subjects:
• A set of teachers: we have to types of them:
1. Full time teachers: are all week periods free teachers, they can attend at any time and have no forbidden periods at any time of the week.
2. Part time teachers: they have certain periods to attend in, we must respect those periods in assigning subject.
• A set of periods of the school week: the week is divided into five days each day has Five periods the total number of periods for each group is 5*5=25 period, it means a maximum of 30 lessons per week to each group.

1.2.3 – Problem Elements (Objectives and Constraints of the Problem)

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:

• (H1) Every lesson has to be assigned to a period or a number of periods, depending on the lesson’s length.
• (H2) No teacher can give two simultaneous lessons.
• (H3) No room can be assigned to two simultaneous lessons.
• (H4) No teacher can give a subject which is out of his specialist, or the set of subjects he can give.
• (H5) Forbidden periods of the teacher must be respected (no part time teacher can give out of his available times.
• (H6) The teacher of a specified subject of a certain group must be unique.

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:

• (S1) All lessons of the same section cannot be assigned to the same day must be respected.
• (S2) Class timetables should be as compact as possible, eliminating idle times for students.
• (S3) Class timetables should be as compact as possible, eliminating idle times for students.
• (S4) In class timetables, if possible students should not have a day with a single lesson.

1.2.4 – Genetic Algorithm Application

1.2.4.1 – Flow Chart

1. Choose the initial population.
2. Select parent chromosomes.
3. Perform Crossover.
4. Perform Mutation.
5. Evaluate fitness of the new population.
6. Repeat 2 until satisfied.

1.2.4.2 – Elements of Our Solution

1. Nod x: which is a set of variables x (R, S, T, P)R: represents room
S: represents subject
T: represents teacher
P: represents period
the number of those variables is equal to the number of all lessons of all groups of all classes.
2. The initial solution (chromosomes):
We start working from the initial solution, which is the totally randomly generated population. When starting working we can reach the newer and newer population with better fitness function results, until totally satisfying the hard constraints. When all the hard constraints are satisfied we start working on the soft constraints until they are satisfied too. It’s essential during the work of this algorithm that all the hard constraints should be satisfied, while it’s not such essential that the soft constraints are satisfied. The chromosome is deemed to be a solution, if it satisfies all the hard constraints, and the optimal solution is the one that satisfies all the soft constraints too, producing a fitness function value of 0.
• Parent Chromosomes:
Parent chromosomes represent a parent with 2 children – male and female chromosomes, which are the actual data of the parent chromosome. These chromosomes are named as parent chromosomes, because they will reproduce using the crossover and mutation modifications to produce newer and more adaptive to the environment chromosomes, which will be decided by the fitness function, and choosing the most fitted parents for the next population.
1. Population:
Population represents the current state in the process of the evolution. Population is a set of chromosomes, which is limited to specific size. By continuous reproduction, and choosing the best fit for the next population, the present population is expected to develop to produce better and better results.
2. Crossover Point:
Crossover is one of the methods used for reproduction. Using this method reproduction is being made. This reproduction method is based on taking parent chromosomes and choosing a point – crossover point, where each one of the parent chromosomes will be divided into two parts. Then, the parent chromosomes reproduce by exchanging their parts, to produce two new chromosomes.One of the parameters needed to be identified how the crossover points are chosen. The basic method for choosing the crossover point is to choose a random cell within the chromosome. The second parameter that needs to be identified is the number of crossovers that has to been. Just as we are doing crossover in one point, we can do it in more than one point that might give a more variety to the reproduced chromosomes.
3. Mutation:
Mutation is another method of reproduction. Mutation is singular method of reproduction, as it is performed on a single chromosome, and not on the parent chromosomes (male and female). Using this method, we choose one of the cell parameters that we want to differentiate from others – to mutate. Then we mutate it to produce some new cell that introduces new data to the chromosome, and thus can affect its fitness.The two parameters that need to be identified here are: what should be mutated – some property of a cell, or all properties of a cell, and the second parameter – what is the best number of mutations that need to be done to introduce some variety, and not to get further from the optimal solution.
• Objective function f(x):
Objective function is the function which takes chromosome as an argument, evaluates it and gives the number, which represents the fitness, or the adaptation of the chromosome to the current environment.
In our scenario, the fitness function gives optimal value, when it equals 0. The fitness function is supposed to be evaluated checking the chromosome to match the hard and soft constraints. In our program the genetic algorithm goes through 2 stages of counting fitness function:
1 – hard stage – here we estimate the hard constraints within the chromosome
2 – soft stage – here we estimate the soft constraints within the chromosome, is used when the chromosome hard stage is accomplished.
• Stopping criteria:
The basic stopping criteria which can be considered is reaching zero as a fitness function of soft stage. As our program is multi-threaded, user can view the progress, pause and resume the algorithm while it’s running. These options help a user a lot, as the program does not have to make decision when to stop. Depending on the results, and user decision, the stop criteria will be decided, unless the fitness function of the second, soft stage reaches zero.

1.2.4.3 – Programming Elements Used

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: