Automatic Timetable Generator Using Genetic Algorithm

$14.42

Code reviewed by PieceX
Support Included What’s included?
Created
16 Mar,2020
User Guide Document
Download

Details

Frontend-HTML,CSS,Bootstrap

Backend-Java

INDEX



 Introduction  Background  Biology lesson  Genetic Algorithm(GA) inspired from Nature  Brief overview of GA  Outline of GA  Design and Implementation  Objects of Scheduler  Terminologies  Algorithm  Testing  Conclusion , Evaluation and Further work  Brief Technical Description  References



INTRODUCTION

Time Table Scheduling Using Genetic Algorithm


Time Table Scheduling is an NP-hard problem and hence polynomial time verifiable using genetic algorithms. It a typical scheduling problem that appears to be a tedious job in every academic institute once or twice a year. In earlier days, time table scheduling was done manually with a single person or some group involved in task of scheduling it manually, which takes a lot of effort and time. Planning timetables is one of the most complex and error-prone applications.

Timetabling is the task of creating a timetable while satisfying some constraints. There are basically two types of constraints, soft constraints and hard constraints. Soft constraints are those if we violate them in scheduling, the output is still valid, but hard constraints are those which if we violate them; the timetable is no longer valid. The search space of a timetabling problem is too vast, many solutions exist in the search space and few of them are not feasible. Feasible solutions here mean those which do not violate hard constraints and as well try to satisfy soft constraints. We need to choose the most appropriate one from feasible solutions. Most appropriate ones here mean those which do not violate soft constraints to a greater extent. In this project hard-constraints have been taken care of strictly and it has been ensured that soft-constraints are as well followed as much as possible.


Soft-constraints (flexible):  More or less equal load is given to all faculties  Required time (hours per week) is given to every Batch

Hard-constraints (rigid):  There should not be any single instance of a faculty taking two classes simultaneously  A class group must not have more than one lectures at the same time

Automated Time Table Scheduler Using Genetic Algorithm

Pranav Khurana

BACKGROUND

Let’s learn some biology first  Our body is made up of trillions of cells. Each cell has a core structure (nucleus) that contains your chromosomes.  Each chromosome is made up of tightly coiled strands of deoxyribonucleic acid (DNA). Genes are segments of DNA that determine specific traits, such as eye or hair color. You have more than 20,000 genes  A gene mutation is an alteration in your DNA. It can be inherited or acquired during your lifetime, as cells age or are exposed to certain chemicals. Some changes in your genes result in genetic disorders  Natural Selection: Darwin's theory of evolution: only the organisms best adapted to their environment tend to survive and transmit their genetic characteristics in increasing numbers to succeeding generations while those less adapted tend to be eliminated.


Automated Time Table Scheduler Using Genetic Algorithm

Pranav Khurana

GA is inspired from Nature  A genetic algorithm maintains a population of candidate solutions for the problem at hand, and makes it evolve by iteratively applying a set of stochastic operators  Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes or the genotype or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves toward better solutions.  Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.  The evolution usually starts from a population of randomly generated individuals and happens in generations.  In each generation, the fitness of every individual in the population is evaluated, multiple individuals are selected from the current population (based on their fitness), and modified (recombined and possibly mutated) to form a new population.  The new population is then used in the next iteration of the algorithm.  Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population.  If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached.


The Genetic Algorithm - a brief overview

Before we can use a genetic algorithm to solve a problem, a way must be found of encoding any potential solution to the problem. This could be as a string of real numbers or, as is more typically the case, a binary bit string. We will refer to this bit string from now on as the chromosome. A typical chromosome may look like this:

Automated Time Table Scheduler Using Genetic Algorithm



10010101110101001010011101101110111111101

