[hazelrink]

I found this project http://www.codeproje...ssSchedule.aspx -> this is about a class scheduler using Genetic Algorithm. I tried to understand the code but I dont understand parts of it.

my questions are:

1. In the Selection and Crossover stages the algorithm chooses parents to "mate" to produce an offspring, in the scenario of this scheduler what are the parents? Are they the whole schedule or are they just a single schedule/class ?
2. if in case that the parents are the whole set of schedules then the population is composed of parents meaning the population is comprised of different set of schedules, thus the program keeps track of some of the schedules? and the good ones are selected to mate to produce a better schedule?
3. I dont get how the software represents its schedules hence i cant understand how the software uses the crossover method.

Thanks for those who tried and help me T__T

[modi123_1]

hazelrink, on 04 August 2010 - 10:47 AM, said:

I found this project http://www.codeproje...ssSchedule.aspx -> this is about a class scheduler using Genetic Algorithm. I tried to understand the code but I dont understand parts of it.

my questions are:

1. In the Selection and Crossover stages the algorithm chooses parents to "mate" to produce an offspring, in the scenario of this scheduler what are the parents? Are they the whole schedule or are they just a single schedule/class ?
2. if in case that the parents are the whole set of schedules then the population is composed of parents meaning the population is comprised of different set of schedules, thus the program keeps track of some of the schedules? and the good ones are selected to mate to produce a better schedule?
3. I dont get how the software represents its schedules hence i cant understand how the software uses the crossover method.

Thanks for those who tried and help me T__T

Regarding the number 3 question - it was pretty well explained out.

Quote

Representation

How can we represent the chromosome for a 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, 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 an std::vector with a size 12*5*number_of_rooms. The slot should be an std::list because during the execution of our algorithm, we allow multiple classes during the same time-space slot. There is an additional hash map which is used to obtain the first time-space slot at which a class begins (its position in vector) from the address of the class' object. Each hour of a class has a separate entry in the vector, but there is only one entry per class in the hash map. For instance, if a class starts at 1pm and lasts for three hours, it has entries in the 1pm, 2pm, and 3pm slots

Quote

Crossover
A crossover operation combines data in the hash maps of two parents, and then it creates a vector of slots according to the content of the new hash map. A crossover 'splits' hash maps of both parents in parts of random size. The number of parts is defined by the number of crossover points (plus one) in the chromosome's parameters

So the hash maps are the first time slot a class starts, right?

This post has been edited by modi123_1: 04 August 2010 - 11:24 AM

[hazelrink]

modi123_1, on 04 August 2010 - 10:23 AM, said:

hazelrink, on 04 August 2010 - 10:47 AM, said:

I found this project http://www.codeproje...ssSchedule.aspx -> this is about a class scheduler using Genetic Algorithm. I tried to understand the code but I dont understand parts of it.

my questions are:

1. In the Selection and Crossover stages the algorithm chooses parents to "mate" to produce an offspring, in the scenario of this scheduler what are the parents? Are they the whole schedule or are they just a single schedule/class ?
2. if in case that the parents are the whole set of schedules then the population is composed of parents meaning the population is comprised of different set of schedules, thus the program keeps track of some of the schedules? and the good ones are selected to mate to produce a better schedule?
3. I dont get how the software represents its schedules hence i cant understand how the software uses the crossover method.

Thanks for those who tried and help me T__T

Regarding the number 3 question - it was pretty well explained out.

Quote

Representation

How can we represent the chromosome for a 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, 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 an std::vector with a size 12*5*number_of_rooms. The slot should be an std::list because during the execution of our algorithm, we allow multiple classes during the same time-space slot. There is an additional hash map which is used to obtain the first time-space slot at which a class begins (its position in vector) from the address of the class' object. Each hour of a class has a separate entry in the vector, but there is only one entry per class in the hash map. For instance, if a class starts at 1pm and lasts for three hours, it has entries in the 1pm, 2pm, and 3pm slots

Quote

Crossover
A crossover operation combines data in the hash maps of two parents, and then it creates a vector of slots according to the content of the new hash map. A crossover 'splits' hash maps of both parents in parts of random size. The number of parts is defined by the number of crossover points (plus one) in the chromosome's parameters

So the hash maps are the first time slot a class starts, right?

From what i understand is that the software uses hash maps to tell what time slots are used per room (right?).
But what kind of data is pushed onto the has map? I mean what does the software store in the hash map? for example the software uses 1 as occupied and 0 as free. the software pushed 1 to the time slot on 9 to 10am in room 101 Monday, how could the software know who the professor is for that class and what subject? (does the software use another representation technique to know who the prof is and what the subject is?)

and in the crossover stage the software uses the hash map of the schedule to produce an offspring but wouldn't this result in an error? I mean the software copies a set of schedules from one parent to another (randomly), say for example he chose class 101 at 9am to 10am Monday on one parent and wants the other parent to adopt this but the other parent already has a class 101 at 5pm to 6pm Monday, wouldn't this make the schedule redundant?

This all are based on what I understand from the software I may be ENTIRELY wrong since i really dont understand it and im not very well adept with C++, i cant even run a proper program using C++ thats how amazing I am HAHA!