Genetic Algorithms (GA) were first introduced by John H. Holland in 1970 at University of Michigan. GAs are based in the idea of natural selection. Technically speaking, GAs are an Artificial Inteligence (AI) technique and belong to the class of search methods. They operate on a population of solutions and not only on one population as most of search methods does. GAs can be applied in problems that are difficult to solve using the standard methods.
The main elements that form a Genetic Algorithm are:
- A chromosomic representation
- An initial population
- An evaluation function (sometimes called the fitness function)
- Crossover operations
- Mutation operation (optional)
The GACS system uses GA to solve the timetabling problem that academic institutions face every year. The system is programmed in an object oriented way. The resources involved in the timetabling process (such as professors, subjects, classrooms and time) are represented by objects. But the most important class in the system is the class Gene. Every object (or instance) of this class contains all the necessary information to describe a class that will be imparted in the academic period. This information includes the subject that the gene is representing, the professor that will impart that class and also the days of the week, the time and the classroom where the class will be imparted.
The initial population starts with an array of Chromosome objects, wich in turn are an array of Gene objects. Every Chromosome represents a possible solution to the problem. The algorithm then starts to evaluate every Chromosome, and what actually does is to evaluate every Gene that contains the Chromosome. Then checks if some Chromosome gets an acceptable convergence value; if not, then the process of crossover (and in some cases the process of mutation too) begins. After that, the algorithm evaluates again the Chromosomes to see if someone gets an acceptable convergence value, and if not, then the cycle begins again. This cycle repeats over and over until the value of some chromosome converges or the number of generations (this number is specified by the user before start the algorithm) has been reached.
(1) Russel Stuart, Norvig Peter, Artificial Intelligence: A modern Approach, Prentice Hall. 1995.
(2) Genetic Algorithms - John H. Holland
(3) Algoritmos Genéticos
(4) Intro to GAs