mmm2

  第7回 セルオートマトンモデル(11月22日)



*出席確認

<出席確認メール> 添付ファイルなし 受付:本日14:30〜17:45

本日のキーワードは授業中に連絡します。


宛先:miwamoto[at]riko.shimane-u.ac.jp

件名:MMM2 20161122

本文: 学生番号 名前 「本日のキーワード」



セルオートマトンとは


 セルオートマトン(cellular automata、CA)は、計算理論、数学、物理学、複雑系、理論生物学などで研究された離散モデルである。1940年代にスタニスラフ・ウラム(Stanislaw Ulam)とジョン・フォン・ノイマン(John von Neumann)によって発見され、1970年代には2次元セルオートマトンのコンウェイのライフゲーム(Game of Life)が有名となった。 1980年代、Stephen Wolframは1次元セルオートマトンを体系的に研究し、これはのちに「複雑系」という新たな分野を作り出す革新的な研究となった。



貝殻の模様


「イモガイ(またはConus)」で検索してみよう。

 貝殻は炭酸カルシウムなどからできており、貝殻の縁に沿って細く帯状に存在する色素細胞のそれぞれは、隣の細胞が色素を分泌するか抑制するかによってその細胞自身が色素を分泌するかどうかが決まるという。ゆっくりとした成長と共にこのような反応が起こると、貝殻の縁に沿う細胞の帯は貝殻の表面に模様を残す。


 自然界や社会には、このような「局所的なルールに基づいて相互作用した結果、大域的な秩序が形成される」例がよくみられる。このような現象を自己組織化という。



1次元セルオートマトン


 簡単のため、横一列にセルが並んでいて、各セルが2つの状態、色素を分泌する(1)or 色素を分泌しない(0)のうちどちらかの状態を取るとする。状態1を黒で、状態0を白で表すこととする。

fig7-1


 初期状態と状態変化のルールが設定されれば、そのルールに基づいて時間発展と共に、その時間における状態が決定される。

 状態変化の(局所的な)ルールが、隣り合う3つのセルから決定されるとする。つまり、注目するセル(真ん中のセル)と両隣の2つのセルの状態から、次の注目するセルが0となるか1となるかが決定されるとする。


fig7-2



この場合、3つのセルが取りうる状態は以下の8パターンである。

fig7-3


それぞれのセルでは、0か1の2状態であるので、この8パターンを3桁の2進数と考えることができる。3近傍からなる8パターンは、0番目〜7番目という風に名付けることができる。

fig7-4




貝殻の模様→Rule30


 クボガイのような貝殻の模様は、次の状態変化のルールで作られることが知られている。

例えば、左端は、

「現在の3つの隣接するセルの状態が 000 であれば、未来の中央のセルは0に決まる」

ということを意味している。

fig7-5


このルールは、

 

 

 

と計算できるため、Rule30と呼ばれている。

プログラムでは、このルールを配列で覚えておく。

int rule[] = {0,1,1,1,1,0,0,0};

これによって、

rule[0]=0

rule[1]=1

rule[2]=1

rule[3]=1

rule[4]=1

rule[5]=0

rule[6]=0

rule[7]=0

という7つの配列が用意される。



周期境界条件


このような3近傍からなるルールを計算が破綻することなく実現するためには、一列ずつ並んだセルの左端と右端に仮想のセルを1つずつ用意しておく必要がある。

fig7-8


この状態を記憶する変数をcellというint型の配列として準備すると、実際に考えるセルが100個であれば、配列はその+2の102個必要ということである。

int cell[] = new int[102];

左端のセル(0番目)は、右端の(仮想でない)セル(100番目)と同じであるとし、

右端のセル(101番目))は、左端の(仮想でない)セル(1番目)と同じであるとする。

これは下のようなセルが和になったような状態を表しており、このような境界(端)の条件を周期境界条件と呼ぶ。

fig7-9

つまり、仮想のセルの状態を

cell[0] = cell[100];

cell[101] = cell[1];

と定義する。



ルールの適用


fig7-5

 

現在の隣接3セルの状態を0〜7で表す。

例えば、50番目のセルの状態pは

 int p = 4*cell[49]+2*cell[50]+1*cell[51];

と計算できる。


cellを現在のセル状態を表す配列とすると、未来のセル状態を表す配列も必要である。

int newCell[]  = new int[102];


未来の50番目のセルの状態newCell[50]は、pの値によって決まる。ここで、ルールは、

int rule[] = {0,1,1,1,1,0,0,0};

と決めたので、例えば、pが4であれば1を入れるわけであるが、それはrule[4]=1を入れるということである。よって、

 newCell[50] = rule[p];

と考えることができる。



アルゴリズム



セルの数を宣言(CELLNUM)

セルの状態を表す配列を宣言(現在)

セルの状態を表す配列を宣言(未来)

int rule[] = {0, 1, 1, 1, 1, 0, 0, 0}


void setup()

{

 ウィンドウサイズ設定

  frameRate(10);//各自計算スピードを調整してください。


初期状態の設定:各セルの状態を表す配列に(ランダムに)0か1を入れる

周期境界条件

  

初期状態の描画(0であれば白、1であれば黒)

 }


void draw()

{

    for (int i = 1; i <= CELLNUM; i++)

  {

   ルールの適用

  }


    for (int i = 1; i <= CELLNUM; i++)

  {

    現在のセルに未来のセルを代入

  }

 周期境界条件


 描画


 if (frameCount == 100) noLoop();

}



画像の保存

プログラムの最後に次のコードを入れておけば、pを押した時に画像が保存される。

void keyPressed()

{

 if(key == 'p') saveFrame("filename.tif"); 

}


練習1 Rule30のセルオートマトンを使って、以下のような貝殻の模様を再現せよ。






車の渋滞→Rule184



車の動きは、次のような特徴がある。

前方が空いていれば進む

・前方が空いていなければその場に留まる

右向きを前方として考え、車がいるセルを1、いないセルを0とすれば、このルールはRule184となる。


 


渋滞現象が起きるのは、密度(車の台数/セルの数)が0.5以上の時であることが知られている。また、渋滞の塊は、進行方向とは逆方向に進むことが知られ、実際の道路ではその速度は約時速20 kmであることが知られている。


本日の課題 Rule184のセルオートマトンを使って、以下のように車の動きを再現せよ。車の数を増やすと渋滞が起きることを確かめよ。





ウルフラムクラス


ウルフラムは、1次元セルオートマトンのそれぞれのRuleから得られる結果を以下の4つに分類し、自然界の現象はクラス3や4のようにカオティックなものであることを示唆した。


クラス 1 (線形系) 単一の平衡状態に収束する。(全てのセルが0 または 1 になる)

クラス 2 (非線形系 ・周期解) 縞模様のように無限に繰り返すパターンに収束する。

クラス 3 (非線形系 ・カオス) 単一の状態にも、周期的な状態にも収束しない。

クラス 4 (非線形系 ・その他) 予測困難な複雑なパターンで、周期・非周期が交互に現われたりパターンが消えたりする。 



グループワークについて