Construction of cellular automata using machine learning models

Capa

Citar

Texto integral

Acesso aberto Acesso aberto
Acesso é fechado Acesso está concedido
Acesso é fechado Acesso é pago ou somente para assinantes

Resumo

The paper is devoted to the development and study of cellular automata approximation methods using machine learning models. Cellular automata are models used to study the dynamics of complex systems based on simple interaction rules. In recent years, machine learning models have become powerful tools in the field of data processing. The paper examines approaches to predicting cellular automata rules using machine learning models, considers their advantages and limitations, and proposes metrics for assessing the quality of cellular automata state predictions and the dependence of cellular automata state prediction on the number of cellular automata rule models entering the input for training. The study aims to understand how machine learning models can be used to analyze and model complex systems based on cellular automata, as well as possible prospects for the development of this approach. Based on the proposed metrics, a comparative analysis of the effectiveness of various machine learning models in predicting cellular automata rules is carried out.

Texto integral

Acesso é fechado

Sobre autores

Gleb Malmygin

Lomonosov Moscow State University

Autor responsável pela correspondência
Email: malmygingleb1@gmail.com
Código SPIN: 7217-4880

Department of Computational Mathematics and Cybernetics

Rússia, Moscow

Nikolay Ershov

Lomonosov Moscow State University

Email: ershov@cs.msu.ru
ORCID ID: 0000-0001-5963-0419

Cand. Sci. (Phys.-Math.), senior researcher, Department of Computational Mathematics and Cybernetics

Rússia, Moscow

Bibliografia

  1. Hawkins J. The mathematics of cellular automata. American Mathematical Society, 2024.
  2. Toffoli T. Cellular automata as an alternative to (rather than an approximation of) differential equations in modeling physics. Physica D: Nonlinear Phenomena. 1984. Vol. 10. No. 1-2. Pp. 117–127.
  3. Richards F.C., Meyer T.P., Packard N.H. Extracting cellular automaton rules directly from experimental data. Physica D: Nonlinear Phenomena. 1990. Vol. 45. No. 1-3. Pp. 189–202.
  4. Yang Y., Billings S.A. Extracting Boolean rules from CA patterns. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 2000. Vol. 30. No. 4. Pp. 573–580.
  5. Billings S.A., Yang Y. Identification of probabilistic cellular automata. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 2003. Vol. 33. No. 2. Pp. 225–236.
  6. Zhao Y., Billings S.A. The identification of cellular automata. 2006.
  7. Mitchell M., Hraber P., Crutchfield J.P. Revisiting the edge of chaos: Evolving cellular automata to perform computations. arXiv. Preprint adap-org/9303003. 1993.
  8. Basanta D. et al. Evolving cellular automata to grow microstructures. In: Genetic programming. Proceedings 6 of the 6th European Conference, EuroGP 2003 (Essex, UK, April 14–16, 2003). Springer Berlin Heidelberg, 2003. Pp. 1–10.
  9. Gilpin W. Cellular automata as convolutional neural networks. Physical Review E. 2019. Vol. 100. No. 3. P. 032402.
  10. Springer J.M., Kenyon G.T. It's hard for neural networks to learn the game of life. In: International Joint Conference on Neural Networks (IJCNN). IEEE, 2021. Pp. 1–8.
  11. Aach M., Göbbert J.H., Jitsev J. Generalization over different cellular automata rules learned by a deep feed-forward neural network. arXiv. Preprint arXiv:2103.14886. 2021.
  12. Malmygin G.A., Ershov N.M. Chemical reactions modeling using cellular automata. System Analysis in Science and Education. 2023. No. 3. Pp. 1–13.
  13. Von Neumann J., Burks A.W. Theory of self-reproducing automata. Urbana: University of Illinois Press, 1966.
  14. Wolfram S. A new kind of science. Wolfram Media, 2002.
  15. Toffoli T., Margolus N. Cellular automata machines: A new environment for modeling. MIT Press, 1987
  16. Delashmit W.H. et al. Recent developments in multilayer perceptron neural networks. In: Proceedings of the seventh annual Memphis area engineering and science conference, MAESC. 2005. Vol. 7. P. 33.
  17. Peterson L.E. K-nearest neighbor. Scholarpedia. 2009. Vol. 4. No. 2. P. 1883.
  18. Ying L.U. et al. Decision tree methods: Applications for classification and prediction. Shanghai Archives of Psychiatry. 2015. Vol. 27. No. 2. P. 130.
  19. Rigatti S.J. Random forest. Journal of Insurance Medicine. 2017. Vol. 47. No. 1. Pp. 31–39.
  20. Game of life cellular automata. A. Adamatzky (ed.). London. Springer, 2010. Vol. 1. P. 168.
  21. White S.H., Del Rey A.M., Sánchez G.R. Modeling epidemics using cellular automata. Applied Mathematics and Computation. 2007. Vol. 186. No. 1. Pp. 193–202.

Arquivos suplementares

Arquivos suplementares
Ação
1. JATS XML
2. Fig. 1. Examples of cellular spaces in cellular automata

Baixar (146KB)
3. Fig. 2. Types of local neighborhoods of two-dimensional rectangular CA of ranks 1 and 2: von Neumann neighborhood (a), Moore neighborhood (b)

Baixar (168KB)
4. Fig. 3. Multilayer perceptron architecture

Baixar (219KB)
5. Fig. 4. Scheme of the nearest neighbor method

Baixar (353KB)
6. Fig. 5. Scheme of the work of the method based on the decision tree

Baixar (188KB)
7. Fig. 6. Scheme of operation of the random forest method

Baixar (314KB)
8. Fig. 7. Examples of states of the cellular automata Life (a) and Cyclic (b)

Baixar (1MB)
9. Fig. 8. Accuracy of models from the size of the training sample for the cellular automaton Life

Baixar (350KB)
10. Fig. 9. Accuracy of models from the size of the training sample for the automaton Cyclic

Baixar (356KB)
11. Fig. 10. Examples of states of the nondeterministic cellular automaton Epidemic (а) and Voting (b)

Baixar (493KB)
12. Fig. 11. Accuracy of restoring the system of rules from the size of the training sample for non-deterministic automata Epidemic and Voting

Baixar (179KB)

Declaração de direitos autorais © Yur-VAK, 2025

Link à descrição da licença: https://www.urvak.ru/contacts/