本研究は,確率的な関数進化アルゴリズムに関する論文である.関数進化アルゴリズムとしては,遺伝的プログラミング(GP:Genetic Programming)が最も有名であるが,GPは突然変異や,交叉などの生物進化の概念を用いており,生物進化の考え方を関数進化に適用した手法と考えることが出来る.近年,進化アルゴリズム(EA:Evolutionary Algorithm)を,確率的アルゴリズムとしてとらえ直す試みが行われており,分布推定アルゴリズム(EDA:Estimation of Distribution Algorithm)と呼ばれる手法の研究が盛んに行われている.EDAは,優良解の分布を仮定したモデルのもとで推定し,推定した分布から新しい個体を生成する.様々なモデルを用いることが出来るため,問題によっては従来手法であるGAやGPを凌ぐ探索性能を示す.従来は,GAと同じ固定長一次元配列への確率モデルの適用が中心であったが,近年,関数進化への適用が行われつつある.本論文では,EDAに基づく関数進化アルゴリズムを提案する.

本論文の構成は以下の通りである.

一章では,本論文の研究目的について説明し,EDAが提案された背景と,木構造のEDAの研究を本論文で行う理由について述べる.

二章では,EDAの基本事項について述べる.この章では従来のGAやGPと,EDAの相違点及び共通点について述べ,一般的なEDAの枠組みについて説明する.さらに,既存のGA-EDAの手法及びGP-EDAについての説明を中心に行う.

三章では,提案手法POLE(Program Optimization with Linkage Learning)について述べる.この章では,POLEと関連するベイジアンネットワークについても簡単に説明を行っている.POLEはプロトタイプ木に基づくGP-EDAであり,拡張構文木と呼ばれる表現手法と,ベイジアンネットワーク学習を組み合わせた手法である.POLEは三つのベンチマークテストに適用されており,有効性が示されている.

四章では二つ目の提案手法であるPAGE(Programming with Annotated Grammar Estimation)の詳細が記されている.PAGEは確率文脈自由文法(PCFG:Probabilistic Context Free Grammar)に基づく手法であり,PCFG-LA(PCFG with Latent Annotations)と呼ばれるPCFGモデルを用いている.モデル学習にはEMアルゴリズムと変分ベイズ法を用いている.この章では,これら関連手法についても説明を行っている.PAGEは大きく分けると二つの手法PAGE-EM(EMアルゴリズム),PAGE-VB(変分ベイズ法)に分けられるが,それぞれのモデル学習アルゴリズムについて説明している.二つのPAGEの有効性を,いくつかのベンチマークテストに適用することで示している.

五章では,本論文で得られた結果についてまとめ,将来研究の方向性について議論する.

本論文は「分布推定に基づく確率的関数進化アルゴリズム」と題し,5章からなり,遺伝的プログラミングを拡張した木構造表現を扱う最適化アルゴリズムを構築し,提案した手法の有用性を実験結果に基づいて実証的に検証している.

第一章では,本論文の研究目的について説明し,分布推定アルゴリズムが提案された背景と,木構造分布推定アルゴリズムの研究を本論文で行う理由について述べている.また,本論文の目的についても記述している.

第二章では,分布推定アルゴリズムの基本事項について述べている.本論文では,進化アルゴリズムは未知の優良解分布からのサンプリングを繰り返す手法であると考えており,遺伝的アルゴリズムと分布推定アルゴリズムの違いはサンプリング方法にあると捉えている.この章では,従来の遺伝的アルゴリズムや遺伝的プログラミングと,分布推定アルゴリズムの相違点及び共通点について述べ,一般的な分布推定アルゴリズムの枠組みについて説明する.さらに,固定長一次元配列を用いる分布推定アルゴリズム,及び木構造を用いる分布推定アルゴリズムについての説明を中心に行う.木構造分布推定アルゴリズムは大きく分類すると,プロトタイプ木に基づく手法と,確率文脈自由文法に基づく手法に大分されるが,これらについても説明している.また,分布推定アルゴリズムの従来手法についても簡単に紹介している.

第三章では,提案手法POLE(Program Optimization with Linkage Learning)について述べている.POLEはプロトタイプ木に基づく手法であるが,従来手法においては確率モデルとして,単変数モデルや親子関係モデルなど,あらかじめ固定された依存関係のみを考慮している.また,従来のプロトタイプ木に基づく木構造分布推定アルゴリズムは,木構造を単純に固定長配列に変換しているが,単純な変換ではシンボル数の多さの問題やノイズの問題を避けて通ることが出来ない.POLEは拡張構文木と呼ばれる表現手法と,ベイジアンネットワーク学習を組み合わせた手法であり,上記の問題点を解決している.POLE は三つのベンチマークテストに適用されており,有効性が示されている.特に,騙し最大値問題やRoyal Tree問題では,従来手法を大きく上回る探索性能を示している.この章では,POLEと関連するベイジアンネットワークについても,パラメータ学習や構造学習について簡単に説明している.

第四章では二つ目の提案手法であるPAGE(Programming with Annotated Grammar Estimation)の詳細が記されている.確率文脈自由文法に基づく木構造分布推定アルゴリズムは,今までに数多く提案されているが,確率文脈自由文法は文脈自由を仮定しているため,ノード間の依存関係を一切考慮することが出来ない.従来手法では,アノテーションを付加することで,文脈自由仮定を緩和しているが,親ノードや深さなどのヒューリスティクスに基づくアノテーションが用いられてきた.このようなアノテーションが有効である問題も存在するが,どのようなアノテーションモデルが有効であるかは事前には分らないことが多い.PAGE では,自然言語処理で提案されたPCFG-LA(PCFG with Latent Annotations)と呼ばれる確率文脈自由文法モデルを用いている.PCFG-LAではアノテーションを隠れ変数として扱っており,ヒューリスティクスに基づくアノテーションモデルと比較して柔軟であると考えられる.PAGEにおいては,PCFG-LAのモデル学習にEMアルゴリズムと変分ベイズ法を用いている.この章では,これら関連手法についても説明を行っている.PAGEは大きく分けると二つの手法PAGE-EM(EM アルゴリズム),PAGE-VB(変分ベイズ法)に分けられるが,それぞれのモデル学習アルゴリズムについて詳細に説明している.二つのPAGE の有効性を,いくつかのベンチマークテストに適用することで示している.

第五章では,本論文で得られた結果についてまとめ,将来研究の方向性について議論する.

以上これを要するに本論文は,遺伝的プログラミングを拡張する確率的関数進化アルゴリズムを提案し,プロトタイプ木に基づく構造学習手法と確率文脈自由文法に基づく木構造分布推定法を構築し,実現したアルゴリズムの有効性を複数の問題に適用することで検証しており,情報学の基盤の発展に貢献するところが少なくない.

したがって,博士(科学)の学位を授与できると認める.