# Genetic Algorithms Tutorial 04 – Class Scheduling JAVA Application

this tutorial will start by running the prebuilt

genetic algorithm java 8 university class scheduling application and 2nd 1 will use

the generated output in order to quickly explain what this application does and 3rd i will

step by step write and explain the code using an eclipse ide this is the prebuilt application

so if i go ahead and run it and the goal is that given some course scheduling supplied

data we need to use genetic algorithm in order to find a university class schedule with no

conflicts so here we run the application and we go from generation 0 to generation 12 where

we find this class schedule with no conflicts so this is a table format of this schedule

here with a fitness of 1 and 0 conflicts and a conflict can be one of 3 things for this

simple application it can be an instructor assigned to teach more than one course at

the same time it can also be a room occupied by more than one course at the same time or

it can be a course assigned to be taught in a room with a seating capacity that is smaller

than the course maximum number of students and here each population of schedules is sorted

by fitness so this is the highest fitness for this population and if we go back to generation

0 so the fittest schedule here had a fitness of this one 0,25 and 3 conflicts so this is

the table representation of that schedule and one of the conflicts here is that room

1 has a capacity of 25 students and we have this class that is assigned or this course

that is assigned to be taught in it which has a max number of students of 35 and those

are the 2 other conflicts room 3 has those 2 classes assigned to be taught in it so 303K

and 303L and they have a max number of students of 45 let’s take a look at another so in generation

1 so this actually we’re elitism here so this might be the same as this course schedule

since the first one is moved as is to the next generation the one with the best fitness

so if we go to generation 2 and this course schedule it has a fitness of this fitness

and 2 conflicts and here’s one of the 2 conflicts so we have jane doe assigned to teach this

class at this time 1uesday thursday from 9:00 to 10:30 and it’s also assigned to teach this

other classat the same time so that’s conflict and another conflict is that room 2 has this

class assigned to be taught on monday wednesday friday from 10:00 to 11:00 and also room 2

has another class assigned to be taught at the same time monday wednesday friday from

10:00 to 11:00 so those are the 2 conflicts here and the data i supplied here is very

simple so we have 3 departments a math a ee and a physics department and each department

this department has just 2 classes and this one has 3 and this one has 2 and those are

the available courses and so this one has a max number of students of 25 and those are

the instructors that can teach this class same for this one etc and the available rooms

are room 1 room 2 and room 3 with room 1 with a maximum seating capacity of 25 etc 45 and

35 for room 3 and the available instructors are those 4 instructors and the available

meeting times are those 4 meeting times monday wednesday friday from 9:00 to 10:00 and then

from 10:00 to 11:00 and then tuesday thursday from 9:00 to 10:30 and tuesday thursday from

10:30 to 12:00 next i’ll start by creating a new project and it’s gonna be running on

Java 8 and here we will have a driver class with a main method that will be in this package

and this will be the driver for the whole application and i will have a data class that

will contain and initialize all the data and i will have a schedule class

and a population class that represents a population of schedules and a genetic algorithm class

that evolve the population from one generation to the next using crossover mutation and elitism

and let me also create another package so the domain genetic algorithm class scheduling

and domain and here i will have a course class representing

a course to be scheduled and an instructor class representing an instructor to teach

a course and a room class where the course will be taught

and a meeting time class representing the meeting time for various

courses and a department class where a course would belong to a department and a class class

representing a course with a specific department that is scheduled to be taught by a specific

instructor in a specific meeting time and in a specific room now the course will have

a course number and a course name and a max number of students and a list of instructors

that can teach this course and a constructor that initializes each one of those values

and get methods that returns them so get number and get name and get instructors and get max

number of students and a toString method that returns the name of this course and a department

will have a department name and a list of courses that it offers and a constructor that

initializes those 2 values and get methods for each one of them and the instructor will

have an instructor id and an instructor name and a constructor that initializes both of

them and get methods that return them and a toString method that returns the name of

this instructor and the class meeting time will have a meeting time id and time and a

constructor that initializes both of them and get methods that returns them and the

room will have a room number and a seating capacity and a constructor that initializes

both of them and get methods that returns them and the schedule will have an array list

of classes and a class will have a class id and a department and a course and an instructor

and a specific meeting time and a specific room and the constructor will initialize the

department and the course and the class id and i will have a set methods for the instructor

and the meeting time and the room and get methods that return each one of those and

the toString method would return a string with the department name and the course number

and the room number and the instructor id and the meeting time id now the data class

will have an array list of rooms and one for instructors and another one for

courses and for department and for meeting times and we will keep track of the number

of classes and i will have get methods that returns each

one of those and an initialize method that initializes each one of those and return this

data instance and the constructor will be calling this initialize method now normally

this data will be coming from a database but for the purpose of this tutorial and for simplicity

we’ll have it here so we’ll have here 3 rooms 1 2 and 3 and 4 meeting times and 4 instructors

and 7 courses and 3 departments and this java 8 code would calculate the total number of

classes next let’s go to the schedule class now here

we will be using data coming from the data class so i’ll have a get data method also

and we will a constructor with the data passed in so this would initialize the data and initialize

