Stochastyczny automat komórkowy

Stochastyczne automaty komórkowe lub probabilistyczne automaty komórkowe (PCA) lub losowe automaty komórkowe lub lokalnie oddziałujące łańcuchy Markowa są ważnym rozszerzeniem automatu komórkowego . Automaty komórkowe to dynamiczne układy oddziałujących na siebie bytów w czasie dyskretnym , których stan jest dyskretny.

Stan zbioru jednostek jest aktualizowany w każdym dyskretnym czasie zgodnie z pewną prostą jednorodną regułą. Stany wszystkich jednostek są aktualizowane równolegle lub synchronicznie. Stochastyczne automaty komórkowe to CA, których reguła aktualizacji jest stochastyczną , co oznacza, że ​​stany nowych obiektów są wybierane według pewnych rozkładów prawdopodobieństwa. Jest to losowy układ dynamiczny w czasie dyskretnym . Z przestrzennej interakcji między podmiotami, pomimo prostoty reguł aktualizacji, mogą wyłonić się złożone zachowania, takie jak samoorganizacja . Jako obiekt matematyczny można go rozpatrywać w ramach procesów stochastycznych jako oddziałujący układ cząstek w czasie dyskretnym. Zobacz bardziej szczegółowe wprowadzenie.

PCA jako procesy stochastyczne Markowa

Jako proces Markowa w czasie dyskretnym, PCA są zdefiniowane w przestrzeni produktu (iloczyn kartezjański $) G}$${\ Displaystyle E = \ prod _ {k \ in G} S_ {k}}$ (iloczyn kartezjański skończonym lub nieskończonym wykresem, jak $i$ jest przestrzenią, jak na $przykład$${\ Displaystyle S_ {k} = \ {- 1, + 1 \}}$ lub ${\ Displaystyle S_ {k} = \ {0,1 \}}$ . P. ${\ Displaystyle P (d \ sigma | \ eta) = \ otimes _ {k \ in G$ gdzie ${\ Displaystyle \ eta \ in E}$ i ${\ Displaystyle p_ {k} (d \ sigma _ {k} | \ eta)}$ jest rozkładem prawdopodobieństwa na ${\ Displaystyle S_ {k}}$ . Ogólnie wymagana jest pewna lokalizacja ${\ Displaystyle p_ {k} (d \ sigma _ {k} | \ eta) = p_ {k} (d \ sigma _ {k} | \ eta _ {V_ {k}})}$ gdzie ${\ Displaystyle \ eta _ {V_ {k}} = (\ eta _ {j}) _ {j \ w V_ {k}}}$ z ${\ Displaystyle {V_ {k} }}$ skończone sąsiedztwo k. Zobacz bardziej szczegółowe wprowadzenie z punktu widzenia teorii prawdopodobieństwa.

Przykłady stochastycznego automatu komórkowego

Większość automatów komórkowych

Istnieje wersja większościowego automatu komórkowego z probabilistycznymi regułami aktualizacji. Zobacz regułę Tooma .

Związek z losowymi polami sieciowymi

PCA może służyć do symulacji modelu ferromagnetyzmu Isinga w mechanice statystycznej . Niektóre kategorie modeli badano z punktu widzenia mechaniki statystycznej.

Komórkowy model Pottsa

Istnieje silny związek między probabilistycznymi automatami komórkowymi a komórkowym modelem Pottsa, zwłaszcza gdy jest on wdrażany równolegle.

Uogólnienie niemarkowskie

Galvesa -Löcherbacha jest przykładem uogólnionej PCA z aspektem niemarkowskim.

Dalsza lektura

• Almeida, RM; Macau, EEN (2010), „Stochastic cellular automata model for wildland fire spread dynamics”, 9. brazylijska konferencja na temat dynamiki, kontroli i ich zastosowań, 7–11 czerwca 2010 r. , Doi : 10.1088/1742-6596/285/1/012038 .
•   Clarke, KC; Hoppen, S. (1997), „Samomodyfikujący się model automatu komórkowego historycznej urbanizacji w rejonie Zatoki San Francisco” (PDF) , Środowisko i planowanie B: Planowanie i projektowanie , 24 (2): 247–261, doi : 10.1068/b240247 , S2CID 40847078 .
• Mahajan, Meena Bhaskar (1992), Badania w klasach językowych zdefiniowanych przez różne typy zmiennych w czasie automatów komórkowych , Ph.D. rozprawa, Indyjski Instytut Technologii w Madrasie .
•   Nishio, Hidenosuke; Kobuchi, Youichi (1975), „Przestrzenie komórkowe odporne na błędy”, Journal of Computer and System Sciences , 11 (2): 150–170, doi : 10.1016/s0022-0000 (75) 80065-1 , MR 0389442 .
•   Smith, Alvy Ray, III (1972), „Rozpoznawanie języka w czasie rzeczywistym przez jednowymiarowe automaty komórkowe”, Journal of Computer and System Sciences , 6 (3): 233–253, doi : 10.1016 / S0022-0000 (72) 80004-7 , MR 0309383 .
•   Louis, PY-Y; Nardi, FR, wyd. (2018). Probabilistyczne automaty komórkowe . Pojawienie się, złożoność i obliczenia . Tom. 27. Springera. doi : 10.1007/978-3-319-65558-1 . hdl : 2158/1090564 . ISBN 9783319655581 .
•    Agapie, A.; Andreica, A.; Giuclea, M. (2014), „Probabilistyczne automaty komórkowe”, Journal of Computational Biology , 21 (9): 699–708, doi : 10.1089/cmb.2014.0074 , PMC 4148062 , PMID 24999557