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.
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:
Frequently asked questions
What is the topic of this document?
This document provides an overview of genetic algorithms and their application to examination scheduling problems. It includes a table of contents, abstract, acknowledgements, lists of tables and figures, a preface, and summaries of each chapter.
What are genetic algorithms (GAs)?
Genetic algorithms are a type of optimization algorithm inspired by biological evolution. They use processes like selection, crossover, and mutation to evolve a population of candidate solutions to a problem.
What are examination scheduling problems?
Examination scheduling problems involve allocating resources like time slots and classrooms to exams while satisfying various constraints, such as avoiding conflicts between students taking multiple exams or ensuring lecturers are available to supervise.
What key concepts related to genetic algorithms are discussed?
The document covers concepts like chromosomes, genes, alleles, locus, genotype, phenotype, recombination, mutation, and fitness. It also explains the basic steps of a genetic algorithm, including initialization, selection, crossover, mutation, and evaluation.
What are the chapters in this document about?
- Chapter 1 introduces genetic algorithms, their history, and biological terminology.
- Chapter 2 discusses examination scheduling problems and related work.
- Chapter 3 describes the application of genetic algorithms to examination scheduling, including system overview, database design, and the proposed algorithm.
- Chapter 4 presents experimental results.
- The document also includes a conclusion, future works, references, and an appendix with a data dictionary.
What is the purpose of this study?
The study aims to provide a system that helps universities solve their examination scheduling problems using genetic algorithms.
What is included in the data dictionary (Appendix A)?
Appendix A includes a data dictionary detailing various entities related to examination scheduling, such as Giaovien (Lecturer), RBGiaovien, Lop (Class), RBLop, MonHoc (Course), PhongHoc (Classroom), RBPhongHoc, and LichCoiThi.
What are the constraints considered in examination scheduling problems?
The examination scheduling problem has hard and soft constraints that involve satisfying desirable objectives to make sure courses can be schedules so that lecturers can supervise, students can attend these courses without any conflicts.
What are some of the related works on examination scheduling?
Related works on examination scheduling include sequential methods, cluster methods, constraint-based methods, and meta-heuristic methods.
What functions does the examination scheduling system provide?
The examination scheduling system functions include:
- Managing information of lecturers, classes, courses, and classrooms.
- Managing conflicts of lecturers, classes, and classrooms.
- Implementing genetic algorithms.
- Displaying statistics in courses, classes, and lecturers.
- Saving the results into excel files.
- Quote paper
- Dang Xuan Tho (Author), 2009, Genetic Algorithms and Application in Examination Scheduling, Munich, GRIN Verlag, https://www.grin.com/document/151708
