セルオートマトンにはまってる今日この頃。
社会シミュレーションの本より
ことのはじまりは、本棚の奥に眠っていた、「社会シミュレーションの技法」を手に取ったこと。
- 作者: ナイジェルギルバート,クラウス・G.トロイチュ,Nigel Gilbert,Klaus G. Troitzsch,井庭崇,高部陽平,岩村拓哉
- 出版社/メーカー: 日本評論社
- 発売日: 2003/02
- メディア: 単行本
- クリック: 5回
- この商品を含むブログ (2件) を見る
この本は、その名の通り、社会シミュレーションの一般的な方法をコードを交えながら零時をあげながら解説してくれている本です。
扱っている内容としては、セルオートマトンの他にも待ち行列シミュレーション何かも含まれています。
今回改めて調べて分かったのですが、この本は既に絶版らしいです。
良い本だと思うけど、やはり需要薄なのでしょうか。
他にもセルオートマトンの本はあるものの、それほど数は無い模様。みんな興味ないのかな、面白いのに・・・
セルオートマトンとは
そもそもセルオートマトンとは、セルごとにONとOFFの定義された空間において、そのON/OFFをある決められたアルゴリズムを持って変遷させるモデルといったところでしょうか。
私の貧弱な説明だとアレなので、ほかにwikipediaでは以下のように説明されています。
セル・オートマトン(英語:cellular automaton、略称:CA)とは、格子状のセルと単純な規則による、離散的計算モデルである。計算可能性理論、数学、物理学、複雑適応系、数理生物学、微小構造モデリングなどの研究で利用される。非常に単純化されたモデルであるが、生命現象、結晶の成長、乱流といった複雑な自然現象を模した、驚くほどに豊かな結果を与えてくれる。
さすが、wikipediaです。最後の「驚くほど豊かな結果」と言うのが、このセルオートマトンの魅力です。
セルオートマトンを書いてみた
さて、この本で改めてセルオートマトンについて気になったので、このところセルオートマトンの代表的なモデルなんかをコードに起こして書いてみたりしています。
ちなみに言語はCです。特に深い意味はありませんが、何となく実行時間がかかるような計算だと思ったので、でもよく考えればこのくらいだったらPythonあたりで書いても普通に問題なく速い気がする。
書いてみたのは下の3つ。
- ライフゲーム
- うわさ伝搬シミュレーション
- 多数決シミュレーション
ちなみに、これらすべて2次元セルオートマトンです。
ライフゲーム
ライフゲームはセルオートマトンのモデルの中で最も有名なものと言って間違いないと思います。
アルゴリズムは以下の通り
- 死んでいるセルにとなりあったセル3個が生きたセルならば誕生。
- 生きたセルに隣り合う生きたセルが2or3個ならば生き残る。
- 生きたセルに隣り合う生きたセルが4個以上ならば過密により死滅。
- 生きたセルに隣り合う生きたセルが1個以下ならば過疎により死滅。
たったこれだけです。
これだけ単純なアルゴリズムにも関わらず、セルの描く模様は驚くほど多彩な動きを見せます。
中には、名前が付いている模様まであり、長い間見ていても飽きません。
いつか、自分のマシンの壁紙を動くライフゲームにするのが夢だたりします。
(割と今すぐ実現可能な気がするけどやってない。)
うわさ伝搬モデル
うわさ伝搬シミュレーションのアルゴリズムは、生きたセルに隣り合ったセルを一定確率で誕生させるというもの。
中心の1セルから正に噂が広がっていくように徐々に生きたセルが広がっていくのがわかります。
広がる確率などをいじることによって、広がりの形状の変化などもシミュレーションから得ることができます。
また、逆に忘却率を与え、一定確率で生きたセルが死滅するようにしておいても面白いです。
うわさ伝搬シミュレーションとしましたが、このシミュレーションの発展を眺めていると他の物理現象や社会現象の中にも現れるような普遍的な印象を受けます。
多数決モデル
最後に多数決シミュレーションのアルゴリズムは隣接するセルのうち生きているマスが多ければ生きており、死んでいるセルの方が多ければセルが死んでいる。また、生死同数であれば、現状維持というようなもの。
なお、初期状態としては全体に乱数でランダムな分布を与えています。
すると、ステップを重ねるごとに徐々に全体の模様が荒くなっていきます。
これは乳化した油(ペペロンチーノ作るときのあれ)が徐々に2相に戻っていく様子などが当てはまるモデルのようです。
ただし、問題が一つ。
どうやら変化はログスケールで遷移するらしく、1000ステップを超えたぐらいからさほど変化がなくなっていくという問題。
なので、どんどん模様が変化していくのが楽しめるというよりは、少し荒くなったところで計算時間の壁に阻まれてしまうといった感じです。
できれば100000ステップ以上も試してみたいですが、そのためには結構時間がかかりそうです。(少なくとも数日は必要?)
本当に驚くほど豊富な結果
以上がだいたい試してみたアルゴリズムになります。
確かに簡単なアルゴリズムから驚くほど豊富なシミュレーション結果が現れています。
もっとちゃんと勉強すればちゃんと研究レベルまで持ってくことも可能でしょうか?
自分の専門でも、セルオートマトンの応用例が無いか探してみたいと思います。
ただ一方で、描画に苦戦中
そんなわけで、一通りのセルオートマトンのコードを書いてみて遊んでいますが、実はその主題とは別のところで苦戦しています。
何かというと、上手い描画方法が思いつかない!
だからせっかく作っても綺麗な画像が無いんです。
現在は、仕方なく簡単なヘッダ処理で直接出力可能な白黒のビットマップ形式(pbm)で出力していますが、これはあまり一般的な形式ではないらしく、Ubuntuなどでは表示できるのですが、Macではいまいち上手く表示できません。(OpenOfficeを使えば表示と変換が可能。)
そのため、このページに載せられるような画像としては出力できていません。
自分はあまり画像処理などの知識を有していないため、jpegやらpngのヘッダを出力したりする力が無いです。(探せばライブラリとかありそうだけど)
ああ、非力・・・
Webアプリとして形にしたい
なので、もっとちゃんとしたレンダリングツールなり描画ソフトなりを使う必要があると思います。
できれば、アニメーションとかを使って遊べるとありがたいです。
そこで、少し考えて思い当たったのがJavascriptあたりを上手いこと使ってブラウザ上で表示してくれるWebアプリのようなものを書けたらなと思っています。
とはいえ、Javascriptをほとんど書いたことがないので、なかなか険しい道のりになりそうですが、年末年始を利用してちょっと取り組んでみたいと思います。