Scalability Property in Solving the Density Classification Task

Scalability Property in Solving the Density Classification Task

Laboudi Zakaria (MISC Laboratory, Constantine2 University, Constantine, Algeria), Chikhi Salim (MISC Laboratory, Constantine2 University, Constantine, Algeria) and Lakhdari Saliha (University of Oum El-Bouaghi, RELA(CS)2 Laboratory, Oum El Bouaghi, Algeria)
Copyright: © 2017 |Pages: 17
DOI: 10.4018/JITR.2017040104


The density classification task (DCT for short) is one of the most studied benchmark problems for analyzing emergent computations performed by cellular automata. Starting from the observation that the performance of the best known solutions is not stable towards initial configurations size; we propose in this paper, some new evolutionary mechanisms for designing new solutions with similar conceptual properties to the best known ones. The approach is based on varying the size of initial configurations which allows making comparisons and analysis between the different solutions. We show then through a set of numerical results that the proposed mechanism allows collecting solutions for the DCT more efficiently and with reduced efforts. Also, we show that the collected solutions are affected by configurations size variations, where only few of them are scalable.
Article Preview


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.

Complete Article List

Search this Journal:
Open Access Articles: Forthcoming
Volume 12: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 11: 4 Issues (2018): 1 Released, 3 Forthcoming
Volume 10: 4 Issues (2017)
Volume 9: 4 Issues (2016)
Volume 8: 4 Issues (2015)
Volume 7: 4 Issues (2014)
Volume 6: 4 Issues (2013)
Volume 5: 4 Issues (2012)
Volume 4: 4 Issues (2011)
Volume 3: 4 Issues (2010)
Volume 2: 4 Issues (2009)
Volume 1: 4 Issues (2008)
View Complete Journal Contents Listing