Using Dynamic Behavior Prediction to Guide an Evolutionary Search for Designing Two-Dimensional Cellular Automata

The investigations carried out about the relationships between the generic dynamic behavior of cellular automata (CA) and their computational abilities have established a very active research area. Evolutionary methods have been used to look for CA with predefined computational abilities; one in particular that has been widely studied is the ability to solve the density classification task (DCT). The majority of these studies are focused on the one-dimensional CA. It has recently been shown that the use of a heuristic guided by parameters that estimate the dynamic behavior of 1D CA can improve the evolutionary search for DCT. The present work shows the application of three parameters previously published in the one-dimensional context generalized to the two-dimensional space: sensitivity, neighborhood dominance and activity propagation were used to evolve CA able to perform the two-dimensional version of the density classification task. The results obtained show that the parameters can effectively help a genetic algorithm in searching for 2D CA. A new rule was found which performed better than others previously published for the 2D DCT.