Using a Genetic Algorithm to Do Consultant Scheduling in C#

TO be more technically accurate, this is not a genetic algorithm, however, a genetic algorithm could easily be substituted in this article with the same fitness function. This is a learning algorithm, so the title should have probably been "Using a Learning Algorithm to Balance a Consultant Schedule"

It takes a while for the next generation to come up, and depending upon your CPU speed it could be a while, but eventually the densities should change. Best, -Mike

I have the arduous task of writing a scheduling program. It has been over 10 years since I last worked on project involving a GA. Do you have any thoughts as to how I might get back to where I need to be for this project? I noticed that you posted your comments in the last few days.

I don't claim to be an expert, I just observed different behavior than that presented in the article. It seems to me the two most important factors of a Genetic Algorithm are 1) Sharing of "genomic" data between elements in the population, and 2) Random variation/mutation for bumping your results out of local min/maxs, 3) An appropriate fitness function #1 above is addressed through what are called "crossover events" - 2 members of the population swap out only parts of their solution. For a schedule this might mean 2 people trading assignments for the day. For better results, you can enforce a meaningful cross over - which is to say you dont allow 2 people with the day off to "switch", because this is meaningless. #2 lets you get your solutions out of local min/max solutions. You might converged on a solution that is decent, but not the best available. However, without introducing random mutations into your data set, your population will quickly converge to a highly similar population, at which point cross-over events between these members accomplish very little, because they are so similar #3 is perhaps the most difficult part of the problem. Generally speaking, you convert the "fitness" of a member of the population to an easily evaluated integer or float value. 0-1. 0-infinity (int32.max). You then specify whether your ideal solution is close or near that ideal value of 0, or of 1. For the schedule in the above article, you might for example specify that your fitness of a single member of the population is RMSD (root mean square deviation) from the average $ made by a consultant over the 60 days. Therefore, the closer the RMSD is to 0, the more similar the wage is earned by each consultant. It is important to note that what you define as a "population" and a member in that population is entirely up to you. The above article is a bit tricky, because you might be inclined to think that each consultant is a member of the population defined as all consultants. But that would be incorrect. You have to think of a member of your population as a complete solution to your problem. In that case, a member is actually all 30 consultants and their entire schedules. And the population is the set of different solutions, not different consultants. There are a handful of attempts at "generic" genetic algorithm libraries out there. The difficulty of a generic GA is that you can often get *much* better results by customizing your approach as it pertains to your specific problem. For example, a generic GA might require you to encode your "genome" (your solution, which is evaluated for fitness) into bits. Staight up 0 or 1s. And then their cross over events and mutation events will operate purely on this bit level, without paying attention to higher order details of the problem. This can lead to problems though, for many domain spaces. For example, in this article randomly flipping a bit would might assign a consultant to a job that is already being attended by another consultant. Or assigning them to two jobs on the same day. And you end up with invalid solutions. One might argue that this is because of a bad encoding - that there is a way to encode the problem into bits that allows for truly random operation while maintaining semantically correct solutions. But I find that in some cases, it makes more sense to have a more semantic description of your genome, which might mean using a higher order construct (such as a struct or a class). The important part comes in how you choose to mutate them and do crossovers. If you maintain higher order constructs in your model, it is easier to obey the rules of those constructs during these events - such as not having 2 jobs on the same day. There are trade offs here. By using higher order constructs, you can get some tunnel vision. One of the neat things about GA's is they might provide a solution you didn't intend. But by using higher order constructs you've limited the way the GA can explore the possible solution space. If you keep things generic, you might get a unique solution, but you lose the benefits of applying sensible heuristics to guide the answer to a result quicker. One last tip - don't hard-code population sizes, mutation rates, or crossover event rates. A very sensible GA implementation will fail if you have have a population size too small. Or it might take eons to step through a generation if it is too large. If your mutation rate is too small you'll easily get stuck in "decent but not great" solutions, but if it is too large you'll have trouble converging or find that your population is losing viable-solutions to fast to become integrated into the population.

How can I solve (using GA) the problem of coloring the nodes of a graph (with less than 100 nodes), any two adiacent nodes having a different color? You're the best! Thank You!