平成19（2007）年度　共同利用登録実施報告書

課題番号	19−共研−13	分野分類		統計数理研究所内分野分類		i
				主要研究分野分類		2
研究課題名	１／ｆゆらぎによる計算万能セルオートマトンの探索
フリガナ 代表者氏名	ニナガワ　シゲル 蜷川　繁		ローマ字		Ninagawa Shigeru
所属機関	金沢工業大学
所属部局	工学部情報工学科
職　　名	准教授

研究目的と成果の概要

　ライフゲームは２次元２状態９近傍セルオートマトンの１種であり，セル平面上で計算機が構成できることが知られている．このように計算万能性を備えたセルオートマトンを計算万能セルオートマトンとよび，類似のセルオートマトンのうち，ライフゲームのみが１／ｆゆらぎを示す．また，単純セルオートマトンとよばれる１次元２状態３近傍セルオートマトンの中でルール１１０と呼ばれるセルオートマトンがもっとも長期にわたり１／ｆゆらぎを示すことが示された．いっぽうルール１１０は計算万能であることが証明されている．これらのことから，セルオートマトンにおける計算万能性と１／ｆゆらぎとの間に何らかの関連性があると予想される．本研究では，計算万能セルオートマトンを発見することをめざして，２次元３状態９近傍セルオートマトンにおいて１／ｆゆらぎを示すものを探索する．探索の対象となるセルオートマトンは，全部で３18＝約２．５９×１０64個あるため，全数探索は現実的ではない．そこで１／ｆゆらぎという特徴に注目し，遺伝的アルゴリズム（ＧＡ）を用いて１／ｆゆらぎ型２次元セルオートマトンを探索する．
　対象とする２次元３状態セルオートマトンの状態遷移規則は１３４桁の３進数列で表現することができるので，これを遺伝子型とし，テーブルウォークスルー法と呼ばれる方法を用いてランダムに生成する．こうして得られた各遷移規則に対して縦×横＝１００×１００のランダムな初期様相から８０００ステップにわたって状態遷移を行わせ，そこからパワースペクトルを求める．さらに最小２乗法によって，パワースペクトルの傾きｂと残差平方和σ2を求め，それらを用いて適合度を求める．こうしてパワースペクトルが１／ｆゆらぎに近いものほど高い適合度をもつようになる．ＧＡ操作としてはルーレット選択方式，一様交叉，突然変異を用い，交叉確率は0.6，突然変異確率は0.03としている．実験は集団の平均適合度に変化が見られなくなるまで繰り返す．
　探索に際しては一度パワースペクトルを計算したルールはデータべースに登録しておき，重複して計算することのないようにして，探索の手間を省いている．また，初期集団の生成に際しては１０２４ステップでパワースペクトルを求め，傾きが−０．３以下の比較的有望なルールだけを選抜して，使用している
　統計数理研のスーパーコンピュータを利用することにより，2007年４月から2008年３月の１年間に約 119,000 種類のルールの適合度を計算することができた．現在のところ，探索は終了していないため，引き続き探索を続ける予定である．