|
ライフゲームは2次元2状態9近傍セルオートマトン(Cellular Automaton;CA)の
1種であり,セル平面上で計算機が構成できることが知られている。このように計算万
能性を備えたCAを計算万能CAとよぶ。類似のCAのうち,ライフゲームのみが1/
fゆらぎを示すことから,CAにおける計算万能性と1/fゆらぎとの間に何らかの関
連性があると予想される。本研究では,計算万能CAを発見することをめざして,2次
元2状態9近傍CAにおいて1/fゆらぎを示すものを探索する。探索の対象となるC
Aは,全部で218=約13万個あるため,全数探索は現実的ではない。そこで1/fゆら
ぎという特徴に注目し,遺伝的アルゴリズム(GA)を用いて1/fゆらぎ型2次元C
Aを探索する。具体的にはランダムな初期様相から出発した場合のセルの変化のパワー
スペクトルから最小2乗法によってパワースペクトルの傾きと残差平方和を求め,それ
らから適応度を求め,GA操作を繰り返すことにより1/fゆらぎを示すCAを求める。
現在,統計数理研究所のスーパーコンピュータのほか,申請者の所属機関の研究室や教
室にあるコンピュータ利用して探索を行なっている。
現在までに30通りの集団に対してのべ5000世代まで計算が進んでおり,3番目に高
い適合度をもつCA(F3とよぶ)は1/fゆらぎを示すだけでなくライフゲームと極
めて近い遷移規則をもつことがわかっている。さらにライフゲーム上で万能計算機を構
成するために必須のグライダーと呼ばれる伝播するパターンがあるが,F3にはグライ
ダーとまったく同じパターンが存在することがわかっており,このことはF3がライフ
ゲームと同じく計算万能性をもつ可能性を示唆している。今後は各初期集団に対して3
00世代まで,計算を行い,さらにその後は2次元3状態9近傍CAに対して同様の実験
を行う予定である。
成果発表
2005年度人工知能学会全国大会(2005年6月16日,北九州市)
蜷川繁:1/fゆらぎによるセルオートマトンの進化
8th European Conference on Artificial Life(2005年9月8日,英国カンタベリー)
S.Ninagawa:Evolving Cellular Automata by 1/f Noise,Advances in Artificial Life,
Springer(2005)453-460.
|