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

非同期セル・オートマトン（ひどうきセル・オートマトン、）はセル・オートマトンの一種であり、それを構成する各セルの状態が他のセルと非同期に更新されるものをいう。
セル・オートマトンは他のマルチエージェント・システムのモデルと同様に、通常は時間を離散的に、そして状態更新が同期的に起こるように扱う。モデルにおける各セルの状態が同時に更新され、他のセルの新しい状態からの影響が及ぶ前に決められる。それに対して非同期セル・オートマトンは各セルが独立に更新され、セルの新しい状態が近傍のセルの状態の計算に影響を与える。
同期的な更新は 2 つのフェーズに分けられる。第 1 のフェーズは相互作用であり、近傍のセルと更新規則に基づいて各セルの新しい状態が計算される。状態値は一時記憶に保持される。第 2 のフェーズにおいては、新しい状態をセルにコピーすることによって状態値を更新する。それとはちがって、非同期の更新はこのようにフェーズを分離することがなく、状態変化がただちに実現される。この違いを次のように要約することができる。
ここで formula_1 は時刻 "t" における要素状態のベクトルであり、formula_2 は更新に使用される一時的なコピーであり "i" は個々の要素のインデクスであり、"N" はこのモデルにおける総要素数であり、f() は集合 "Ki の要素の現在の状態要素の新しい状態を計算する関数である (formula_3)。
同期アプローチは大域的なクロック同期信号が存在して全セルの同時更新が保証されることを仮定する。これはコンピュータ・システムにおいては便利な仮定だが、そのような機構の存在が示せないときには、たとえば生物システムにおいては、非現実的な仮定である。
更新スキーム.
いくつかの研究は非同期的なモデルを実現して、同期的なモデルとのふるまいの違いを発見した。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)。
下記の時刻と状態との関係図は、他のパラメタが変化しないときの、セル・オートマトンのモデルの更新スキームの変化に起因する違いを示す。使用する規則 30 は各図に共通である。
含意.
しばしば、セル・オートマトンのようなモデルは現実に作用しているプロセスの理解を助けるために使われる。単純化されたモデルをつくることによって、新しい洞察を得ることができる。モデル化されつつあるものを適切に記述するためにそれらのモデルはどのくらい単純化されているべきなのかが常に問題になる。非同期のモデルはそのモデルに更なるレベルのリアリズムをもたらす。上記のすべてのスキームは現実のなかでそれぞれの位置を占める。ランダム独立スキームはソーシャル・ネットワークやコンピュータネットワークにおける通信をモデル化するのに適当かもしれない。自己クロックスキームは昆虫のコロニーをモデル化するのに適当かもしれない。また、自己同期スキームは neural tissue に適用できるかもしれない。