Evolution of Cellular Automata using Lindenmayer Systems and Fourier Transforms

Abstract

Cellular automata (CAs) are a class of highly parallel computing systems consisting of many simple computing elements called cells. The cells can only communicate with neighboring cells, meaning there is no global communication in the system. Programming such a system to solve complex problems can be a daunting task, and indirect methods are often applied to make it easier. In this thesis we use evolutionary algorithms (EAs) to evolve CAs. We also look at the possibility of employing L-systems to develop complex CAs while maintaining a relatively small genome. Input and output are handled by streaming them through the edge cells, and we look at the use of a discrete Fourier transform (DFT) as a way to interpret the output. Experiments show that it is possible to evolve uniform and semi-uniform CAs that solve various problems. On harder problems semi-uniform CAs outperform uniform CAs, and using an L-system further improves the performance. However, on simpler problems the extra complexity of semi-uniform CAs seem to only hinder evolution. The experiments also show that interpreting the output with a DFT works well, and outperforms a more direct approach.