Chapter 5 |
Introduction
In this chapter, we will create a genetic algorithm that schedules classes for a college timetable. We will examine a couple of different scenarios in which a class-scheduling algorithm may be used, and the constraints that are usually implemented when designing a timetable. Finally, we will build a simple class scheduler, which can be expanded to support more complex implementations.
In artificial intelligence, class scheduling is a variation of the constraint satisfaction problem. This category of problem relates to problems, which have a set of variables that need to be assigned in such a way that they avoid violating a defined set of constraints.
Constraints fall into two categories: hard constraints—constraints which need to be satisfied to produce a functional solution, and soft constraints—constraints which are preferred but not at the expense of the hard constraints.
For instance, when manufacturing a new product, the product’s functional requirements are hard constraints and specify the important performance requirements. Without these constraints, you have no product. A phone that can’t make calls is hardly a phone! However, you may also have soft constraints, which, although unrequired, are still important to consider, such as the cost, weight, or aesthetics of the product.
When creating a class-scheduling algorithm there will typically be many hard and soft constraints that need to be considered. Some typical hard constraints for the class-scheduling problem are:
- Professors can only be in one class at any given time
- Classrooms need to be big enough to host the class
- Classrooms can only host one class at any given time
- Classrooms must contain any required equipment
Some typical soft constraints may be:
- Room capacity should be suitable for the class size
- Preferred classroom of the professor
- Preferred class time of the professor
Sometimes multiple soft constraints may conflict and a tradeoff will need to be found between them. For example, a class might only have 10 students so a soft constraint may reward assigning a suitable classroom, which has capacity of around 10; however, the professor taking the class may prefer a larger classroom, which can hold 30 students. If professor preferences are accounted for as soft constraints, one of these configurations will be preferred and hopefully found by the class scheduler.
In more advanced implementations it is also possible to weight soft constraints so the algorithm understands which soft constraints are the most important to consider.
Like the traveling salesman problem, iterative methods can be used to find an optimal solution to the class-scheduling problem; however, it becomes increasingly more difficult to find an optimal solution as the number of class configurations increases. In these circumstances, where the possible number of class configurations exceeds what is feasible to solve by iterative methods, genetic algorithms are good alternatives. Although they’re not guaranteed to find the optimal solution, they are extremely good at finding close to optimal solutions within a reasonable timeframe.
The Problem
The class-scheduling problem we will be looking at in this chapter is a college class scheduler that can create a college timetable based on data we provide it, such as the available professors, available rooms, timeslots and student groups.
We should note that building a college timetable is slightly different from building a grade school timetable. Grade school timetables require their students to have a full timetable of scheduled classes throughout the day with no free periods. Conversely, typical college timetables will frequently have free periods depending on how many modules the student enrolls in.
Each class will be assigned a timeslot, a professor, a room and a student group by the class scheduler. We can calculate the total number of classes that will need scheduling by summing the number of student groups multiplied by the number of modules each student group is enrolled in.
For each class scheduled by our application we will consider the following hard constraints:
- Classes can only be scheduled in free classrooms
- A professor can only teach one class at any one time
- Classrooms must be big enough to accommodate the student group
To keep things simple in this implementation we will consider only hard constraints for now; however there would typically be many more hard constraints depending on the timetable specifications. There would also likely be a number of soft constraints included in the specification, which for now we will ignore. Although not necessary, considering soft constraints can often make a big difference in the quality of the timetables produced by the genetic algorithm.
Implementation
It is time to go ahead and tackle the problem using our knowledge of genetic algorithms. After setting up a new Java/Eclipse package for this problem, we’ll begin by encoding the chromosome.
Before You Start
This chapter will build on the code you developed in all of the previous chapters – so it’s especially important to follow this section closely!
Before you start, create a new Eclipse or NetBeans project, or create a new package in your existing project for this book called “chapter5”.
Copy the Individual, Population, and GeneticAlgorithm classes over from chapter4 and import them into chapter5. Make sure to update the package name at the top of each class file! They should all say “package chapter5” at the very top.
Open the GeneticAlgorithm class and make the following changes:
- Delete the selectParent method, and replace it with the selectParent method from chapter3 (tournament selection)
- Delete the crossoverPopulation method, and replace it with the crossoverPopulation method from chapter2 (uniform crossover)
- Delete the initPopulation, mutatePopulation, evalPopulation, and calcPopulation methods – you’ll re-implement them in this chapter
The Population and Individual classes can be left alone for now, but keep in mind that you’ll be adding a new constructor to each one of these files later in the chapter.
Encoding
The encoding we use in our class scheduling application will need to be capable of efficiently encoding all of the class properties we require. For this implementation, they are: the timeslot the class is scheduled for, the professor teaching the class, and the classroom for the class.
We can simply assign a numerical ID to each timeslot, professor and classroom. We can then use a chromosome that encodes an array of integers—our familiar approach. This means each class that needs scheduling will only require three integers to encode it as shown below:
By splitting this array into chucks of three, we can retrieve all of the information we need for each class.
Initialization
Now that we have an understanding of our problem and how we’re going to encode the chromosome, we can begin the implementation. First, we’ll need to create some data for our scheduler to work with: in particular, the rooms, professors, timeslots, modules and student groups that we’re trying to build a timetable around.
Usually this data comes from a database containing the complete course module and student data. However, for the purpose of this implementation we will create some hard-coded dummy data to work with.
Let’s first set up our supporting Java classes. We’ll create a container class for each of the data types above (room, class, group, professor, module, and timeslot). While each of these container classes is very simple—they mostly define some class properties, getters, and setters, with no real logic. We’ll print each of them in turn here.
First, create a Room class that stores information about a classroom. As always, if using Eclipse, you can create this class using the File 
New Class menu option.
package chapter5;
public class Room {
private final int roomId;
private final String roomNumber;
private final int capacity;
public Room(int roomId, String roomNumber, int capacity) {
this.roomId = roomId;
this.roomNumber = roomNumber;
this.capacity = capacity;
}
public int getRoomId() {
return this.roomId;
}
public String getRoomNumber() {
return this.roomNumber;
}
public int getRoomCapacity() {
return this.capacity;
}
}
This class contains a constructor, which accepts a room ID, a room number and the room capacity. It also provides methods to get the room’s properties.
Next, create a Timeslot class; the timeslot represents the day of week and time that a class takes place.
package chapter5;
public class Timeslot {
private final int timeslotId;
private final String timeslot;
public Timeslot(int timeslotId, String timeslot){
this.timeslotId = timeslotId;
this.timeslot = timeslot;
}
public int getTimeslotId(){
return this.timeslotId;
}
public String getTimeslot(){
return this.timeslot;
}
}
A timeslot can be created using the constructor and passing it a timeslot ID and the timeslot details as a string (the details might look like “Mon 9:00 – 10:00”). The class also contains getters to fetch the object’s properties.
The third class to set up is the Professor class:
package chapter5;
public class Professor {
private final int professorId;
private final String professorName;
public Professor(int professorId, String professorName){
this.professorId = professorId;
this.professorName = professorName;
}
public int getProfessorId(){
return this.professorId;
}
public String getProfessorName(){
return this.professorName;
}
}
The Professor class contains a constructor accepting a professor ID and professor name; it also contains getter methods to retrieve the professor’s properties.
Next, add a Module class to store information about the course modules. A “module” is what some might call a “course”, like “Calculus 101” or “American History 302”, and like real-life courses, can have multiple sections and groups of students taking the course at different times of the week with different professors.
package chapter5;
public class Module {
private final int moduleId;
private final String moduleCode;
private final String module;
private final int professorIds[];
public Module(int moduleId, String moduleCode, String module, int professorIds[]){
this.moduleId = moduleId;
this.moduleCode = moduleCode;
this.module = module;
this.professorIds = professorIds;
}
public int getModuleId(){
return this.moduleId;
}
public String getModuleCode(){
return this.moduleCode;
}
public String getModuleName(){
return this.module;
}
public int getRandomProfessorId(){
int professorId = professorIds[(int) (professorIds.length * Math.random())];
return professorId;
}
}
This module class contains a constructor that accepts a module ID (numeric), module code (something like “CS101” or “Hist302”), module name and an array of professor IDs, which can teach the module. The module class also provides getter methods – and a method to select a random professor ID.
The next class needed is a Group class class, which holds information about student groups.
package chapter5;
public class Group {
private final int groupId;
private final int groupSize;
private final int moduleIds[];
public Group(int groupId, int groupSize, int moduleIds[]){
this.groupId = groupId;
this.groupSize = groupSize;
this.moduleIds = moduleIds;
}
public int getGroupId(){
return this.groupId;
}
public int getGroupSize(){
return this.groupSize;
}
public int[] getModuleIds(){
return this.moduleIds;
}
}
The group class constructor accepts a group ID, a group size, and the module IDs the group is taking. It also provides getter methods to fetch the group information.
Next, add a “Class” class. Understandably, the terminology here may be confusing throughout the chapter – therefore a capitalized “Class” will refer to this Java class that you’re about to create, and we’ll use the lowercase “class” to refer to any other Java class.
The Class class represents a combination of all of the above. It represents a student group taking a section of a module at a specific time, in a specific room, with a specific professor.
package chapter5;
public class Class {
private final int classId;
private final int groupId;
private final int moduleId;
private int professorId;
private int timeslotId;
private int roomId;
public Class(int classId, int groupId, int moduleId) {
this.classId = classId;
this.moduleId = moduleId;
this.groupId = groupId;
}
public void addProfessor(int professorId) {
this.professorId = professorId;
}
public void addTimeslot(int timeslotId) {
this.timeslotId = timeslotId;
}
public void setRoomId(int roomId) {
this.roomId = roomId;
}
public int getClassId() {
return this.classId;
}
public int getGroupId() {
return this.groupId;
}
public int getModuleId() {
return this.moduleId;
}
public int getProfessorId() {
return this.professorId;
}
public int getTimeslotId() {
return this.timeslotId;
}
public int getRoomId() {
return this.roomId;
}
}
Now we can create a Timetable class to encapsulate all these objects into one single timetable object. The Timetable class is the most important class thus far, as it’s the only class that understands how the different constraints are supposed to interact with one another.
The Timetable class also understands how to parse a chromosome and create a candidate Timetable to be evaluated and scored.
package chapter5;
import java.util.HashMap;
public class Timetable {
private final HashMap<Integer, Room> rooms;
private final HashMap<Integer, Professor> professors;
private final HashMap<Integer, Module> modules;
private final HashMap<Integer, Group> groups;
private final HashMap<Integer, Timeslot> timeslots;
private Class classes[];
private int numClasses = 0;
/**
* Initialize new Timetable
*
*/
public Timetable() {
this.rooms = new HashMap<Integer, Room>();
this.professors = new HashMap<Integer, Professor>();
this.modules = new HashMap<Integer, Module>();
this.groups = new HashMap<Integer, Group>();
this.timeslots = new HashMap<Integer, Timeslot>();
}
public Timetable(Timetable cloneable) {
this.rooms = cloneable.getRooms();
this.professors = cloneable.getProfessors();
this.modules = cloneable.getModules();
this.groups = cloneable.getGroups();
this.timeslots = cloneable.getTimeslots();
}
private HashMap<Integer, Group> getGroups() {
return this.groups;
}
private HashMap<Integer, Timeslot> getTimeslots() {
return this.timeslots;
}
private HashMap<Integer, Module> getModules() {
return this.modules;
}
private HashMap<Integer, Professor> getProfessors() {
return this.professors;
}
/**
* Add new room
*
* @param roomId
* @param roomName
* @param capacity
*/
public void addRoom(int roomId, String roomName, int capacity) {
this.rooms.put(roomId, new Room(roomId, roomName, capacity));
}
/**
* Add new professor
*
* @param professorId
* @param professorName
*/
public void addProfessor(int professorId, String professorName) {
this.professors.put(professorId, new Professor(professorId, professorName));
}
/**
* Add new module
*
* @param moduleId
* @param moduleCode
* @param module
* @param professorIds
*/
public void addModule(int moduleId, String moduleCode, String module, int professorIds[]) {
this.modules.put(moduleId, new Module(moduleId, moduleCode, module, professorIds));
}
/**
* Add new group
*
* @param groupId
* @param groupSize
* @param moduleIds
*/
public void addGroup(int groupId, int groupSize, int moduleIds[]) {
this.groups.put(groupId, new Group(groupId, groupSize, moduleIds));
this.numClasses = 0;
}
/**
* Add new timeslot
*
* @param timeslotId
* @param timeslot
*/
public void addTimeslot(int timeslotId, String timeslot) {
this.timeslots.put(timeslotId, new Timeslot(timeslotId, timeslot));
}
/**
* Create classes using individual’s chromosome
*
* @param individual
*/
public void createClasses(Individual individual) {
// Init classes
Class classes[] = new Class[this.getNumClasses()];
// Get individual’s chromosome
int chromosome[] = individual.getChromosome();
int chromosomePos = 0;
int classIndex = 0;
for (Group group : this.getGroupsAsArray()) {
int moduleIds[] = group.getModuleIds();
for (int moduleId : moduleIds) {
classes[classIndex] = new Class(classIndex, group.getGroupId(), moduleId);
// Add timeslot
classes[classIndex].addTimeslot(chromosome[chromosomePos]);
chromosomePos++;
// Add room
classes[classIndex].setRoomId(chromosome[chromosomePos]);
chromosomePos++;
// Add professor
classes[classIndex].addProfessor(chromosome[chromosomePos]);
chromosomePos++;
classIndex++;
}
}
this.classes = classes;
}
/**
* Get room from roomId
*
* @param roomId
* @return room
*/
public Room getRoom(int roomId) {
if (!this.rooms.containsKey(roomId)) {
System.out.println("Rooms doesn’t contain key " + roomId);
}
return (Room) this.rooms.get(roomId);
}
public HashMap<Integer, Room> getRooms() {
return this.rooms;
}
/**
* Get random room
*
* @return room
*/
public Room getRandomRoom() {
Object[] roomsArray = this.rooms.values().toArray();
Room room = (Room) roomsArray[(int) (roomsArray.length * Math.random())];
return room;
}
/**
* Get professor from professorId
*
* @param professorId
* @return professor
*/
public Professor getProfessor(int professorId) {
return (Professor) this.professors.get(professorId);
}
/**
* Get module from moduleId
*
* @param moduleId
* @return module
*/
public Module getModule(int moduleId) {
return (Module) this.modules.get(moduleId);
}
/**
* Get moduleIds of student group
*
* @param groupId
* @return moduleId array
*/
public int[] getGroupModules(int groupId) {
Group group = (Group) this.groups.get(groupId);
return group.getModuleIds();
}
/**
* Get group from groupId
*
* @param groupId
* @return group
*/
public Group getGroup(int groupId) {
return (Group) this.groups.get(groupId);
}
/**
* Get all student groups
*
* @return array of groups
*/
public Group[] getGroupsAsArray() {
return (Group[]) this.groups.values().toArray(new Group[this.groups.size()]);
}
/**
* Get timeslot by timeslotId
*
* @param timeslotId
* @return timeslot
*/
public Timeslot getTimeslot(int timeslotId) {
return (Timeslot) this.timeslots.get(timeslotId);
}
/**
* Get random timeslotId
*
* @return timeslot
*/
public Timeslot getRandomTimeslot() {
Object[] timeslotArray = this.timeslots.values().toArray();
Timeslot timeslot = (Timeslot) timeslotArray[(int) (timeslotArray.length * Math.random())];
return timeslot;
}
/**
* Get classes
*
* @return classes
*/
public Class[] getClasses() {
return this.classes;
}
/**
* Get number of classes that need scheduling
*
* @return numClasses
*/
public int getNumClasses() {
if (this.numClasses > 0) {
return this.numClasses;
}
int numClasses = 0;
Group groups[] = (Group[]) this.groups.values().toArray(new Group[this.groups.size()]);
for (Group group : groups) {
numClasses += group.getModuleIds().length;
}
this.numClasses = numClasses;
return this.numClasses;
}
/**
* Calculate the number of clashes
*
* @return numClashes
*/
public int calcClashes() {
int clashes = 0;
for (Class classA : this.classes) {
// Check room capacity
int roomCapacity = this.getRoom(classA.getRoomId()).getRoomCapacity();
int groupSize = this.getGroup(classA.getGroupId()).getGroupSize();
if (roomCapacity < groupSize) {
clashes++;
}
// Check if room is taken
for (Class classB : this.classes) {
if (classA.getRoomId() == classB.getRoomId() && classA.getTimeslotId() == classB.getTimeslotId()
&& classA.getClassId() != classB.getClassId()) {
clashes++;
break;
}
}
// Check if professor is available
for (Class classB : this.classes) {
if (classA.getProfessorId() == classB.getProfessorId() && classA.getTimeslotId() == classB.getTimeslotId()
&& classA.getClassId() != classB.getClassId()) {
clashes++;
break;
}
}
}
return clashes;
}
}
This class contains methods to add rooms, timeslots, professors, modules and groups to the timetable. In this manner, the Timetable class serves dual purposes: a Timetable object knows all of the available rooms, timeslots, professors, etc., but the Timetable object can also read a chromosome, create a subset of classes from that chromosome, and help evaluate the fitness of the chromosome.
Pay close attention to the two important methods in this class: createClasses and calcClashes.
The createClasses method accepts an Individual (that is, a chromosome) – and using its knowledge of the total number of student groups and modules that must be scheduled, creates a number of Class objects for those groups and modules. The method then starts reading the chromosome and assigns the variable information (a timeslot, a room, and a professor) to each one of those classes. Therefore, the createClasses method makes sure that every module and student group is accounted for, but it uses a genetic algorithm and the resultant chromosome to try different combinations of timeslots, rooms, and professors. The Timetable class caches this information locally (as “this.classes”) for later use.
Once the Classes have been built, the calcClashes method checks each one in turn and counts the number of “clashes”. In this case, a “clash” is any hard constraint violation, such as a class whose room is too small, a conflict with room and timeslot, or a conflict with professor and timeslot. The number of clashes is used later by the GeneticAlgorithm’s calcFitness method.
The Executive Class
We can now create an executive class that contains the program’s “main” method. As in previous chapters, we’ll build this class based on the pseudocode from Chapter 2 with a number of “TODO” comments in place of the implementation details that we’ll fill out throughout this chapter.
First, create a new Java class and call it “TimetableGA”. Make sure it’s in “package chapter5” and add the following code to it:
package chapter5;
public class TimetableGA {
public static void main(String[] args) {
// TODO: Create Timetable and initialize with all the available courses, rooms, timeslots, professors, modules, and groups
// Initialize GA
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.9, 2, 5);
// TODO: Initialize population
// TODO: Evaluate population
// Keep track of current generation
int generation = 1;
// Start evolution loop
// TODO: Add termination condition
while (false) {
// Print fitness
System.out.println("G" + generation + " Best fitness: " + population.getFittest(0).getFitness());
// Apply crossover
population = ga.crossoverPopulation(population);
// TODO: Apply mutation
// TODO: Evaluate population
// Increment the current generation
generation++;
}
// TODO: Print final fitness
// TODO: Print final timetable
}
}
We’ve given ourselves eight TODOs in order to complete this chapter. Note that crossover is not a TODO we’re reusing tournament selection from Chapter 3 with uniform crossover from Chapter 2.
The first TODO is easy to resolve, and we’ll do that now. Generally, the information for a school’s course scheduler will come from a database, but let’s hard-code some classes and professors now. Since the following code is a little lengthy, let’s create a separate method in the TimetableGA class for it. Add this method anywhere you like:
private static Timetable initializeTimetable() {
// Create timetable
Timetable timetable = new Timetable();
// Set up rooms
timetable.addRoom(1, "A1", 15);
timetable.addRoom(2, "B1", 30);
timetable.addRoom(4, "D1", 20);
timetable.addRoom(5, "F1", 25);
// Set up timeslots
timetable.addTimeslot(1, "Mon 9:00 - 11:00");
timetable.addTimeslot(2, "Mon 11:00 - 13:00");
timetable.addTimeslot(3, "Mon 13:00 - 15:00");
timetable.addTimeslot(4, "Tue 9:00 - 11:00");
timetable.addTimeslot(5, "Tue 11:00 - 13:00");
timetable.addTimeslot(6, "Tue 13:00 - 15:00");
timetable.addTimeslot(7, "Wed 9:00 - 11:00");
timetable.addTimeslot(8, "Wed 11:00 - 13:00");
timetable.addTimeslot(9, "Wed 13:00 - 15:00");
timetable.addTimeslot(10, "Thu 9:00 - 11:00");
timetable.addTimeslot(11, "Thu 11:00 - 13:00");
timetable.addTimeslot(12, "Thu 13:00 - 15:00");
timetable.addTimeslot(13, "Fri 9:00 - 11:00");
timetable.addTimeslot(14, "Fri 11:00 - 13:00");
timetable.addTimeslot(15, "Fri 13:00 - 15:00");
// Set up professors
timetable.addProfessor(1, "Dr P Smith");
timetable.addProfessor(2, "Mrs E Mitchell");
timetable.addProfessor(3, "Dr R Williams");
timetable.addProfessor(4, "Mr A Thompson");
// Set up modules and define the professors that teach them
timetable.addModule(1, "cs1", "Computer Science", new int[] { 1, 2 });
timetable.addModule(2, "en1", "English", new int[] { 1, 3 });
timetable.addModule(3, "ma1", "Maths", new int[] { 1, 2 });
timetable.addModule(4, "ph1", "Physics", new int[] { 3, 4 });
timetable.addModule(5, "hi1", "History", new int[] { 4 });
timetable.addModule(6, "dr1", "Drama", new int[] { 1, 4 });
// Set up student groups and the modules they take.
timetable.addGroup(1, 10, new int[] { 1, 3, 4 });
timetable.addGroup(2, 30, new int[] { 2, 3, 5, 6 });
timetable.addGroup(3, 18, new int[] { 3, 4, 5 });
timetable.addGroup(4, 25, new int[] { 1, 4 });
timetable.addGroup(5, 20, new int[] { 2, 3, 5 });
timetable.addGroup(6, 22, new int[] { 1, 4, 5 });
timetable.addGroup(7, 16, new int[] { 1, 3 });
timetable.addGroup(8, 18, new int[] { 2, 6 });
timetable.addGroup(9, 24, new int[] { 1, 6 });
timetable.addGroup(10, 25, new int[] { 3, 4 });
return timetable;
}
Now, resolve the first TODO at the top of the main method by replacing it with the following:
// Get a Timetable object with all the available information.
Timetable timetable = initializeTimetable();
The top of the main method should now look like this:
public class TimetableGA {
public static void main(String[] args) {
// Get a Timetable object with all the available information.
Timetable timetable = initializeTimetable();
// Initialize GA ... (and the rest of the class, unchanged from before!)
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.9, 2, 5);
This gives us a Timetable instance with all of the necessary information, and the GeneticAlgorithm object we create is similar to those in previous chapters: a genetic algorithm with a population of 100, a mutation rate of 0.01, a crossover rate of 0.9, 2 elite individuals and a tournament size of 5.
We now have seven TODOs remaining. The next TODO is related to initializing a population. In order to create a population, we’ll need to know the length of the chromosome we need; and that’s determined by the number of groups and modules in the Timetable.
We need to be able to initialize a Population from a Timetable object, which means that we also need to be able to initialize an Individual from a Timetable object. In order to resolve this TODO, therefore, we must do three things: add an initPopulation(Timetable) method to the GeneticAlgorithm class, add a constructor to Population that accepts a Timetable, and add a constructor to Individual that accepts a Timetable.
Let’s start from the bottom and work our way up. Update the Individual class by adding a new constructor that builds an Individual from a Timetable. The constructor uses the Timetable object to determine the number of classes that must be scheduled, which dictates the chromosome length. The chromosome itself is built by taking random rooms, timeslots, and professors from the Timetable.
Add the following method to the Individual class, anywhere you like:
public Individual(Timetable timetable) {
int numClasses = timetable.getNumClasses();
// 1 gene for room, 1 for time, 1 for professor
int chromosomeLength = numClasses * 3;
// Create random individual
int newChromosome[] = new int[chromosomeLength];
int chromosomeIndex = 0;
// Loop through groups
for (Group group : timetable.getGroupsAsArray()) {
// Loop through modules
for (int moduleId : group.getModuleIds()) {
// Add random time
int timeslotId = timetable.getRandomTimeslot().getTimeslotId();
newChromosome[chromosomeIndex] = timeslotId;
chromosomeIndex++;
// Add random room
int roomId = timetable.getRandomRoom().getRoomId();
newChromosome[chromosomeIndex] = roomId;
chromosomeIndex++;
// Add random professor
Module module = timetable.getModule(moduleId);
newChromosome[chromosomeIndex] = module.getRandomProfessorId();
chromosomeIndex++;
}
}
this.chromosome = newChromosome;
}
This constructor accepts a timetable object and loops over each student group and each module the group is enrolled in (giving us the total number of Classes that need scheduling). For each Class a random room, professor, and timeslot is selected and the corresponding ID is added to the chromosome.
Next, add this constructor method to the Population class. This constructor builds a Population from Individuals initialized with the Timetable, by simply calling the Individual constructor we just created.
public Population(int populationSize, Timetable timetable) {
// Initial population
this.population = new Individual[populationSize];
// Loop over population size
for (int individualCount = 0; individualCount < populationSize; individualCount++) {
// Create individual
Individual individual = new Individual(timetable);
// Add individual to population
this.population[individualCount] = individual;
}
}
Next, re-implement the initPopulation method in the GeneticAlgorithm class to use the new Population constructor:
public Population initPopulation(Timetable timetable) {
// Initialize population
Population population = new Population(this.populationSize, timetable);
return population;
}
We can finally resolve our next TODO: replace “TODO: Initialize Population” in the executive class’ main method and invoke the GeneticAlgorithm’s initPopulation method:
// Initialize population
Population population = ga.initPopulation(timetable);
The main method of the executive TimetableGA class should now look like the following. Since we haven’t implemented a termination condition, this code won’t do anything interesting yet, In fact the Java compiler may complain about unreachable code inside the loop. We’ll fix this shortly.
public static void main(String[] args) {
// Get a Timetable object with all the available information.
Timetable timetable = initializeTimetable();
// Initialize GA
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.9, 2, 5);
// Initialize population
Population population = ga.initPopulation(timetable);
// TODO: Evaluate population
// Keep track of current generation
int generation = 1;
// Start evolution loop
// TODO: Add termination condition
while (false) {
// Print fitness
System.out.println("G" + generation + " Best fitness: " + population.getFittest(0).getFitness());
// Apply crossover
population = ga.crossoverPopulation(population);
// TODO: Apply mutation
// TODO: Evaluate population
// Increment the current generation
generation++;
}
// TODO: Print final fitness
// TODO: Print final timetable
}
Evaluation
Our initial population has been created, and we need to evaluate those individuals and assign them fitness values. We know from earlier that the goal is to optimize our class timetable in a way that will avoid breaking as many constraints as possible. This means an individual’s fitness value will be inversely proportional to how many constraints it violates.
Open up and inspect the Timetable class’ “createClasses” method. Using its knowledge of all the Groups and Modules that need to be scheduled into classrooms with professors at specific times, it transforms a chromosome into an array of Class objects and stashes them away for evaluation. This method doesn’t do any actual evaluation, but it is the bridge between a chromosome and the evaluation step.
Next, inspect the “calcClashes” method in the same class. This method compares each class to every other class and adds a “clash” if any hard constraints are violated, for instance: if the selected room is too small, if there’s a scheduling conflict for the room, or if there’s a scheduling conflict for the professor. The method returns the total number of clashes it found.
Now we have everything in place to create our fitness function and finally to evaluate the fitnesses of the individuals in our population.
Open the GeneticAlgorithm class and first add the following calcFitness method.
public double calcFitness(Individual individual, Timetable timetable) {
// Create new timetable object to use -- cloned from an existing timetable
Timetable threadTimetable = new Timetable(timetable);
threadTimetable.createClasses(individual);
// Calculate fitness
int clashes = threadTimetable.calcClashes();
double fitness = 1 / (double) (clashes + 1);
individual.setFitness(fitness);
return fitness;
}
The calcFitness method clones the Timetable object given to it, calls the createClasses method, and then calculates the number of clashes via the calcClashes method. The fitness is defined as the inverse as the number of clashes—0 clashes will result in a fitness of 1.
Add an evalPopulation method to the GeneticAlgorithm class as well. As in previous chapters, this method simply iterates through the population and calls calcFitness for each.
public void evalPopulation(Population population, Timetable timetable) {
double populationFitness = 0;
// Loop over population evaluating individuals and summing population
// fitness
for (Individual individual : population.getIndividuals()) {
populationFitness += this.calcFitness(individual, timetable);
}
population.setPopulationFitness(populationFitness);
}
Finally, we can evaluate the population and resolve some TODOs in the executive TimetableGA class’ main method. Update the two locations that have “TODO: Evaluate Population” to instead show:
// Evaluate population
ga.evalPopulation(population, timetable);
At this point, there should be four TODOs remaining. The program is still not runnable at this point, because the termination condition hasn’t been defined and the loop hasn’t yet been enabled.
Termination
Our next step in building our class scheduler is to set up a termination check. Previously, we have used both the number of generations and the fitness to decide whether we want to terminate our genetic algorithm. This time we will combine both of these termination conditions, terminating our genetic algorithm either after a certain number of generations have past, or if it finds a valid solution.
Because the fitness value is based on the number of broken constraints, we know that a perfect solution will have a fitness value of 1. Leave the previous termination check intact, and add this second termination check to the GeneticAlgorithm class. We’ll use both checks in our executive loop.
public boolean isTerminationConditionMet(Population population) {
return population.getFittest(0).getFitness() == 1.0;
}
At this point, confirm that the second isTerminationConditionMet method (which should already be in the GeneticAlgorithm class) looks like the following:
public boolean isTerminationConditionMet(int generationsCount, int maxGenerations) {
return (generationsCount > maxGenerations);
}
Now we can add our two termination checks to our main method and enable the evolution loop. Open up the executive TimetableGA class, and resolve the “TODO: Add termination condition” TODO as follows:
// Start evolution loop
while (ga.isTerminationConditionMet(generation, 1000) == false
&& ga.isTerminationConditionMet(population) == false) {
// Rest of the loop in here...
The first isTerminationConditionMet call limits us to 1,000 generations, while the second checks to see if there are any individuals with a fitness of 1 in the population.
Let’s resolve two more TODOs very quickly. We have some simple reporting to present when the loop ends. Delete the two TODOs after the loop (“Print final fitness” and “Print final timetable”) and replace them with the following:
// Print fitness
timetable.createClasses(population.getFittest(0));
System.out.println();
System.out.println("Solution found in " + generation + " generations");
System.out.println("Final solution fitness: " + population.getFittest(0).getFitness());
System.out.println("Clashes: " + timetable.calcClashes());
// Print classes
System.out.println();
Class classes[] = timetable.getClasses();
int classIndex = 1;
for (Class bestClass : classes) {
System.out.println("Class " + classIndex + ":");
System.out.println("Module: " +
timetable.getModule(bestClass.getModuleId()).getModuleName());
System.out.println("Group: " +
timetable.getGroup(bestClass.getGroupId()).getGroupId());
System.out.println("Room: " +
timetable.getRoom(bestClass.getRoomId()).getRoomNumber());
System.out.println("Professor: " +
timetable.getProfessor(bestClass.getProfessorId()).getProfessorName());
System.out.println("Time: " +
timetable.getTimeslot(bestClass.getTimeslotId()).getTimeslot());
System.out.println("-----");
classIndex++;
}
At this point, you should be able to run the program, watch the evolution loop, and get a result. Without mutation, you may never find a solution, but the existing crossover methods that we repurposed from Chapters 2 and 3 are often sufficient to find a solution. However, if you run the program a number of times and you never reach a solution in less than 1,000 generations, you may want to re-read this chapter and make sure you haven’t made any mistakes.
We leave the familiar “Crossover” section out of this chapter, as there are no new techniques to present here. Recall that uniform crossover from Chapter 2 selects chromosomes at random and swaps them with a parent, without preserving any continuity within groups of genes. This is a good approach for this problem, given that groups of genes (representing professor, room, and timeslot combinations) are more likely to be harmful than helpful in this case.
Mutation
Recall that constraints upon the chromosome often dictate the mutation and crossover techniques one selects for a genetic algorithm. In this case, a chromosome is built of specific room, professor, and timeslot IDs; we can not simply select random numbers. Additionally, since the rooms, professors, and timeslots all have a different range of IDs, we also can not simply choose a random number between 1 and “X”. Potentially, we could choose random numbers for each of the different types of objects we’re encoding (room, professor, and timeslot), but that also assumes that IDs are contiguous, and they may not be!
We can take a tip from uniform crossover to solve our mutation problem. In uniform crossover, genes are selected at random from an existing and valid parent. The parent might not be the fittest individual in the population, but at least it’s valid.
Mutation can be implemented in a similar manner. Instead of choosing a random number for a random gene in the chromosome, we can create a new random but valid individual and essentially run uniform crossover to achieve mutation! That is, we can use our Individual(Timetable) constructor to create a brand new random Individual, and then select genes from the random Individual to copy into the Individual to be mutated. This technique is called uniform mutation, and makes sure that all of our mutated individuals are fully valid, never selecting a gene that doesn’t make sense. Add the following method anywhere in the GeneticAlgorithm class:
public Population mutatePopulation(Population population, Timetable timetable) {
// Initialize new population
Population newPopulation = new Population(this.populationSize);
// Loop over current population by fitness
for (int populationIndex = 0; populationIndex < population.size(); populationIndex++) {
Individual individual = population.getFittest(populationIndex);
// Create random individual to swap genes with
Individual randomIndividual = new Individual(timetable);
// Loop over individual’s genes
for (int geneIndex = 0; geneIndex < individual.getChromosomeLength(); geneIndex++) {
// Skip mutation if this is an elite individual
if (populationIndex > this.elitismCount) {
// Does this gene need mutation?
if (this.mutationRate > Math.random()) {
// Swap for new gene
individual.setGene(geneIndex, randomIndividual.getGene(geneIndex));
}
}
}
// Add individual to population
newPopulation.setIndividual(populationIndex, individual);
}
// Return mutated population
return newPopulation;
}
In this method, like mutations in previous chapters, the population is mutated by looping over the population’s non-elite individuals. Unlike other mutation techniques which tend to modify genes directly, this mutation algorithm creates a random but valid individual and copies genes at random from that.
We can now resolve the final TODO in our executive class’ main method. Add this one-liner to the main loop:
// Apply mutation
population = ga.mutatePopulation(population, timetable);
We should now have everything in place to run our genetic algorithm and create a new college timetable. If your Java IDE is showing errors, or if it won’t compile at this point, please go back through this chapter and resolve any issues you find.
Execution
Make sure your TimetableGA class looks like the following:
package chapter5;
public class TimetableGA {
public static void main(String[] args) {
// Get a Timetable object with all the available information.
Timetable timetable = initializeTimetable();
// Initialize GA
GeneticAlgorithm ga = new GeneticAlgorithm(100, 0.01, 0.9, 2, 5);
// Initialize population
Population population = ga.initPopulation(timetable);
// Evaluate population
ga.evalPopulation(population, timetable);
// Keep track of current generation
int generation = 1;
// Start evolution loop
while (ga.isTerminationConditionMet(generation, 1000) == false
&& ga.isTerminationConditionMet(population) == false) {
// Print fitness
System.out.println("G" + generation + " Best fitness: " + population.getFittest(0).getFitness());
// Apply crossover
population = ga.crossoverPopulation(population);
// Apply mutation
population = ga.mutatePopulation(population, timetable);
// Evaluate population
ga.evalPopulation(population, timetable);
// Increment the current generation
generation++;
}
// Print fitness
timetable.createClasses(population.getFittest(0));
System.out.println();
System.out.println("Solution found in " + generation + " generations");
System.out.println("Final solution fitness: " + population.getFittest(0).getFitness());
System.out.println("Clashes: " + timetable.calcClashes());
// Print classes
System.out.println();
Class classes[] = timetable.getClasses();
int classIndex = 1;
for (Class bestClass : classes) {
System.out.println("Class " + classIndex + ":");
System.out.println("Module: " +
timetable.getModule(bestClass.getModuleId()).getModuleName());
System.out.println("Group: " +
timetable.getGroup(bestClass.getGroupId()).getGroupId());
System.out.println("Room: " +
timetable.getRoom(bestClass.getRoomId()).getRoomNumber());
System.out.println("Professor: " +
timetable.getProfessor(bestClass.getProfessorId()).getProfessorName());
System.out.println("Time: " +
timetable.getTimeslot(bestClass.getTimeslotId()).getTimeslot());
System.out.println("-----");
classIndex++;
}
}
/**
* Creates a Timetable with all the necessary course information.
* @return
*/
private static Timetable initializeTimetable() {
// Create timetable
Timetable timetable = new Timetable();
// Set up rooms
timetable.addRoom(1, "A1", 15);
timetable.addRoom(2, "B1", 30);
timetable.addRoom(4, "D1", 20);
timetable.addRoom(5, "F1", 25);
// Set up timeslots
timetable.addTimeslot(1, "Mon 9:00 - 11:00");
timetable.addTimeslot(2, "Mon 11:00 - 13:00");
timetable.addTimeslot(3, "Mon 13:00 - 15:00");
timetable.addTimeslot(4, "Tue 9:00 - 11:00");
timetable.addTimeslot(5, "Tue 11:00 - 13:00");
timetable.addTimeslot(6, "Tue 13:00 - 15:00");
timetable.addTimeslot(7, "Wed 9:00 - 11:00");
timetable.addTimeslot(8, "Wed 11:00 - 13:00");
timetable.addTimeslot(9, "Wed 13:00 - 15:00");
timetable.addTimeslot(10, "Thu 9:00 - 11:00");
timetable.addTimeslot(11, "Thu 11:00 - 13:00");
timetable.addTimeslot(12, "Thu 13:00 - 15:00");
timetable.addTimeslot(13, "Fri 9:00 - 11:00");
timetable.addTimeslot(14, "Fri 11:00 - 13:00");
timetable.addTimeslot(15, "Fri 13:00 - 15:00");
// Set up professors
timetable.addProfessor(1, "Dr P Smith");
timetable.addProfessor(2, "Mrs E Mitchell");
timetable.addProfessor(3, "Dr R Williams");
timetable.addProfessor(4, "Mr A Thompson");
// Set up modules and define the professors that teach them
timetable.addModule(1, "cs1", "Computer Science", new int[] { 1, 2 });
timetable.addModule(2, "en1", "English", new int[] { 1, 3 });
timetable.addModule(3, "ma1", "Maths", new int[] { 1, 2 });
timetable.addModule(4, "ph1", "Physics", new int[] { 3, 4 });
timetable.addModule(5, "hi1", "History", new int[] { 4 });
timetable.addModule(6, "dr1", "Drama", new int[] { 1, 4 });
// Set up student groups and the modules they take.
timetable.addGroup(1, 10, new int[] { 1, 3, 4 });
timetable.addGroup(2, 30, new int[] { 2, 3, 5, 6 });
timetable.addGroup(3, 18, new int[] { 3, 4, 5 });
timetable.addGroup(4, 25, new int[] { 1, 4 });
timetable.addGroup(5, 20, new int[] { 2, 3, 5 });
timetable.addGroup(6, 22, new int[] { 1, 4, 5 });
timetable.addGroup(7, 16, new int[] { 1, 3 });
timetable.addGroup(8, 18, new int[] { 2, 6 });
timetable.addGroup(9, 24, new int[] { 1, 6 });
timetable.addGroup(10, 25, new int[] { 3, 4 });
return timetable;
}
}
Running the class scheduler as-is should generate a solution in approximately 50 generations, and in all cases should present a solution with zero clashes (hard constraints). If your algorithm repeatedly hits the 1,000 generation limit, or if it presents solutions with clashes, there’s likely something wrong with your implementation!
Take a minute to visually inspect the timetable results that the algorithm returns. Confirm that there are no actual clashes between professors, rooms, and timeslots.
At this point, you may also want to play with adding more professors, modules, timeslots, groups and rooms to the Timetable initialization in TimetableGA’s “initializeTimetable” method. Can you force the algorithm to fail?
Analysis and Refinement
The class-scheduling problem is a good example of using genetic algorithms to search a solution space for valid solutions rather than optimal solutions. This problem can have many solutions with a fitness of 1, and all we need to do is find just one of those valid solutions. When considering only hard constraints, there’s no real difference between any two valid solutions, and we can choose simply the first solution we find.
Unlike the traveling salesman problem from Chapter 4, this property of the class-scheduling problem means the algorithm can actually return invalid solutions. A solution in the traveling salesman problem can be invalid if it doesn’t visit each city once, but because we took great care to design our initialization, crossover, and mutation algorithms, we won’t ever encounter an invalid solution using the code from Chapter 4. All of the routes returned by our TSP solver are valid, and it’s just a matter of finding the shortest possible route. If we stop the TSP algorithm at any point, during any generation, and pick a member of the population at random, it will be a valid solution.
In this chapter, however, most solutions are invalid and we stop only when we find the first valid solution or run out of time. The difference between the two problems is as follows: in the traveling salesman problem, it’s easy to create a valid solution (just ensure every city is visited once; no guarantees as to the solution’s fitness, though!), but in the class scheduler, creating a valid solution is the difficult part.
Additionally, without any soft constraints, there’s no difference in fitness between any two valid solutions returned by the class scheduler. In this context, hard constraints determine whether a solution is valid, but soft constraints determine a solution’s quality. The implementation above does not prefer any particular valid solution, because it has no means of determining the quality of a solution—it only knows if a solution is valid or not.
Adding soft constraints to the class scheduler changes the problem significantly. No longer are we searching for just any valid solution, but we want the best valid solution.
Fortunately, genetic algorithms are particularly good at this type of constraint juggling. The fact that an individual is judged only by a single number—its fitness—works to our advantage. The algorithm that determines an individual’s fitness is completely opaque to the genetic algorithm—it’s a black box as far as the genetic algorithm is concerned. While the fitness score is massively important to the genetic algorithm and can’t be implemented haphazardly, its simplicity and opaqueness also lets us use it to reconcile all sorts of constraints and conditions. Because everything boils down to a single non-dimensional fitness score, we are able to scale and transform as many constraints as we like, and the importance of that constraint is represented by how strongly it contributes to the fitness score.
The class scheduler implemented above uses only hard constraints and confines the fitness score to the range 0-1. When combining different types of constraints, one should make sure that hard constraints have an overwhelming effect on the fitness score, while soft constraints make a more modest contribution.
As an example, imagine you needed to add a handful of soft constraints to the class scheduler, each with a slightly different importance. The hard constraints still apply, of course. How do you reconcile soft constraints with hard constraints? The existing fitness score of “1 / (clashes + 1)” clearly does not incorporate soft constraints—and even if it considered a broken soft constraint a “clash”, would still put them all on equal footing with hard constraints. Under that model, it’s possible to select an invalid solution because it may have a number of satisfied soft constraints that make up for the lost fitness caused by the broken hard constraint.
Instead, consider a new fitness scoring system: each broken hard constraint subtracts 100 from the fitness score, while any satisfied soft constraint may add 1, 2, or 3 points to the fitness score depending on its importance. Under this scheme, we should only consider solutions with a score of zero or above, as anything negative has a broken hard constraint. This scheme also ensures that there’s no way a broken hard constraint can be canceled out by a large number of satisfied soft constraints – the contribution of a hard constraint to the fitness score is so overwhelming that there’s no way the soft constraints can make up the 100 points penalized by a broken hard constraint. Finally, this scheme also allows you to prioritize the soft constraints—more important constraints can contribute more to the fitness score.
To further illustrate the idea that the fitness score normalizes constraints; consider any mapping and directions tool (like Google Maps). When you search for directions between two locations, the primary contributor to the fitness score is the amount of time it takes to get from place to place. A simple algorithm might use travel time in minutes as its fitness score (in this case, we’ll call it “cost score”, since lower is better, and the inverse of fitness is generally called “cost”).
A route that takes 60 minutes is better than a route that takes 70 minutes – but we know that’s not always the case in real life. Perhaps the shorter route has an exorbitant toll of $20. The user may choose the “Avoid Tolls” option, and now the algorithm has to reconcile driving minutes versus toll dollars. How many minutes is a dollar worth? If you decide that each dollar adds one point to the cost score, the shorter route now has a cost of 80, and loses to the longer but cheaper route. On the other hand, if you weigh toll-avoidance less and decide that one dollar of toll only adds a cost of 0.25 to the route, the shorter route will still win with a cost of 65.
Ultimately, when working with hard and soft constraints in genetic algorithms, be sure to understand what the fitness score represents and how each constraint will affect an individual’s score.
Exercises
- Add soft constraints to the class scheduler. This could include preferred professor time and preferred classrooms.
- Implement support for a config file or database connection to add initial timetable data.
- Build a class scheduler for a school timetable that requires students to have a class scheduled for each period.
Summary
In this chapter, we have covered the basics of class scheduling using genetic algorithms. Rather than using a genetic algorithm to find an optimal solution, we used a genetic algorithm to find the first valid solution that satisfies a number of hard constraints.
We also explored a new mutation tactic that ensures mutated chromosomes remain valid. Instead of modifying the chromosome directly and adding randomness—which may have led to invalid chromosomes in this case—we created a known-valid random Individual and swapped genes with it in a style reminiscent to uniform crossover. This algorithm is still considered uniform mutation, however the new approach used in this chapter made it easier to ensure valid mutation.
We also combined uniform crossover from Chapter 2 with tournament selection from Chapter 3, showing that many aspects of genetic algorithms are modular, independent, and able to be combined in different ways.
Finally, we discussed the flexibility of the fitness score in genetic algorithms. We learned that the non-dimensional fitness score can be used to introduce soft constraints and reconcile them with hard constraints, with the ultimate goal of producing not just valid results, but high-quality results as well.