Being the god of kitchen plans

I once took a very interesting postgrad course in genetic algorithms (taught by Zbigniew Michalewicz), and since then it’s been a technique I occasionally pull out of my sleeve.

For a number of years I’ve been producing kitchen plans telling all members of the family when they’ve got to cook, set the table, fill the dishwasher and tidy up the kitchen. In my experience, it’s very hard to get kids to do anything if you try to convince them on the day that’s it’s their turn, but if you put up a plan on the fridge, they’ll moan once the day you put it up and will then get on with it.

However, in a family as big as ours, making such a plan is a very difficult problem. For instance, I can’t cook on Mondays, nobody should do anything on their birthday, Marcel is only here during holidays, and nobody should do two things on the same day or the same task two days in a row, etc., etc. To make it even worse, if anybody has skipped a task the month before (or done too much), the new plan should take it into account.

For a long time, I’ve been using an old-fashioned program to generate these plans, and its complexity has grown and grown with time. At the same time, the quality has decreased because it was simply getting too hard for the computer to satisfy all the competing requirements.

I therefore decided to employ genetic algorithms.

I created a world consisting of 27 islands, each with a population of kitchen plans (initially they were all random, but consisting of the right number of tasks for each person). I then let them live their rich and satisfying lives, having sex, producing offspring (sometimes with random mutations), and as a good Darwinist I ensured only the fittest individuals survived to have kids. After 200 generations, I took the fittest plan from each island, put them all on a new island of champions and let them evolve for another 1000 generations. I then took the fittest plan of all time, put it on our fridge, and extinguished the world. Basically I was the God of kitchen plans for ten minutes.

The result is so much better than the old plans, but then this type of problem really lends itself to the genetic approach: It’s very easy to assign a fitness value to a plan (-5 points if I cook on a Monday, -2 points for a repeated task, etc.) — in fact it’s much easier than actually producing a plan — and it’s also easy to figure out how to breed plans (e.g., take all the cooking tasks from one plan and combine it with the other tasks from another one).

That’s basically the basis for successful evolution: If it’s hard to calculate the right answer, but you can rank individuals by fitness and figure out how to let the fit ones have sex, then your solution will evolve over time, and as a bonus, you will be a god for a little while.