I’ve written before about using genetic algorithms to solve problems, but I wanted to show how flexible they can be by writing here about how they helped me this week. My problem was that I wanted to assign standards to students for our oral exam week coming up after spring break (next week). I want each student to do three different standards throughout the week. However, I want to make sure of each of the following:
- No student should do the same standard twice
- On any given day, there should be a minimum of repeat standards
- No two students should have the same set of standards (even in a different order)
At first I thought I could just randomize the student names and then count out the standards in order. It takes care of the first two bullet points, but it turns out that the third one kept happening. So, on to using a genetic algorithm to do this.
Here’s what I did:
- Put together a population of possibilities
- each one of these randomly assigns three standards to each student
- Note that the three bullet points above are not at all considered (in fact, usually all three are violated with each of these random starters)
- rank each candidate according to the three bullet points above
- For example, if a student has a repeat, that’s a penalty. If they have all the same standard all three times, that’s a double penalty
- Using a weighted selection scheme, choose a parent and then mutate it to make a new candidate for the next generation
- The weights are the penalties (lower are selected more often, though)
- A mutation consists of randomly changing one or more of the student/standard assignments
- The mutation rate goes down throughout the run (this I borrowed from Simulated Annealing)
- Repeat 2-4 until you have a solution you like
After about 100 iterations it settles into something that meets all the requirements.
The flexibility I was mentioning above comes in when I realize that I want to make some other subtle changes. I realized that I want to add these conditions:
- Minimize the number of standards that students repeat throughout the semester (we have 9 oral exams all together)
- Maximize the spread of the standards for each student
- I simply do Max(list) – Min(list) to get that
- In an earlier “solution” I noticed that one student was assigned numbers 1, 2, and 3 and I didn’t want them to spend the week working on just one section of our material
Instituting those changes was simple, just change the cost function to include them and then re-run the simulation.
At the end of the day it all works quite well. I get a distribution of the standards into my students hands (so they can prepare over spring break) and I know that all my bullet points are met.
So what do you think? Here are some Rhett-Allain(TM) starters for you:
- I’m in this class and I’m really glad you’ve worked this out. I was super nervous that a fellow student might have the same standards as me and this fixes that.
- I’m in this class and I’d much rather just pick my own standards, focussing on the ones I’ve done poorly on.
- Why do you put “solution” in quotes?
- How much do you pay Rhett when you use these starters?
- Why do you have the mutation rate change? Why not have it evolve?
- If you change the weights of each category, do you get drastically different results? (yes, though not if I let it run a really long time)
- Can you post the code you use for this?
- I’ve got a similar problem, how would you code it?
- Wait, this is the Friday before your break? Why are you posting to your blog? Get a life!