報告番号

※甲第主号

論

文の要

旨

論文題目

集団構造に基づく進化的計算手法の拡張氏

大谷隆浩

論文

名

内容の要

旨

最適化問題とは与えられた制約条件のもとで，指定された関数 (目的関数) の値が最小または最大となるような変数の値 (最適解) を求める問題である．実社会における数理的問題の多くは最適化問題に帰着できるため，この問題を解くための効果的なアルゴリズムを開発することは極めて重要である．最適化問題の解法として，自然界に生育する生物の適応プロセスに着想を得た進化的計算手法が提案されている．特に生物の遺伝と進化の仕組みに着想を得た遺伝的アルゴリズムは数多くの実問題に応用され，高い性能を示している．その他にも，蟻の食料採集行動を参考にした手法や，鳥や魚の群れ行動を応用した手法など様々なアルゴリズムが提案されている．
進化的計算はあらかじめ定められた関数の最適解を探索する問題においては一定の成功を収めていると言える．このような枠組みについて，進化する集団の構造という点に注目してみる．集団の構造には，複数の進化集団が形成する構造 (集団間構造) と，単一集団内の個体が形成する構造 (集団内構造) の 2 つのレベルがあると考えられる．集団間構造は，基本的には独立して進化する集団の間でどのような情報がやり取りされるか，どの集団とどの集団が情報のやり取りを行うかを表現するものである．集団内構造は，集団内の各個体が探索空間上においてどのような位置関係をとるかを表現するものである．基本的な進化計算手法の枠組みについて集団構造を見てみると，単一の集団を用いているため集団間構造は無く，集団内構造は集団内の個体が最適解一点に集まるように進化するという単純な構造になっている．
本研究では，進化する集団の集団間構造と集団内構造に基づき，進化的計算手法の拡張を行うことを目的とする．また，単純な最適化ではない問題クラスを対象とした効果的な手法を開発することで，進化的計算の適用可能範囲を拡大することを目指す．まず集団間構造に着目し，複数の集団が密に相互作用し共に進化していく共進化アルゴリズム (Coevolutionary Algorithm: CA) の改良を行う．一般的な進化的計算手法が対象とする問題では，各候補解の評価値はあらかじめ定められた目的関数に基づいて算出されるが，CA では各個体間の相互作用に基づいて評価値が算出される．このような構成により，ソーティング・ネットワーク設計問題やゲームの戦略の進化など，通常の進化的計算手法を適用しづらい問題クラスを取り扱うことが出来るため，この手法の性能を向上することで進化的計算の適用範囲を拡大できると考えられる．次に集団内構造に着目し，各個体が探索空間中の複数の最適解に対して均等に配置されるよう進化させる，多峰性関数の最適化を行う手法を開発する．機械学習におけるクラス分類問題や遠地地震波の解析問
題のような実問題の多くは多峰性を有する関数最適化問題と考えられ，その場合，複数の最適解を網羅的に発見することが求められる．このことから，効果的な計算手法を開発することは応用面からも重要である．
本論文の構成は次の通りである．第 2 章では，集団間構造に着目し，共進化アルゴリズム (CA) の改良について述べる．本章では，確率モデルを用いた進化的計算手法である確率モデル構築型遺伝的アルゴリズム (Probabilistic Model-Building

Genetic Algorithm: PMBGA) を CA に取り入れたアルゴリズムを提案し，それを確率モデル構築型共進化アルゴリズム (Coevolutionary Algorithm with Probabilistic
Model-Building: CA-PMB) と名付けた．PMBGA は解の生成確率を表現する確率モデルを保持し，これを更新しながら解空間を探索する手法の総称である．この手法の利点として，変数間の関係を明示的に取り扱った効果的な探索が行えることが挙げられる．また CA においては，表現力の高いモデルを用いることにより，他集団の構成を予測しそれに対抗する個体を効率的に生み出すようなモデルが構築されることが期待でき，これにより相乗的に性能を向上できると考えられる．本章
では，PMBGA の最も基本的な手法である PBIL (Population-Based IncrementalLearning) を CA の枠組みに取り入れた CA-PBIL (Coevolutionary Algorithm with
Population-Based Incremental Learning) を実装し，CA のベンチマークとしてよく使用される非推移的ナンバーズ・ゲームを用いた計算機実験により性能を評価した．実験結果より，進化の停滞や不適切な方向への進化など，問題の非推移性に起因する様々な進化挙動が引き起こされ，適切な共進化が妨げられる場合があることが分かった．さらに，2 つの集団で異なる学習率を設定し，進化の速度を調節することで，望ましい共進化挙動を引き起こす方法を発見した．同一の学習率を設定した場合，最適解の発見率が 10%程度であったが，学習率を調節することで最大70%程度まで向上させられた．
第 3 章では，単一集団内における個体間の構造に着目し，集団内の個体が探索空間中にある複数の最適解に分散して配置するように進化させる，多峰性関数の最適化手法について検討する．本研究では，進化計算手法の一種である差分進化(Diﬀerential Evolution: DE) に着目し，この手法を基として多峰性関数最適化を行える拡張手法を開発した．差分進化を用いた理由として，アルゴリズムが単純であるため実装と拡張が比較的簡単に行えること，多くの最適化問題において高い性能を示していることが挙げられる．本章では，多峰性関数最適化行うための差分進化の拡張として，DE/isolated/1 を提案した．この手法では，解空間内で孤立している個体に基づいて新たな個体を生成する．このように設定することで，新しい個体は孤立個体の近くに生成される．そして，新たに生成された個体が現在の個体よりも良好な評価値を持っていれば，その個体に置き換わる．従って，集団中の個体は各世代において，孤立している領域に向かって積極的に移住を行うようになる．
これにより，解空間内の各最適解に均等に個体を割り当てられると考えられる．このアルゴリズムを実装し，8 つの 2 次元多峰性関数をベンチマークとして用いた計算機実験により，これまでに提案されている拡張手法と性能を比較した．実験結果
より，提案手法は既存の拡張手法に比べ概ね良好な性能を示すことが分かった．特に大小の谷が混在する関数においては，既存手法では複数の最適解を全て発見することができなかったが，提案手法では 60%程度の割合で全最適解の発見に成功した．これは，移住を繰り返すことで各最適解に割り当てられる個体数を均等化するメカニズムがうまく働いたためであると考えられる．
本研究では，進化する集団の集団間構造と集団内構造に基づき，進化的計算手法の拡張を行った．集団間構造を拡張する手法として，共進化アルゴリズムに PMBGAを取り入れた確率モデル構築型共進化アルゴリズムを提案し，集団内構造を拡張する手法としては，多峰性関数最適化に向けた差分進化の拡張手法 DE/isolated/1を提案した．それぞれの手法について，計算機実験を通して探索性能の評価を行った．研究を通して，集団構造を適切に制御することが探索性能を引き出す上で非常に重要であることを示した．集団間構造については，評価関数の定義や，どのような進化集団を用意し相互作用させるかなど，集団間の関係を適切に設定しなければならない．また集団内構造については，所望の構造を得るための進化方法について，適用する問題の特徴を考慮した上で適切なものを選定する必要がある．この研究の発展として，集団間と集団内の拡張を同時に施した手法を開発することが挙げられる．本研究では集団間構造の拡張と集団内構造の拡張を独立に行ったが，本来これら 2 つのレベルの構造は相互に依存しており，その組合せが探索性能に大きく影響する．このことを勘案し，適切な集団構造を効果的に扱える手法を開発することで，大規模複雑な実問題の解決に進化的計算手法を応用できるようになると考えられる．