Genetic Algorithms and Application in Examination Scheduling

TABLE OF CONTENTS

ACKNOWLEDGEMENTS

LIST OF TABLES

LIST OF FIGURES

PREFACE

Chapter 1. Introduction Genetic Algorithms
1.1. A brief history of genetic algorithms
1.2. Biological terminology
1.2.1. Chromosome
1.2.2. Reproduction
1.3. A basic genetic algorithms
1.4. Operators of GAs
1.4.1. Selection
1.4.2. Encoding
1.4.3. Crossover and mutation
1.5. Parameters of GAs
1.5.1. Crossover probability
1.5.2. Mutation probability
1.5.3. Population size
1.6. Preliminary

Chapter 2. The Examination Scheduling Problems
2.1. The set of hard and soft constraints
2.2. The activities needed for a basic examination scheduling problem
2.2.1. General activities for examination scheduling
2.2.2. The activities of staffs in a faculty
2.2.3. Activities of staffs at the central examination scheduling office
2.3. The related works on examination scheduling problems
2.3.1. Sequential methods
2.3.2. Cluster methods
2.3.3. Constraint based methods
2.3.4. Meta-heuristic methods
2.4. Preliminary

Chapter 3. The Application in Examination Scheduling
3.1. System overview
3.1.1. Project overview
3.1.2. The actor and specification
3.1.3. The database design
3.2. The proposed genetic algorithms
3.2.1. Representations
3.2.2. Initializing a random population of chromosomes
3.2.3. Evaluating fitness function
3.2.4. Crossover
3.2.5. Mutation
3.3. The functions of the examination scheduling system
3.3.1. Manage information of lecturers, classes, courses and classrooms
3.3.2. Manage all conflicts of the examination scheduling problem
3.3.3. Implement genetic algorithms
3.3.4. Display the statistics in courses, classes and lecturers
3.3.5. Save the results into file excel
3.4. Preliminary

Chapter 4. Experimental Results
4.1. The actors diagram
4.1.1. The actors
4.1.2. Use case
4.2. All functions of the examination scheduling system
4.2.1. Login
4.2.2. Manage all information of lecturers, classes, courses and classrooms
4.2.3. Manage all conflicts of lecturers, classes and classrooms
4.2.4. Implement genetic algorithms
4.2.5. Display the results
4.2.6. Save the results into file excel
4.3. Preliminary

CONCLUSION
Conclusion
Future Works

REFERENCES

APPENDIX A

DATA DICTIONARY
A1. Giaovien
A2. RBGiaovien
A3. Lop
A4. RBLop
A5. MonHoc
A6. PhongHoc
A7. RBPhongHoc
A8. LichCoiThi

Abstract

In this thesis, we present an introduction about genetic algorithms (GAs). Genetic algorithms are not too hard to program or understand, since they are biologically based. This thesis also shows scheduling problems, expecially examination scheduling problems. We provide a way that can be easily used to apply the evolutionary principle to the problem solutions. Furthermore, these are the program’s applications in reality as well as in science

Keyword: Genetic Algorithms, Scheduling Problems, Examination Scheduling Problems

ACKNOWLEDGEMENTS

First and foremost, I would like to thank Assistant Professor Dr. Vu Dinh Hoa for his support and encouragement throughout my studying master at Hanoi National University of Education. I deeply appreciate not only his intelligence, knowledge, and willingness to provide guidance for my thesis, but also his sense of humor and his enthusiasm.

Grateful acknowledgements are addressed to Mr. Do Trung Kien, Mr. Nguyen Huu Xuan Truong, Mr. Pham Thi Lan and other members of the seminar Computer Science for their valuable and constructive comments on this thesis.

I wish to express my gratitude to all teachers, staffs at Hanoi National University of Education for their knowledge, encouragement and support during my study.

Thanks to my friends, graduate students, for their encouragement. They also made my time at HNUE an enjoyable experience.

The most sincere thanks to my parents who have always been true believers and encouraged me in the past two years.

Dang Xuan Tho

LIST OF TABLES

Table 2-1. Examination supervised by a faculty

Table 2-2. Examination assignment

Table 2-3. Sample timetable

Table 4-1. Giaovien

Table 4-2. RBGiaovien

Table 4-3. Lop

Table 4-4. RBLop

Table 4-5. MonHoc

Table 4-6. PhongHoc

Table 4-7. RBPhongHoc

Table 4-8. LichCoiThi

LIST OF FIGURES

Figure 1-1. Lecturers, Classes, Classrooms, Courses and conflict

Figure 1-1. Roulette Wheel Sellection

