24-08-2012, 10:04 AM
A TIMETABLE PREDICTION FOR TECHNICAL EDUCATIONAL SYSTEM USING GENETIC ALGORITHM
A TIMETABLE PREDICTION FOR TECHNICAL.pdf (Size: 101.19 KB / Downloads: 82)
ABSTRACT
This paper deals with the implementation of a computer program, which employs Genetic Algorithms (GAs) in
the quest for an optimal class timetable generator. The program is written in Java and incorporates a repair strategy for
faster evolution. This paper also explains an example usage of Genetic Algorithms (GAs) for finding optimal solutions
to the problem of Class Timetable. It is seen that the GA could be improved by the further incorporation of repair
strategies, and is readily scalable to the complete timetabling problem. The system at present does not take care of other
constraints like unavailability of lecturers, small size of rooms and time required by the lecturer to move from one class
to other class, which is to be considered in the future up gradations. The automated class timetable is used at the dept.
of Computer Science & Engineering, Guru Nanak Institute of Technology (GNIT), Hyderabad, India and in future it
will be used by other faculty administrators and proposes solutions to be considered by the parties involved:
administration, departments and students.
Keywords: Genetic Algorithms, Timetable, Scheduling, and Automated
1. INTRODUCTION
The class timetabling is a major administrative
activity for a wide variety of institutions. A
timetabling problem can be defined to be the
problem of assigning a number of events into a
limited number of time periods. A. Wren defines
timetabling as follows: “Timetabling is the
allocation, subject to constraints, of given to objects
being placed in space time, in such a way as to
satisfy as nearly as possible a set of desirable
objectives [1]”.
In this paper, we concentrate on the classtimetabling
problem. The problem is subject to
many constraints that are usually divided into two
categories: “hard” and “soft” [4]. This work was
partially supported by the Research Committee of
the Guru Nanak Institute of Technology (GNIT),
under the research program, in order to produce
high quality timetables with optimal constraint
satisfaction and optimization of the timetable’s
objectives at the same time.
1.1 Hard Constraints
Hard constraints are rigidly enforced.
Examples of such constraints are:
No lecturer should have different classes at
the same time slot.
There cannot be more than 2 classes for a
subject on one day
For each time period there should be
sufficient resources (e.g. rooms and
lecturers) available for all the events that
have been scheduled for that time period.
1.2 Soft Constraints
Soft constraints are those that are desirable but
not absolutely essential. In real-world situations it
is, of course, usually impossible to satisfy all soft
constraints. Examples of soft constraints (in both
exam and course timetabling) are:
Every staff should get at least one first
hour
Lecturer having two theory subjects has no
lab assignments
Lecturer having one theory may get two
lab classes.
A particular class may need to be
scheduled in a particular time period.
Lab Classes may not be in consecutive
hours.
Lecturers may prefer to have all their
lectures in a number of days and to have a
number of lecture-free days.
1.3 The Class Timetable Problem
Journal of Theoretical and Applied Information Technology
© 2005 - 2010JATIT. All rights reserved.
www.jatit.org
60
Time Table problems are mainly classified as
constraint satisfaction problems, where the main
goal is to satisfy all problem constraints, rather than
optimizing a number of objectives. At present,
science has no analytical solution method for all
problem cases of this category, other than
exhaustive search, which however cannot be
applied but only to toy problems. Due to the
immense search spaces, Automated timetable
scheduling, on the other hand, is a task of great
importance as it can save a lot of man-hours work,
to institutions and companies, and provides optimal
solutions with constraint satisfaction [3].
Scheduling is the arrangement of entities (people,
tasks, vehicles, lectures, exams, meetings, etc.) into
a pattern in space-time in such a way that
constraints are satisfied and certain goals are
achieved [1]. Constructing a schedule is the
problem in which time, space and other (often
limited) resources have to be considered in the
arrangement.
Holland’s original schema was a method of
classifying objects, then selectively “breeding”
those objects with each other to produce new
objects to be classified [5]. Created for the direct
purpose of modeling Darwinian natural selection,
the programs followed a simple pattern of the birth,
mating and death of life forms. A top-level
description of this process is given in figure 1[5],
[6], [7].
Create a population of creatures.
Evaluate the fitness of each creature.
While the population is not fit enough:
{
Kill all relatively unfit creatures.
While population size< max;
{
Select two population members.
Combine their genetic material to create a new creature.
Cause a few random mutations on the new creature.
Evaluate the new creature and place it in the population.
}
}
Figure 1: Top Level description of a GA.
Genetic algorithms (GAs) are evolutionary
algorithms that use the principle of natural selection
to evolve a set of solutions toward an optimum
solution. GAs are not only very powerful, but are
also very easy to use as most of the work can be
encapsulated into a single component, requiring
users only to define a fitness function that is used to
determine how “good” a particular solution is
relative to other solutions.
The creatures upon which the genetic
algorithm acts are composed of a series of units of
information- referred to as genes. The genes, which
make up each creature, are known as the
chromosome. Each creature has its own
chromosome.
A GA, as shown in figure 1 requires a process
of initializing, breeding, mutating, choosing and
killing. The order and method of performing each
of these gives rise to many variations on Holland’s
original schema.
1.4 Chromosome Encoding, Fitness, Crossover and Mutation
Holland encoded chromosomes as a string of
binary digits. A number of properties of binary
encoding work to provide simple, effective and
elegant GAs. There are, however, many other ways
to represent a creature’s genes, which can have
their own implicit advantages. In order to get a
problem into gene form, the substance of its
solution must be represented as a collection of units
of information [8]. This is true of many problems.
For example, when designing a weekly budget, the
amount spent on each item could be stored as a
number in a column. This can be thought of as not
just a list of values but a string of genes. The value
in the first row might represent the amount of
money to spend on rice, and the second row might
be the amount of money to spend on caviar and so
on. Each of these values might be converted from
base 10 to base 2 to create a fixed width binary
number. Hence the problem of minimizing your
budget while maintaining your survival is translated
into a genetic representation. A collection of
possible budgets could be thus encoded, producing
a population of Budget creatures. Random
populations are almost always extremely unfit [8].
In order to determine which are fitter than others,
each creature must be evaluated. In order to
evaluate a creature, some knowledge must be
known about the environment in which it survives.
Depending on the way we structure the method of
evaluating a chromosome we can either aim to
generate the least costly population or the most fit;
it is a question of minimizing cost or maximizing
fitness. In the budgeting example, the heuristic
concerning caviar can be represented with a cost. In
optimization problems cost is not a measure of
money, but a unit of efficiency [7], [8]. When
discussing optimization techniques, the range of
possible solutions is often referred to as the solution
space and the cost/fitness of each point in the
solution space is referred to as the altitude in the
landscape of the problem. To looking for the global
minimum of the cost is also to look for the lowest
point in the lowest valley of the cost landscape.
Similarly, to look for the global maximum fitness is
Journal of Theoretical and Applied Information Technology
© 2005 - 2010JATIT. All rights reserved.
www.jatit.org
61
to look for the highest point of the highest mountain
in the fitness landscape.
In various GAs, the method of selecting
creatures for breeding is handled in different ways.
Holland’s original model uses a method where the
healthiest are most likely to breed. Other methods
select any two creatures at random for breeding.
Selective breeding can be used in conjunction with
or in the absence of an Elitist Natural Selection
Operator- in either case the GA can perform
evolution [7]. Once parents have been chosen,
breeding itself can then take place. A new creature
is produced by selecting, for each gene in the
chromosome, an allele from either the mother or the
father. The process of combining the genes can be
performed in a number of ways. The simplest
method of combination is called single point crossover
[5], [7], [8]. This can be best demonstrated
using genes encoded in binary, though the process
is translatable to almost any gene representation. A
child chromosome can be produced using single
point crossover, as shown in figure 2. A crossover
point is randomly chosen to occur somewhere in
the string of genes. All genetic material from before the
crossover point is taken from one parent, and all material
after the crossover point is taken from the other [8].
Figure 2: An Example of Crossover with Fully
encoded Genes
After crossover is performed and before the child is
released into the wild, there is a chance that it will
undergo mutation. The chance of this occurring is
referred to as the mutation rate. This is usually kept
quite small [8]. The purpose of mutation is to inject
noise, and, in particular, new alleles, into the
population. This is useful in escaping local minima
as it helps explore new regions of the multi
dimensional solution space [7]. Once a gene has
been selected for mutation, the mutation itself can
take on a number of forms. This, again, depends on
the implementation of the GA. In the case of a
binary string representation, simple mutation of a
single gene causes that genes value to be
complemented- a 1 becomes a 0 and vice versa.
In Holland’s founding work on GAs he made
mention of another operator, besides selection,
breeding, crossover and mutation which takes place
in biological reproduction. This is known as the
inversion operator [8]. An inversion is where a
portion of chromosomes detaches from the rest of
the chromosome, then changes direction and
recombines with the chromosome.
We present an approach to solve this large, highly
constrained timetabling problem, based on
evolutionary algorithms. In chapter two we describe
the proposed system taking as an example the
department of Computer Science and Engineering,
GNIT. Third chapter gives the implementation
details about the algorithm. While the fourth
chapter shows the results of the program (written in
java) and chapter five shows the conclusion and
future works.