            ½  ゆらぎによるセルオートマトンの進化        蜷川 繁  金沢工業大学 情報工学科

                                                                                                                                      !
  "
 # 
類できる  次元 $ 状態 6 近傍セルオートマトンを探索する研 はじめに究 ,:   %* :   %-. があり，現在までに知られていライフゲームは $ 次元 $ 状態 % 近傍セルオートマトンの一るセルオートマトンのなかでは最良の「 ";# ルール」とよば種であり，あるセルの状態を  とし ，そのセルの周囲 & セルれるセルオートマトンに近い振る舞いをするものが得られてのうち状態が  のセル数を  とすると，次の時刻でのセルの状いる．
態を示す状態遷移関数 ' ( は次のように表される．
 適合度の計算') *( + ' $( + ' *( +   + ) 

与えられたセルオートマトンにおいて，ある初期様相から遷移規則にしたがい， ステップにわたって状態遷移を行う．時
刻  における位置   のセルの状態を    とすると，次式によりセル   のパワースペクトル    を求める．

'(' (' (遷移規則はこのように単純であるにもかかわらず，ライフゲームには，セル平面上を伝播する「グライダー」と呼ばれるパターンをはじめ，種々の興味深いパターンが存在するこ．さらに，グライダー列をとが知られている
デジタル信号とみなすことにより，セル平面上に論理演算回路やレジスタ等を構成できることから，じゅうぶん広いセル平面上で汎用コンピュータを作ることができると予想されてい．
る
いっぽう，ライフゲームにおいて，ランダムな初期様相から状態遷移させ，セルの時系列データからパワースペクトルを求．
めると，  ゆらぎを示すことが知られている
 ゆらぎはパワースペクトルが周波数  に反比例すること
年に真空管を流れる電流にからその名がつけられたが，おいて初めて報告されて以来，種々のシステムや現象において観測されているにもかかわらず，その発生のメカニズムには未だに不明の点が多い．
以上のことから，セルオートマトンにおける  ゆらぎと計算万能性との間には何らかの関連性があることが予想されるが，  ゆらぎを示すセルオートマトンはあまり知られていないので，この予想を検証するためには，そのようなセルオートマトンを探し出し，それらのセル平面上で計算機が構成できることを示す必要がある．そこで，本研究では  ゆらぎを示すセルオートマトンを探索することを目的とする．ライフ
ゲームのような 次元 状態 近傍外総和型のセルオートマ

種類あり，全数探索は不可能
トンは全部で ）を用なので，遺伝的アルゴ リズム（を用いて目的の振る舞いを示すセいる．本研究のように，ルオートマトンを探索する研究としては，初期様相の密度を分,  &-.

< ' (+   ,/ ! &$.


%$1$$' (' $ (' + )      $(  

これを次式のように全セルにわたって和をとり，パワースペクトル  を求める．

,0  %&.

+<  ' ('$(+))))$+&)))



本研究では，セル空間は縦 横個のセルからなの状態が等確率で出現するようにランダムり，初期様相はに生成し ，境界条件としてセル平面が 次元トーラスとなるの場合のライフゲームの周期境界条件を用いている．
パワースペクトルを図 に示す．パワーが周波数に反比例する  ゆらぎを示していることがわかる．
を適用するためには，遷移規則に対して，適合度を求式によって得られたパワースペめる必要がある．そこで，
 に対して，最小 乗法を用いてクトルの周波数域    と近似し，式により残差平方和  を求める．

)'(< '("3'$(+ ' ( + = ' ($ %$ 2$  )"  3  4"3"3



35 金沢工業大学情報工学科，石川県石川郡野々市町扇が丘 6，
 7 !8 9+'*($' ' (     ' (('*(ここで， は   を求める際に用いるデータ数である．さより，適合度  を求める．
らに式'-(½             ln(Sf) = a - 1.4021 ln(f)10Sf

10.10.001
10100f5$ -)$

1000

10000+ ) に
' ( + = ' ( ++   )+  = Æ

本研究で対象となるセルオートマトンは，自分自身のセルの状態と周囲のセルにおける種々の状態のセルの個数だけで次）とよばれの時刻での状態が決まる外総和型（るものである． 次元 状態 近傍外総和型セルオートマトンの遷移関数  は次式で表現される．

%') ( +   ' ( +     ' + )      &('1(&') )( + )6

ここで  の第一引数は自セルの状態を示し ， は周囲 セルのうち，状態が のセル数を表す．本研究では  という遷移規則のみを対象とするので，遷移規則はビット     で表現することにする．この記法では，ライフゲーとなる．
ムの遷移規則はセルが取り得る状態数を  とすると がもっとも均質 はもっとも不均質なルールを表す．
なルールとなり，
そこで，初期集団として用いる遷移規則はをみたすように，ランダムに生成する．
ライフゲームにおいてランダムな初期様相から状態遷移させると，多くの場合に周期 および の周期的に変動するパターンのみが残る．したがって，ライフゲームにおいては様相が周期 になることによって安定状態になったことがわかる．の周期境界条件を用いた場合，安定状態にセル数がであることがわかっなるまでの平均過渡ステップ数は約．さらに  ゆらぎの持続ステップ数はそのている 蜷川倍となる 蜷川．
約ステップ程度に渡りパワースペクトル
そこで最低でもを求める必要があるが，そのためには膨大な計算時間が必要となる．そこで，ランダムに生成した初期集団に対し ，の場合にパワースペクトルを求め，最小 乗法を用いてにわたって    と近似し，となる遷移規則だけを取り出す．こうすることによってあらかじめ， ゆらぎから大きくはずれたものを除外することができる．

2))))))))))))))+ $))  )), ).
*2, )$.
6$)))$+ -))' (++)
 &   % &6)



