Конструирование клеточных автоматов с использованием моделей машинного обучения

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

Работа посвящена разработке и исследованию методов аппроксимации клеточных автоматов с применением моделей машинного обучения. Клеточные автоматы – это модели, используемые для изучения динамики сложных систем на основе простых правил взаимодействия. В последние годы модели машинного обучения стали мощными инструментами в области обработки данных. В работе исследуются подходы к предсказанию правил клеточных автоматов с использованием моделей машинного обучения, рассматриваются их преимущества и ограничения, а также предлагаются метрики для оценки качества предсказаний состояний клеточных автоматов и зависимость предсказания состояний клеточных автоматов в зависимости от числа поступающих на вход для обучения моделей правил клеточных автоматов. Исследование направлено на понимание того, как модели машинного обучения могут быть использованы для анализа и моделирования сложных систем на основе клеточных автоматов, а также на возможные перспективы развития данного подхода. На основе предложенных метрик проводится сравнительный анализ эффективности различных моделей машинного обучения в предсказании правил клеточных автоматов.

Об авторах

Глеб Антонович Малмыгин

Московский государственный университет имени М.В. Ломоносова

Автор, ответственный за переписку.
Email: malmygingleb1@gmail.com
SPIN-код: 7217-4880

факультет вычислительной математики и кибернетики

Россия, г. Москва

Николай Михайлович Ершов

Московский государственный университет имени М.В. Ломоносова

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

кандидат физико-математических наук, старший научный сотрудник, факультет вычислительной математики и кибернетики

Россия, г. Москва

Список литературы

  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.

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
2. Рис. 1. Примеры клеточных пространств в клеточных автоматах

Скачать (146KB)
3. Рис. 2. Типы локальных окрестностей двумерных прямоугольных КА ранга 1 и 2: окрестность фон Неймана (а), окрестность Мура (b)

Скачать (168KB)
4. Рис. 3. Архитектура многослойного перцептрона

Скачать (219KB)
5. Рис. 4. Схема работы метода ближайших соседей

Скачать (353KB)
6. Рис. 5. Схема работы метода на основе дерева решений

Скачать (188KB)
7. Рис. 6. Схема работы метода случайного леса

Скачать (314KB)
8. Рис. 7. Примеры состояний детерминированных клеточных автоматов Life (а) и Cyclic (b)

9. Рис. 8. Точность работы моделей от размера обучающей выборки для клеточного автомата Life

Скачать (350KB)
10. Рис. 9. Точность работы моделей от размера обучающей выборки для клеточного автомата Cyclic

Скачать (356KB)
11. Рис. 10. Примеры состояний недетерминированных клеточных автоматов Epidemic (а) и Voting (b)

Скачать (493KB)
12. Рис. 11. Точность восстановления системы правил о т размера обучающей выборки для недетерминированных автоматов Epidemic и Voting

Скачать (179KB)


Ссылка на описание лицензии: https://www.urvak.ru/contacts/

Согласие на обработку персональных данных с помощью сервиса «Яндекс.Метрика»

1. Я (далее – «Пользователь» или «Субъект персональных данных»), осуществляя использование сайта https://journals.rcsi.science/ (далее – «Сайт»), подтверждая свою полную дееспособность даю согласие на обработку персональных данных с использованием средств автоматизации Оператору - федеральному государственному бюджетному учреждению «Российский центр научной информации» (РЦНИ), далее – «Оператор», расположенному по адресу: 119991, г. Москва, Ленинский просп., д.32А, со следующими условиями.

2. Категории обрабатываемых данных: файлы «cookies» (куки-файлы). Файлы «cookie» – это небольшой текстовый файл, который веб-сервер может хранить в браузере Пользователя. Данные файлы веб-сервер загружает на устройство Пользователя при посещении им Сайта. При каждом следующем посещении Пользователем Сайта «cookie» файлы отправляются на Сайт Оператора. Данные файлы позволяют Сайту распознавать устройство Пользователя. Содержимое такого файла может как относиться, так и не относиться к персональным данным, в зависимости от того, содержит ли такой файл персональные данные или содержит обезличенные технические данные.

3. Цель обработки персональных данных: анализ пользовательской активности с помощью сервиса «Яндекс.Метрика».

4. Категории субъектов персональных данных: все Пользователи Сайта, которые дали согласие на обработку файлов «cookie».

5. Способы обработки: сбор, запись, систематизация, накопление, хранение, уточнение (обновление, изменение), извлечение, использование, передача (доступ, предоставление), блокирование, удаление, уничтожение персональных данных.

6. Срок обработки и хранения: до получения от Субъекта персональных данных требования о прекращении обработки/отзыва согласия.

7. Способ отзыва: заявление об отзыве в письменном виде путём его направления на адрес электронной почты Оператора: info@rcsi.science или путем письменного обращения по юридическому адресу: 119991, г. Москва, Ленинский просп., д.32А

8. Субъект персональных данных вправе запретить своему оборудованию прием этих данных или ограничить прием этих данных. При отказе от получения таких данных или при ограничении приема данных некоторые функции Сайта могут работать некорректно. Субъект персональных данных обязуется сам настроить свое оборудование таким способом, чтобы оно обеспечивало адекватный его желаниям режим работы и уровень защиты данных файлов «cookie», Оператор не предоставляет технологических и правовых консультаций на темы подобного характера.

9. Порядок уничтожения персональных данных при достижении цели их обработки или при наступлении иных законных оснований определяется Оператором в соответствии с законодательством Российской Федерации.

10. Я согласен/согласна квалифицировать в качестве своей простой электронной подписи под настоящим Согласием и под Политикой обработки персональных данных выполнение мною следующего действия на сайте: https://journals.rcsi.science/ нажатие мною на интерфейсе с текстом: «Сайт использует сервис «Яндекс.Метрика» (который использует файлы «cookie») на элемент с текстом «Принять и продолжить».