the array list of classes given the number of classes that we calculated over here

and let me define a class number counter and i will be using this instance variable in

the initialize method and let’s add an import for department over here and an import for

class also so using the data to pickup all the departments and picking up all the courses

in each department and for each we instantiate a new class using this class number counter

passing it in and the department and the course so the department and this course and we randomly

set the meeting time to one of the meeting times in data so we are using math dot random

here and we do the same for room we randomly set that and the same for instructor

and then we add this new class instance to the array list of classes and we return this

schedule instance and a schedule can have a number of conflicts so let’s define that

here and we’ll have a get method that returns the number of conflicts and also a schedule

will have a fitness so let’s define that here and i will also have a boolean flag is fitness

changed and set it initially to true and let me have a calculate fitness method that would

calculate and return the fitness so for now let’s just return 0 and i’ll have a get fitness

method that checks if the is fitness changed flag is true than it recalculates the fitness

and sets the is fitness changed flag to false and it would return the fitness and the get

classes method that would return the classes sets the is fitness changed flag to true since

we might change the classes after obtaining them and calculate fitness would return a

fitness of 1 if there is no conflicts so we start with a number of conflicts of 0 and

if the number of conflicts is 0 than we end up with 1 over 1 so that would be returning

a fitness of 1 so here we are using java 8 to go through all the classes and for each

class if the room capacity is smaller than the max number of students for the course

than we add 1 to the number of conflicts and we use here classes dot stream so the same

as here classes so but we use classes dot index of y is bigger or equal to classes dot

index of x so we use a filter here and than we do for each so we check if we have the

same meeting time and its a different class instance than if it is the same room than

we have a conflict so we add 1 to the number of conflicts and if it is the same instructor

than we also have a conflict and we add 1 to the number of conflicts and the fitness

i am returning here is 1 over the number of conflicts plus 1 as a double here and what’s

left is the toString method that would return all the classes separated by a comma and if

we go to the class each class would be returned would be this so the department name course

number etc and this should do it for this class now going to the population class

so this is a population of schedules so we will have an array list of schedules and a

get method that would return those schedules and we will have a constructor

with the size of the population of schedules passed in and the data that contains all the

data and we use that data instance to pass it to the schedule when we instantiate it

to each schedule we instantiate than we call initialize on and we use the size for the

size of this array list of schedules when we instantiate a new instance so here we are

instantiating schedules and initializing them and adding them to the schedules array list

and we will have this method sort by fitness that sorts the schedules by fitness using

java 8 and returns this population of schedules and this should do it for population next

let’s go to the genetic algorithm class and here i will be writing the code that does

crossover mutation and elitism and i will need the data coming in from the data class

and which will be initialized in the constructor so we want to perform crossover for all schedules

in the population so i’ll have this method crossover population and for now let’s just

return null and this method would use tournament selection in order to select 2 schedules to

do crossover on for now let’s return null and this method does the crossover of those

2 schedules that are selected here and it would return a crossed over schedule but for

now let’s just return null and i will also have this mutate population method that will

end up calling the mutate schedule method on all schedules in this population and here

for now let’s also just return null and we will have a public method evolve that ends

up calling crossover population and then what the population that’s returned from that it

ends up calling mutate population on it and returning that mutated population and before

writing the code here let me go to the driver class

and here i want to add those public static final constants so we have the population

size and the mutation rate crossover rate and tournament selection size that will be

used by this method select tournament population and the number of elite schedules

now here i will be instantiating a new population so crossover population given the population

schedule size this population and the data and i will return that new population but

before doing that i will perform elitism where i will pickup the number of elite schedules

from the original population and put them as is in the new crossover population and

here we have just one elite schedule and let’s make it more visible

and for the remaining schedules in this population and since the schedules are sorted by fitness

i will start here from the number of elite schedules so i will start from 1 and go over

all the remaining schedules in the population and only perform crossover if crossover rate

is bigger than a random number math dot random otherwise i will take the schedules as is

from the original population and put them in this new crossover population so in case

we are doing crossover than i will use select tournament population and than do a sort by

fitness and do get schedules and than get the fittest schedule from those and this would

be schedule 1 and i will do the same and get the fittest schedule and this would schedule

2 and than i will call crossover schedule on schedules 1 and schedule

2 and set the returned schedule in the crossover population now here we will instantiate a

new schedule passing in the data and call initialize on it and this is the schedule

that we will be returning but before doing that it will be populated by classes from

either schedule 1 or schedule 2 depending on if math dot random is bigger than 0.5 or

not and for this method this is the population that we will be returning and it will have

this size tournament selection size so here it have a size of 3 and we will pass it the

data and return it but before doing that i will pickup 3 schedules randomly from the

passed in population so we’re using here math dot random and let me make it more visible

and for mutate population i will instantiate this new population and return it but before

doing that i will start by picking up the schedules so mutate population dot get schedules

and i will move the elite schedules as is from the original population to the new population

so these schedules in this population mutate population and i will perform mutation on

all schedules other than the elite schedules so we’re starting here from the number of

elite schedules 1 and we are calling mutate schedule and setting it in this schedules

