2013年9月15日
粘菌から着想した解探索コンピュータ
理研No. 08028, 08093
発明者
青野 真士、原 正彦(揺律機能研究チーム)他
概要
[粘菌を用いる解探索コンピュータ]
従来のノイマン型デジタルコンピュータとは対照的に、生物組織においては、生体分子の大集団が自律分散的なやり方で情報を処理しています。 こうした超並列分子計算システムの情報処理に学び、その制御の方法論を確立できれば、シリコンデバイスとは異なる素材の物性やダイナミクスを活用して、低消費エネルギーで効率よく高速に解を探索したり、想定外の環境変化に自律的に適応できるような、非ノイマン型コンピュータの開発可能性が拓かれます。こうした期待から、アメーバ状単細胞生物・粘菌の変形行動を光刺激により制御する事で、様々な組合せ最適化問題の解を探索できるバイオコンピュータの研究開発を進めてきました。
図1: 粘菌コンピュータの実験セットアップ(バウンスバック制御)
図2:巡回セールスマン問題の解を探索する粘菌コンピュータ
[量子ドットを用いる解探索コンピュータ]
粘菌コンピュータから着想した光学的バウンスバック制御を導入することで、量子ドット(InGaAs、ZnO、CdSe等のナノ構造)のネットワークにおける励起子移動の時空間ダイナミクスを用い、組合せ爆発を生じるNP完全問題として知られる「充足可能性判定問題(SAT; Satisfiability Problem)」の解を探索できます。SATの解を探索できるシステムは、人工知能に関連した自動推論、ソフトウェア/ハードウェア検証、情報セキュリティーや、バイオインフォマティクスに関連したDNA配列解析等を含めた、極めて広範な用途に適用可能です。さらに、その単位動作である励起子移動のエネルギー消費は、従来型電子デバイスの単位動作(ビットフリップ回路)の約1万分の1なので、低消費エネルギーで効率よく高速に解を探索できる高汎用性コンピュータを実現できます。(※本研究は、NICTと東京大学との共同研究として行われました。)
図3:粘菌原形質流動に類似した励起子移動ダイナミクス
図4:充足可能性判定問題(SAT)解探索のためのバウンスバック制御
[電子回路を用いる解探索コンピュータ]
粘菌コンピュータの解探索ダイナミクスに学び、その本質を抽出したSAT解探索モデル「AmoebaSAT」を定式化しました。AmoebaSATは、従来型デジタルコンピュータ上で走るアルゴリズムとしても優秀な性能を示し、従来から良く知られたアルゴリズム「WalkSAT」と比較して、劇的に少ない反復回数で短時間のうちに解を探索することができます。さらに、通常のアルゴリズムがプログラムの形式で表現されているのとは対照的に、AmoebaSATは物理的な運動を記述する力学系モデルの形式で表現されているので、電子回路(FPGA等)をはじめとする様々な物理系によって実装することができます。
図5:粘菌アルゴリズムAmoebaSAT
図6:粘菌アルゴリズムの効率的で高速なSAT解探索能力
文献情報
- 1.特願2012-116725、US13/898335
- 2.特願2012-232402
知的財産情報に関するお問い合わせ
理化学研究所
お問い合わせフォーム