Monday, 16 July 2012

Creating Harmony

Last week I did some work on a new project, which came about from a conversation in the staff room. At school, we have a system where pupils stay with the same group of peers for three years. In years 7,8 and 9, the form doesn't change (although the form tutor does).

When they reach year 10, we muddle the forms up and re-assign pupils. Not sure why, we just do. Maybe it's because we change from five forms to six, so we need to redistribute the pupils. However, because we're nice, we don't just assign people to form randomly. We allow them to influence the procedure. Having said that, it might be fun to do it by drawing coloured balls from a big sack. Or maybe we could let a magic hat decide.

Anyway, pupils get to choose up to four people who they would like to be placed with. They also get to choose one person who they would rather NOT be placed with. The challenge is to place 100+ pupils into 6 forms, keeping the most people happy and making sure everyone has at least one preferred classmate.
It takes a teacher about 4 hours to do this job. It's a bit like filling in a sudoku. Just when you have one thing right, you realise that you have created a new problem. Sounds like a job for a computer!

I decided to see if a computer could do it more quickly. As with all computing tasks, the first part is to think about some general rules. I decided on the following:

We would measure how successful an arrangement is by giving it a score. If a person is in the same class as their chosen pupils, the arrangement scores one point per match. If they are in the same class as someone they have chosen to avoid, the arrangement loses two points. Using this scoring system, we can measure any given arrangement and compare it to see if it is better than a different arrangement. We can also grade it against the "perfect" score, which is where every person has everyone they requested. At this stage, I had no idea how easy it would be to find this perfect score, or if it is even possible.

I then started thinking about how to go about testing different arrangements. Computers are fast, so it might be possible to do a "brute force" method and test every possible combination. However, the numbers get very big very quickly. The first person has a choice of 6 forms, so does the next, and the next, leading to a possible 6^100 combinations. This is not feasible to compute in a reasonable time.
So a completely dumb loop through every combination would take too long. I needed a smarter method of testing candidate arrangements. I decided on the following algorithm:

  1. Take a random pupil.
  2. Look at each form and test to see how "harmonious" it would be with the new pupil (scored as previously described). If there's an obvious best choice, put them in there so long as it is not full (each form has a maximum number of pupils).
  3. If there is more than one best choice, or the best choice is full, choose again based on class size. Put them in the smallest form.
  4. Take another random pupil and repeat until all the pupils have been assigned.
  5. Once all pupils have a form, assess the "harmony score" of the whole year group.
  6. If it's better than any arrangement we have seen so far, keep a record of the form arrangements.
  7. Wipe all the forms and repeat until we have either found a perfect arrangement or we give up

After I programmed it, I set it loose on the real data from last year's options. I entered all the names and the options for the actual Year 9 group and started off running the program for 1,000 attempts. On each attempt, it picked pupils at random, so there was an equally good chance of hitting a workable combination at any time. It didn't find a perfect arrangement, though. It couldn't even find an arrangement where everyone had at least one preferred classmate. I tried it again for 10,000 loops with no luck. I even set it going for 100,000 loops, and it couldn't find a perfect outcome. It was close, though. In just a few minutes, the program had managed to find a solution where all but three pupils were happy, and many of them were very happy indeed because they had all their preferred classmates. I worked out that a human could look at the solution and do some manual shuffling so that the last 3 people were happy. At the least, it would shave a significant amount of time off the 4 hours the job had previously taken.

Then I ran the program again, and it found a great solution almost straight away. And the next time, it did it again! Because it's picking randomly, it could find a solution quickly, or it could take a while. I'm sure there's a more efficient way of doing the job, but for the moment it looks like the program can definitely make a contribution here. It just needs tidying up and a decent interface so that pupils can enter their preference directly. I've even thought of a name: Harmoniza.

No comments:

Post a Comment