セルオートマトンと複雑系

Complex Systems Created by Cellular Automata

(English here)
トップページ

ギャラリー

セルオートマトンて何？

セルオートマトンの歴史

複雑系て何？

人工生命て何？

リンク集

アイコンの説明:

  1. [new] : 新情報
  2. [good] : お勧め
  3. [demo] : デモ

セルオートマトン・ギャラリー

ここではアニメーションを用いて2次元セルオートマトンによる複雑系の例を紹介します。以下のアニメーションはJavaアプレットを用いています。アプレットの実行にはJava1.1のVM（Virtual Machine）が必要です。現在ほとんどのブラウザーがJava1.1以上をサポートしているはずです。なお、ユーザーインターフェースの見た目は各プラットフォームによって少々異なります。最もユーザー数が多いWindowsに最適化していることをお許しください。

なおこのJavaアプレットのデモをもっとじっくり見たい方、または自分なりにカスタマイズしたい方は、ツールをダウンロードしてローカルに実行することをお勧めします。まだそれほど汎用性はありませんがの自作のルールを実行することも可能です。ダウンロードしたい方はトップページからどうぞ。

実行時の注意：初期のPentium等、速度が遅いマシーンではセルオートマトンのアップデート時に画面が乱れるものがあります。この場合は、speedボタンでspeed選択ウィンドウを表示させ"medium"を選択して下さい。"medium"でも乱れる場合は、"slow"を選択して下さい。なお、初期設定は"fast"になっています。私の経験では、同じクロック周波数ならば、Windowsが最も速く実行できます。
  • generation.html: Generationルール[demo]
    ムーア・ネイバーによって定義されるルール群です。１つのセルに基底状態、中間状態、励起状態の３種類が定義されており、中間状態は任意数定義できます。アプレット中の'states'のチョイスを２にすれば０個の中間状態、３にすれば１個の中間状態が定義され、以下同様です。励起状態はルールによって、その状態を保持、もしくは最上位の中間状態に崩壊します。それぞれの中間状態はルールに関わらず、現在の中間状態の次に低い中間状態に崩壊します。一番下の中間状態はルールに関わらず、基底状態に崩壊します。基底状態はルールによって、その状態を保持、もしくは励起状態に変位します。ルールはセル自身の状態と、ムーア近傍にいくつ励起状態と基底状態があるかで定義します。この様式で定義できるルールは次のものを含みます。
    • Game of Life
      最もよく知られているセルオートマトンです。これは厳密にはgenerationsのルールではないのですがその特別な場合として定義できます。このルールの背景についてはセルオートマトンの歴史をお読みください。
    • Brian's brain
      Brian Silvermanによって発見されたルール。generationsルールの中で最も知られているルールでしょう。
    • StarWars
      Mirek Wojtowicz（MCellおよびMJCellの作者）によって発見されたルール。
    • Transers
      J. M. G. Elliott（Webside CAの作者）によって発見されたルール
    • Dizzy
      webmasterのオリジナルルール．めまいがしてきますのであまり長く見つめないでください．
    以上のルールはアプレット上で簡単に選択できます．また，ユーザーのオリジナルのGenerationsルール定義も可能です．ルールの設定にはruleボタンをクリックして、ルール設定ウィンドウを開いてそこで行って下さい．ルール変更後はinitilalizeボタンで初期化ウィンドウを開き，もう一度初期化してください．
  • fredkin2.html: ２状態Fredkinルール[demo]
    自己複製するセルオートマトン。これはMITのエドワード・フレドキン（Edward Fredkin）によって発見されたルールです。
  • fredkin3.html: ３状態Fredkinルール[demo]
    ちょっと複雑化されたフレドキン・ルール
  • loop.html: ラングトンのループ[demo]
    より複雑な構造の自己複製．詳細はセルオートマトンの歴史の項を参照．
  • cyclic.html: Cyclicセルオートマトンの一例[demo]
    循環的セルオートマトン。波が広がるようなパターンがみれる。これはcyclicセルオートマトンのほんの一例に過ぎません。より詳しく知りたい方は参考文献[Fi90][De89]や、GriffeathのPrimordial Soup Kitchenを参照して下さい。
  • gmbrain.html: GMBrain[demo]
    George Maydwellによって提案されたBrian's Brainの変種
  • life2.html: Life2[demo]
    ゲーム・オブ・ライフを２つ重ねるとどうなるか？
  • ising.html: Ising Model[demo]
    通常のセルオートマトンでは空間内のすべてのセルを同時に更新しますが、このルールは更新するセルをランダムに選択します。このようなダイナミクスは特にモンテカルロシミュレーションと呼ばれています。このルールは統計物理学でお馴染みのイジングモデルのシミュレーションです。ルールボタンをクリックして逆温度betaをいじってランダムにしたり磁化させたりしてみてください。アルゴリズムはM. Creutzによって提案された方法を用いています。詳細は[Cr83]を参照して下さい。またM. Creutz自身によるプログラムXisingもあります。これはXtoysを参照してください。

