PROFILPELAJAR.COM

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

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

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

同期フェーズ 1 (相互作用):	$\forall i\in N:\tau _{i}^{(t+1)}=f(\sigma _{k\in K_{i}}^{(t)})$
同期フェーズ 2 (更新):	${\hat {\sigma }}^{(t+1)}={\hat {\tau }}^{(t+1)}$
非同期:	$\forall i\in N:\sigma _{i}^{(t+1)}=f(\sigma _{k\in K_{i}}^{(t)})$

ここで $\sigma ^{(t)}$ は時刻 t における要素状態のベクトルであり、 ${\hat {\tau }}^{(t)}$ は更新に使用される一時的なコピーであり i は個々の要素のインデクスであり、N はこのモデルにおける総要素数であり、f() は集合 K_i の要素の現在の状態要素の新しい状態を計算する関数である ( $|K_{i}|\leq N$ )。

同期アプローチは大域的なクロック同期信号が存在して全セルの同時更新が保証されることを仮定する。これはコンピュータ・システムにおいては便利な仮定だが、そのような機構の存在が示せないときには、たとえば生物システムにおいては、非現実的な仮定である。

更新スキーム

いくつかの研究は非同期的なモデルを実現して、同期的なモデルとのふるまいの違いを発見した。Bersini and Detours (1994) は Conway のライフゲームが更新スキームにどれだけ敏感であるかを示した。どんな興味深いふるまいも非同期の場合には消えてしまう。Harvey and Bossomaier (1997) はランダムな 2 値のネットワーク (random boolean network) の確率的な更新は固定的アトラクタ (point attractor) だけを生みだす、つまり周期的なふるまいは起こらないことを指摘した。ただし、彼らは緩い周期アトラクタという概念を導入した。金田 (Kanada (1994)) は、同期的に更新されるときはカオスの淵のパターンを生成する 1 次元セル・オートマトンのモデルが、非同期かつランダムに更新されるときにはカオス的でないパターンを生成することを示した。Orponen (1997) はどのような同期的に更新される閾値のある論理ユニット（人工神経参照）のネットワークも、更新順序に制約のないネットワークによってシミュレートできることを示した。Sipper et al. (1997) は特定の計算を実行する一様でないセル・オートマトンの進化をしらべた。これらのモデルにおいては全ノードが同一の更新規則に従うという通常の要件をゆるめている。これらのモデルにおいてはノードはブロックにまとめられる。すなわち、ブロック内のノードは同期的に更新されるが、各ブロックは非同期的に更新される。彼らは 3 つのスキームを実験した。(1) 各タイムステップにおいて 1 個のブロックがランダムに選択されて置換され、(2) 各タイムステップにおいて 1 個のブロックがランダムに選択されるが置換されず、(3) 各タイムステップにおいて 1 個のブロックが固定的な更新順序に従って選択される。

様々な型の非同期更新があり、様々な著者が様々なやり方でそれらを記述している。下図に示すスキームは次の通りである (Cornforth et al. 2005)。

同期スキーム - 全セルがタイムステップごとに並列に更新される。これが従来のモデルであり、比較のために記述している。
ランダム独立スキーム - 各タイムステップに 1 個のセルがランダムに選択されて更新される。
ランダム順序スキーム - 各タイムステップに全ノードがランダムな順序で更新される。
周期的スキーム - 各タイムステップに 1 個のノードが固定の更新順序に従って選択される。この順序はモデルの初期化時にランダムに決められる。
自己クロック (self-clocked) スキーム - 各セルは独立なタイマーを持ち、その周期とフェーズとはランダムに初期化される。その 1 周期が終わると、セルは更新されてタイマーがリセットされる。更新は自律的に起こり、異なるセルについては異なるレートで進行する。
自己同期 (self-sync) スキーム - 自己クロック・スキームと同様に、しかしタイマーのフェーズは近傍のセルとの局所的な結合によって影響され、そのために局所的な同期が実現される。

下記の時刻と状態との関係図は、他のパラメタが変化しないときの、セル・オートマトンのモデルの更新スキームの変化に起因する違いを示す。使用する規則 30 は各図に共通である。


もとの (同期的に更新される) 規則 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.