so let’s go to mutate schedule will instantiate this schedule and return it but before doing

that actually we’ll return this mutate schedule that was passed in and before doing that i

will check if the mutation rate is bigger than math dot random and in that case i will

do mutate schedule the one that we will be returning dot get classes dot set and i’ll

set to that schedule that we instantiated here so schedule dot get classes dot get x

which would a schedule which would be a class in this schedule ok so this will do it for

this class and next i’ll be doing the driver class now

here i will have this data as the instance variable and in main i will instantiate an

instance of this class and a data instance for this data and before doing anything i

want to add this method the print available data which will print out all the data that

we picked up from the data class all this data

so let me call it from here and let’s quickly test it before writing the remaining code

so here we go this is the data that we have those are the 3 departments and the courses

for each department and those are the available courses we have 7 of them and the instructors

that can teach each one of the courses and the max number of students for each course

and those are the available rooms with the max seating capacity for each room and those

are the available instructors and the available meeting times and this is monday wednesday

friday and this is tuesday thursday and let me have this generation number here and we

will be starting from generation 0 and i will be printing

the generation number on one line and than on a second line i will be printing the schedule

number the classes which would be the for each class i would print the department the

class the room and the instructor and the meeting time and i will also print the fitness

for each schedule and the number of conflicts so let’s instantiate a genetic algorithm passing

in the data and a sorted population of schedules so new population and sort by fitness and

i will go through all those schedules in that population printing them and let me define

here this schedule number and let’s tab here make it more visible

and let’s quickly test run this with generation 0 before adding the remaining code so here

we go we have generation 0 of those schedules with the fitness and the number of conflicts

for each schedule and i want to be able to print the fittest schedule in this population

as a table so i’ll have this method and let me add this class number over here

and let’s import this class domain dot class and i will be printing the fittest schedule

here so i do population dot get schedule dot get 0 which would be the fittest and i will

pass it the generation number which we’re still in generation 0 so let’s test run it

quickly before moving forward so here we go printed this schedule in table format it has

2 conflicts and i will be looping over the remaining schedules in the population with

a while loop which would terminate if we find a schedule a fittest schedule in a population

with a fitness of 1 which means it doesn’t have any conflicts

so let’s go ahead and run it and we find a solution in 15 generations so went from

generation 0 and so generation 0 has this is the fittest schedule with four conflicts

and we went to generation 14 and this schedule will have no conflicts it has a fitness of

1 this is the schedule and let’s quickly take a look at what a conflict mean so we would

have a conflict if an instructor is teaching more than one class at the same time so an

example is here jane doe is teaching 2 classes at the same time and another form of conflict

is when a room is hosting more than one class at the same time and we have that case for

this same so room 1 is hosting those 2 classes 360C and 464K and we can have a conflict when

a room is hosting a class that contain more student than its seating capacity and an example

of that is also here we have here the max number of student for this class is 35 and

this room can have a maximum of 25 and here so this one 25 and this one also this course

has a max number of students of 30 and the max room seating capacity is 25 also

I want to know how the data will be coming from database??

thnx

source code please

http://www.zaneacademy.com Not found in website

assistive

finally found the tutorial i have been searching for ages.Thank you so much. and I am trying to develop a automatic time table generator which have lots of constraints like :

-number of lectures a teacher can teach per day

-equally distribution of teacher load between first half and second half of the day

-a teacher cannot have continuous lecture in the same class.

-a teacher cannot have more than two first lectures in the entire week.

and lot more. I am not sure how to represents these constraints using genetic algorithm??

any help would be greatly appreciated.

P.S This video might generate lots of traffic if you rename it to "Time table generator using GA " or something like that.

Thank you very much! I've to solve a very similar problem and I think i can use the information you provided ๐

Pls explain what is tournament selection size and elite schedules i am ver confused. thx sir

Thank you for the explanation

hey bro can you do this step in python pliz. thanks in advance

it works like a magic ๐

This tutorial + SQLite DB @ https://youtu.be/PQPs-vJuHC0

Python version of this turorial @ https://youtu.be/8NrNX_jCkjw

Python version of this tutorial + SQLite DB @ https://youtu.be/6SDQdx5VLO8

Genetic Algorithms w/ Java – Tutorial 01 @ https://youtu.be/UcVJsV-tqlo

Genetic Algorithms w/ JAVA + JavaFX – Tutorial 02 @ https://youtu.be/0VijcOA5ZAY

TSP By Genetic Algorithms w/ JAVA @ https://youtu.be/Z3668A0zLCM

Genetic Algorithms Tutorial 05 – Robotics JAVA Application @ https://youtu.be/mhtTOp8rWOU

Genetic Algorithms Tutorial 06 – data mining + JAVA 8 + logical operators @ https://youtu.be/Ha9xddd7xTY

Genetic Algorithms Tutorial 07 – data mining + arithmetic operators + JAVA @ https://youtu.be/azdlGExeXKc

Genetic Algorithms w/ Python – Tutorial 01 @ https://youtu.be/zumC_C0C25c

Genetic Algorithms w/ Scala – Tutorial 01 @ https://youtu.be/6ngju74tHbI