The Phylogenetic Comparative Method and Evolving Cellular Automata

10 Apr 2009 17:40

Once upon a time, I was a minor contributor to the Evolving Cellular Automata project at the Santa Fe Institute. The goal of the project was to study how evolutionary search methods (specifically, genetic algorithms) could discover ways to get distributed, decentralized computers (specifically, cellular automata) to approximately solve problems which are easy with centralized processors but hard or even impossible to do exactly without them. The hope was that this would shed some light on how natural distributed information processing gets done.

A typical problem was "density classification": given a string of bits, decide whether it contains more 0s than 1s or vice versa. The fitness of a rule was just what fraction of (randomly generated) configurations it classified correctly. Run with large populations for a long time, you ended up with the gene pool being dominated by rules which did, in fact, do a pretty good job, even though, demonstrably, no conceivable rule of this sort could work perfectly. The successful rules tended to have certain features in common, namely they tended to produce propagating coherent structures ("particles") whose interactions look a lot like logical circuits. (See, e.g., here for some details, and other EvCA papers for much, much more.) A very convincing story can be told about how these particles and their interactions are actually what let these rules be as successful as they are.

One question I was interested in at the time, but never followed up, was whether one could provide some kind of quantitative, statistical support for this assertion, in addition to the more "physical" reasoning. A natural idea would be to do something like a regression of rule fitness on the "phenotypic" features of the kinds of particles produced, aspects of their interactions, etc. A problem, though, is that the rules are not independent samples, but related through common descent, and so some phenotypes might be associated with high fitness due to founder effects, etc. Teasing apart adaptive effects from common descent is what the phylogenetic comparative method is supposed to let us do. So: somebody should apply the comparative method to EvCA data. It won't be me, but I'd be very interested in hearing about the results of this.