Стохастический клеточный автомат
Клеточный автомат с вероятностными правилами

Стохастические клеточные автоматы или вероятностные клеточные автоматы ( PCA ) или случайные клеточные автоматы или локально взаимодействующие цепи Маркова [1] [2] являются важным расширением клеточного автомата . Клеточные автоматы представляют собой дискретно-временную динамическую систему взаимодействующих сущностей, состояние которой дискретно.

Состояние набора сущностей обновляется в каждый дискретный момент времени в соответствии с некоторым простым однородным правилом. Состояния всех сущностей обновляются параллельно или синхронно. Стохастические клеточные автоматы — это КА, правило обновления которых является стохастическим , что означает, что состояния новых сущностей выбираются в соответствии с некоторыми распределениями вероятностей. Это случайная динамическая система с дискретным временем . Из пространственного взаимодействия между сущностями, несмотря на простоту правил обновления, может возникнуть сложное поведение, такое как самоорганизация . Как математический объект, он может рассматриваться в рамках стохастических процессов как система взаимодействующих частиц в дискретном времени. См. [3] для более подробного введения.

PCA как марковские стохастические процессы

Как дискретный марковский процесс, PCA определяются на пространстве произведений (декартово произведение), где — конечный или бесконечный граф, например , и где — конечное пространство, например , или . Вероятность перехода имеет форму произведения , где и — распределение вероятностей на . В общем случае требуется некоторая локальность , где с конечной окрестностью k. См. [4] для более подробного введения с точки зрения теории вероятностей. Э = ∏ к ∈ Г С к {\displaystyle E=\prod _{k\in G}S_{k}} Г {\displaystyle G} З {\displaystyle \mathbb {Z} } С к {\displaystyle S_{k}} С к = { − 1 , + 1 } {\displaystyle S_{k}=\{-1,+1\}} С к = { 0 , 1 } {\displaystyle S_{k}=\{0,1\}} П ( г σ | η ) = ⊗ к ∈ Г п к ( г σ к | η ) {\displaystyle P(d\sigma |\eta) =\otimes _ {k\in G}p_ {k} (d\sigma _{k}|\eta)} η ∈ Э {\displaystyle \eta \in E} п к ( г σ к | η ) {\displaystyle p_{k}(d\sigma _{k}|\eta)} С к {\displaystyle S_{k}} п к ( г σ к | η ) = п к ( г σ к | η В к ) {\displaystyle p_ {k}(d\sigma _{k}|\eta) = p_ {k} (d\sigma _{k}|\eta _{V_{k}})} η В к = ( η дж ) дж ∈ В к {\displaystyle \eta _{V_{k}} = (\eta _{j})_{j\in V_ {k}}} В к {\displaystyle {V_{k}}}

Примеры стохастического клеточного автомата

Мажоритарный клеточный автомат

Существует версия мажоритарного клеточного автомата с вероятностными правилами обновления. См. правило Тоома .

Связь с решетчатыми случайными полями

PCA может быть использован для моделирования модели ферромагнетизма Изинга в статистической механике . [5] Некоторые категории моделей были изучены с точки зрения статистической механики.

Сотовая модель Поттса

Существует тесная связь [6] между вероятностными клеточными автоматами и клеточной моделью Поттса, особенно когда они реализуются параллельно.

Немарковское обобщение

Модель Гальвеса–Лёхербаха является примером обобщенного PCA с немарковским аспектом.

Ссылки

  1. ^ Toom, AL (1978), Локально взаимодействующие системы и их применение в биологии: Труды школы-семинара по марковским процессам взаимодействия в биологии, состоявшейся в Пущино, март 1976 г. , Lecture Notes in Mathematics, т. 653, Springer-Verlag, Берлин-Нью-Йорк, ISBN 978-3-540-08450-1, МР  0479791
  2. ^ RL Dobrushin; VI Kri︠u︡kov; AL Toom (1978). Стохастические клеточные системы: эргодичность, память, морфогенез. Manchester University Press. ISBN 9780719022067.
  3. ^ Фернандес, Р.; Луис, П.-Й.; Нарди, Ф. Р. (2018). "Глава 1: Обзор: модели PCA и проблемы". В Louis, П.-Й.; Нарди, Ф. Р. (ред.). Вероятностные клеточные автоматы . Springer. doi : 10.1007/978-3-319-65558-1_1. ISBN 9783319655581. S2CID  64938352.
  4. ^ П.-Й. Луи, доктор философии
  5. ^ Vichniac, G. (1984), «Моделирование физики с помощью клеточных автоматов», Physica D , 10 ( 1– 2): 96– 115, Bibcode : 1984PhyD...10...96V, doi : 10.1016/0167-2789(84)90253-7.
  6. ^ Боас, Соня EM; Цзян, И; Меркс, Руланд М.Х.; Прокопиу, Сотирис А.; Ренс, Элизабет Г. (2018). «Глава 18: Клеточная модель Поттса: приложения к васкулогенезу и ангиогенезу». В Луи, П.-Ю.; Нарди, Франция (ред.). Вероятностные клеточные автоматы . Спрингер. дои : 10.1007/978-3-319-65558-1_18. hdl : 1887/69811. ISBN 9783319655581.

Дальнейшее чтение

  • Almeida, RM; Macau, EEN (2010), «Модель стохастических клеточных автоматов для динамики распространения лесных пожаров», 9-я Бразильская конференция по динамике, управлению и их применению, 7–11 июня 2010 г. , том 285, стр. 012038, doi : 10.1088/1742-6596/285/1/012038.
  • Кларк, К.С.; Хоппен, С. (1997), «Самомодифицирующаяся клеточно-автоматная модель исторической урбанизации в районе залива Сан-Франциско» (PDF) , Environment and Planning B: Planning and Design , 24 (2): 247– 261, Bibcode : 1997EnPlB..24..247C, doi : 10.1068/b240247, S2CID  40847078.
  • Махаджан, Мина Бхаскар (1992), Исследования языковых классов, определяемых различными типами изменяющихся во времени клеточных автоматов, докторская диссертация, Индийский технологический институт Мадраса.
  • Нисио, Хидэносукэ; Кобути, Юичи (1975), «Отказоустойчивые клеточные пространства», Журнал компьютерных и системных наук , 11 (2): 150–170 , doi : 10.1016/s0022-0000(75)80065-1 , MR  0389442.
  • Смит, Элви Рэй III (1972), «Распознавание языка в реальном времени одномерными клеточными автоматами», Журнал компьютерных и системных наук , 6 (3): 233–253 , doi : 10.1016/S0022-0000(72)80004-7 , MR  0309383.
  • Louis, P.-Y.; Nardi, FR, ред. (2018). Вероятностные клеточные автоматы . Возникновение, сложность и вычисления. Том 27. Springer. doi : 10.1007/978-3-319-65558-1. hdl : 2158/1090564. ISBN 9783319655581.
  • Агапие, А.; Андреика, А.; Джуклеа, М. (2014), «Вероятностные клеточные автоматы», Журнал вычислительной биологии , 21 (9): 699–708 , doi :10.1089/cmb.2014.0074, PMC  4148062 , PMID  24999557
Взято с "https://en.wikipedia.org/w/index.php?title=Стохастический_клеточный_автомат&oldid=1254235203"