平成21(2009)年度 共同利用登録実施報告書
課題番号 |
21−共研−9 |
分野分類 |
統計数理研究所内分野分類 |
i |
||
主要研究分野分類 |
2 |
|||||
研究課題名 |
1/fゆらぎによる計算万能セルオートマトンの探索 |
|||||
フリガナ 代表者氏名 |
ニナガワ シゲル 蜷川 繁 |
ローマ字 |
Ninagawa Shigeru |
|||
所属機関 |
金沢工業大学 |
|||||
所属部局 |
情報学部 |
|||||
職 名 |
准教授 |
研究目的と成果の概要 |
ライフゲームは2次元2状態9近傍セルオートマトンの1種であり,セル平面上で計算機が構成できることが知られている.このようなセルオートマトンを計算万能セルオートマトンとよび,類似のセルオートマトンのうち,ライフゲームのみが1/fゆらぎを示す.また,単純セルオートマトンとよばれる1次元2状態3近傍セルオートマトンの中で計算万能性を備えたルール110と呼ばれるセルオートマトンがもっとも長期にわたり1/fゆらぎを示す.これらのことから,セルオートマトンにおける計算万能性と1/fゆらぎとの間に何らかの関連性があると予想される.本研究では,計算万能セルオートマトンを発見することをめざして,2次元3状態9近傍セルオートマトンにおいて1/fゆらぎを示すものを探索する.探索の対象となるセルオートマトンは,全部で318=約2.59×1064個あるため,全数探索は現実的ではない.そこで1/fゆらぎという特徴に注目し,遺伝的アルゴリズム(GA)を用いて1/fゆらぎ型2次元セルオートマトンを探索する.各遷移規則に対して縦×横=100×100のランダムな初期様相から8000ステップにわたって状態遷移を行わせ,そこからパワースペクトルを求める.さらに最小2乗法によって,パワースペクトルの傾きbと残差平方和σ2を求め,それらを用いて適合度を求める.こうしてパワースペクトルが1/fゆらぎに近いものほど高い適合度をもつようになる.GA操作としてはルーレット選択方式,一様交叉,突然変異を用い,交叉確率は0.6,突然変異確率は0.03としている.実験は集団の平均適合度に変化が見られなくなるまで繰り返す.探索に際しては一度パワースペクトルを計算したルールはデータベースに登録しておき,重複して計算することのないようにして,探索の手間を省いている.また,初期集団の生成に際しては1024ステップでパワースペクトルを求め,傾きが-0.3以下の比較的有望なルールだけを選抜して,使用している.統計数理研のスーパーコンピュータを利用することにより,2009年4月から2010年3月の1年間に約80,000種類の適合度を計算することができた.現在のところ,探索は終了していないため,引き続き探索を続ける予定である |