非同期セルオートマトン

セルオートマトン（CMA）は、他のマルチエージェントシステムモデルと同様に、通常、時間を離散的に扱い、状態の更新は同期的に行われるものとみなします。モデル内の各セルの状態は、新しい状態が他のセルに影響を与える前に、同時に更新されます。対照的に、非同期セルオートマトン（AMA ）は個々のセルを独立して更新することができ、あるセルの新しい状態が隣接するセルの状態の計算に影響を与えます。

同期更新の実装は2つのフェーズで分析できます。最初のフェーズである相互作用では、近傍と更新規則に基づいて各セルの新しい状態を計算します。状態値は一時ストアに保持されます。2番目のフェーズでは、新しい状態をセルにコピーすることで状態値を更新します。

対照的に、非同期更新では、必ずしもこれら 2 つのフェーズが分離されるわけではありません。最も単純なケース (完全に非同期の更新) では、状態の変更は即座に実装されます。

同期アプローチでは、すべてのセルが同時に更新されることを保証するために、グローバルクロックの存在を前提としています。これはコンピュータシステムの準備には便利ですが、例えばそのようなデバイスの存在を示す証拠がない生体システムをモデル化しようとする場合、この仮定は非現実的かもしれません。

独立して繰り返し発見された一般的な方法（1970年代にK. Nakamura、1980年代にT. Toffoli、1998年にCL Nehaniv）により、同期セルオートマトンを単純に修正した非同期セルオートマトンを介して、同期セルオートマトンの動作を正確にエミュレートすることが可能になりました（Nehaniv 2002）。しかし、この方法の正しさはごく最近になって厳密に証明されました（Nehaniv, 2004）。結果として、同期セルオートマトンの結果から、非同期セルオートマトンが、例えばコンウェイのライフゲーム、普遍的計算、自己複製（例えば、フォン・ノイマンの普遍的構築子など）をエミュレートできることが直ちに分かります。さらに、一般的な構成と証明は、より一般的なクラスの同期オートマトンネットワーク (有向グラフ上のオートマトン不均質ネットワークで外部入力が可能。特殊なケースとしてセルオートマトンを含む) にも適用され、それらの動作が対応する非同期オートマトンネットワークによって非同期的に実現される方法を構成的に示します。

更新スキーム

いくつかの研究では非同期モデルを実装し、その動作が同期モデルとは異なることを発見しました。Bersini と Detours (1994) は、Conway のライフゲームが更新方式にどれほど敏感であるかを示しました。興味深い動作は非同期の場合にはすべて消えてしまいます。Harvey と Bossomaier (1997) は、ランダムブールネットワークでの確率的更新の結果は点アトラクターのみの表現になり、緩い周期的アトラクターの概念を導入したものの、繰り返し可能な周期的動作はないことを指摘しました。Kanada (1994) は、同期更新時に非カオスパターンを生成する一部の 1 次元 CA モデルが、ランダム化されるとカオスエッジパターンを生成することを示しました。Orponen (1997) は、しきい値論理ユニット (人工ニューロンを参照) の同期更新ネットワークは、更新順序に制約のないネットワークでシミュレートできることを実証しました。Sipper ら (1997) は、特定のコンピューティングタスクを実行する非均一 CA の進化を調査しました。これらのモデルは、すべてのノードが同じ更新規則を持つという通常の要件を緩和します。これらのモデルでは、ノードはブロックに編成されます。ブロック内のノードは同期的に更新されますが、ブロックは非同期的に更新されます。彼らは3つの手法で実験を行いました。(1) 各タイムステップで、ブロックをランダムに選択し、置換する。(2) 各タイムステップで、ブロックをランダムに選択し、置換しない。(3) 各タイムステップで、固定された更新順序に従ってブロックを選択する。

非同期更新には様々な種類があり、様々な著者によってそれぞれ異なる方法で説明されています。以下の図に示されているスキームは以下のとおりです（Cornforth et al. 2005）。

