分布推定アルゴリズムを学ぶ (1) ～概要～

分布推定アルゴリズム(Estimation of Distribution Algorithms; EDAs)とは

明示的な確率モデルを構築し，そこからサンプリングした候補解を用いて探索を行う確率的最適化手法である．
分布推定アルゴリズムは以下のような特徴を持つ．

• 目的関数の導関数を必要としない
  • 関数が明示的である必要が無い
  • 関数が連続でなくてもいい
• 基本的には離散問題を扱う
• 巨大で複雑な問題への適用が可能(らしい)

以降はEDAsという呼称で統一する．

用語定義

• EDAs：分布推定アルゴリズム(Estimation of Distribution Algorithms)のこと
• 目的関数：最適化をしたい対象の関数
• 候補解(個体)：目的関数に入力する値(主にベクトル)
• 集団：任意個の候補解の集合
• 評価値(fitness)：候補解を目的関数に入力した際の関数値

概略

対象とする問題

EDAsが対象とする最適化問題を以下に示す．

\max_{\boldsymbol{c}\in C} f(\boldsymbol{c})

ここで$f:C\rightarrow \mathbb{R}$は$\boldsymbol{c}\in C$に対してブラックボックスとなるような目的関数である．ここでブラックボックスとは，関数の形状が与えられないという意味である．つまり，入力として$\boldsymbol{c}$を与えたときに内部でどのような計算が行われているかは分からないという設定になる．
領域$C$はカテゴリカル空間(特に2値)の場合が多い．以降は特に断りがない場合，領域$C$をビット列に仮定する．

アルゴリズムの流れ

EDAsの基本的なアルゴリズムの流れをAlgorithm 1に示す．

EDAsは一般に目的関数に対する候補解の集団を利用して最適化を行う．
まず，2行目で初期の集団$P^0$を生成する．この時，生成される候補解は領域$C$から一様分布にしたがってサンプルされる．
各候補解を目的関数に入力し，評価値を得る．ここでは評価値が大きいほど良い解という解釈になる．
次に，評価値によるランク付けをされた集団からより良い解が多く含まれるような部分集合$S^t$を選択する(4行目)．選択方法としてはトーナメント選択やルーレット選択などが挙げられる．
そして，選ばれた部分集合$S^t$を用いて確率分布を推定した確率モデル$M^t$を構築する(5行目)．
確率モデル$M^t$が構築できれば，つぎはそこから新たな候補解の集団$O^t$を生成し(6行目)，元の集団$P^t$と統合する(7行目)．統合方法としては，集団$P^t$において評価値の悪い候補解を集団$O^t$の候補解に置換していくなどの方法がある．
以降，終了条件を満たすまでこのサイクルを続ける．
終了条件としては，(1)十分に良い評価値を持つ候補解が得られた時，(2)反復回数の上限に達した時，(3)確率分布が収束した時などが考えられる．

他の多くのメタヒューリスティクスな最適化手法との違いは，より良い候補解の集団による確率分布を捉えた確率モデルを構築する点である．
すなわち，EDAsは集団の特徴を捉えられるような確率モデルを効率的に構築することが重要になる．

EDAsの分類

EDAsは利用する確率分布によって大きく4つに分類できる．

離散問題

固定長の有限な整数空間(主にバイナリ)を対象にしたもの．
大きく三つに分類される．

1. 変数間の依存性を考慮しないもの
2. 変数間を木構造で表現することで依存性を考慮するもの
3. 変数をクラスタリングすることで依存性を考慮するもの

順序問題

与えられた変数の順番によって目的関数の値が決定されるような問題設定を指す．巡回セールスマン問題(Traveling Salesman Problem; TSP)などが該当する．
この問題設定では，EDAsは(1)変数の絶対位置，(2)各変数の相対的な順番という二つの特徴を捉える必要がある．

実数問題

候補解が実数ベクトルによって表現される問題設定を指す．
実問題の多くは実数ベクトルによって表現されるが，EDAsは固定長の有限な整数空間を対象とした手法になっており，EDAsを直接実数問題に適用することはできない．
EDAsを実数問題に適用するためのアプローチとしては大きく二つに分けられる．

1. 離散化：実数変数を離散領域に写す
2. 実数変数で定義された確率モデルに基づいたEDAsを用いる

遺伝的プログラミング

名前の通り，遺伝的プログラミング(Genetic Programming; GP)の問題設定を指す．
GPは，ラベル付けされた木構造によって表現されたコンピュータープログラム(数式など)の集団を進化させていくタスクある．
GPではこれまでの問題設定と異なり可変長であるという性質がある．また，親と子の関係が少し変化するだけで評価値が大きく変わってしまうという性質を持つ．

多目的問題

