Comparison of Evolutionary Development of Cellular Automata Using Various Representations
Abstract
A comparative study is presented regarding the evolutionary design of complex multi-state cellular automata. In particular, two-dimensional cellular automata will be considered in combination with pattern development problem as a~case study. Two techniques for the representation of transition functions for the cellular automata are proposed: a conventional table-based method and an advanced concept utilising conditionally matching rules. It will be shown that using a proper settings of Evolution Strategy, various working solutions can be obtained using both representations. Some observations from an analysis of resulting cellular automata will be presented which indicate that the behavior of the automata is totally different and depends on the representation applied. Specifically, the table representation exhibit a chaotic development during which a target pattern emerges at a moment. On the other hand, the conditional rules are able to achieve behavior that progressively constructs the target pattern which, in addition, represents a stable final state. Moreover, the latter method also exhibits significantly higher success rate which represents one of its advantages and proves an importance of systematic research in this area.References
Bahar, A. N., Waheed, S., and Hossain, N. 2015. A new approach of presenting reversible logic gate in nanoscale. SpringerOpen Journal - Electronics and Electrical Engineering 4. DOI: 10.1186/s40064-015-0928-4
Balijepalli, H. and Niamat, M. 2012. Design of a nanoscale quantum-dot cellular automata congurable logic block for fpgas. In 2012 IEEE 55th International Midwest Symposium on Circuits and Systems (MWSCAS). IEEE, pp. 622-625.
Bandini, S., Bonomi, A., and Vizzari, G. 2012. An analysis of different types and effects of asynchronicity in cellular automata update schemes. Natural Computing 11, 2, pp. 277-287.
Berlekamp, E. R., Conway, J. H. and Guy, R. K. 2004. Winning Ways for Your Mathematical Plays, 2nd Ed., Volume 4. A K Peters/CRC Press, USA.
Bidlo, M. 2015. Investigation of replicating tiles in cellular automata designed by evolution using conditionally matching rules. In 2015 IEEE International Conference on Evolvable Systems (ICES), Proceedings of the 2015 IEEE Symposium Series on Computational Intelligence (SSCI). IEEE, pp. 1506-1513.
Bidlo, M. 2016. Evolution of generic square calculations in cellular automata. In Proceedings of the 8th International Joint Conference on Computational Intelligence - Volume 3: ECTA. SciTePress - Science and Technology Publications, pp. 94-102.
Bidlo, M. 2016. On routine evolution of complex cellular automata. IEEE Transactions on Evolutionary Computation 20, 5, pp. 742-754.
Bidlo, M. 2019. Results of evolutionary development of cellular automata using various representations with interactive simulator. URL https://github.com/bidlom/Mendel2019-ES
Bidlo, M. and Vasicek, Z. 2013. Evolution of cellular automata with conditionally matching rules. In 2013 IEEE Congress on Evolutionary Computation (CEC 2013). IEEE, pp. 1178-1185.
Bisio, A., D'Ariano, G., Perinotti, P., and Tosini, A. 2015. Free quantum eld theory from quantum cellular automata. Foundations of Physics 45, 10, pp. 1137-1152.
Breukelaar, R. and Back, T. 2005. Using a genetic algorithm to evolve behavior in multi dimensional cellular automata. In Proceedings of the 2005 Genetic and Evolutionary Computation Conference, GECCO 2005. ACM, pp. 107-114.
Byl, J. 1989. Self-reproduction in small cellular automata. Physica D: Nonlinear Phenomena 34, 1-2, pp. 295-299.
Capcarrere, M. S., Sipper, M., and Tomassini, M. 1996. Two-state, r = 1 cellular automaton that classifies density. Physical Review Letters 77, pp. 4969-4971.
Codd, E. F. 1968. Cellular Automata. Academic Press, New York, USA.
Elmenreich, W. and Fehervari, I. 2011. Evolving self-organizing cellular automata based on neural network genotypes. In Proc. of the 5th International Conference on Self-organizing Systems. Springer, pp. 16-25.
Fogel, L. J., Owens, A. J., and Walsh, M. J. 1966. Artificial Intelligence through Simulated Evolution. Wiley, New York, USA.
Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, USA.
Javaheri Javid, M. A., al Rifaie, M. M., and Zimmer, R. 2014. Detecting symmetry in cellular automata generated patterns using swarm intelligence. In: Theory and Practice of Natural Computing, Lecture Notes in Computer Science. Springer, vol. 8890, pp. 83-94.
Land, M. and Belew, R. K. 1995. No perfect two-state cellular automata for density classification exists. Physical Review Letters 74, pp. 5148-5150.
Langton, C. G. 1984. Self-reproduction in cellular automata. Physica D: Nonlinear Phenomena 10, 1-2, pp. 135-144.
Mardiris, V., Sirakoulis, G., and Karafyllidis, I. 2015. Automated design architecture for 1-d cellular automata using quantum cellular automata. IEEE Transactions on Computers 64, 9, pp. 2476-2489.
Medernach, D., Kowaliw, T., Ryan, C., and Doursat, R. 2013. Long-term evolutionary dynamics in heterogeneous cellular automata. In Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. ACM, pp. 231-238.
von Neumann, J. 1966. The Theory of Self-Reproducing Automata. University of Illinois Press, USA.
Ninagawa, S. 2013. Solving the parity problem with rule 60 in array size of the power of two. Journal of Cellular Automata 8, 3-4, pp. 189-203.
Packard, N. H. 1988. Adaptation toward the edge of chaos. In Dynamic Patterns in Complex Systems. World Scientic, pp. 293-301.
Reggia, J. A., Armentrout, S. L., Chou, H. H., and Peng, Y. 1993. Simple systems that exhibit self-directed replication. Science 259, 5099, pp. 1282-1287.
Rendell, P. 2013. A fully universal turing machine in Conway's game of life. Journal of Cellular Automata 9, 1-2, pp. 19-358.
Richards, F. C., Meyer, T. P., and Packard, N. H. 1990. Extracting cellular automaton rules directly from experimental data. Physica D 45, 1-3, pp. 189-202.
Sahoo, S., Choudhury, P. P., Pal, A., and Nayak, B. K. 2014. Solutions on 1-d and 2-d density classification problem using programmable cellular automata. Journal of Cellular Automata 9, 1, pp. 59-88.
Sahu, S., Oono, H., Ghosh, S., Bandyopadhyay, A., Fujita, D., Peper, F., Isokawa, T., and Pati, R. 2010. Molecular implementations of cellular automata. In Cellular Automata for Research and Industry, Lecture Notes in Computer Science. Springer, Vol. 6350, pp. 650-659.
Sapin, E. 2010. Gliders and glider guns discovery in cellular automata. In: Game of Life Cellular Automata. Springer, pp. 135-165.
Sapin, E., Bailleux, O., and Chabrier, J. 1997. Research of complexity in cellular automata through evolutionary algorithms. Complex Systems 17, 3, pp. 231-241.
Sipper, M. 1995. Quasi-uniform computation-universal cellular automata. In Advances in Artificial Life, ECAL 1995, Lecture Notes in Computer Science. Springer, Vol. 929, pp. 544-554.
Sipper, M. 1997. Evolution of Parallel Cellular Machines - The Cellular Programming Approach, Lecture Notes in Computer Science, Vol. 1194. Springer, Berlin, Germany.
Sridharan, K. and Pudi, V. 2015. Design of Arithmetic Circuits in Quantum Dot Cellular Automata Nanotechnology. Springer International Publishing, Switzerland.
Stefano, G. D. and Navarra, A. 2012. Scintillae: How to approach computing systems by means of cellular automata. In Cellular Automata for Research and Industry, Lecture Notes in Computer Science. Springer, Vol. 7495, pp. 534-543.
Tempesti, G. 1995. A new self-reproducing cellular automaton capable of construction and computation. In Advances in Artificial Life, Proc. 3rd European Conference on Artificial Life, Lecture Notes in Artificial Intelligence.Springer, Vol. 929, pp. 555-563.
Wolfram, S. 2002. A New Kind of Science. Wolfram Media, Champaign IL, USA.
Yunes, J. B. 2010. Achieving universal computations on one-dimensional cellular automata. In Cellular Automata for Research and Industry, Lecture Notes in Computer Science. Springer, Volume 6350, pp. 660-669.
MENDEL open access articles are normally published under a Creative Commons Attribution-NonCommercial-ShareAlike (CC BY-NC-SA 4.0) https://creativecommons.org/licenses/by-nc-sa/4.0/ . Under the CC BY-NC-SA 4.0 license permitted 3rd party reuse is only applicable for non-commercial purposes. Articles posted under the CC BY-NC-SA 4.0 license allow users to share, copy, and redistribute the material in any medium of format, and adapt, remix, transform, and build upon the material for any purpose. Reusing under the CC BY-NC-SA 4.0 license requires that appropriate attribution to the source of the material must be included along with a link to the license, with any changes made to the original material indicated.