以下はWebmasterによるオリジナルのセルオートマトンです。これらのいくつかはMJCellやCellspringsでも見れます。
  • aggre.html: Aggregation[demo]
    流体中の分子が徐々に凝集するモデル。
  • aqua.html: Aquarium[demo]
    Webmaster自作のセルオートマトン中で最も評価が高いルール群です。もともとロトカボルテラモデルを基に捕食被捕食関係をセルオートマトンでプログラムしたものです。色々な小動物ような遊泳パターンや渦巻きが見えて楽しいセルオートマトンです。ruleボタンをクリックしてルール編集ウインドウを出してルールを変えてみて下さい。編集ウインドウ内で自作のルール作成も可能ですが、以下の様々なプリセットルールも用意してあります。詳しくは[Su02]を参照して下さい。
    1. Pond: これは最も典型的なAquariumの例です。たくさんの小さな生き物たちが泳いでいるようです。
    2. Lake: Pondより大きな生物を見ることができます。
    3. Plankton: Pondと似ていますが、生き物は魚というよりプランクトンのように見えます。
    4. Tanks: Pondと似ていますが、動いているものは戦車のように見えます。
    5. Birds: 渡り鳥の集団が作るパターンに見えます。
    6. Typhoon: 最初はPondのような穏やかな動きをしますが、最終的に全ての生き物は画面一杯に成長する渦に巻き込まれてしまいます。初期値によって渦ができるまで時間がかかる場合があります。なかなかできない時は画面をrandomに初期化して下さい。
    7. Galaxy: Tyhoonに似ていますが、渦はある大きさで成長が止まってしまいます。ルールの中身はほぼTyphoonと同じで、違うのは赤セルどうしが近傍にいる時それらのセルは生き残れないとしたところだけです。
    8. Wave: Tyhoonに似ていますが、渦は成長過程で潰れる可能性があります。
    9. Honeycomb: 規則正しい定常パターンとカオスパターンが共存する面白いダイナミクス。
  • aquaP2.html: AquariumP2[demo]
    これはAquariumを少し拡張したもので、少し複雑なパターンが見れます。
  • colony.html: Colony[demo]
    少しずつ四角の不動パターンできていきます。時間をかけて見て下さい。
  • knitting.html: Knitting[demo]
    一見規則的なパターンに見えるますが、徐々に変化します。編み物をしているようなパターンに見えるのでこのような名前にしました。
  • butterfly.html: Butterfly[demo]
    蝶のような動きをするCA。自己再生する。
複雑系を研究するには、そこに現れる自己組織化がどのような条件のもとで発生するかを知ることが重要になってきます。セルオートマトンを利用すると様々な自己組織化現象を単純なルールダイナミクスで再現することが可能で、それらの自己組織化を支配する原理が見えてくるかもしれません。