複数の目的関数に対して最適な解を探索するという問題設定を指す．
これまでのEDAsは単目的，すなわち目的関数が一つのみであった．しかし，実問題においては複数の目的が設定されている場合が存在する．車のエンジンを例にすると，(1)燃費の向上と(2)馬力を上げるという二つの目的が存在するというイメージである．
多目的問題を解くための方法の一つとして，複数の目的関数を重み和によって単目的の問題に変換するというものがある．しかし，一般に複数の目的は互いにtrade-offの関係になっていることが多い(エンジンの例でも燃費を良くしようとすれば馬力は上げられず，馬力を上げれば燃費は悪くなる)．そのため，実際にはパレートフロントと呼ばれるtrade-offの曲線を求めることが最終目的になる．

EDAsの利点

####柔軟性が高い
多くのメタヒューリスティックな手法は問題固有の操作(工夫)が用いられている．
EDAsでは問題ごとに様々な操作を切り替えられる．
更に，一つの問題を最適化する中でも，動的に複数の操作・確率モデル等を切り替えながらの最適化が可能．
すなわち，手法の適用範囲が広い．

説明能力の高さ

EDAsは目的関数の大域的最適解を探索するだけでなく，そこに行き着くまでにどのように最適化が行われたのかという情報を提供してくれる．これは，各世代の確率モデルのことを指している．
つまり，最適化における確率モデルの推移等を分析することによって，問題特有の特徴などを明らかにすることができる．
これによって問題領域の理解が進み，新しい最適化のテクニックを設計する際の指針にもなりうる．

事前知識の導入のしやすさ

非常に複雑な最適化問題の場合，実用的な解を求めるためにはユーザーの事前知識を必要とする場合がある．
多くの最適化手法は事前知識を用いるためにアドホックな手法や問題固有の手法になりやすい．
EDAsでは，事前知識を導入するためのより根本的なフレームワークを提供できる．
例えばベイズ統計を使用すれば，大域的最適解に繋がる可能性の高い候補解や，解決が期待できる問題構造により密接に対応する確率モデルに対してバイアスをかけることができる．

メモリ消費量が少ない

EDAsでは集団を確率モデルに置き換えるため，メモリの消費量が少なくて済む．
そのため，他の手法では動かせないような高次元の問題に対しても適用することができる．

例）$2^{25}$(約$3.3\times10^7$)次元の目的関数を解く場合
普通の遺伝的アルゴリズム：約700GB
CGA(EDAsの手法の1つ)：128MB

EDAsの欠点

実行時間

EDAsでは明示的に確率モデルを構築するが，トーナメント選択や2点交叉といった操作によって暗に確率モデルを用いる手法と比較して実行時間が多くなりやすい．

確率モデルの構築の困難さ

目的関数に対して適切な確率モデルを構築することは困難な場合があり，それによって非効率的な最適化になってしまう可能性がある．
例えばBOAやECGAといった手法では貪欲アルゴリズムを用いるが，貪欲アルゴリズムでは不適切な確率モデルを構築してしまう可能性があることが知られている．

EDAsの性能を底上げするためのテクニック

EDAsは一定のスケーラビリティを有する一方で，非常に複雑な問題の場合には効率的な工夫(Efficiency Enhancement; EE)を必要とする場合がある．
EDAsにおける計算上のボトルネックとして，(1)目的関数の計算と(2)確率モデルの構築があり，これらに対処するために以下のようなEEが提案されている．

1. 並列化
2. 評価の緩和
3. ハイブリッド化
4. Time continuation
5. Sporadic and incremental model building
6. 問題固有の知識と経験からの学習

並列化

EDAsにおける並列化は，一般に目的関数の計算部分を対象としている．
ここでは目的関数と言っているので，一瞬で計算ができるイメージを持つ．しかし，実際にはシミュレーション結果などを用いる場合があり，そういった場合には各候補解の評価に非常に時間がかかる．

また，手法によっては確率モデルの構築部分を並列化できる場合もある．

評価の緩和

目的関数の計算がボトルネックになっているのは，各候補解を評価する際の計算が重いからである．
それならば，計算が軽くなるように目的関数を近似したモデルを考えようというのがこのEEのアイデアである．
目的関数自体を特定のモデルで近似することで，もともとの目的関数では計算コストの増大につながっていた部分を削除することができる．

当然ながら，目的関数の近似をするので解の精度は悪くなる．

ハイブリッド化

EDAsに他の最適化アルゴリズムを組み合わせることである．
一般にEDAsよりもシンプルで高速なローカルサーチの手法を導入し，計算コストの削減を図る．

Time continuation

一般に集団サイズが小さいと反復数は多くなり，集団サイズが大きいと反復数は小さくなる．
このtrade-offの関係において，最も効率的な場所を探すための手法？

