Original scientific paper

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

Evolutionary Synthesis of Cellular Automata

Jernej Zupanc ; University of Ljubljana, Slovenia
Bogdan Filipič ; Jozef Stefan Institute, Slovenia

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

Hrčak ID:

71045

URI

https://hrcak.srce.hr/71045

Publication date:

30.6.2011.

Visits: 1.910 *