A new paradigm for evolving cellular automata rules

In cases where the cellular automata (CA) is a direct mapping of a physical, biological or social process, the transition rules may be intuitive. The converse problem of going from observed global behaviour to transition rules is largely intractable. For this reason heuristic search methods, notably evolutionary computation, have been used to deduce rules. In general the rule space to search is vast and evolutionary techniques have been only weakly successful. In earlier work we have shown show that by invoking the structure of rule space, it is possible to dramatically reduce the search space size and thus improve search speed and accuracy. We conjecture that restricting the search space is a more powerful strategy than increasing the algorithm complexity by techniques such as coevolution. We extend the formalism to cover rules of greater complexity and power. The density classification problem for one-dimensional two-state cellular automata has long been of interest to researchers in evolutionary computation. The approach described generates high quality rules and has the potential to achieve the best possible results for this problem