Convergence to Uniformity in a Cellular Automaton via Local Coevolution

Moshe Sipper () and Marco Tomassini ()
Additional contact information
Moshe Sipper: Logic Systems Laboratory, Swiss Federal Institute of Technology, CH-1015 Lausanne, Switzerland
Marco Tomassini: Logic Systems Laboratory, Swiss Federal Institute of Technology, and Institute of Computer Science, University of Lausanne, Switzerland

International Journal of Modern Physics C (IJMPC), 1997, vol. 08, issue 05, 1013-1024

Abstract: Cellular programming is a coevolutionary algorithm by which parallel cellular systems evolve to solve computational tasks. The evolving system is a massively parallel, locally interconnected grid of cells, where each cell operates according to a local interaction rule. If this rule is identical for all cells, the system is referred to asuniform, otherwise, it isnon-uniform. This paper describes an experiment that addresses the following question: Employing a local coevolutionary process to solve a hard problem, known as density classification, can an optimaluniformsolution be found? Since our approach involves the evolution of non-uniform CAs, where cellular rules are initially assigned at random, such convergence to uniformity cannot bea prioriexpected to easily emerge. The question is of both theoretical and practical interest. As for the latter, one major advantage of local evolutionary processes is their amenability to parallel implementation, using commercially available parallel machines or specialized hardware. Our experiment shows that when such local evolution is applied to the density problem, the optimal solution can be found.

Keywords: Non-uniform Cellular Automata; Cellular Programming; Evolutionary Computation (search for similar items in EconPapers)
Date: 1997
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183197000898
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:08:y:1997:i:05:n:s0129183197000898

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183197000898

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().