Evolutionary Synthesis of Cellular Automata

Jernej Zupanc, Bogdan Filipič

Abstract


Synthesis of cellular automata is an important area of modeling and describing complex systems. Large amounts of combinations and candidate solutions render the usage of deterministic approaches impractical and thus nondeterministic optimization methods have to be employed. Two of the typical evolutionary approaches to synthesizing cellular automata are the evolution of a single automaton and a genetic algorithm that evolves a population of automata. The first approach, with addition of some heuristics, is known as the cellular programming algorithm. In this paper we address the second approach and develop a genetic algorithm that evolves a population of cellular automata. We test both approaches on the density classification task, which is one of the most widely studied computational problems in the context of evolving cellular automata. Comparison of the synthesized cellular automata demonstrates unexpected similarity of the evolved rules and comparable classification accuracy performance of both approaches.

Keywords


cellular automata, cellular programming algorithm, density classification task, evolutionary computing, genetic algorithm

Full Text:

PDF


DOI: https://doi.org/10.2498/cit.1001419

Creative Commons License
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.

Crossref Similarity Check logo

Crossref logologo_doaj