Neighborhood detection and rule selection from cellular automata patterns

Abstract

Using genetic algorithms (GAs) to search for cellular automation (CA) rules from spatio-temporal patterns produced in CA evolution is usually complicated and time-consuming when both, the neighborhood structure and the local rule are searched simultaneously. The complexity of this problem motivates the development of a new search which separates the neighborhood detection from the GA search. In the paper, the neighborhood is determined by independently selecting terms from a large term set on the basis of the contribution each term makes to the next state of the cell to be updated. The GA search is then started with a considerably smaller set of candidate rules pre-defined by the detected neighhorhood. This approach is tested over a large set of one-dimensional (1-D) and two-dimensional (2-D) CA rules. Simulation results illustrate the efficiency of the new algorithm.