Article Preview
TopIntroduction
A complex system is a system composed of many independent components that are locally interacting and which allow describing it at different levels. In last decades, complex systems have been widely studied in order to understand how collective computations are produced by local interactions between their components without any central control mechanism, such as ant colonies, the human brain, immune systems and flying birds’ flocks.
On the other hand, Cellular Automata (CAs for short) are artificial systems that have been adopted to model complex systems and analyze their behaviors. Within CAs, cells are arranged in a lattice that forms a configuration by assigning states to cells. Configurations are evolved following some local transition rules to perform computations using only local communication between cells. Also, they have been successfully used in further fields among others: modeling physical systems (Hoekstra, Kroc, & Sloot, 2010), studying dynamical systems (Hoekstra, Kroc, & Sloot, 2010), designing some decentralized architecture systems (Alba & Tomassini, 2002; Tayarani-N & Akbarzadeh-T, 2008).
As reported in (Wolz & De Oliveira, 2008), studying emergent computations within CAs was mainly done on two well-known tasks: the firing squad synchronization problem and the density classification task (DCT for short). Subsequently, there were some attempts to use other benchmark problems, such as the parity and the synchronization problems (De Oliveira, Bortot, & Oliveira, 2006; Oliveira, Martins, De Carvalho & Fynn, 2009). For all these tasks, the effectiveness of the computation is granted by reaching some predefined global configurations, after sufficiently long time. Thus, emergent computations could appear through information transmission across time and space. Obviously, such tasks are non-trivial for CAs since each cell has a local view about the global state of the lattice, unlike centralized systems. That is why it is believed that deeply studying the DCT and similar benchmark problems is important for building fully decentralized artificial systems where computations result only from local communication between their components by taking into account the space limitations.
In fact, due to their decentralized architecture and their nonlinear characteristics, manual design of CA rules to produce a specific behavior or to perform a particular computation is usually considered as a difficult task. Therefore, many recent researches have been turned out to the automatic design, often through training mechanisms. Generally, these works focus on exploring CA rules spaces by evolutionary algorithms (EAs) to find the suitable rules for computational tasks (Packard, 1988; Mitchell, Hraber, & Crutchfield, 1993; Mitchell, Crutchfield, & Hraber, 1994; Wolz & De Oliveira, 2008; Márques, Manurung, & Pain, 2006).
Commonly, in works that deal with the automatic training of CAs, searching for one-dimensional binary CA rules of neighborhood radius r=3 which are applied on initial configurations (ICs) of size N=149 (i.e. to simulate infinite configurations), was turned out to become the standard benchmark settings for measuring the abilities of the different training mechanisms (De Oliveira, 2013). Moreover, the DCT remains to this date the most used benchmark problem in such works.