The Role of Conceptual Structure in Learning Cellular Automata to Perform Collective Computation

Manuel Marques-Pita1,2,3, Melanie Mitchell2 and Luis M. Rocha1,3

1 School of Informatics, Indiana University, 919 East Tenth Street, Bloomington IN 47408, USA
2Portland State University
3FLAD Computational Biology Collaboratorium, Instituto Gulbenkian de Ciencia, Portugal

Citation: M. Marques-Pita, M. Mitchell, and L.M. Rocha [2008]. "The Role of Conceptual Structure in Learning Cellular Automata to Perform Collective Computation". In: Unconventional Computation: 7th International Conference (UC 2008). Lecture Notes in Computer Science. Springer-Verlag, 5204: 146-163. doi: 10.1007/978-3-540-85194-3_13. BibTex

The pre-print is available in Adobe Acrobat (.pdf) format only. Due to mathematical notation and graphics, only the abstract is presented here.


The notion of conceptual structure in CA rules that perform the density classification task (DCT) was introduced by Marques-Pita et al. (2006). Here we investigate the role of process-symmetry in CAs that solve the DCT, in particular the idea of conceptual similarity, which defines a novel search space for CA rules. We report on two new processsymmetric one-dimensional rules for the DCT which have the highest “balanced” performance observed to date on this task, as well as the highest-performing CA known to perform the DCT in two dimensions. Finally, we investigate the more general problem of assessing how different learning strategies (based on evolution and coevolution, with and without spatial distribution), previously compared by Mitchell et al. (2006), are suited to exploit conceptual structure in learning CAs to perform collective computation.

Keywords:Cellular Automata, Emergent Computation, Complex Networks, Artificial Life, Density Classification Task.

For the full paper please download the preprint in pdf

For more information contact Luis Rocha at Check the Web Design Credits, for due credit.
Last Modified: September 9, 2008