Evolving Compositional Pattern Producing Networks For Cellular Automata Transition Rules

Abstract

Traditional Cellular Automata (CA) transition rules are encoded as tables that grow quickly when the number of cell states or the size of the CA neighborhood increases. For methods that search for good transition rules, such as genetic algorithms, the space of possible encodings also grows rapidly with both parameters. This thesis investigates replacing the traditional encoding with Compositional Pattern Producing Networks (CPPNs), a Neural Network-like structure. The search for good CPPN-based transition encodings is performed with the NeuroEvolution of Augmenting Topologies (NEAT) genetic algorithm.

A software framework is implemented and CA problem solving experiments are performed. The problems investigated include both morphology problems and computational problems. The results found are diverse, with some problems solved easily, some with moderate difficulty and some not at all.

In another experiment, the new CA framework is also modified to extend the cellular model with environmental information. The model lends itself very easily to extension, and the result is that previously difficult tasks become solvable.

In addition to the task-solving experiments, another experiment is performed to investigate the relationships between the mechanisms of the NEAT algorithm and the properties of the CPPN encoding and the CA model. The results from this experiment can inform decisions about parameters in future experiments.

A variation of the NEAT algorithm called novelty search is also implemented. While it is not able to produce any more interesting results than the objective NEAT search is, it does lead to some insights about the algorithm that could lead to success in the future. The results of the experiments indicate that the new combination of encoding and algorithm has merit. In addition to the CA model, the algorithm and encoding may also have applications in other morphogenetic engineering situations.