Sporadic and incremental model building

ECGAやhBOAといったEDAsの手法では，確率モデルの構築を二つの部分に分けて行う．
一つは構造の学習であり，もう一つは各構造におけるパラメータの学習である．
一般に，構造の学習の方がパラメータの学習よりも難しいことが知られている．しかし，モデルの構造は一反復でそれほど劇的に変化する可能性は低いため，それを改善するためにsporadic modelによる確率モデルの構築を行う．
つまりsporadic modelを用いることで各反復で一から構造の推定を行うよりも構造の学習が効率的に行える．

問題固有の知識と経験からの学習

通常のEDAsでは問題に関する情報は全く必要ない．しかし，問題固有の情報が利用できるならば，それを利用することで劇的に計算コストを削減できる場合がある．基本的には二通りの事前知識が活用される．(1)初期集団の生成の確率分布を一様分布から変更すること，(2)確率モデルの構築過程にバイアスをかける，または制限を加えることである．

EDAsの理論

いくつかの研究の概要を紹介する．

収束の証明

Factorized Distribution Algorithm(FDA)と呼ばれる手法を用いて，収束時間に関する分析が行われている．
この研究では，比例選択を用いた場合の収束時間の真の方程式を導出している．また，一般に比例選択はほとんど用いられないという理由より，よく用いられるtruncation selection(評価値の良いものから決定的に選択する方法)における分析もしている．truncation selectionの場合は，収束時間の近似的な方程式を導出している．
FDAは関数の加法分解に基づくものであり，上記の研究では部分関数同士の重複を認めない条件での収束時間を導出している．
その他の研究として，部分関数同士の重複を認める条件において，個体数が無限であるという仮定のもとで三つの選択方法における収束を分析しているものがある．結果として，選択の前後で確率分布が同一である限り全て(三つ)の選択方法で収束することが導かれている．
また，高次の統計量を用いるFDAと一次の統計量しか用いないUMDAという手法の収束性を比較した研究もある．結果として，一般の目的関数においてFDAはUMDAより大域的最適解に到達する可能性が高いことが導かれている．

集団サイズ

収束の証明では基本的に集団サイズを無限に仮定しているが，現実には有限である．
EDAsにおいて集団サイズは探索の安定性と複雑度に大きく関係している．つまり，集団サイズが小さければ解の精度は悪化して大域的最適解を見つけることが難しくなり，集団サイズが大きければ確率モデルからのサンプリングや候補解の評価等の複雑度が上がるということである．
そのため，適切な集団サイズを選択することは非常に重要である．

一般に変数間の依存性を考慮する手法では集団サイズを大きくする必要があると知られている．
これを示すためにBOAという変数間の依存性を考慮する手法を用いて，いくつかの部分関数に分割できるような目的関数で調査を行った研究がある．
この研究では，各部分関数が同一の難しさの最適化問題となる場合(一様スケール)と各部分問題で最適化の難易度が変化する場合(非一様スケール)でそれぞれ目的関数と集団サイズの関係性を調査している．その結果，集団サイズは線形に増やす必要があるということを明らかにしている．また，一様スケールの場合には準二次，非一様スケールの場合には二次で評価回数が増加することを明らかにしている．

多様性の消失

確率モデルから候補解をサンプリングする際に同じ解ばかりがサンプルされてしまうと集団の多様性が失われる場合がある．
多様性が失われると，その集団には問題(目的関数)を解くために必要な情報が含まれていない状態になってしまう．
そこで，UMDAという手法を用いて多様性を失わないようにするための学習率の設定などの研究が行われている．

メモリ消費量

変数間の依存性を考慮するような手法では，変数間の情報を保持するために多くのメモリを消費してしまう．
実際に，FDAやBOAといった手法では次元に比例して指数的に空間のオーダーが増加する．
これに対処する方法として，incremental EDAsというものが研究されている．
incremental EDAsは，変数間の依存性を考慮しないモデルから始まり，各反復でいくつかの解(最良解と最悪解など)の情報を用いてモデルの複雑度を徐々に増やす手法である．

モデルの精度

モデルの精度の研究では，大域的最適解を求められた場合の確率モデルの精度を調査する．
これによって，モデルの構造や複雑度に対する理解が進み，新たな手法の提案や理論的な研究の指標とすることができる．

hBOAという手法を用いて複数の目的関数を最適化したときの確率モデルの差異について調査した研究がある．
この研究では，確率モデルは目的関数の関数構造に密接に対応しており，各反復での確率モデルはそれほど大きく変化しないということを明らかにしている．

参考文献

1. An introduction and survey of estimation of distribution algorithms
2. 遺伝的アルゴリズム -その理論と先端的手法-