非同期セル・オートマトン

ウィキペディア

非同期セル・オートマトン

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/04/11 05:32 UTC 版)

非同期セル・オートマトン（ひどうきセル・オートマトン、英: Asynchronous cellular automaton）はセル・オートマトンの一種であり、それを構成する各セルの状態が他のセルと非同期に更新されるものをいう。

セル・オートマトンは他のマルチエージェント・システムのモデルと同様に、通常は時間を離散的に、そして状態更新が同期的に起こるように扱う。モデルにおける各セルの状態が同時に更新され、他のセルの新しい状態からの影響が及ぶ前に決められる。それに対して非同期セル・オートマトンは各セルが独立に更新され、セルの新しい状態が近傍のセルの状態の計算に影響を与える。

同期的な更新は 2 つのフェーズに分けられる。第 1 のフェーズは相互作用であり、近傍のセルと更新規則に基づいて各セルの新しい状態が計算される。状態値は一時記憶に保持される。第 2 のフェーズにおいては、新しい状態をセルにコピーすることによって状態値を更新する。それとはちがって、非同期の更新はこのようにフェーズを分離することがなく、状態変化がただちに実現される。この違いを次のように要約することができる。

同期 フェーズ 1 (相互作用):	$\forall i\in N:\tau _{i}^{(t+1)}=f(\sigma _{k\in K_{i}}^{(t)})$
もとの (同期的に更新される) 規則 30	ランダムに更新される規則 30
ランダムな順序で更新される規則 30	周期的な順序で更新される規則 30
自己クロック付きの規則 30	自己同期する規則 30

含意

しばしば、セル・オートマトンのようなモデルは現実に作用しているプロセスの理解を助けるために使われる。単純化されたモデルをつくることによって、新しい洞察を得ることができる。モデル化されつつあるものを適切に記述するためにそれらのモデルはどのくらい単純化されているべきなのかが常に問題になる。非同期のモデルはそのモデルに更なるレベルのリアリズムをもたらす。上記のすべてのスキームは現実のなかでそれぞれの位置を占める。ランダム独立スキームはソーシャル・ネットワークやコンピュータネットワークにおける通信をモデル化するのに適当かもしれない。自己クロックスキームは昆虫のコロニーをモデル化するのに適当かもしれない。また、自己同期スキームは neural tissue に適用できるかもしれない。

参考文献

• H. Bersini and V. Detours, 1994. Asynchrony induces stability in cellular automata based models, Proceedings of the IVth Conference on Artificial Life , pages 382-387, Cambridge, MA, July 1994, vol 204, no. 1-2, pp. 70-82.
• Cornforth, D., Green, D., and Newth, D. (2005), Ordered Asynchronous Processes in Multi-Agent Systems, Physica D, vol. 204, no. 1-2, pp. 70-82.
• Cornforth, D., Green, D. G., Newth, D., and Kirley, M. (2002), Do Artificial Ants March in Step? Ordered Asynchronous Processes and Modularity in Biological Systems. In Standish, Bedau, Abbass, Proceedings of the Eighth International Conference on Artificial Life, Sydney, pp. 28-32.
• Harvey, I., and Bossomaier, T. R. J. (1997). Time Out of Joint: Attractors in Asynchronous Boolean Networks. In Husbands and Harvey (eds.), Proceedings of the Fourth European Conference on Artificial Life, pp. 67-75, MIT Press.
• Kanada, Y. (1994). The Effects of Randomness in Asynchronous 1D Cellular Automata. Artificial Life IV.
• Orponen, P. (1997). Computing with Truly Asynchronous Threshold Logic Networks. Theoretical Computer Science 174(1-2):123-136.
• Sipper, M, Tomassini, M., and Capcarrere, M. S. (1997). Evolving Asynchronous and Scalable Non-Uniform Cellular Automata. Proc. of Intl. Conf. on Artificial Neural Networks and Genetic Algorithms (ICANNGA 97), Springer-Verlag.
• Virtual Laboratory at Monash University Online simulations of asynchronous updating in cellular automata.

関連項目

• セル・オートマトン
• ライフゲーム