No | 121591 | |
著者(漢字) | 柳井,孝介 | |
著者(英字) | ||
著者(カナ) | ヤナイ,コウスケ | |
標題(和) | プログラムのインタラクションによる情報構造の創発に関する研究 | |
標題(洋) | Emergence of Information Structures through Program Interaction | |
報告番号 | 121591 | |
報告番号 | 甲21591 | |
学位授与日 | 2006.03.23 | |
学位種別 | 課程博士 | |
学位種類 | 博士(科学) | |
学位記番号 | 博創域第173号 | |
研究科 | 新領域創成科学研究科 | |
専攻 | 基盤情報学専攻 | |
論文審査委員 | ||
内容要旨 | 本研究は創発システムによる構造生成に関する考察である.本論文では次の2つを主題として議論を行う. プログラムインタラクション:システムを構成する個々の要素はコンピュータプログラムであり,プログラム同士が相互作用することによって創発が生じる. エントロピー駆動性:システムはランダム性を構成要素として持ち,ランダム性がシステムの動作においてポジティブな役割を持つ. 本研究では,相互作用する個々の要素がプログラムであるようなシステムを考察の主な対象とする.このような創発システムについて,シミュレーションを用いてシステムの振る舞いを調べ,ランダム性の役割について考察する. 本論文では,遺伝的アルゴリズム,確率モデルを用いたプログラム生成システム,マルチエージェント環境におけるロボット学習システム,λ関数モデルによる化学反応系,ランク選択に基づくスケールフリー・ネットワークモデルを研究対象とし,独立にシステムの詳細を調べる.これら個々の事例研究から,ランダム性と創発システムの関わり方やプログラムインタラクションによる創発のバリエーションを抽出し,共通の構造を明らかにすることを目的とする. まず2章では遺伝的アルゴリズムにおけるランダム性について議論する.遺伝的アルゴリズムにおいては,乱数発生アルゴリズムの違いによってシステム性能が変化するという報告がこれまでにいくつかなされている.これらの研究を概観し,ランダム性を用いない遺伝的アルゴリズムの構成を試みる.実験により,ランダム性を用いない遺伝的アルゴリズムが探索性能の面で標準的な遺伝的アルゴリズムに劣ることを示す.これにより「GAは解の情報量(エントロピー)を消失して,それを解の質の向上に変換するシステムである」との見方を提案する.また標準的な遺伝的アルゴリズムにおいてランダム性を小さくしていき,システムの探索性能が劣化することをみる.遺伝的アルゴリズムがエントロピー駆動型システムであることを示し,創発システムにおいてランダム性は情報量としての意味合いが強いことを述べる. 3章と4章では,確率分布を用いたプログラム生成システムを提案する.プログラムを自動生成する手法として一般的によく知られているものは遺伝的プログラミングである.遺伝的プログラミングは数々の成果を挙げている一方で,遺伝的プログラミングによる探索が困難である問題の存在がこれまでに報告されている.従って遺伝的プログラミングとは異なるメカニズムでプログラム生成を行う新しい手法の提案が期待されている. 提案するシステムは,確率モデルを用いて個体の遺伝子分布を推定することによりプログラムを進化させる.突然変異と交叉は用いない.まずシステムは集団の適合度が高い個体を一定数選択する.続いて選択された個体が持つ遺伝子の分布を推定する.次に得られた確率分布に従う乱数を発生させることにより,遺伝子を決定し,新しい個体を生成する.推定された分布は集団内で高い適合度を持つ個体群に基づいているため,確率分布に従って生成された個体は前の集団の適合度が高い個体グループの周りに散らばると考えられる.従って集団全体の適合度の平均的な上昇が期待できる.3章ではEDP(Estimation-of-Distribution Programming)を提案し,提案手法の探索性能を遺伝的プログラミングと比較する.比較実験によりEDPが遺伝的プログラミングとは本質的に異なることを示し,EDPの欠点であると考えられるposition-dependenceに関して議論する. 4章ではEDPを拡張することにより,システム性能の向上を試みる.まずEDPとGPのハイブリッドシステムを構成し,ハイブリッド比を変えながらシステムの性能を調べる.実験結果からハイブリッド比を0.5とすると最も良い性能が得られること,EDPオペレータは進化の初期段階に有効に働き,一方GPオペレータは後期に有効に働くことを示す.またXEDP (Extended Estimation-of-Distribution Programming)を提案し,GPと同等かそれ以上の性能を持つことを示す.他の確率モデルを用いたシステムと性能を比較し,確率モデルにおける依存関係が有効であること,部分構造の抽出が有効に働いていることを示す. 5章では遺伝的プログラミングによるロボット行動の共進化について考察する.交叉による遺伝子形でのインタラクションに加え,共進化による表現形でのインタラクションと,移民による集団間でのインタラクションを行うシステムを構成する.マルチエージェント環境における協調行動プログラムの自動生成を目的とし,実機での動作を想定して学習を行う.まず共進化に関する議論を行い,協調的共進化用の進化システムをモデリングする.本論文では脱出問題と捕球問題における協調行動の共進化実験を行い,構成したシステムにより協調行動が創発されることを見る.実験結果から,ロバスト性の発生メカニズム,共進化における役割分担について考察する. 6章ではλ関数モデルを用いて,抽象的な化学反応系をシミュレーションする.化学反応系をシミュレーションするという研究は広く行われており,本研究と同様にλ関数モデルを用いたものとしてAlChemyがある.AlChemyの実験では,実際の生命システムで見られるような現象と類似した現象が創発したと報告されている.しかしながらAlChemyの拡張モデルを用いた著者の独自の実験では,AlChemyの結果を再現することができなかった.そこで本研究では,モデルに非平衡性を導入することにより,システムを非平衡系に置くことを試みる.これによりシステムが複雑な構造を維持できることを見る.6章の実験から,創発システムの構造形成における散逸機構の重要性が直接的に示唆される.実験結果が示すことと生命の起源の問題の関連について議論し,エントロピー増大則に抗して秩序を保つ生命システムとの類似点について述べる. 7章と8章では,創発システムにおける個体情報の伝達に関して議論する. 7章ではランクに基づくスケールフリー・ネットワークを提案する.提案するモデルでは,ランク選択によりノードを2つ選択し,選択されたノード間にリンクを加える.この手続きを繰り返すことにより,ネットワークを生成する.7章ではまず提案モデルがスケールフリー性を持つことを,シミュレーションと理論計算を用いて示す.この結果は,遺伝的アルゴリズムの交叉によりできる個体のネットワークがスケールフリー性を持つことを意味している.また理論計算により生成されるネットワークのベキ指数が1に近いことを示す.さらに提案モデルがSmall-world性を持つこと,および比較的大きいクラスタリング係数を持つことをシミュレーションにより示す. 8章では進化システムにおける情報伝播機構について考察する.まず遺伝的アルゴリズムにおける交叉ネットワークがスケールフリー性を持つことから,スケールフリー性が情報拡散に対する耐性を生み出すという仮説を提案する.次に進化システムにおける遺伝子圧縮の進化について議論する.遺伝的アルゴリズムにおいては,交叉や突然変異は破壊的作用があるため,エクソンはイントロンに比べて相対的に短くなっていくと考えられる.遺伝的アルゴリズムにおける情報圧縮メカニズムを調べるため,遺伝子の情報圧縮率が可変であるモデルを2つ提案し進化実験を行う.実験結果から,短い期間では冗長性のみが消去されるが,長い期間では情報内容そのものが圧縮されることを示す. 本論文では,2章から8章までに得た実験結果と考察を基に,創発システムに共通して見られた性質について議論し,主題であるプログラムインタラクションとエントロピー駆動性について考察する.これにより,ランダム性,散逸構造,情報伝達構造の3つの点から創発システムを捉え直すことを試みる. | |
審査要旨 | 本論文は「プログラムのインタラクションによる情報構造の創発に関する研究」と題し、10章からなり、プログラムインタラクションとエントロピー駆動性を主題として,創発システムにおけるランダム性の役割と散逸的な構造を明らかにしている. 第1章は序論であり、主題と目的が述べられ、創発、プログラムインタラクション、エントロピー駆動性の概念が説明されている。また本論文に関連する基礎的なことがらが簡潔に説明されている。 第2章においては、遺伝的アルゴリズムにおけるランダム性について議論される。遺伝的アルゴリズムにおいては、乱数発生アルゴリズムの違いによってシステム性能が変化するという報告がなされている。まずこれらの研究を概観し、ランダムさの計量について議論している。次にランダム性を用いない遺伝的アルゴリズムを構成し、標準的な遺伝的アルゴリズムとの比較がなされている。また10の異なる乱数を用いて遺伝的アルゴリズムの性能比較を行い、ランダム性が小さい場合に性能が劣化するという結果を得ている。2つの実験結果を基に、遺伝的アルゴリズムにおけるランダム性の役割について考察している。 第3章においては、確率分布を用いたプログラム生成システム、EDP(Estimation-of-Distribution Programming)を提案している。従来手法である遺伝的プログラミングは数々の驚異的な成果を挙げている一方で、遺伝的プログラミングによる探索が困難な問題もこれまでにいくつか報告されている。従って遺伝的プログラミングとは異なるメカニズムでプログラム生成を行う新しい手法の提案が期待されている。提案手法は、突然変異や交叉は用いず、確率モデルを用いて個体の遺伝子分布を推定することにより、プログラムを進化させる。提案手法を遺伝的プログラミングと比較し、提案手法が本質的に遺伝的プログラミングとは異なることを実験により示している。また提案手法の欠点であるposition-dependenceに関して議論している。 第4章においては、EDPを改良する試みがなされる。まずEDPと遺伝的プログラミングのハイブリッドシステムを構成し、ハイブリッド比を変えながらシステムの性能を調べている。実験結果からハイブリッド比を0.5とすると最も良い性能が得られることを示している。またXEDP(Extended Estimation-of-Distribution Programming)を提案し、高い探索性能が得られることを示している。実験結果から、確率モデルにおける木構造の依存関係が重要であること、部分構造の抽出が有効に働いていることを結論付けている。 第5章においては、遺伝的プログラミングによるロボット行動の共進化について考察している。マルチエージェント環境における協調行動プログラムの自動生成を目的とし、実機での動作を想定してシステムを構成している。論文では脱出問題と捕球問題における協調行動の共進化実験を行い、構成したシステムにより協調行動が獲得されることを示している。実験結果から、ロバスト性の発生メカニズムと共進化による役割分担の創発について考察がなされる。 第6章においては、λ関数モデルを用いて抽象的な化学反応系をシミュレーションしている。様々な条件で実験を行った結果、非平衡性を導入することによりシステムが複雑な構造を維持できると結論付けている。 第7章においては、ランクに基づくスケールフリー・ネットワークモデルを提案している。提案するモデルでは、ランク選択におりノードを2つ選択し、選択されたノード間にリンクを生成する。この手続きを繰り返して生成されるネットワークがスケールフリー性を持つことを、シミュレーションと理論計算を用いて示している。 第8章においては、進化システムにおける情報伝播機構が議論される。まず遺伝的アルゴリズムの交叉によりできる個体のネットワークがスケールフリー性を持つことから、スケールフリー性が情報拡散に対する耐性を生み出すという仮説を提案している。次に進化システム遺伝子の圧縮率の進化について議論している。遺伝的アルゴリズムにおいては、交叉や突然変異は破壊的作用があるため、エクソンはイントロンに比べて相対的に短くなっていくと考えられる。遺伝的アルゴリズムにおける情報圧縮メカニズムを調べるため、遺伝子の情報圧縮率が可変であるモデルを2つ提案し進化実験を行い、短い期間では冗長性のみが消去されるが、長い期間では情報内容そのものが圧縮されるという結論を得ている。 第9章においては、2章から8章までに得た実験結果と考察を基に、これらの創発システムに共通して見られた性質について議論し、主題であるプログラムインタラクションとエントロピー駆動性について考察している。これにより、ランダム性、散逸構造、情報伝達構造の3つの点から創発システムを捉え直すことを試みている。 第10章においては、本論文の結論と今後の展望が述べられ、それと平行して本論文のアプローチに関する考察が述べられている。 なお、本論文の一部は共同研究によって行われたものであるが、論文提出者が主体となって提案及び実験・分析・検証を行ったもので、論文提出者の寄与が十分であると判断する。 以上これを要するに本論文は、プログラムインタラクションとエントロピー駆動性を主題として、5つの創発システムを解析している。またEDP、XEDPなどのプログラム進化のための新しい手法を提案しており、その有用性を実験により実証している。さらにロボット協調行動の学習のための共進化システムやスケールフリー・ネットワークモデルも提案しており、その性質を詳しく調べている。多くの実験結果を基に、創発システムにおけるランダム性、散逸構造、情報伝播構造について議論がなされており、情報科学の発展に貢献するところが少なくない。 したがって、博士(科学)の学位を授与できると認める。 | |
UTokyo Repositoryリンク |