同期方式 - すべてのセルが各タイムステップで並列に更新されます。これは従来のモデルであり、ここでは比較のために示します。
ランダム独立方式 - 各タイムステップで、セルがランダムに選択され、置換され、更新されます。
ランダム順序スキーム - 各タイムステップですべてのノードが更新されますが、順序はランダムです。
循環方式 - 各タイムステップで、モデルの初期化中にランダムに決定された固定更新順序に従ってノードが選択されます。
自己クロック方式 - 各セルは独立したタイマーを持ち、ランダムな周期と位相に初期化されます。周期が経過すると、セルが更新され、タイマーはリセットされます。更新は自律的に行われ、セルごとに異なる速度で進行します。
自己同期方式 - クロック方式と同じですが、タイマーの位相は近隣のタイマーとのローカル結合によって影響を受けるため、ローカル同期を実現できます。

以下の時系列図は、セルオートマトンモデルの更新スキームを変更したが、他のパラメータは変更しなかった場合に生じる差異を示しています。使用されるルール（ルール30）は、各図で同じです。


元のルール30	ルール30はランダムに更新されます

ルール30はランダムな順序で更新されました	規則30は巡回的に更新されました

自己クロックルール30	自己同期規則30

意味合い

セルオートマトンのようなモデルは、現実世界で機能するプロセスを理解するためによく用いられます。簡略化されたモデルを構築することで、新たな知見を得ることができます。モデル化対象を適切に記述するためには、これらのモデルはどの程度簡略化されるべきかという問題は常に存在します。非同期モデルを用いることで、モデルのリアリティをさらに高めることができます。上記のすべての手法は、現実世界で活用されています。ランダム独立手法は、ソーシャルネットワークやコンピュータネットワークにおける通信のモデル化に適しています。クロック制御手法は昆虫コロニーのモデル化に適しており、自己同期手法は神経組織に適用できます。

参考文献

H. Bersini および V. Detours、1994 年、「非同期性はセルラーオートマトンベースのモデルの安定性を誘導する」、第 4 回人工生命会議の議事録、382 ～ 387 ページ、マサチューセッツ州ケンブリッジ、1994 年 7 月、第 204 巻、第 1 ～ 2 号、70 ～ 82 ページ。
Cornforth, D, Green, D, & Newth, D 2005, 「マルチエージェントシステムにおける順序付き非同期プロセス」、Physica D、vol 204、no. 1-2、pp. 70-82。
コーンフォース、D、グリーン、DG、ニュース、D、カーリー M 2002、「人工アリは足並みを揃えて行進するのか？生物システムにおける秩序立った非同期プロセスとモジュール性」。スタンディッシュ、ベダウ、アバス共著、第8回国際人工生命会議議事録、シドニー、pp. 28-32
Fatès N., (2014), 非同期セルラーオートマトンガイドツアー, Journal of Cellular Automata : Vol. 9(5-6), pp. 387-416,プレプリント
Fatès N.、および Morvan M.、(2005)、「基本的なセルオートマトンにおける非同期性に対する堅牢性の実験的研究」、Complex Systems : Volume 16 / Issue 1、pp. 1-27。
Fatès N.、Morvan M.、N. Schabanel、および E. Thierry、(2006)「二重静止基本セルラーオートマトンの全非同期動作」、理論計算機科学：第 362 巻、pp. 1 - 16。
Harvey I.、Bossomaier TRJ (1997). 「タイムアウト・オブ・ジョイント：非同期ブールネットワークにおけるアトラクター」Husbands and Harvey (編)、Proceedings of the Fourth European Conference on Artificial Life、67-75ページ、MIT Press .
金田雄一 (1994).非同期1次元セルオートマトンにおけるランダム性の影響.人工生命IV .
Nehaniv, CL (2002). 非同期セルオートマトンにおける進化, Artificial Life VIII , 65-73, MIT Press.
Nehaniv, CL (2004). 非同期オートマトンネットワークは任意の同期オートマトンネットワークをエミュレートできる, International Journal of Algebra & Computation , 14(5-6):719-739.
オルポネン, P. (1997). 真に非同期な閾値論理ネットワークを用いた計算.理論計算機科学174(1-2):123-136.
Sipper M, Tomassini M., Capcarrere MS (1997). 非同期かつスケーラブルな非一様セルオートマトンの開発. Proc. of Intl. Conf. on Artificial Neural Networks and Genetic Algorithms (ICANNGA97) , Springer-Verlag.
モナッシュ大学の仮想実験室セルオートマトンにおける非同期更新のオンラインシミュレーション。