Genetic algorithm for randomizing oral exams

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:

  1. Put together a population of possibilities
    1. each one of these randomly assigns three standards to each student
    2. 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)
  2. rank each candidate according to the three bullet points above
    1. 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
  3. Using a weighted selection scheme, choose a parent and then mutate it to make a new candidate for the next generation
    1. The weights are the penalties (lower are selected more often, though)
    2. A mutation consists of randomly changing one or more of the student/standard assignments
    3. The mutation rate goes down throughout the run (this I borrowed from Simulated Annealing)
  4. 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!
Advertisements

About Andy "SuperFly" Rundquist

Professor of physics at Hamline University in St. Paul, MN
This entry was posted in mathematica, syllabus creation. Bookmark the permalink.

8 Responses to Genetic algorithm for randomizing oral exams

  1. Joss Ives says:

    Andy, can you share your code to one of your genetic algorithms?

  2. jg says:

    How would you deal with inviolable conditions? Something like killing those combinations off, or requiring that the change be to the part that’s not allowed?

    • Andy "SuperFly" Rundquist says:

      There’s 2 ways I could think of: make it a huge cost (like 10000 or something) and there’s no way that it’ll ever converge to that; or don’t allow those children to survive in the first place when creating the next generation.

      • jg says:

        I’m thinking about a scheduling algorithm – scheduling students and periods for fixed sections of courses. Teachers can’t teach two classes at once, kids can’t take two at once, etc. Prob. too many possibilities to be able to implement it, though.

      • Andy "SuperFly" Rundquist says:

        I know some schools do this sort of thing for scheduling finals, which sounds similar. Basically if you can calculate the cost of a particular set of outcomes, then this will work.

        On Fri, Mar 27, 2015 at 8:58 PM, SuperFly Physics wrote:

        >

      • jg says:

        Is there an NP issue, though? It seems like it’ll either require a gigantic initial set or forever. Just scared about the factorial.

      • Andy "SuperFly" Rundquist says:

        that’s the beauty of this approach. You’re supposed to use it when the number of possibilities is too hard to do by brute force. In my case the total number of possibilities is 13^(3×12) which is huge (~10^40).

        On Fri, Mar 27, 2015 at 10:10 PM, SuperFly Physics wrote:

        >

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s