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

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

研究目的と成果の概要

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