Figure 1-2. Situation before ranking (graph of fitnesses)

Figure 1-3. Situation after ranking (graph of order numbers)

Figure 1-4. ( + x ( / 5 y ) )

Figure 1-5. ( do_until step wall )

Figure 1-6. Single point Crossover – Binary Encoding

Figure 1-7 Two point Crossover – Binary Encoding

Figure 1-8. Uniform Crossover – Binary Encoding

Figure 1-9. Arithmetic Crossover – Binary Encoding

Figure 1-10. Mutation – Binary Encoding

Figure 2-1. Graph of 12 events

Figure 2-2. Graph after coloring

Figure 2-3. Multi agent system

Figure 3-1. The system overview

Figure 3-2. The system’s functions outline

Figure 3-3. The Database Design

Figure 3-4. High level representation of the proposed genetic algorithm

Figure 3-5. A sub-timetable

Figure 3-6. A chromosome

Figure 3-7. Population

Figure 3-8. Algorithm for initializing a random population

Figure 3-9. Crossover

Figure 3-10. Mutation

Figure 4-1. Actor diagram

Figure 4-2. Use case diagram of the examination scheduling system

Figure 4-3. Login

Figure 4-4. Functions of administrator

Figure 4-5. The day started the examination

Figure 4-6. Manage lecturers

Figure 4-7. Manage classes

Figure 4-8. Manage courses

Figure 4-9. Manage classrooms

Figure 4-10. Conflicts of lecturers

Figure 4-11. Conflict of classes

Figure 4-12. Conflicts of classrooms

Figure 4-13. Implement GAs

Figure 4-14. Implement GAs finished

Figure 4-15. Display courses

Figure 4-16. Display classes

Figure 4-17. Display lecturers

Figure 4-18. Save the result into file excel

PREFACE

Problem Statement

Examination scheduling problems are very common, but very difficult to solve in practice. They are known as constraint optimization problems, NP hard problems, these are concerned with the allocations, subject to constraints of given resources to objects in space and time in such a way as to satisfy a possible set of desirable objectives [1]. Courses will be scheduled to time and classrooms so that lecturers can supervise and students can attend these courses without any conflicts. A large number of researches have been carried out on these problems [1].

illustration not visible in this excerpt

Figure 1-1. Lecturers, Classes, Classrooms, Courses and conflict

The examination scheduling will become more complex in a multiple classes, subjects, classrooms and lecturers, as illustrated in Figure 1-1. So, the number of conflicts about them is creasing more and more. The lecturers may be busy in some differents days, the classrooms are sometime shared between faculties, the classes have the different numbers of students. Each faculty needs its own timetable for its own resources. As a result, many problems still exist in the examination scheduling related to the resources.

The examination scheduling itself contains a large number of conflicts and needs a large amount of processing time. This study proposes a hybrid centralized and de-centralized approach and genetic algorithm to the examination scheduling problem in a faculty universities. The proposed approach and the genetic algorithm are used to solve the NP hard problems.

Background

The genetic algorithm (GA) is a global search optimization algorithm using parallel points. While searching for solutions, the GA uses a fitness function that affects the direction of the search [2]. The GA evaluates the population by using genetic operators such as selection, crossover, and mutation. The outline of the basic GA is presented:

illustration not visible in this excerpt

The GA is based on the principle of survival of the fittest members of the population to produce the solution. The selected individual according to the fitness level of the problem domain creates the set of solutions. The GA is an iterative process that is repeated until the convergence criterion is satisfied.

The Objectives of the Study

The objectives of this study can be defined as follows:

- To provide a system that helps multiple faculty universities solve their course scheduling problems.
- To investigate the use of the proposed GAs to the examination scheduling problem in a faculty universities.

Overview

Help the readers can get the insights from general to detail as well as the results of the thesis, the structure of the thesis is presented:

Chapter 1: About genetic algorithm. This Chapter introduction to the brief history, some developments of the genetic algorithm, biological basis, the operators, the parameters of the algorithm. More details on the operation selection, coding, crossover and mutation. Help readers have an overview of genetic algorithms.

Chapter 2: Examination Scheduling problem is reviewed. This chapter presents the problem NPC - as examination scheduling problem, the problem that required the test as scheduled, and related issues to resolve some problems have made the world today. Help readers better understand the problem that be solved by the thesis.

Chapter 3. The application in examination scheduling. This chapter presents an overview of the system, system architecture, user class specification, design database and system functions. The chapter also describes how specific applications of genetic algorithms to scheduling problems, giving readers detailed information about features, system implementation examination scheduling.

