Advice on implementing genetic algorithm for different type of scheduling?

[SmithsonianDSP]

I saw your article about using genetic algorithms for scheduling a couple of weeks ago and it piqued my interest in genetic algorithms, in general. I've been looking at some genetic algorithm frameworks for C# and have been considering using them for a somewhat different kind of scheduling.

But I've run into a point where I'm not entirely certain how to best implement the gene/chromosome parts for what I'm trying to do, and I'm hoping that you might be willing to offer some suggestions or advice given your experience in the area? I think I really just need a little help to get me going in the right direction.

The kind of scheduling I'm considering is for scheduling events over the course of year. For example, let's say that Event A should occur every 7 days, and Event B should occur every 30 days: having the two events too close together is bad (e.g., Event A on one day and Event B on the second or third day), but having multiple events on the same day is good (e.g., Event A and B on the same day); scheduling closer to their ideal date is better, but not as good as having them on the same day (e.g., having Event B occur 3 days sooner so it can be on the same day as Event A would be better fitness than having Event A and Event B occur exactly on the ideal days). There are some other things that would be considered, but these are the main ones and should give you a pretty good idea.

I haven't worked with dart, but I believe your code has each session mapped to an integer, with the int value stored as a gene in the chromosome, and the order of the genes represents the order of the schedule... but I don't think the same approach will work for this. I've looked at a number of examples but none of them seem to be quite applicable. I think I have a good idea of how to handle the fitness evaluation, crossover, mutation, etc., stuff—once I get to that point—but I'm just kind of stuck on how to represent this in the genes/chromosomes for this.

Do I have a gene for each event and the gene's value corresponds with the frequency of that event? Do chromosomes contain genes mapping out a full year of events so it can align for things with frequencies that don't divide nicely (e.g., every 45 days)? (Or maybe a genetic algorithm isn't really a good fit for this?)

Any insight, suggestions, or advice you can offer that will help get me going in the right direction will be greatly appreciated.

[filiph]

That's a really good application of GA, in my opinion. It's not clear to me whether all events should be periodical, and whether the period can be assumed to be constant no matter what (e.g. what if the third instance of Event A falls on a Sunday, or a public holiday?), and whether there is some hiatus (like summer vacation).

If the events are really strictly periodical, then you can track just an offset and a period, per recurring event.

But I don't think that's a valid assumption in most cases (especially if your events involve people). So I'm going to assume these events are only somewhat periodical. I'm not going to assume anything about the days available for scheduling (Mon-Sun, Jan 1 to Dec 31 is all valid). In that case, here's what I would start with in regards to encoding into a chromosome:

• Let's say you have n recurring events: E1, E2, ... En
• Every recurring event Ex has its own frequency, freq(Ex). This is the number of times this event should ideally happen during the year. Let's call these instances ExIy, where y is 1, 2, ... freq(Ex). For example E2I3 is the third instance of the second recurring event.
• The genotype is a string of integers.
• Each recurring event Ex takes freq(Ex) genes. Each instance ExIy has its own integer.
• Each gene is in the range 1..365.

Example. You have 2 recurring events, E1 and E2. E1 should only happen once, E2 should happen twice during the year.

A chromosome could look something like this is:

[   1,  365,    2]
  E1I1  E2I1  E2I2

This chromosome translates to:

• One event of E1 on January 1st (gene #1).
• First event of E2 on January 2nd (gene #3).
• Second event of E2 on December 31st (gene #2).

When decoding the genotype, the order of instances of each recurring event is normalized. In the example above, E2I2 comes before E2I1, and that's okay. If it wasn't okay, a lot of chromosomes would be invalid (you'd basically be asking the genetic algorithm to not only schedule the events, but also sort them, which is a bad idea — not that GA can't do it, but it would take a lot more time).

One last note: if you can't predict the exact number of freq(Ex), then you might want to assign more genes per recurring event, allow genes to go up to, say, 400, and treat genes with values between 366 and 400 as "not happening". This is what I do for breaks in my algorithm (because I don't know in advance how many breaks will be needed).

[SmithsonianDSP]

Awesome, this is extremely helpful!

Your suggestion is quite close to what I was initially leaning towards (before I started second guessing myself), which makes me feel a lot better about my overall approach to this.

But your comment about the sequence/ordering of the events in the chromosome not really mattering wasn't something I had actually considered, and it should help save me some head-scratching by anticipating that aspect and taking it into account from the start.

I really appreciate you taking the time to give me your input on this—and for writing the article that introduced me to the idea of genetics algorithms and inspired this project, in the first place! This has been a really big help!