Advances in the Evolution of Complex Cellular Automata
In this study we present some advanced experiments dealing with the evolutionary design of multi-state uniform cellular automata. The generic square calculation problem in one-dimensional automata will be treated as one of the case studies. An analysis of
- PDF / 2,138,856 Bytes
- 24 Pages / 439.37 x 666.142 pts Page_size
- 79 Downloads / 171 Views
Abstract In this study we present some advanced experiments dealing with the evolutionary design of multi-state uniform cellular automata. The generic square calculation problem in one-dimensional automata will be treated as one of the case studies. An analysis of the evolutionary experiments will be proposed and properties of the resulting cellular automata will be discussed. It will be demonstrated that various approaches to the square calculations in cellular automata exist, some of which substantially overcome the known solution. The second case study deals with a non-trivial pattern development problem in two-dimensional automata. Some of the results will be presented which indicate that an exact behaviour can be automatically designed even for cellular automata working with more than ten cell states. A discussion for both case studies is included and potential areas of further research are highlighted. Keywords Evolutionary algorithm · Cellular automaton · Transition function · Conditional rule · Square calculation · Pattern development
1 Introduction The concept of cellular automata was introduced by von Neumann in [25]. One of the aspects widely studied in his work was the problem of (universal) computational machines and the question about their ability to make copies of themselves (i.e. to self-reproduce). Von Neumann proposed a model with 29 cell states to perform this task. Later Codd proposed another approach and showed that the problem of computation and construction can be performed by means of a simplified model working with 8 states only [7]. M. Bidlo (B) Faculty of Information Technology, IT4Innovations Centre of Excellence, Brno University of Technology, Božetˇechova 2, 61266 Brno, Czech Republic e-mail: [email protected] URL: http://www.fit.vutbr.cz/~bidlom © Springer Nature Switzerland AG 2019 J. J. Merelo et al. (eds.), Computational Intelligence, Studies in Computational Intelligence 792, https://doi.org/10.1007/978-3-319-99283-9_7
123
124
M. Bidlo
Several other researchers studied cellular automata usually by means of various rigorous techniques. For instance, Sipper studied computational properties of binary cellular automata (i.e. those working with 2 cell states only) and proposed a concept of universal computing platform using a two-dimensional (2D) CA with non-uniform transition function (i.e. each cell can, in general, be controlled by a different set of transition rules) [20]. Sipper showed that, by introducing the non-uniform concept to the binary CAs, universal computation can be realised, which was not possible using the Codd’s model. In fact, Sipper’s work significantly reduced the complexity of the CA in comparison with the models published earlier. Nevertheless even the binary uniform 2D CAs can be computationally universal if 9-cell neighbourhood is considered. Such CA was implemented using the famous rules of the Game of Life [2] (original proof of the concept was published in 1982 and several times revisited – e.g. see [8, 11, 16, 17]). Although binary CAs may be adva
Data Loading...
