From: Howard Andrew GUTOWITZ (gutowitz@amoco.saclay.cea.fr)
Date: Fri Mar 26 1993 - 19:15:44 UTC
This is in partial response to Eric Seigel's suggestion to use some symmetry properties of CA rules along with the genetic algorithm to produce better parameters than lambda for exploring CA rulespace in particular to find "interesting" rules. Actually, the symmetry part of this program has been worked out in some detail in my article, "A Hierarchical Classification of CA" in Physica D 45. This paper shows that lambda is at the base of a hierarchy of parameters. As one ascends in hierarchy more and more of the symmetry (in terms of permutations of blocks of sites) is taken into account. For example, in the case of two-state automata, the lambda parameter (0th-order theory) says that all rules which have the same number of transitions to 1 are the same. They are the same in the sense that one can take a rule with a given value of lambda, permute all of the neighborhoods in the rule table, and get another rule with the same value of lambda. In the next order of theory, the mean field theory or 1st-order theory, there are a collection of parameters. One can take a rule and permute all the neighborhoods which have the same number of "1's" in them and get a new rule with the same mean-field parameters. This goes on. You can define a 2nd-order theory with more restrictions on the permutations allowed and so on. At each increase in level, you get more and more control over the properties of the rules which have given values for the parameters. There is no real need to use the genetic algorithm. The properties of the rules depend smoothly on the parameters. Any sort of hill-climbing algorithm will work to adjust the parameters, say Newton's method. The genetic algorithm may still have a use when the number of parameters grows too large to handle by these methods. A good number of people (Langton, Wootters, Chate-Manneville, to name but a few) have used mean field theory for various purposes, but a handfull (McIntosh, Eisele, Grassberger, Li (again a sample)) have gone beyond. There is a lot of work which remains to be done. I did some preliminary exploration on the Packard-Mitchell-Hraber-Crutchfield problem about 6 years ago, and found that I could get rules that had jumps in density not only at 0.5, but just about anywhere I chose using only mean field theory and some hunting and pecking. Nothing remains of those results, but any interested person could recreate them. If you cannot find the above mentioned article in the library, email and I will send you a copy. --H. Gutowitz
This archive was generated by hypermail 2.1.7 : Tue Oct 14 2003 - 21:44:11 UTC