第７回 セルオートマトンモデル（１１月２２日）
＊出席確認
＜出席確認メール＞ 添付ファイルなし 受付：本日１４：３０〜１７：４５
本日のキーワードは授業中に連絡します。
宛先：miwamoto[at]riko.shimane-u.ac.jp
件名：MMM2 20161122
本文： 学生番号 名前 「本日のキーワード」
セルオートマトンとは
セルオートマトン（cellular automata、CA）は、計算理論、数学、物理学、複雑系、理論生物学などで研究された離散モデルである。1940年代にスタニスラフ・ウラム（Stanislaw Ulam）とジョン・フォン・ノイマン（John von Neumann）によって発見され、1970年代には２次元セルオートマトンのコンウェイのライフゲーム（Game of Life）が有名となった。 1980年代、Stephen Wolframは1次元セルオートマトンを体系的に研究し、これはのちに「複雑系」という新たな分野を作り出す革新的な研究となった。
貝殻の模様
「イモガイ（またはConus）」で検索してみよう。
貝殻は炭酸カルシウムなどからできており、貝殻の縁に沿って細く帯状に存在する色素細胞のそれぞれは、隣の細胞が色素を分泌するか抑制するかによってその細胞自身が色素を分泌するかどうかが決まるという。ゆっくりとした成長と共にこのような反応が起こると、貝殻の縁に沿う細胞の帯は貝殻の表面に模様を残す。
自然界や社会には、このような「局所的なルールに基づいて相互作用した結果、大域的な秩序が形成される」例がよくみられる。このような現象を自己組織化という。
１次元セルオートマトン
簡単のため、横一列にセルが並んでいて、各セルが２つの状態、色素を分泌する（１）or 色素を分泌しない（０）のうちどちらかの状態を取るとする。状態１を黒で、状態０を白で表すこととする。
初期状態と状態変化のルールが設定されれば、そのルールに基づいて時間発展と共に、その時間における状態が決定される。
状態変化の（局所的な）ルールが、隣り合う３つのセルから決定されるとする。つまり、注目するセル（真ん中のセル）と両隣の２つのセルの状態から、次の注目するセルが０となるか１となるかが決定されるとする。
この場合、３つのセルが取りうる状態は以下の８パターンである。
それぞれのセルでは、０か１の２状態であるので、この８パターンを３桁の２進数と考えることができる。３近傍からなる８パターンは、０番目〜７番目という風に名付けることができる。
貝殻の模様→Rule30
クボガイのような貝殻の模様は、次の状態変化のルールで作られることが知られている。
例えば、左端は、
「現在の３つの隣接するセルの状態が 000 であれば、未来の中央のセルは0に決まる」
ということを意味している。
このルールは、
と計算できるため、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
という７つの配列が用意される。
周期境界条件
このような３近傍からなるルールを計算が破綻することなく実現するためには、一列ずつ並んだセルの左端と右端に仮想のセルを１つずつ用意しておく必要がある。
この状態を記憶する変数をcellというint型の配列として準備すると、実際に考えるセルが100個であれば、配列はその+2の102個必要ということである。
int cell[] = new int[102];
左端のセル（0番目）は、右端の（仮想でない）セル（100番目）と同じであるとし、
右端のセル（101番目）)は、左端の（仮想でない）セル（1番目）と同じであるとする。
これは下のようなセルが和になったような状態を表しており、このような境界（端）の条件を周期境界条件と呼ぶ。
つまり、仮想のセルの状態を
cell[0] = cell[100];
cell[101] = cell[1];
と定義する。
ルールの適用
現在の隣接３セルの状態を０〜７で表す。
例えば、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);//各自計算スピードを調整してください。
初期状態の設定：各セルの状態を表す配列に（ランダムに）０か１を入れる
周期境界条件
初期状態の描画（０であれば白、１であれば黒）
}
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");
}
練習１ Rule30のセルオートマトンを使って、以下のような貝殻の模様を再現せよ。
車の渋滞→Rule184
車の動きは、次のような特徴がある。
・前方が空いていれば進む
・前方が空いていなければその場に留まる
右向きを前方として考え、車がいるセルを１、いないセルを０とすれば、このルールはRule184となる。
渋滞現象が起きるのは、密度（車の台数／セルの数）が0.5以上の時であることが知られている。また、渋滞の塊は、進行方向とは逆方向に進むことが知られ、実際の道路ではその速度は約時速20 kmであることが知られている。
本日の課題 Rule184のセルオートマトンを使って、以下のように車の動きを再現せよ。車の数を増やすと渋滞が起きることを確かめよ。
ウルフラムクラス
ウルフラムは、１次元セルオートマトンのそれぞれのRuleから得られる結果を以下の４つに分類し、自然界の現象はクラス３や４のようにカオティックなものであることを示唆した。
クラス 1 （線形系） 単一の平衡状態に収束する。（全てのセルが0 または 1 になる）
クラス 2 （非線形系 ・周期解） 縞模様のように無限に繰り返すパターンに収束する。
クラス 3 （非線形系 ・カオス） 単一の状態にも、周期的な状態にも収束しない。
クラス 4 （非線形系 ・その他） 予測困難な複雑なパターンで、周期・非周期が交互に現われたりパターンが消えたりする。