自律的分散型計算としての分子計算
山下雅史∗ , 櫻井幸一∗ , 溝口佳寛† ,朝廣雄一‡ , 藤田聡§ , 貞広泰造¶ , 小野廣隆∗

1

研究目的と研究実施状況

分子計算には計算過程の物理的拘束や選択的ランダム性など , 自律性が由来すると期待される魅力的な側面を有するものの, 現在の所は , ごく大雑把に言えば , 塩基間の相補性を計算規則とする超並列シラミ潰し探索に留まっている. そこで , 分子計算の特徴を生かした分子プログラムの設計論の開発が焦眉の課題であり, これが本特定領域研究を行う目的の一つであった.
分子計算の自然な見方の一つは個々の生体分子をエージェントとする自律的分散型システムと捉えることである. このようにすれば , 分子計算をインターネットなどの計算機ネットワークや群ロボットシステムなど 他の分散型システムと同じ観点から検討できるとともに ,セルオートマトンやタイリングといった, 計算機科学者にとってなじみの分野で蓄積されてきた多くの研究成果を自然に継承できると期待できる. これが九州-広島班の分子計算に対するアプローチ方法である.
九州-広島班のメンバーは , 並列/分散計算やセルオートマトン , タイリングなどを中心に研究してきており, 初年度である今年の目標を分子計算に対する理解を深め, 来年度以降の研究目標を明確にすることとした. ２回開催された全体会議の他に , 本年度は班会議も２回開催し , 班員の現在に至る研究の概要を確認すると共に , その分子計算研究への応用について意見交換を行った. 本班のホームページは現在非公式に運用しており, 近い将来に公開する予定である.

2

研究成果概要本年度の研究成果のいくつかを概説する. 文献番号は次節に掲載する研究業績リスト番号である.
山下は , 巨大分散システムの振る舞いを統計的に解析することを目指して, 有限グラフ上のランダムウォークの振る舞いを解析した [1, 2]. 分子の統計的な振る舞いを知ることが効率的な分子プログラムを作成するために不可欠であると考えられ , 上記の解析技術はそのための基礎技術となる. つぎに , 一過性の故障から自律的に復帰するような分散システムであ∗九州大学大学院システム情報科学研究院 ({mak,sakurai,ono}@csce.kyushu-u.ac.jp)
九州大学大学院数理学研究院 (ym@math.kyushu-u.ac.jp)‡
九州産業大学情報科学部 (asahiro@is.kyusan-u.ac.jp)§
広島大学工学部 (fujita@se.hiroshima-u.ac.jp)¶
熊本県立大学総合管理学部 (sadahiro@pu-kumamoto.ac.jp)†

1

