Discrete Tranformation of Output in Cellular Automata

Abstract

Cellular automata (CA) is an example of cellular computing: large numbers of simple components, no central control, and limited communication among components. A CA consists of an array of cells, each in one of a finite number of possible states. The cells are updated synchronously in discrete time steps, according to a local, identical interaction rule. CA have been studied for years due to their architectural simplicity and the wide spectrum of behaviors. It can be difficult to design CA to exhibit a specific behavior, and there is no programming paradigm for implementing parallel computations in CA. This makes CA a prime candidate for adaptive programming methods such as evolutionary algorithms (EA). EA have been successfully used to evolve CA to perform computations, such as the majority problem. In problem solving like this, CA are treated as input-output systems and evolved to visit certain states given certain initial states. The n-th state of a CA is commonly treated as its output, such that one input gives one output.In this report a way to transform the output of CA such that multiple outputs emerge is investigated. The evolution of transformed CA is also investigated. Useful applications of this include controlling multi-variable systems such as a pole balancing system.The transformation process was tested in the elementary and 3-state rule spaces. Evolution of transformed CA was successful in the elementary rule space. This suggests there is a correlation between rules of CA and their transformed output. The evolution of transformed CA was unsuccessful in the 3-state rule space. This suggests the chosen evolutionary algorithm doesn't scale with the size of the rule space.