Using Genetic Algorithm Library For Class Schedule
Contents
This article demonstrates usage of Genetic Algorithm Library. In order to compile this example
you must obtain copy of the library. Installation procedure of the library is described
here.
Genetic Algorithm Library 1.2 Open Source can be downloaded at
this page.
Making class schedule is one of those NP hard problems. The problem can be solved using heuristic search algorithm to
find optimal solution, but it works for simple cases. For more complex inputs and requirements finding considerably good solution
can take a while or it may be impossible. This is where genetic algorithms come in the game.
When you make class schedule you must take into consideration many requirements (number of professors, students, classes and
classrooms, size of classroom, laboratory equipment in classroom and many other). These requirements can be divided into several
groups by their importance. Hard requirements (if you break one of these then the schedule is infeasible):
- Class can be placed only in spear classroom.
- No professor or student group can have more then on class at one time.
- Classroom must have enough seats to accommodate all students.
- To place class in classroom, classroom must have laboratory equipment (computers in our case) if class requires it.
Some soft requirements (can be broken but schedule is still feasible):
- Preferred time of class by professors.
- Preferred classroom by professors.
- Distribution (in time or space) of classes for student groups or professors.
Hard and soft requirements of course depend on situation. In this example only hard requirements are implemented. Let start by explaining
object which makes on class schedule.
Professor class has ID and name of professor. It also contains list of classes
that professor teaches.
StudentsGroup class has ID and name of student group, as well as number of
students (size of group). It also contains list of classes that group attends.
Room class has ID and name of classroom, as well as number of seats and if there
are computers in it. If classroom has computers, it is expected that there is a computer for
each seat. IDs are generated internally and automatically.
Course class has ID and name of course.
CourseClass holds reference to course to which class belongs, reference to
professor who teaches and list of student groups that attend class. It also stores how many
seats are needed (sum of student groups' sizes), if class requires computers in classroom and
duration of class (in hours).
The first thing we should consider when we deal with genetic algorithm
is how to represent our solution in such way that is feasible for genetic operations
such as crossover and mutation and we should know how to specify how good our solution is
(called fitness).
How we represent chromosome? Well we need a slot (time-space slot) for each hour,
we assume that time is in one hour granules, for every room of every day. Also we
assume that classes cannot begin before 9am and should finish before or at 10pm
(12 hours total) and working days are Monday to Friday (5 days total). So we need vector
with size
12*5*number_of_rooms. Slot should be of
std::list
type because during execution of our algorithm we allow multiple classes at same slot.
There is additional hash map which is used to obtain slot at which class begins
(its position in vector) from address of class's object. Each hour of a class has separate
entry in vector, but there is only one entry per class in hash map. For instance if class
starts at 1pm and lasts for three hours, it has entries in 1pm, 2pm and 3pm slots.
Figure 1 - Chromosome Representation
As we have vector of slots we can use
Chromosome::Representation::GaMultiValueChromosome
template class to represent our chromosome, but we must modify it by adding previously
explained hash map.
class Schedule : public GaMultiValueChromosome>
{
friend class ScheduleCrossover;
friend class ScheduleMutation;
friend class ScheduleFitness;
friend class ScheduleObserver;
private:
hash_map _classes;
hash_map _backupClasses;
public:
Schedule(GaChromosomeDomainBlock>* configBlock);
Schedule(const Schedule& c, bool setupOnly);
virtual ~Schedule();
virtual GaChromosomePtr GACALL MakeCopy(bool setupOnly) const;
virtual GaChromosomePtr GACALL MakeNewFromPrototype() const;
virtual void GACALL PreapareForMutation();
virtual void GACALL AcceptMutation();
virtual void GACALL RejectMutation();
};
Chromosome has three major parts: code, fitness value and setup. Chromosome's code contains
representation of solution, in our case it is hash map and vector of slots. Fitness value keeps
information about how good that solution is. Setup of chromosomes stores references to genetic
operations which are used to operate on chromosome (such as fitness operation, crossover operation
or mutation operation). It also stores parameters which are used by these genetic operation as well
as parameters of chromosomes. Chromosome's setup is stored in Chromosome Configuration Block (CCB).
When we make first chromosome we must give reference to CCB. The CCB is then used for new chromosomes
produced by copy constructor or
MakeCopy and
MakeFromPrototype methods.
_classes attribute stores hash map and
_backupClasses used to
save copy of it if improving only mutations are enabled. The first constructor takes configuration
block and initialize empty chromosome (no chromosome's code) with provided setup. The second
constructor is copy constructor with additional parameter
setupOnly. This parameter
specifies weather constructor should copy only setup of chromosomes or it should copy chromosome's
code as well (hash map and vector of slots). Destructor must be declared even if it doesn't do
anything to avoid memory leakage.
MakeCopy does what it says - it makes copy of the
chromosomes and returns smart pointer to it. It copies CCB to new chromosome as well as chromosome's
code and fitness (if specified so).
MakeNewFromPrototype method makes new chromosome
with same CCB but it initializes new chromosome's code with random values (size of new code is same
as size of prototype code).
PreapareForMutation method called before algorithm performs
mutation operation on chromosome, it is used to save current chromosomes code.
AcceptMutation method is called if algorithm has accepted mutation that had been made,
it is used to clear saved code.
RejectMutation method is called if algorithm has rejected
mutation that had been made, it is used to restore chromosome's code. When overriding these methods,
overridden methods of base class should also be called from child class.
Now we need to assign a fitness value to the chromosome.We will use minimal requirements
for a class schedule (nothing fancy, for instance we assume that professor can have classes
at any time). This is how we do it:
- Each class can have from 0 to 5 points.
- If class use empty room, we increment its score.
- If class requires computers and it is located in room with them, we increment its score.
But if class doesn't requires computers, well we increment its score anyway.
- If class is located in room with enough available seats, guess what,
we increment its score.
- If professor is available (has no other classes) at the time,
we increment class's score once again.
- And last criteria that we check is if student groups of the class has no other classes
at same time, and if they don't we increment score of the class.
- If class brakes some rule at any slot that the score is not incremented
- Total score of schedule is sum of points of all classes.
- Fitness value is calculated as
schedule_score/maximum_score,
and maximum_score is number_of_classes*5.
Fitness values are represented by single-precision floating point number (
float).
Fitness operation must inherit
Chromosome::GaFitnessOperation.
class ScheduleFitness : public GaFitnessOperation
{
public:
virtual float GACALL operator ()(const GaChromosome* chromosome) const;
virtual GaParameters* GACALL MakeParameters() const;
virtual bool GACALL CheckParameters(const GaParameters& parameters) const;
};
operator () calculates fitness value of chromosome and returns that value.
MakeParameters and
CheckParameters don't do anything they just override
pure virtual functions from
Common::GaOperation class.
Crossover operation combines data in hash maps of two parent chromosomes, and then it creates
vector of slots according to content of new hash map. Crossover 'splits' hash maps of both parents
in parts of random size. Number of parts is defined by number of crossover points (plus one) in
chromosome's parameters. Then it alternately copies parts form parents to new chromosome, and forms
new vector of slots.
Figure 2 - Crossover operation
GAL has some built-in crossover operations, but now we need specialized crossover, so we make our own.
Crossover operation must inherit
Chromosome::GaCrossoverOperation class.
class ScheduleCrossover : public GaCrossoverOperation
{
public:
virtual GaChromosomePtr GACALL operator ()(const GaChromosome* parent1,
const GaChromosome* parent2) const;
virtual GaParameters* GACALL MakeParameters() const;
virtual bool GACALL CheckParameters(const GaParameters& parameters) const;
};
operator () performs crossover operation, produces new chromosomes and returns
smart pointer to it.
MakeParameters and
CheckParameters like in
fitness operation don't do anything.
Mutation operation is very simple. It just takes class randomly and moves it to another
randomly chosen slot. Number of classes which are going to be moved in a single operation is
defined by mutation size in chromosome's parameters.
GAL also has built-in mutation operations, but now we need specialized crossover, so we make
our own. Crossover operation must inherit
Chromosome::GaMutationOperation class.
class ScheduleMutation : public GaMutationOperation
{
public:
virtual void GACALL operator ()(GaChromosome* chromosome) const;
virtual GaParameters* GACALL MakeParameters() const;
virtual bool GACALL CheckParameters(const GaParameters& parameters) const;
};
operator () performs mutation operation.
MakeParameters and
CheckParameters like in crossover operation don't do anything.
GAL observer pattern to notify user about progress of the algorithm and changes of it state.
Observer's class must inherit
Observing::GaObserver. All methods in this class
are abstract and must be overridden:
StatisticUpdate - this method is called each time before algorithm progress
to next generationNewBestChromosome - this method is called each time when algorithm
finds new best solutionEvolutionStateChanged - this method is called when user stops, starts,
pauses or resumes execution of algorithm
If we don't have to handle all these events observer can inherit
Observing::GaObserverAdapter class, and only override methods that handles
desired events.
class ScheduleObserver : public GaObserverAdapter
{
private:
HANDLE _event;
void ReleaseEvent();
public:
ScheduleObserver();
virtual ~ScheduleObserver();
void WaitEvent();
virtual void GACALL NewBestChromosome(const GaChromosome& newChromosome,
const GaAlgorithm& algorithm);
virtual void GACALL EvolutionStateChanged(GaAlgorithmState newState,
const GaAlgorithm& algorithm);
};
On top of all things what we need is genetic algorithm. We choose an incremental
genetic algorithm (it replaces only few chromosomes in each generation). But to make an algorithm
object we need stop criteria, population on which algorithm is going to operate and parameters for
the algorithm. Desired algorithm use
Algorithm::GaMultithreadingAlgorithmParams class
as parameters because it only needs number of working threads. To specify stop criteria to the algorithm,
there should be parameters for it. We use stop criteria based on fitness value (in our case, based on
fitness value of best chromosome)
Algorithm::StopCriterias::GaFitnessCriteria and its
parameters
Algorithm::StopCriterias::GaFitnessCriteriaParams.
Population is encapsulated in
Population::GaPopulation class. To instantiate a population
object we must provide prototype of chromosome, and configuration of population. Configuration is consists
genetic operations which are performed over population (selection, coupling, scaling and replacement),
comparator of chromosomes' fitness values which is used to sort chromosome in population and sorted groups
and parameters of population. Configuration of population is represented by
GaPopulationConfiguration class. Because algorithm should maximize fitness values
Chromosome::FitnessComparators::GaMaxFitnessComparator comparator should be used.
Population::GaPopulationParameters class represents parameters of population. Incremental
algorithm requires population with fixed size. Because random selection and replacement is used population
don't have to be sorted. Also we want to track few best and few worst chromosomes. Last thing about population
parameters is whether we'll use scaled fitness values or non-scaled fitness values. Because we won't use
scaling operation population will use non-scaled fitness values. As said, we select chromosomes randomly
produce few chromosomes and replace random chromosomes in each generation. As selection operation
Population::SelectionOperations::GaSelectRandomBest is used with
Population::SelectionOperations::GaSelectRandomBestParams class as parameters. Replacement operation
is
Population::ReplacementOperations::GaReplaceRandom with
Population::ReplacementOperations::GaReplaceElitismParams class as parameters. Default coupling
operation is used and scaling operation isn't used.
Chromosome prototype is empty chromosome, has no code, with defined Chromosome Configuration Block (CCB) and
defined size of code. Because our chromosome inherits
Chromosome::Representation::GaMultiValueChromosome
we must use
Chromosome::Representation::GaChromosomeDomainBlock CCB even if we don't use value set.
When constructing CCB we specify chromosomes parameters, which crossover, mutation and fitness operations are going
to be used as well as fitness comparator. Chromosome parameters are represented by
Chromosome::GaChromosomeParams class. This class also handles parameters for genetic operation
which operates on chromosome. Parameters define how frequently crossover and mutation operation are going to
be performed, size of mutation and number of crossover points. Also it tells if only the mutations that
improve fitness value should be accepted.
And here's the code:
int main()
{
// parse config file
Configuration::GetInstance().ParseFile( "GaSchedule.cfg" );
// initialize GAL internal structures
GaInitialize();
// make chromosome parameters
// crossover probability: 80%
// crossover points: 2
// no "improving only mutations"
// mutation probability: 3%
// number of moved classes per mutation: 2
GaChromosomeParams chromosomeParams( 0.8F, 2, false, 0.03F, 2 );
// instances of genetic operations
ScheduleCrossover crossoverOperation;
ScheduleMutation mutationOperation;
ScheduleFitness fitnessOperation;
// make CCB with fallowing setup:
// there are no value set with ScheduleCrossover,
// ScheduleMutation, ScheduleFitness genetic operations
// set fittnes comparator for maximizing fitness value
// use previously defined chromosome's parameters
GaChromosomeDomainBlock<list<CourseClass*>> configBlock( NULL,
&crossoverOperation, &mutationOperation, &fitnessOperation,
GaFitnessComparatorCatalogue::Instance().GetEntryData(
"GaMaxFitnessComparator" ),
&chromosomeParams );
// make prototype of chromosome
Schedule prototype( &configBlock );
// make population parameters
// number of chromosomes in population: 100
// population always has fixed number of chromosomes
// population is not sorted
// non-transformed(non-scaled) fitness values are used
// for sorting and tracking chromosomes
// population tracks 5 best and 5 worst chromosomes
GaPopulationParameters populationParams( 100, false, false, false, 5, 5 );
// make population parameters
// number of chromosomes in population: 100
// population always has fixed number of chromosomes
// population is not sorted
// non-transformed(non-scaled) fitness values are used
// for sorting and tracking chromosomes
// population tracks 5 best and 5 worst chromosomes
GaPopulationParameters populationParams( 100, false, false, false, 5, 5 );
// make parameters for selection operation
// selection will choose 16 chromosomes
// but only 8 best of them will be stored in selection result set
// there will be no duplicates of chromosomes in result set
GaSelectRandomBestParams selParam( 8, false, 16 );
// make parameters for replacement operation
// replace 8 chromosomes
// but keep 5 best chromosomes in population
GaReplaceElitismParams repParam( 8, 5 );
// make parameters for coupling operation
// coupling operation will produce 8 new chromosomes
// from selected parents
GaCouplingParams coupParam( 8 );
// make population configuration
// use defined population parameters
// use same comparator for sorting as comparator used by chromosomes
// use selection operation which randomly selects chromosomes
// use replacement operation which randomly chooses chromosomes
// from population which are going to be replaced,
// but keeps best chromosomes
// use simple coupling
// disable scaling
GaPopulationConfiguration populationConfig( populationParams,
&configBlock.GetFitnessComparator(),
GaSelectionCatalogue::Instance().GetEntryData( "GaSelectRandomBest" ),
&selParam,
GaReplacementCatalogue::Instance().GetEntryData( "GaReplaceRandom" ),
&repParam,
GaCouplingCatalogue::Instance().GetEntryData( "GaSimpleCoupling" ),
&coupParam,
NULL, NULL );
// make population
// with previously defined prototype of chromosomes
// and population configuration
GaPopulation population( &prototype, &populationConfig );
// make parameters for genetic algorithms
// algorithm will use two workers
GaMultithreadingAlgorithmParams algorithmParams( 2 );
// make incremental algorithm with previously defined
// population and parameters
GaIncrementalAlgorithm algorithm( &population, algorithmParams );
// make parameters for stop criteria based on fitness value
// stop when best chromosome reaches fitness value of 1
GaFitnessCriteriaParams criteriaParams( 1, GFC_EQUALS_TO,
GSV_BEST_FITNESS );
// sets algorithm's stop criteria (base on fitness value)
// and its parameters
algorithm.SetStopCriteria(
GaStopCriteriaCatalogue::Instance().GetEntryData(
"GaFitnessCriteria" ),
&criteriaParams );
// make observer and subscribe it on algorithms events
ScheduleObserver observer;
algorithm.SubscribeObserver( &observer );
// start execution
algorithm.StartSolving( false );
observer.WaitEvent();
// free memory used by GAL internal structures
GaFinalize();
return 0;
}
Note that
GaInitialize must be called before any part of GAL is used, and
GaFinalize must be called before program exits or when GAL is not needed anymore.
Types of objects:
- professor (
#prof tag) - describes professor.
- course (
#course tag) - describes course.
- room (
#room tag) - describes room.
- group (
#group tag) - describes student group.
- course class (
#class tag) - describes class, binds
professor, course and student groups.
Each object begins with its tag and finishes with
#end tag,
all tags must be in separate lines. In a body of an object each line contains
only one key and value pair (attribute) separated by
= character.
Each attribute should be specified just one time except for group attribute
in
#group object which can have multiple group attributes.
Tag and key names are case sensitive. List of objects' attributes:
#prof
id (number, required) - ID of the professor.name (string, required) - name of the professor.
#course
id (number, required) - ID of the course.name (string, required) - name of the course.
#room
name (string, required) - name of the room.size (number, required) - number of seats in the room.lab (boolean, optional) - indicates if the room is lab (has computers).
If not specified, default value is false.
#group
id (number, required) - ID of the student groups.name (string, required) - name of the student groups.size (number, required) - number of students in the group.
#class
professor (number, required) - ID of a professor.
Binds professor to class.course (number, required) - ID of a course.
Binds course to class.group (number, required) - ID of a student group.
Binds student group to class.
Each class can be bound to multiple student groups.duration (number, optional) - duration of class (in hours).
If not specified, default value is 1.lab (boolean, optional) - is the class requires computers in a room.
If not specified, default value is false.
Note that professor, student group and course objects must be defined before
they are bound to course class object.
#prof
id = 1
name = John Smith
#end
#course
id = 1
name = Introduction to Programming
#end
#room
name = R1
lab = true
size = 24
#end
#group
id = 1
name = 1O1
size = 19
#end
#group
id = 2
name = 1O2
size = 20
#end
#class
professor = 1
course = 1
duration = 2
group = 1
group = 2
#end
#class
professor = 1
course = 1
duration = 3
group = 1
lab = true
#end
#class
professor = 1
course = 1
duration = 3
group = 2
lab = true
#end
Parsing of configuration file is done by
Configuration class.
ParseFile method opens and parse configuration file.
It searches for object tags and calls appropriate method for parsing object.
ParseFile method also clears previously parsed object.
public:
void ParseFile(char* fileName);
private:
Professor* ParseProfessor(ifstream& file);
StudentsGroup* ParseStudentsGroup(ifstream& file);
Course* ParseCourse(ifstream& file);
Room* ParseRoom(ifstream& file);
CourseClass* ParseCourseClass(ifstream& file);
To parse file:
Configuration::GetInstance().ParseFile( "GaSchedule.cfg" );
Parsed objects are kept in hash map except course classes, so they can be accessed easily and fast.
private:
hash_map<int, Professor*> _professors;
hash_map<int, StudentsGroup*> _studentGroups;
hash_map<int, Course*> _courses;
hash_map<int, Room*> _rooms;
list<CourseClass*> _courseClasses;
Configuration class also contains methods for retrieving parsed information and objects.
public:
inline Professor* GetProfessorById(int id) //...
inline int GetNumberOfProfessors() const //...
inline StudentsGroup* GetStudentsGroupById(int id) //...
inline int GetNumberOfStudentGroups() const //...
inline Course* GetCourseById(int id) //...
inline int GetNumberOfCourses() const //...
inline Room* GetRoomById(int id) //...
inline int GetNumberOfRooms() const //...
inline const list<CourseClass*>& GetCourseClasses() const //...
inline int GetNumberOfCourseClasses() const //...