導入
分布推定アルゴリズム( EDA ) は、遺伝的アルゴリズムに触発されたメタヒューリスティックのファミリーを形成します。これらは、考えられる解の品質を記述する関数のサンプリングを操作することにより、最適化問題を解決するために使用されます。点の母集団を使用するすべてのメタヒューリスティックと同様、それらは反復的です。
「古典的な」進化的アルゴリズムとは異なり、この方法の核心は、サンプルの各点に関連付けられた確率分布の推定を通じて、最適化問題のさまざまな変数間の関係を推定することで構成されます。したがって、交差演算子や突然変異演算子は使用せず、サンプルは前の反復で推定された分布パラメーターから直接構築されます。
アルゴリズム
分布推定アルゴリズムに関連する語彙は進化アルゴリズムの語彙から借用したものであるため、「点のサンプル」ではなく「個人の母集団」について、または「目的関数」ではなく「適合度」について説明しますが、これらはすべて用語は同じ意味を持ちます。
一般的なアルゴリズム
基本的なアルゴリズムは、反復ごとに次のように処理されます。
- 与えられた確率分布に従って一連の点をランダムに描画する、
- ベストなポイントを厳選し、
- これらの点の分布を記述する確率分布のパラメータの抽出。
より正確には、アルゴリズムは次のように処理されます。
- M 人の個人をランダムに抽出して母集団Dを形成します。
- i = 0
- 停止基準が検証されない限り、次のようになります。
- i = i + 1
- 前の母集団 ( D i − 1 ) からN個の個体 ( N < M ) を選択して母集団を形成します。 $$ {D^S_{i-1}} $$。
- 母集団の分布を表す確率分布Pi ( x )を推定します。 $$ {D^S_{i-1}} $$。
- Pi ( x )からM個の個人をランダムに抽出します。
- ループの終わり。
「最大 1 つ」問題の例
「one max」問題では、指定された次元数にわたって 1 の数を最大化しようとします。したがって、3 次元問題の場合、解x = {1,1,0} は解x = {0,1,0}よりも品質が高く、最適な値はi * = {1,1,1 }です。したがって、機能を最大化することを追求します
最初のステップは、各変数に対して 2 分の 1 の確率で 1 または 0 を抽選するという条件で、ランダムに個人を抽選することで構成されます。言い換えれば、確率分布を使用します。
6 人の個体からなる母集団D 0から抽出する例では、最後の行は各変数の確率p ( x )を示します。
| 私 | ×1 | ×2 | ×3 | f(x) |
| 1 | 0 | 1 | 0 | 1 |
| 2 | 0 | 1 | 0 | 1 |
| 3 | 1 | 0 | 1 | 2 |
| 4 | 1 | 0 | 1 | 2 |
| 5 | 0 | 1 | 1 | 2 |
| 6 | 1 | 0 | 0 | 1 |
| p(x) | 0.5 | 0.5 | 0.5 |
次のステップは、トレーニングするために最適な個人の選択で構成されます。
| 私 | ×1 | ×2 | ×3 | f(x) |
| 3 | 1 | 0 | 1 | 2 |
| 4 | 1 | 0 | 1 | 2 |
| 5 | 0 | 1 | 1 | 2 |
| p(x) | 0.7 | 0.3 | 1 |
確率分布(
| 私 | ×1 | ×2 | ×3 | f(x) |
| 1 | 1 | 1 | 1 | 3 |
| 2 | 0 | 1 | 1 | 2 |
| 3 | 1 | 0 | 1 | 2 |
| 4 | 1 | 0 | 1 | 2 |
| 5 | 1 | 0 | 1 | 2 |
| 6 | 0 | 0 | 1 | 1 |
| p(x) | 0.7 | 0.3 | 1 |
停止基準が検証されるまで続きます (たとえば、上の表の個体1 のように、すべての個体が最適状態にある場合)。
行動
組み合わせ最適化のほとんどのバージョンは収束します (つまり、最適値を 1回で見つけることができます) ことが (通常はマルコフ モデルまたは動的システムを使用して) 示されています。実数変数での最適化を扱うバリアントの場合、使用される分布モデルがエルゴード性を許容する (つまり、各移動で任意の解を達成することが可能) 場合、収束を実証するのはさらに簡単ですが、多くの場合、準エルゴード性で満足します (メタヒューリスティックが有限の移動数で任意の解に到達できる場合)。
配布モデル
分布推定アルゴリズムの動作は、母集団の状態を記述するために使用される分布モデルの選択に大きく依存します。 Pedro Larrañaga と彼の同僚は、変数間の依存関係を考慮する度合いに応じてこれらのモデルを分類することを提案しています。
- 依存関係のないモデル、
- バイバリアント依存関係を持つモデル、
- 複数のバリアント依存関係を持つモデル。
依存関係のないモデルの場合、確率分布は単一の変数に対して定義された一連の分布から構築されます。言い換えれば、分布は各変数に関係なく、一変量分布から因数分解されます。
上で示した「one max」問題の例は、このカテゴリに分類されます。つまり、変数 x に 1 が含まれる確率は、変数 x に 1 が含まれる確率に影響を与えず、2 つの変数間に相関関係はありません。
依存関係のないモデルは扱いが簡単ですが、依存関係が多数あることが多いため、難しい最適化問題をあまり表現できないという欠点があります。分散モデルの外部で依存関係に対処することは可能ですが、アルゴリズムの操作がより困難になる可能性があります。
二変量依存モデルのタイプでは、二変量分布を基礎として使用することができます。ララニャガら。次に、学習を構造の概念で分類することを提案します。
複数バリアントの依存関係を持つモデルでは、すべての依存関係がモデル内で考慮されます。
 共分散のない二変正規分布から生成されたサンプルの例。 |  共分散が -0.5 の二変正規分布から生成されたサンプルの例。 |