現実の複雑系の中で最も興味深いのはなんといっても生命です。生命体の中で、分子が自発的に作る様々な組織は奇跡としか言い様がありません。セルオートマトンを使って、生命が作り出すような組織を作り出す抽象化学系ができないものでしょうか？ここで私が注目しているのは結晶成長です。たかが結晶成長と思われるかもしれません。それに結晶成長自体は簡単な物理化学実験で作ることができます。でもそれを実現させているアルゴリズムはどのようなものかというと、そう簡単には答えられません。分子を一つ一つ、ピンセットで望みのところにくっつけていくわけにはいきません。小さな分子は自律的に集まってきて生命が必要としているDNA等の高分子を作っていくわけです。様々な規則的パターンの成長、すなわち結晶成長が抽象化学系で実現できれば、生命体の中で使われている”アルゴリズム”を理解するヒントになるのではないかと期待しています。また結晶成長はイギリスの化学者ケアンズ・スミスによって生命の起原の候補の一つにあげられています。[Ca85]

下に結晶成長、すなわち規則的パターンが広がるセルオートマトンを示しています。このようなダイナミクスが起きるのは、セルオートマトンが静的からカオス的に変化する相転移点（カオスの縁とも呼ばれている）であることが分かりました（詳細は[Su99]で）。 結晶は急激な固化ではなく徐々に固化して行く場合に生ずるので、分かってみれば当然のことかもしれません。生命が規則的なパターンを作り出すのに不安定な臨界現象を利用している結果はとても興味深いと思います。この結果はまた、クリス・ラングトンの言った「生命はカオスの縁に」という言葉とも一致しています。

そして、より現実的な結晶成長を模擬するため上記のルールを改良しています。まず、規則的な結晶成長がセル空間全体が一斉に更新されるという偶然から発生しないように、同一時刻で状態が更新されるセルを一つとしてそれを全体からランダムに選択するようにしました。また、結晶成長の担い手である分子が勝手に発生するのではなく、空間から獲得するようにするため質量保存則を組み入れました。
  • acrystal24.html: acrystal24[demo]
    １種類の分子の結晶成長、2x2の４セル内で質量保存するようにルールを設定。
  • acrystal25.html: acrystal25[demo]
    １種類の分子の結晶成長、フォンノイマン型近傍の５つのセル内で質量保存するようにルールを設定。
  • acrystal35.html: acrystal35[demo]
    2種類の分子の結晶成長、フォンノイマン型近傍の５つのセル内で質量保存するようにルールを設定。
上記の３つのルールは試行錯誤によって作成していますので，近傍数が増え，分子種数が増えると規則性を獲得するルール作成がだんだん困難になってきます．

ギャラリーはこれで終りですが，上記の結晶成長の話の続きは筆者の論文[SU03,SU04a,SU04b]で読めますので興味のある方は参照してください．


参考文献

[Ca85] Cairns-Smith, A. G.; "Seven Clues to the Origin of Life", Cambridge University Press(1985).
[Cr83] Creutz, M. "Microcanonical Monte Calro Simulation'", 1983 Phys. Rev. Let. , 50-19, 1411-1414.
[De89] Dewdney A. K. "Computer recreations", 1989 Sci. Am., 261August, 102-105.
[Fi90] Fisch, R.. "Cyclic celluar automata and related process", Physica D 45, 19-25 (1990).
[Su99] Suzudo, T. "Crystallisation of two-dimensional cellular automata", Complexity International,Vol. 6 (1999). to download pdf-formatted file
[Su02] Suzudo, T. "Diversity of complex systems produced by a class of cellular automata", 6th International Conference on Complex Systems (CS02), Tokyo, September (2002). (to download pdf-formatted file)(1,113kB)
[SU03] 鈴土知明 ”質量保存則を有する非同期セルオートマトンの空間パターン形成と遺伝的アルゴリズムによる探索”，情報処理学会研究会報告，2003-MPS-47(4), 13(2003). (to download pdf-formatted file of the paper)(388kB)
[SU04a] 鈴土知明 ”非同期セルオートマトンの創発的パターン形成”，信学技報，NLP2003-168, 2004-3, 55(2004). (to download pdf-formatted file of the paper)(539kB)
[SU04b] Suzudo, T. "Spatial Pattern Formation in Asynchronous Cellular Automata with Mass Conservation", to be published in Physica A.

[CA] [CA] [CA] [CA]

Last Modification on 22, June, 2004