 |
General Programming »
Algorithms & Recipes »
Algorithms
Intermediate
License: The Code Project Open License (CPOL)
Making Class Schedule Using Genetic AlgorithmBy Mladen JankovicHow to make class schedule using genetic algorithm |
C++, Windows, Win32, MFC, STL, Dev
|
||||||||
|
Advanced Search Add to IE Search |
|
|
||||||||||||||||||
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 information about equipment (computers). 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 (sum of student groups' sizes) are needed in classroom, 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. Also we should know how to specify how good our solution is. In other words we should be able to calculate fitness value of our solution.
How we represent chromosome for class schedule? 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 9pm (12 hours total) and working days are from Monday to Friday (5 days total). We can use std::vector with size 12*5*number_of_rooms. Slot should be std::list because during execution of our algorithm we allow multiple classes at same time-space slot. There is additional hash map which is used to obtain the first time-space 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
Chromosomes are represented by Schedule class and it stores representation of class schedule in these two attributes:
// Time-space slots, one entry represent one hour in one classroom vector<list<CourseClass*>> _slots; // Class table for chromosome // Used to determine first time-space slot used by class hash_map<CourseClass*, int> _classes;
Additionally chromosome should store its fitness value and parameters which are used by genetic operations.
Fitness value is stored here:
// Fitness value of chromosome float _fitness; // Flags of class requiroments satisfaction vector<bool> _criteria;
Chromosome parameters:
// Number of crossover points of parent's class tables int _numberOfCrossoverPoints; // Number of classes that is moved randomly by single mutation operation int _mutationSize; // Probability that crossover will occure int _crossoverProbability; // Probability that mutation will occure int _mutationProbability;
Now we need to assign a fitness value to the chromosome. As I previously said only hard requirements is used to calculate fitness of class schedule. This is how we do it:
schedule_score/maximum_score, and maximum_score is number_of_classes*5. Fitness values are represented by single-precision floating point number (float) in range from 0 to 1.
Crossover operation combines data in hash maps of two parents, 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
// Performes crossover operation using to chromosomes // and returns pointer to offspring Schedule* Crossover(const Schedule& parent2) const;
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.
// Performs mutation on chromosome void Mutation();
Genetic algorithm is fairly simple. For each generation it performs two basic operations:
And these two operations are repeated until the best chromosome reaches fitness value equals to 1 (meaning that all classes in schedule meet requirement). As mentioned before, genetic algorithm keeps track of M best chromosomes in population and guarantees that they are not going to be replaced while they are among the best chromosomes.
// Genetic algorithm class Algorithm { private: // Population of chromosomes vector<Schedule*> _chromosomes; // Inidicates wheahter chromosome belongs to // best chromosome group vector<bool> _bestFlags; // Indices of best chromosomes vector<int> _bestChromosomes; // Number of best chromosomes currently saved in // best chromosome group int _currentBestSize; // Number of chromosomes which are replaced in // each generation by offspring int _replaceByGeneration; // Pointer to algorithm observer ScheduleObserver* _observer; // Prototype of chromosomes in population Schedule* _prototype; // Current generation int _currentGeneration; // State of execution of algorithm AlgorithmState _state; // Synchronization of algorithm's state CCriticalSection _stateSect; // Pointer to global instance of algorithm static Algorithm* _instance; // Synchronization of creation and destruction // of global instance static CCriticalSection _instanceSect; public: // Returns reference to global instance of algorithm static Algorithm& GetInstance(); // Frees memory used by gloval instance static void FreeInstance(); // Initializes genetic algorithm Algorithm(int numberOfChromosomes, int replaceByGeneration, int trackBest, Schedule* prototype, ScheduleObserver* observer); // Frees used resources ~Algorithm(); // Starts and executes algorithm void Start(); // Stops execution of algoruthm void Stop(); // Returns pointer to best chromosomes in population Schedule* GetBestChromosome() const; // Returns current generation inline int GetCurrentGeneration() const { return _currentGeneration; } // Returns pointe to algorithm's observer inline ScheduleObserver* GetObserver() const { return _observer; } private: // Tries to add chromosomes in best chromosome group void AddToBest(int chromosomeIndex); // Returns TRUE if chromosome belongs to best chromosome group bool IsInBest(int chromosomeIndex); // Clears best chromosome group void ClearBest(); };
ScheduleObserver class handles events that are triggered by genetic algorithm. This class you send messages to view window of application. Also you can block caller"s thread until execution of algorithm is not finished or stopped by calling WaitEvent() method.
// Handles event that is raised // when algorithm finds new best chromosome void NewBestChromosome(const Schedule& newChromosome); // Handles event that is raised when state // of execution of algorithm is changed void EvolutionStateChanged(AlgorithmState newState); // Block caller's thread until algorithm finishes execution inline void WaitEvent() //...
If you plan to change NewBestChromosome method keep in mind that if you want to keep the best chromosome to display it you must make hard copy (by using MakeCopy method of Schedule class), because algorithm can delete that chromosome in next generation.
#prof tag) - describes professor. #course tag) - describes course. #room tag) - describes room. #group tag) - describes student group. #class tag) - describes class, binds professor, course and student groups. #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. #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
#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 //...
This article is written based on this text but with different license.
General 
News 
Question 
Answer 
Joke 
Rant 
Admin
Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads.
|
PermaLink |
Privacy |
Terms of Use
Last Updated: 22 Jan 2008 Editor: |
Copyright 2008 by Mladen Jankovic Everything else Copyright © CodeProject, 1999-2010 Web22 | Advertise on the Code Project |
2005/2008