Chapter 4. Experimental Results. This chapter summaries the conclusions during the thesis. Giving readers more specific information about the functions has been implemented in the system.

Conclusion. Last chapter, this section presents about the conclusions, the limitations and the future development of the thesis.

Chapter 1. Introduction Genetic Algorithms

Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence.

As we can guess, genetic algorithms are inspired by Darwin's theory about evolution. Simply said, solution to a problem solved by genetic algorithms is evolved. [2]

1.1. A brief history of genetic algorithms

In the 1950s and the 1960s several computer scientists independently studied evolutionary systems with the idea that evolution could be used as an optimization tool for engineering problems. The idea in all these systems was to evolve a population of candidate solutions to a given problem, using operators inspired by natural genetic variation and natural selection. [3]

In the 1960s, Rechenberg (1965, 1973) introduced "evolution strategies" ( Evolutionsstrategie in the original German), a method he used to optimize realívalued parameters for devices such as airfoils. This idea was further developed by Schwefel (1975, 1977). Fogel, Owens, and Walsh (1966) developed "evolutionary programming," a technique in which candidate solutions to given tasks were represented as finiteístate machines.

Several other people working in the 1950s and the 1960s developed evolutioníinspired algorithms for optimization and machine learning. Box (1957), Friedman (1959), Bledsoe (1961), Bremermann (1962), and Reed, Toombs, and Baricelli (1967) all worked in this area, though their work has been given little or none of the kind of attention or followup that evolution strategies, evolutionary programming, and genetic algorithms have seen.

Genetic algorithms (GAs) were invented by John Holland in the 1960s and were developed by Holland and his students and colleagues at the University of Michigan in the 1960s and the 1970s.

Holland's 1975 book Adaptation in Natural and Artificial Systems presented the genetic algorithm as an abstraction of biological evolution and gave a theoretical framework for adaptation under the GA. Holland's GA is a method for moving from one population of "chromosomes" (e.g., strings of ones and zeros, or "bits") to a new population by using a kind of "natural selection" together with the geneticsíinspired operators of crossover, mutation, and inversion. Each chromosome consists of "genes" (e.g., bits), each gene being an instance of a particular "allele" (e.g., 0 or 1). The selection operator chooses those chromosomes in the population that will be allowed to reproduce, and on average the fitter chromosomes produce more offspring than the less fit ones. Crossover exchanges subparts of two chromosomes, roughly mimicking biological recombination between two singleíchromosome ("haploid") organisms; mutation randomly changes the allele values of some locations in the chromosome; and inversion reverses the order of a contiguous section of the chromosome, thus rearranging the order in which genes are arrayed. (Here, as in most of the GA literature, "crossover" and "recombination" will mean the same thing.)

In the last several years there has been widespread interaction among researchers studying various evolutionary computation methods, and the boundaries between GAs, evolution strategies, evolutionary programming, and other evolutionary approaches have broken down to some extent. Today, researchers often use the term "genetic algorithm" to describe something very far from Holland's original conception.

1.2. Biological terminology

At this point it is useful to formally introduce some of the biological terminology that will be used throughout the thesis. In the context of genetic algorithms, these biological terms are used in the spirit of analogy with real biology, though the entities they refer to are much simpler than the real biological ones.

1.2.1. Chromosome

All living organisms consist of cells. In each cell there is the same set of chromosomes . Chromosomes are strings of DNA and serves as a model for the whole organism. A chromosome consist of genes , blocks of DNA. Each gene encodes a particular protein. Basically can be said, that each gene encodes a trait , for example color of eyes. Possible settings for a trait (e.g. blue, brown) are called alleles . Each gene has its own position in the chromosome. This position is called locus .

Complete set of genetic material (all chromosomes) is called genome . Particular set of genes in genome is called genotype . The genotype is with later development after birth base for the organism's phenotype , its physical and mental characteristics, such as eye color, intelligence etc.

1.2.2. Reproduction

During reproduction, first occurs recombination (or crossover ). Genes from parents form in some way the whole new chromosome. The new created offspring can then be mutated. Mutation means, that the elements of DNA are a bit changed. This changes are mainly caused by errors in copying genes from parents. [2]

The fitness of an organism is measured by success of the organism in its life.

1.3. A basic genetic algorithms

Algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope, that the new population will be better than the old one. Solutions which are selected to form new solutions (offspring) are selected according to their fitness - the more suitable they are the more chances they have to reproduce.

This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied.

Outline of the Basic Genetic Algorithm:

illustration not visible in this excerpt