Stabilize This!

Matt brought up some good points in his post; we should be only posting about interesting and unique things. I look forward to his future posts, even if less regular.

This past week I have started a small project, inspired by a talk given by Alan Jamieson of St. Mary's College of Maryland on self-stabilizing algorithms for graphs. Hopefully he will post an abstract of his talk soon, since I'm sure that it will explain the subject much better than I am about to.

One of the most simple example is the toddlers and cookies example: each node of the graph can either be a plate of cookies or a toddler. For a toddler to be happy, it must be next to at least on plate of cookies (connected by a vertex). Giving a random graph with a random configuration of cookies and toddlers, write a set of rules that will place toddlers and cookies in such a way that all toddlers are happy (and thus stop their incessant crying).

The rules are as simple as "if a toddler is not next to any cookies, replace that toddler with cookies." The rules may become more complicated if you would like to find a set of rules that always result in happy toddlers with the least amount of cookies. The important part is that the rules are all simple "if...then" statements.

It occurred to me that one could easily generate these rules and then a bunch of graphs to test them out on. It would then be a simple matter to find the best set of rules. For a simple example like toddlers and cookies, one could just test every possible combination of rules. For a more complicated problem this might be unfeasible as the possibilities grow quickly.

At this point, I would like to see if a genetic programming approach could lead to usable results. All the elements are there: easy to generate and modify programs (the rules) that are easy to evaluate (number of moves, is the final graph correct).

So that's what I'm doing now. This post is quite long enough as it is, so I'll save my progress so far for another night.