Evolutionary Search for Cellular Automata that Exhibit Self-Organizing Properties Induced by External Perturbations

Abstract — Cellular Automata (CAs) have been investigated extensively as abstract models of the distributed systems composed of autonomous entities characterized by local interaction. However, how CAs can interact with their external environment still needs discussion. This paper aims at understanding emergent properties of CAs induced by external perturbations. We assumed a task in which a CA has to change its global state distinguished by the distribution ratio of cell states after every occurrence of a perturbation period. In the perturbation period, each cell state is modified by using an external rule with a small probability. By conducting evolutionary searches for rules of CAs that can solve this task, we obtained interesting behaviors of CAs in which their global state cyclically transited among different stable states in either ascending or descending order. Detailed analyses showed that such behaviors are due to their self-organizing properties that a drastic change in their global state occurs every when the number of the subsequent dominant cell state goes beyond a certain threshold through occurrences of perturbation periods. I