る自己安定システムについて検討した [3]. 自己安定システムは初期化がまったく必要のないシステムとして特徴付けられる. 分子プログラミングは , 多くの分子を含むシステムを対象とするが , 制御対象を理想的に “初期化” することは困難であると考えられる. このような不安定な初期状況から実行を行っても正しい結果を返すシステムはその意味で自己安定的であると考えられる. 分子計算は超並列の発見的アルゴ リズムであると見做すこともできる.
従来から検討が進んでいる発見的手法を分子計算アルゴ リズムの設計に活かすことを視野に入れて, 朝廣, 小野, 山下は発見的アルゴ リズムの並列／分散化を検討した [4, 5].
櫻井は , 一方向性関数と分子現象の非可逆性に関する調査研究を行った. Adlemann は分子の非可逆現象をモデルに一方向性関数の理論を展開した. その後, 一方向性関数は暗号理論の発展に伴い大きく進歩するが , 分子現象の非可逆性への演繹まではいたっていないようであることを認識した. 次年度はこの課題を掘り下げる. また, 貞広と共同で , 有限オートマンによる２次元タイル張りの構造を解析した [6]. Wang タイル貼りは２次元の有限型記号力学系と考えることが出来る. 高次元の有限型記号力学系のエントロピーについて理論的,実験的な研究を行った. DNA 計算でもいくつかのタイルモデルが研究されているが , DNA計算の場合は有限オートマトンよりも能力の高い計算機を考察している. 我々が行ってきた古典的なタイル張りおよび DNA 計算のおけるタイルモデルとの相関と違いを (次年度の研究へ向け ) 調査した.
溝口は , セルラオートマトンと有限遷移系について以下の研究を行った. 分散計算モデルとしても用いられるセルラーオートマトン (CA) は , 汎用性に富む計算モデルとして人工生命,
ダ イナミカルシステム, カオス理論など 様々な分野で応用されている. J.Watrous は , 1995
年, 従来のセルオートマトンの定義を一般化し , 量子セルオートマトン (QCA) を提案した.
しかし , この QCA は遷移関数が well-formed かど うかの判断が難しく, 具体的な QCA の挙動についてはほとんど調べられていなかった. そこで , QCA と分割 QCA の定義を一般化し ,遷移関数が well-formed であるための十分条件を与えると共に , 具体的な挙動をシミュレーションを駆使して検討した [7]. つぎに , 有限遷移系の挙動解析に関して, 有限遷移系の遷移図を代数式で表現する方法を定式化し , その代数式から直接有限遷移系の遷移図をグラフ表示するアルゴ リズムを Mathematica を用いて実現した [8].
最後に藤田は , 分子の構造配置に関して, 以下の詰め込み問題を考察した [9]. ここで考えるのは , アイテムの (オンライン ) 系列を正方形のグリッド 列に効率よく詰め込む問題であるが , 空けておくことのできるグリッド 数をひとつに限定しているという特徴がある. 分子計算との関係は明確ではないが , 具体的な構造をもつ分子を固定された空間にどのくらいた
くさんオンライン的に詰め込めるかといった, 一種の密度の見積もりに使えないかと考えている. また, 応用面から今後に期待できる, 以下の結果を示した. 二次元平面上に配置された (無線通信のための) ベースステーション上にサーバから配送される位置依存情報をキャッシュしておくことを考える. キャッシュのリプレースメントアルゴ リズムをシミュレーションで評価した [10]. 通常の LRU だけでなく, 空間的な連続性 (対象が位置依存情報なので )や統計情報などもうまく併用すべきだということがこれまでにわかっている. 分子計算の内部でおこなれる自律的な振る舞いを特定の解空間にマップしてから使うのではなく, 「そのままの形」でうまく観測して利用することを狙っている.

2

3

研究成果

前節で触れた結果に関する業績だけを参考文献にリストアップした. また代表的な論文として [4] と [7](2002 年 12 月 9 日に行なわれた研究会資料) を掲載する. 各人のそれ以外の業
績については各人のホームページを参照頂きたい.

参考文献[1] S. Ikeda, N. Okumoto, I.Kubo, and M. Yamashita: “Fair Circulation of a Token,”IEEE Trans. Parallel and Distributed Systems 13, 4, 367–372 (2002).
[2] S. Ikeda, I. Kubo, N. Okumoto, and M. Yamashita: “Local Topological Information
and Cover Time,” (submitted to Siam J. Computing).
[3] H. Kakugawa and M. Yamashita: “Uniform and Self-Stabilizing Fair Mutual Exclusion on Unidirectional Rings with Unfair Distributed Daemon,” Journal of Paralleland Distributed Computing 62, 885–898 (2002).
[4] M. Ishibashi, Y. Asahiro, and M. Yamashita: “Parallelization of a Local Search
Method for the Generalized Assignment Problem,” Proc. of the Second JapaneseSino Optimization Meeting(JSOM 2002), p.85 (2002).
[5] 石橋正裕，小野廣隆，朝廣雄一，山下雅史: “ メタ戦略アルゴ リズムに対するロバストな並列化” 冬の LA シンポジウム，1–8 (2003).
[6] 貞広泰造, 櫻井幸一: “自己相似タイル貼り構成の計算例” 京都大学数理解析研究所講究
録 1286,
数学解析の計算機上での理論的展開とその遂行可能性, 119–130 (2002).

[7] S.Inokuchi and Y.Mizoguchi: “Generalized Partitioned Quantum Cellular Automata
and Quantumization of Classical CA (Draft),” Proc. Eighth International Workshop
on Cellular Automata, Prague, Czech Republic (2002).
[8] 井口修一, 溝口佳寛, 河原康雄: “有限遷移系の木表現式からの遷移図の自動作成,” 応用
数学合同研究集会報告集, 25–30 (2002).
[9] S. Fujita: “On-Line Grid Packing with a Single Active Grid,” Information Processing
Letters, 85, 4, 28, 199–204 (2003).
[10] S. Tagashira, Y. Wang, and S. Fujita: “Location-Aware Buﬀering Schemes for Road
Vehicle Communication Systems,” Proc. IASTED Int’l Conf. Networks, Parallel andDistributed Processing and Applications (NPDPA 2002), Tsukuba, 99-104 (2002).

3