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

10 Comments

Add a Comment

Your email address will not be published. Required fields are marked *