Cell state change dynamics in cellular automata

Cellular automata are discrete dynamical systems having the ability to generate highly complex behaviour starting from a simple initial configuration and set of update rules. The discovery of rules exhibiting a high degree of global self-organization is of major importance in the study and understanding of complex systems. This task is not easily achieved since coordinated global information processing must rise from the interactions of simple components with local information and communication. In this paper, a fast supporting heuristic of linear complexity is proposed to encourage the development of rules characterized by increased dynamics with regard to cell state changes. This heuristic is integrated in an evolutionary approach to the density classification task. Computational experiments emphasize the ability of the proposed approach to facilitate an efficient exploration of the search space leading to the discovery of complex rules situated beyond the simple block-expanding rules.