Genetic algorithms and application in examination scheduling

Application of genetic algorithms on the specific problem is not trivial; encoding the solution of the problem, identifying the mutation and crossover operator and fitness function of the solutions of the specific problem. In this paper we have developed a way of encoding the solutions of examination scheduling in order to apply genetic algorithm.
Nội dung trích xuất từ tài liệu:
Genetic algorithms and application in examination scheduling JOURNAL OF SCIENCE OF HNUE 2011, Vol. 56, N◦ . 1, pp. 40-49 GENETIC ALGORITHMS AND APPLICATION IN EXAMINATION SCHEDULING Vu Dinh Hoa(∗) and Dang Xuan Tho Hanoi National University of Education (∗) E-mail: hoavd@fpt.com.vn Abstract. Examination Scheduling is an optimization problem with con- straints, a scheduling problem is one of the NP-hard problems, there is no algorithm that can solve them in polynomial time. Genetic algorithm is an algorithm for finding approximate optimal test of the global optimization problems. Application of genetic algorithms on the specific problem is not trivial; encoding the solution of the problem, identifying the mutation and crossover operator and fitness function of the solutions of the specific prob- lem. In this paper we have developed a way of encoding the solutions of examination scheduling in order to apply genetic algorithm. Keywords: Genetic Algorithms, Scheduling Problems, Examination Scheduling.1. Introduction Examination scheduling is a part of a general scheduling problem. It deals withthe satisfactory allocation of resources over time to achieve organizations tasks. It isa decision-making process with the intention of optimizing one or more objectives. As we already knew, a general scheduling problem is a NP-complete problem.So the question is that what if examination scheduling is a NP-complete problemor not? It is very difficult to prove that a problem is a NPC problem. We havesome papers from several prestigious magazines said that examination schedulingproblems is a NPC problem (see [1,2,3,4]).2. Content2.1. The Examination scheduling Problems The examination scheduling is a difficult problem, one of the NP - completeproblems.40 Genetic algorithms and application in examination scheduling2.1.1. The set of hard and soft constraints In the examination scheduling problem, available resources are lecturers, classes,courses, classrooms, and sections. A solution must group these resources together tocreate a timetable that satisfies the constraints. There are two types of constraints:hard constraints and soft constraints. - Each classroom must be booked with two lecturers. - A lecturer not to be assigned more than one classroom at the same time. - Each course must be booked to a classroom that is large enough to holdstudents of that course. - Lecturers can require some busy working-sessions. - A classroom cannot be booked for more than one course at the same time. - A class cannot be tested more than one course at a time. - A course cannot be booked twice. - Two courses of a class must be separated by at least two days.2.1.2. The related works on examination scheduling problems Examination scheduling is a NP-Complete problem that has generated hun-dreds of papers and thousands of researchers who have attempted to solve the prob-lem. Here are some of the primary approaches: - Sequential methods. - Cluster methods. - Constraint based methods. - Meta-heuristic methods. + Simulated annealing. + Tabu search. + Genetic algorithms. + Hybrid approaches.2.2. Genetic Algorithms Genetic algorithms (GAs) was invented by John Holland in the 1960s and weredeveloped by Holland, his students and colleagues at the University of Michigan inthe 1960s and the 1970s. Outline of the Basic Genetic Algorithm [5] is presented in Figure 1. We add one more operator: reproduce in step 4. We will select two individualswhich have the best fitness value and keep them in the next generation. So we canmake sure that the future generations have better or equal fitness value than theformer generations. 41 Vu Dinh Hoa and Dang Xuan Tho 1. [Start] Generate random population of n chromosomes (suitable solutions for the problem). 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population. 3. [New population] Create a new population by repeating following steps until the new population is complete. a. [Selection] Select two parent chromosomes from a population accord- ing to their fitness (the better fitness, the bigger chance to be selected). b. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents. c. [Mutation] With a mutation probability mutate new offspring at each locus. d. [Accepting] Place new offspring in a new population. 4. [Replace] Use new generated population for a further run of algorithm. 5. [Test] If the end condition is satisfied, stop, and return the best solution in current population. 6. [Loop] Go to step 2. Figure 1. The Basic Genetic Algorithm2.2.1. Encoding of a Chromosome The chromosome can be represented in many ways of encoding depending onthe solved problem. The most widely used way of encoding is as a binary string.The chromosome will look like [6]: Chromosome 1: 1010001010011 Chromosome 2: 1100110110101 Each chromosome has one binary string. Each bit in this string can representsome characteristic of the solution.2.2.2. Crossover Crossover selects genes from parent chromoso ...