分布推定アルゴリズムあるいは確率モデル遺伝的アルゴリズム

分布推定アルゴリズム（estimation of distribution algorithm: EDA）、あるいは確率モデル遺伝的アルゴリズム（probabilistic model-building genetic algorithm: PMBGA）と呼ばれる、ヒューリスティックな最適化アルゴリズムについて調べる機会があったのでメモ。

遺伝的アルゴリズムは、個体同士を交叉・突然変異させることで最適解をヒューリスティックに探索する最適化アルゴリズムであり、個体の生成モデルは陽に示されない。一方でEDAは、個体が生成される確率モデルを陽に定義し、それを逐次修正していくものである。英語版Wikipediaの図を見るとわかりやすい（ブログの背景が黒いせいで見づらくなっているが）。探索中に得られた最小値（注：真の最小値とは限らない）の近傍で確率が高くなるように確率密度関数を修正していく。確率が低い裾野の部分が、遺伝的アルゴリズムでいうところの「突然変異」に相当するのだろうと理解している。

By Johann Dréo (User:Nojhan) - Own work, CC BY-SA 3.0, Link

上記図は、以下ページより引用。 en.wikipedia.org

同様のアイデア（モデルの更新方法は違うっぽいが）でより広く知られているのは、 CMA-ES (covariance matrix adaptation evolution strategy)だろう。個体の生成モデルは多変量正規分布であり、良い個体に対する尤度が最大になるよう平均と分散が更新される（英語版Wikipedia斜め読みしただけなので違うかも）。

By Sentewolf (talk) (Uploads) - Transferred from en.wikipedia to Commons., Public Domain, Link