本日の目標 パターンを作る セル オートマトン ライフゲーム

Transcription

1 数理生物学演習 第 10 回セル オートマトン

2 本日の目標 パターンを作る セル オートマトン ライフゲーム

3 セルオートマトン (CA:Cellular Automaton) 生命現象によく見られる 自己組織化 を表現するために作られたモデル 格子状に並ぶ数値 ( セル ) を 局所的ルールの下で変化させ続ける 単純さの割に面白い結果が出るので プログラムの練習にはうってつけ!

4 セル オートマトン Cellular Automaton セルの 状態 を, 局所的なルールに従い更新してゆくことで, 計算 を行う離散的なモデル 1 次元セル オートマトン 仮定 セルが 1 次元的に並んでいる セルは状態 0 または 1 のいずれかをもつ セルは自身と近傍の状態により次のステップでの状態が決まる ある時間での セルの状態 時間発展を記録していく

5 初期条件と境界条件について 初期条件 時間発展するシステムを計算する場合 初期値の決め方 を考える必要がある CAの場合 中央だけ 1 か あるいは全部ランダムに割り振るなどすれば良い 境界条件 空間構造のあるシステムを計算する場合 端の値の決め方 を考える必要がある CAの場合 両端を常に 0 か あるいは右端と左端が隣接しているという扱いにすれば良い 周期境界条件と呼ばれる ( イメージ )

6 1 次元セル オートマトン 遷移ルール (2 近傍 ) 状態 0 状態 1 例 1 場所 j-1 j j+1 場所 j-1 j j+1 時間 i i+1 時間 i i+1 自分が状態 0 で 左隣が状態 0 で 右隣が状態 0 なら次は状態 0 になる 自分が状態 0 で 左隣が状態 0 で 右隣が状態 1 なら次は状態 1 になる

7 1 次元セル オートマトン 遷移ルール (2 近傍 ) 状態 0 状態 1 一次元セルオートマトンのルールにはすべて名前が付いている ルールを次のような表に書いたとき 次の時刻の内部状態を並べると二進数になっている これを十進数に直したものがルールの名前になる 隣り合う 3 つのセル (2x2x2) の状態によって次のセルの状態が決まる 8 個の場合について 0 か 1 か決めるので 2^8=256 通りのルールが考えられる =178 ルール 178

8 ウルフラムのクラス Wolfram (1983) クラス 1 セルの状態が すべて同じになり, 変化が起こらない. クラス 2 安定したパタンに落ち着き変化が 周期的になる. クラス 4 あるときは規則的なパタンを示し, あるときはランダムに振る舞う. クラス 3 全体がランダムに振る舞う. ただし, 決定論的. 平衡点 リミットサイクル 複雑系 カオス 秩序 安定 クラス 4 で 複雑さ が最大になる 生命現象はここにあるのかも? 無秩序 不安定

9 ライフゲーム Conway s Game of Life 2 次元のセル オートマトンの特殊な場合 かなり, 色々なパタンが観察できる 仮定 各セルは状態 生 と 死 をもつ 誕生, 生存, 死亡のプロセスを経て, 生 と 死 の状態を更新する 8 近傍のセルの状態により次の状態がきまる 遷移ルールは誕生, 維持, 過疎, 過密の 4 つ 誕生 過疎 8 近傍中 ちょうど 3 つが 生 ならば 次のステップで 生 8 近傍中 生 が 1 つ以下ならば 次のステップで 死 維持 過密 8 近傍中 ちょうど 2 つが 生 ならば 次のステップで更新なし 8 近傍中 生 が 4 つ以上ならば 次のステップで 死

10 ライフゲームにみられるパタン 固定物体 still life ブロック 銃 guns グライダー銃 振動子 oscillators ブリンカー 長寿 methuselahs ダイハード

11 情報処理センター講義室へ移動!

12 1 次元セルオートマトン // 次元セル オートマトン #include <stdio.h> int main(void){ int t,i; int cell[100]; int tempcell[100]; FILE *fp; fp=fopen("ca.txt","w"); // 配列の初期化 for(i=0;i<100;i++){ cell[i]=0; tempcell[i]=0; // 初期条件 cell[50]=1; for(i=0;i<100;i++){ fprinx(fp,"%d ",cell[i]); fprinx(fp,"\n"); for(t=;t<100;t++){ // 一番左, セル 0 if(cell[99]==1){ if(cell[0]==1){ f(cell[1]==1){ tempcell[0]=1; if(cell[1]==0) { tempcell[0]=0; if(cell[0]==0){ if(cell[1]==1){ tempcell[0]=1; if(cell[1]==0) { tempcell[0]=1; 関数 rule の定義 if(cell[99]==0){ if(cell[0]==1){ if(cell[1]==1){ tempcell[0]=0; if(cell[1]==0) { tempcell[0]=0; if(cell[0]==0){ if(cell[1]==1){ tempcell[0]=1; if(cell[1]==0) { tempcell[0]=0; // 中 for(i=1;i<99;i++){ if(cell[i- 1]==1){ if(cell[i]==1){ if(cell[i+1]==1){ tempcell[i]=1; if(cell[i+1]==0) { tempcell[i]=0; if(cell[i]==0){ if(cell[i+1]==1){ tempcell[i]=1; if(cell[i+1]==0) { tempcell[i]=1; あまり賢い関数の定義の仕方ではない. 余裕のある人はもっと優れた実装方法を 考えてみてください.