本研究ではセルオートマトンのパワースペクトルが  ゆらぎに近いほど ，高い値をとる適合度を用いることによって， ゆらぎを示すセルオートマトンを見つけることが出来た．
特に， 番目に高い適合度をもつ遷移規則は，ライフゲームに極めて近い振る舞いをすることがわかった．このことは，セルオートマトンにおける計算万能性と  ゆらぎの関係を示唆しているといえる．
今後は，試行回数を増やすとともに，もっとも高い適合度をもつが必ずしも，  ゆらぎに近いとはいえないことから，適合度については，特に低周波域での振る舞いを反映するように修正する必要があると思われる．



$)))

 ) *)( おわりに*$+ *)))))*%*- +  -)$ + 6 $1&  )'%%2)% + ) 1&22 + 1 &6%  ))))))))))) 22& + ) $&% + - $1-  )))))))))) $$*))))$*$ 6,> .
*16*&1 +  )1)& +  &*) ))))))))))))) * )))*') &( + ') 6( +  実験$+ )*)

ここで，Æは分母がゼロになることを避けるための項である．このように適合度を決めることによって，パワースペクトルが  ゆらぎに近い個体ほど大きな適合度をもつ．

$+ &)))


現在のところ通りの初期集団に対して合計世代まで実験が進んでいる．
現在までに得られた遷移規則の中で，もっとも高い適合度（ ）をもつ遷移（とよぶ ）と，次に高い適合度規則（ ）をもつ遷移規則（とよぶ）のパワースペクトルを図（上），図 （上）にそれぞれ示す．しかし，これらのパワースペクトルは低周波域で傾き  がいずれも に近いため，  ゆらぎとはいえない．また，同じ初期様相を用いた場合のステップにおける様相を図 （下），図 （下）にそれぞれ示す．にはライフゲームのグライダーのような伝播するパターン．
はなく， には 種類の伝播パターンが存在する
番目に高い適合度（ ）をもつ遷移規則（とよぶ）のパ（ 上）に示す．このパワースペクトル
ワースペクトルをに近いことから  ゆらぎといえは低周波域で傾き  がステップにおける様相を図 （下）に示す． の遷る．
 である点を除けばライフゲーム移規則は  と同じである．これらの違いは近傍における状態 の密度が極めて高い場合にしか，影響をおよぼさないので，ライフゲームと同じような振る舞いをする．事実，この遷移規則ではライフゲームと同じグライダーが観測された．

'-(

 実験結果

図ライフゲームのパワースペクトル．点線は  おいて最小 乗法で近似した直線．

 + &))))20.011-)

こうして得られた遷移規則を個まとめて 集団とし ，としてパワースペクトルから，先ほどと同様に  と  を求める．本研究ではライフゲームよりも長いステップに渡り ゆらぎを示すセルオートマトンを見つけることを目指していとした．また， については，低周波域での振るのでとし，  については，スペクトる舞いを調べるために ル全体が  ゆらぎに近いかど うか調べるために，とする．選択はルーレット選択 エリート数はとし，交叉の一様交叉とし，ビット当たりの突然変異確率は確率とした．図 に示されたパワースペクトルから求めたライフ（ ）
ゲームの適合度はだった．

100*+謝辞 本研究は統計数理研究所共同研究プログラム（）に基づいて行われた．

)))6

参考文献

6共研,  &-.   5  ?   @ 
 : A  '%&-( '邦訳5 ウィリアム・パウ¾             
100ln(Sf) = a - 1.0508 ln(f)100ln(Sf) = a - 0.5866 ln(f)
10Sf

Sf

101

1
0.1
0.1
0.01
10.01
1

$5

10100
f1000

10000

5'$))*((,/ ! &$. / ! > ?  B C "  ? ;5           D $ 3   '%&$(,0  %&. 0  E F :  C  E5  G       H"  # H    I D &
 -%  1$ '%%&(,:   %*. :    : C        B 5 ?      >   5 >    3        E D 6  &%  *) '%%*(,:   %-. :    :     B C  5 >     3     5:    J    I D 61  *2  *% '%%-(,蜷川 ). 蜷川繁 米田政明 広瀬貞樹5 ライフゲームにおける過渡現象のセル数依存性 人工知能学会論文誌 D 2 2-  22 '$))(,蜷川 )$. 蜷川繁5 ライフゲームにおける   ゆらぎと過渡現象 情報処理学会論文誌 D -*  $)6  $)$) '$))$(,> . 5KK    K  KKln(Sf) = a - 0.2819 ln(f)Sf1010.1

0.01
100
f

1000

10000

ンド ストーン著 有澤誠訳 ライフゲイムの宇宙「新装版」
日本評論社

100101000-5 $ 番 目 に 高 い 適 合 度 16*&1 を も つ 遷 移 規 則)))))))))))) のパワースペクトル（ 上）．点線は  +) において最小 $ 乗法で近似し た直線 ' ( +  = ' ( +  )1)&．))) ステップ目の様相（下）．

%%2)%))))))))))+ )
$' ( + = ' ( + ) 1&22 )))
)

1100f

図

図最高適合度をもつ遷移規則のパワースペクトル（ 上）．点線は において最小乗法で近似した直線   ．
ステップ目の様相（下）．白のセルは状態 ，黒のセルは状態を表す．



1010000*5 $ 番 目 に 高 い 適 合 度 22& を も つ 遷 移 規 則))))))))) のパワー スペクトル（ 上 ） ．点線は + ) において最小 $ 乗法で近似した直線 ' ( + =  ' ( + ) $&%．))) ステップ目の様相（下）．
図¿