The best currently known class of dynamically equivalent cellular automata rules for density classification

The possibility of performing computations with cellular automata (CAs) opens up new conceptual issues in emergent computation. Driven by this motivation, a recurring problem in this context is the automatic search for good one-dimensional, binary CA rules that can perform well in the density classification task (DCT), that is, the ability to discover which cell state outnumbers the other state. In the past, the most successful attempts to reach this target have relied on evolutionary searches in the space of possible rules. Along this line, a multiobjective, heuristic evolutionary approach, implemented as a distributed cooperative system, is presented here, which yielded outstanding results, including a rule that led to the characterisation of a class of four equivalent rules, all of them with the best performance currently available in the literature for the DCT. (c) 2006 Elsevier B.V. All rights reserved.