分布推定アルゴリズム

Estimation of Distribution Algorithm。EDA。Probabilistic Model-Building Genetic Algorithms (PMBGA) とも呼ばれる。最適化問題のアルゴリズム。

遺伝的アルゴリズムの拡張である。シンプルGAが交叉と突然変異から次の世代を作るのに対して、EDAでは、個体の分布の推定を求め、それに基づいて次の世代の探索点を決める。シンプルGAは個体の集合を元に探索を行うのに対して、EDAでは個体の生成確率に基づいて探索を行う。

1994年に、Shumeet BalujaのPopulation-Based Incremental Learning (PBIL)によって、この分野の開拓が始まった。PBILは遺伝的アルゴリズムよりも単純なアルゴリズムであるにもかかわらず、品質と速度の両面で遺伝的アルゴリズムを上回った。

アルゴリズムの一例

• ビットストリング
  • Population-Based Incremental Learning (PBIL)
  • Hill Climbing with Learning (HCwL)
  • 単変量周辺分布アルゴリズム (Univariate Marginal Distribution Algorithm; UMDA)
  • Compact Genetic Algorithm (cGA)
  • Mutual Information Maximimization for Input Clustering (MIMIC)
  • 二変量周辺分布アルゴリズム (Bivariate Marginal Distribution Algorithm; BMDA)
  • Extended Compact Genetic Algorithm (ECGA)
  • ベイジアン最適化アルゴリズム (Bayesian Optimization Algorithm; BOA)
  • Estimation of Bayesian Networks Algorithm (EBNA)
• 実数値ベクトル
  • Stochastic hill climbing with learning by vectors of normal distributions (SHCLVND)
  • Real-coded PBIL
  • Probabilistic Incremental Program Evolution (PIPE)
  • Estimation of Gaussian Networks Algorithm (EGNA)