Lunch Assignment Problem

Last week someone I work with was assigned the task of setting up lunch groups for the interns in my program. This is something we do every week to meet new people, and it is intended that people eat with new and different people every week if possible. It should be clear that there may not be a solution after several weeks, but we can still find a solution with as small as possible a number of "collisions" (people eating together that have been assigned the same lunch group together in a previous week). Perhaps you can already see where I'm going with this?

This problem involves partitioning a set of people into n disjoint subsets with the minimal number of collisions. If each person is taken to be a node in an simple undirected graph then there is an edge between two people iff (if and only if) they have had lunch together before, and the edges can be weighted such that the weight is the number of times they have had lunch together. Alternatively each pair of people have a weight, which is simply 0 if they have never been in the same group. This provides a measure of the correctness of a solution, and therefore can be used as a fitness in an evolutionary algorithm!
I wrote a simple Random Mutation Hill Climber (RMHC) which we have been using the last two weeks to come up with our lunch assignments, and so far it has found perfect solutions. A RMHC simply mutates a randomly generated solution, and replaces the current solution with the mutated solution if the new one is better or equal to the previous one according to the fitness measure. The initial solution is generated by shuffling the list of people randomly and cutting the list into sublists of a fixed length. After that mutations occur by choosing two people and swapping the groups they are in.

I also tried a Genetic Algorithm for this problem, but it takes longer to run and seems to perform worse. Interestingly, next week it looks like the problem has gotten much harder in the sense that I doubt there is going to be a perfect solution. For this new instance of the problem the GA actually seems to work better! This is probably because the solution space has gotten much more complex and the RMHC, being merely a hill climber, has trouble exploring it even when run many times (so that many possible hills are climbed).

So! Evolutionary Algorithms tackling a very simple, real-life-style problem! Despite being a simple problem (simple to describe) the set of possible solutions is huge. It is infeasible to enumerate the solutions, and it doesn't seem to have an efficient deterministic solution, so it is the sort of problem that AI is often used to tackle. If anyone can classify this problem exactly I would be interested to hear about it- it doesn't remind me of anything off hand.