13 1 次元セルオートマトン 続き if(cell[i- 1]==0){ if(cell[i]==1){ if(cell[i+1]==1){ tempcell[i]=0; if(cell[i+1]==0) { tempcell[i]=0; if(cell[i]==0){ if(cell[i+1]==1){ tempcell[i]=1; if(cell[i+1]==0) { tempcell[i]=0; // 一番右,99 if(cell[98]==1){ if(cell[99]==1){ if(cell[0]==1){ tempcell[99]=1; if(cell[0]==0) { tempcell[99]=0; if(cell[99]==0){ if(cell[0]==1){ tempcell[99]=1; if(cell[0]==0) { tempcell[99]=1; if(cell[98]==0){ if(cell[99]==1){ if(cell[0]==1){ tempcell[99]=0; if(cell[0]==0) { tempcell[99]=0; if(cell[99]==0){ if(cell[0]==1){ tempcell[99]=1; if(cell[0]==0) { tempcell[99]=0; /* 情報の更新と出力 */ for(i0;i<100;i++){ cel[i]=tempcell[i]; fprinx(fp,"%d ",cell[i]); fprinx(fp,"\n"); /* 情報の更新と出力ここまで */ fclose(fp); return 0; ルール178

14 周期境界条件 端 同士が張り合わされていると考える. プログラムを組むときも, この部分の処理は注意! 固定端 端 の値を与えて, 変動しないとする. 例えば, この端で常に状態 0

15 エクセルのヒント 1. データを貼付けた後 列の幅を調整してセルを正方形にする 表の左上の角を押して全選択をする 列 A と B の間をダブルクリック

16 ズームアウトして全体像を見る 示する この数字を 35 に変更

17 条件付き書式で値が 1 のセルだけ強調表示する あとは OK を押す

18 ライフゲーム 9-2. ライフゲームのプログラムを組んでみてください. 境界条件は周期を採用してください 格子のサイズは で作ってください. 誕生 やるべきこと 初期条件の設定 状態遷移ルールの実装 境界条件の処理 結果の出力 過疎 8 近傍中 ちょうど 3 つが 生 ならば 次のステップで 生 8 近傍中 生 が 1 つ以下ならば 次のステップで 死 維持 過密 8 近傍中 ちょうど 2 つが 生 ならば 次のステップで更新なし 8 近傍中 生 が 4 つ以上ならば 次のステップで 死

19 二次元配列 n 個 データ型配列名 [m][n]; データ型 int とか double のこと m 個 n-2 n m-2 m-1 配列名 [m-2][2] という名前のデータ型変数 m n 個のデータ型変数が作られるただし 要素の番号は 0 から始まる int x[2][4]; と宣言すると8 個のint 型変数 x[0][0] x[0][1] x[0][2] x[0][3] x[1][0] x[1][1] x[1][2] x[1][3] が作られる for(i=0;i<2;i++){ for(j=0;j<4;j++){ を使って初期化する

20 ライフゲーム ( ヒント ) いろいろな初期配置を試してみましょう 境界の部分は自分で行列を書いて確認しましょう // 配列の初期化 for(i=0;i<50;i++){ for(j=0;j<50;j++){ cell[i][j]=0; tempcell[i][j]=0; // 初期条件 for(i=0;i<50;i++){ for(j=0;j<50;j++){ if(i+j<50){ cell[i][j]=1; for(i=0;i<50;i++){ for(j=0;j<50;j++){ fprinx(fp,"%d ",cell[i][j]); fprinx(fp,"\n"); for(i=1;i<49;i++){ for(j=1;j<49;j++){ live=0; //8 近傍の様子を確認 if(cell[i- 1][j- 1]==1){ live++; if(cell[i- 1][j]==1){ live++; if(cell[i- 1][j+1]==1){ live++; if(cell[i][j- 1]==1){ live++; if(cell[i][j+1]==1){ live++; if(cell[i+1][j- 1]==1){ live++; if(cell[i+1][j]==1){ live++; if(cell[i+1][j+1]==1){ live++; // セル i,j の次の状態の決定 if(live<=1){ tempcell[i][j]=0; if(live==2){ tempcell[i][j]=cell[i][j]; if(live==3){ tempcell[i][j]=1; if(live>=4){ tempcell[i][j]=0;

21 ライフゲーム エクセルを使ってアニメーションを表現しますが ちょっと設定が複雑なので あらかじめファイルを用意しておきました のページへ行き 課題用エクセルファイル をクリックしてダウンロードしてください そのあと 出力結果 のシートに結果を貼付けてください

22 お知らせ 次回は 6/29( 月 ) です

23 ライフゲーム i=1 48, j=1 48 はヒントにあるやり方で出来る i=0, j=0 i=49, j=49 i=0, j= i=0, j=49 i=1 48, j=49 50 i=49, j=49

24 スクリーンショットの取り方 1) shia + command + 4 を同時押し 2) 撮りたい範囲をドラッグする 3) デスクトップにファイルが出来て いるはず