At the beginning of a run of a genetic algorithm a large population of random chromosomes is created. Each one, when decoded will represent a different solution to the problem at hand. Let's say there are N chromosomes in the initial population. Then, the following steps are repeated until a solution is found

 Test each chromosome to see how good it is at solving the problem at hand and assign a Fitness Score accordingly. The fitness score is a measure of how good that chromosome is at solving the problem to hand.


 Select two members from the current population. The chance of being selected is proportional to the chromosomes fitness. Roulette Wheel Selection is a commonly used method.


 Dependent on the Crossover rate crossover the bits from each chosen chromosome at a randomly chosen point.


 Step through the chosen chromosomes bits and flip dependent on the Mutation rate.


 Repeat step 2, 3, 4 until a new population of N members has been created.


 Keep repeating until required fitness is achieved.






Automated Time Table Scheduler Using Genetic Algorithm

Pranav Khurana

DESIGN AND IMPLEMENTATION

Objects of Time Table Scheduler

 Students Group

The StudentGroup class has the ID, name of the student group, number of subjects, array of subject names and hours of study required for each subject per week. It also contains the id of teachers who will teach those subjects.

 Teacher

It is a class to hold the faculty information. It has an id, name of faculty, subject that he/she teaches and an in assigned which represents the no. of batches assigned to the teacher.

 Slot

A slot here is the most basic unit of Genetic algorithm. It represents a single characteristic of a Gene.

 Time Table

This class’ object holds an array of Slot. This is basically a class to generate new slots initially for each Student group.

 Gene

It is the main constituent of a Chromosome and is made up of a sequence of slot numbers. It represents a Time table of a single class group

 Chromosome

A chromosome here is a collection or an array of Genes. It is the main class of algorithm and it undergoes crossover and mutation to furnish fitter individuals.

Automated Time Table Scheduler Using Genetic Algorithm

 Utility

It is basically for testing purpose only. It contains some mehods like printSlots() which help to keep track of algorithm through console.

 Inputdata

This is a class mainly to fetch the input from user either through text file or through form and provide it to the working classes of the algorithm.

 SchedulerMain

This is the main class of the algorithm which invokes other classes and calls methods for crossover, mutation , selection etc.

Terminologies involved  Permutation Encoding

In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence. Other encoding techniques are Binary encoding Value encoding tree Encoding.  Elitism

A practical variant of the general process of constructing a new population is to allow the best organism(s) from the current generation to carry over to the next, unaltered. This strategy is known as elitist selection and guarantees that the solution quality obtained by the GA will not decrease from one generation to the next.  Roulette Wheel Selection

It is a selection procedure in which the possibility of selection of a chromosome is directly proportional to its fitness.  Single Point Crossover

It is that type of crossover between two chromosomes in which the chromosomes are broken at a single point and then crossed. When single point crossover happens in this project, it is made sure that chromosome is not so cut that it intersects the timetable of any student group.  Swap Mutation

It is the type of mutation technique in which the chromosomes are so mutated that two portions of the chromosome get exchanged resulting in a new chromosome.



Algorithm

 First of all an initial generation of chromosomes is created randomly and their fitness value is analysed.


 New Generations are created after this. For each generation, it performs following basic operations:


a. First of all preserve few fittest chromosomes from the previous generation as it is. This is called Elitism and is necessary to preserve desired characteristics in the coming generations .


b. Randomly select a pair of chromosomes from the previous generation. Roulette wheel selection method has been used here in this project.


c. Perform crossover depending on the crossover rate which is pretty high usually. Here single point crossover has been used.


d. Perform mutation on the more fit chromosome so obtained depending on the mutation rate which is kept pretty small usually.


 Now analyze the fitness of the new generation of chromosomes and order them according to fitness values.


 Repeat creating new generations unless chromosomes of desired fitness value i.e. fitness=1, are obtained.

Highest Price
70.95
Lowest Price
9.86
Average Price
32.67
AI Price Forecast
NA
Start to Communicate (If you want to start communication with the seller about this item, you can start here)
Loading…

We use cookies and other technologies to improve your experience on our website and to analyze our traffic. By browsing our website, you consent to our use of cookies and other tracking technologies.

Accept cookies and close this message
Win now