分布推定アルゴリズム

UMDA ^{[ 5 ]}は、演算子を使用するシンプルな EDA です。${\displaystyle \alpha _{UMDA}}$選択された母集団から周辺確率を推定する${\displaystyle S(P(t))}$仮定することで${\displaystyle S(P(t))}$含む${\displaystyle \lambda }$要素、${\displaystyle \alpha _{UMDA}}$確率を生成する：

${\displaystyle p_{t+1}(X_{i})={\dfrac {1}{\lambda }}\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N.}$

UMDAの各ステップは次のように説明できます。

${\displaystyle D(t+1)=\alpha _{\text{UMDA}}\circ S\circ \beta _{\lambda }(D(t)).}$

PBIL ^{[ 6 ]}は、そのモデルによって暗黙的に集団を表現し、そこから新しい解をサンプリングしてモデルを更新します。各世代で、${\displaystyle \mu }$個人がサンプリングされ、${\displaystyle \lambda \leq \mu }$が選択される。これらの個体は、次のようにモデルを更新するために使用される。

${\displaystyle p_{t+1}(X_{i})=(1-\gamma )p_{t}(X_{i})+(\gamma /\lambda )\sum _{x\in S(P(t))}x_{i},~\forall i\in 1,2,\dots ,N,}$

どこ${\displaystyle \gamma \in (0,1]}$は学習率を定義するパラメータであり、小さい値は前のモデルが${\displaystyle p_{t}(X_{i})}$サンプリングされた新しいソリューションによってわずかに修正されるだけであるはずです。PBILは次のように説明できます。

${\displaystyle D(t+1)=\alpha _{\text{PIBIL}}\circ S\circ \beta _{\mu }(D(t))}$

CGA ^{[ 7 ]}もまた、単変量分布によって定義される暗黙の母集団に依存している。各世代において${\displaystyle t}$2人の個人${\displaystyle x,y}$サンプリングされる、${\displaystyle P(t)=\beta _{2}(D(t))}$人口${\displaystyle P(t)}$次に、適応度の高い順に並べ替えられます。${\displaystyle S_{{\text{Sort}}(f)}(P(t))}$、 と${\displaystyle u}$最高であること、そして${\displaystyle v}$最悪の解決策である。CGAは単変量確率を次のように推定する。

${\displaystyle p_{t+1}(X_{i})=p_{t}(X_{i})+\gamma (u_{i}-v_{i}),\quad \forall i\in 1,2,\dots ,N,}$

どこ、${\displaystyle \gamma \in (0,1]}$は学習率を定義する定数で、通常は に設定されます。${\displaystyle \gamma =1/N}$CGAは次のように定義できます。

${\displaystyle D(t+1)=\alpha _{\text{CGA}}\circ S_{{\text{Sort}}(f)}\circ \beta _{2}(D(t))}$

MIMIC ^{[ 8 ]}は、変数間の連続的な依存関係を表す連鎖のようなモデルで結合確率分布を因数分解します。決定変数の順列を見つけ、${\displaystyle r:i\mapsto j}$、したがって${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$真の確率分布との関連でカルバック・ライブラー情報量を最小化する、すなわち${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$MIMICモデルは分布をモデル化します。

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=p_{t}(X_{r(N)})\prod _{i=1}^{N-1}p_{t}(X_{r(i)}|X_{r(i+1)}).}$

新しい解は左端の変数から右端の変数へとサンプリングされ、最初の解は独立して生成され、残りは条件付き確率に基づいて生成されます。推定分布は世代ごとに再計算する必要があるため、MIMICは具体的な母集団を次のように使用します。

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{MIMIC}}\circ S(P(t)).}$

BMDA ^{[ 9 ]}は、結合確率分布を二変量分布に因数分解します。まず、ランダムに選択された変数がグラフのノードとして追加され、グラフ内のいずれかの変数に最も依存する変数が、まだグラフに含まれていない変数の中から選択されます。この手順は、残りの変数がグラフ内のどの変数にも依存しなくなるまで繰り返されます (閾値に従って確認)。

結果として得られるモデルは、ノードに根を張った複数の木を持つ森である。${\displaystyle \Upsilon _{t}}$検討する${\displaystyle I_{t}}$非ルート変数に関して、BMDAは因子化分布を推定し、ルート変数は独立してサンプリングできるが、他のすべての変数は親変数に条件付けされなければならない。${\displaystyle \pi _{i}}$。

${\displaystyle p_{t+1}(X_{1},\dots ,X_{N})=\prod _{X_{i}\in \Upsilon _{t}}p_{t}(X_{i})\cdot \prod _{X_{i}\in I_{t}}p_{t}(X_{i}|\pi _{i}).}$

BMDAの各ステップは以下のように定義される。

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BMDA}}\circ S(P(t)).}$

ECGA ^{[ 10 ]}は、決定変数間の高次の依存関係をモデル化できる多変量因子分解を採用した最初の EDA の 1 つです。そのアプローチでは、結合確率分布を多変量周辺分布の積に因子分解します。${\displaystyle T_{\text{eCGA}}=\{\tau _{1},\dots ,\tau _{\Psi }\}}$は部分集合の集合であり、その中のすべての${\displaystyle \tau \in T_{\text{eCGA}}}$連結セットであり、${\displaystyle |\tau |\leq K}$変数。因数分解された同時確率分布は次のように表されます。

${\displaystyle p(X_{1},\dots ,X_{N})=\prod _{\tau \in T_{\text{eCGA}}}p(\tau ).}$

ECGAは、リンケージセットを特定する手順を指す用語として「リンケージ学習」を普及させた。ECGAのリンケージ学習手順は、(1)モデル複雑度(MC)と(2)圧縮個体群複雑度(CPC)という2つの指標に基づいている。MCは、すべての周辺確率を格納するために必要なビット数でモデル表現のサイズを定量化する。

${\displaystyle MC=\log _{2}(\lambda +1)\sum _{\tau \in T_{\text{eCGA}}}(2^{|\tau |-1}),}$

一方、CPCは、すべてのパーティションにわたる周辺分布のエントロピーの観点からデータ圧縮を定量化する。${\displaystyle \lambda }$選択された人口規模は、${\displaystyle |\tau |}$は、連結セット内の決定変数の数です。${\displaystyle \tau }$そして${\displaystyle H(\tau )}$は、変数の結合エントロピーです。${\displaystyle \tau }$

${\displaystyle CPC=\lambda \sum _{\tau \in T_{\text{eCGA}}}H(\tau ).}$

ECGAにおけるリンケージ学習は、以下の手順で行われます。(1) 各変数をクラスターに挿入する、(2) 現在のリンケージセットのCCC = MC + CPCを計算する、(3) クラスターのペアを結合することによって得られるCCCの増加を確認する、(4) CCCの改善が最も大きいクラスターを結合する。この手順は、CCCの改善が不可能になるまで繰り返され、リンケージモデルが生成されます。${\displaystyle T_{\text{eCGA}}}$ECGAは具体的な集団を扱うため、ECGAによってモデル化された因子化分布を使用すると、次のように記述できます。

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{eCGA}}\circ S(P(t))}$

BOA ^{[ 11 ] [ 12 ] [ 13 ]}は、有望な解をモデル化およびサンプリングするためにベイジアンネットワークを使用します。ベイジアンネットワークは有向非巡回グラフであり、ノードは変数を表し、エッジは変数のペア間の条件付き確率を表します。変数の値は${\displaystyle x_{i}}$最大で条件付け可能${\displaystyle K}$その他の変数は、${\displaystyle \pi _{i}}$BOAは、因数分解された同時分布を符号化したPGMを構築します。このPGMでは、ネットワークのパラメータ、すなわち条件付き確率は、選択された母集団から最尤推定法を用いて推定されます。

${\displaystyle p(X_{1},X_{2},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}|\pi _{i}).}$

一方、ベイジアンネットワーク構造は反復的に構築する必要があります（リンケージ学習）。エッジのないネットワークから始まり、各ステップで、何らかのスコアリング指標（例えば、ベイジアン情報量規準（BIC）または尤度等価性を持つベイジアン・ディリクレ距離（BDe））をより良く改善するエッジを追加します。 ^{[ 14 ]}スコアリング指標は、選択された集団のモデリングにおける精度に基づいてネットワーク構造を評価します。構築されたネットワークから、BOAは次のように新しい有望な解をサンプリングします。（1）各変数の祖先順序を計算し、各ノードの前に親ノードを配置します。（2）各変数は、親ノードに条件付きでサンプリングされます。このようなシナリオでは、BOAの各ステップは次のように定義できます。

${\displaystyle P(t+1)=\beta _{\mu }\circ \alpha _{\text{BOA}}\circ S(P(t))}$

LTGA ^{[ 15 ]}は、確率分布を明示的にモデル化するのではなく、リンケージツリーと呼ばれるリンケージモデルのみをモデル化するという点で、ほとんどの EDA とは異なります。${\displaystyle T}$これは確率分布が関連付けられていない連結セットの集合であるため、新しい解を直接サンプリングする方法はありません。${\displaystyle T}$リンケージモデルは、集合のファミリー（FOS）として生成され格納されるリンケージツリーです。

${\displaystyle T_{\text{LT}}=\{\{x_{1}\},\{x_{2}\},\{x_{3}\},\{x_{4}\},\{x_{1},x_{2}\},\{x_{3},x_{4}\}\}.}$

リンクツリー学習手順は階層的クラスタリングアルゴリズムであり、次のように動作します。各ステップで最も近い2 つのクラスター${\displaystyle i}$そして${\displaystyle j}$マージされ、この手順はクラスターが 1 つだけ残るまで繰り返され、各サブツリーはサブセットとして保存されます。${\displaystyle \tau \in T_{\text{LT}}}$。

LTGAは${\displaystyle T_{\text{LT}}}$再結合演算子に似ているが、改善する動きのみを受け入れる「最適混合」手順を導く。これを次のように表す。${\displaystyle R_{\text{LTGA}}}$表記法${\displaystyle x[\tau ]\gets y[\tau ]}$は、遺伝物質の移転を示します。${\displaystyle \tau }$から${\displaystyle y}$に${\displaystyle x}$。

アルゴリズム：遺伝子プール最適混合 入力：部分集合の集合${\displaystyle T_{\text{LT}}}$そして人口${\displaystyle P(t)}$ 出力: 人口${\displaystyle P(t+1)}$. 各${\displaystyle x_{i}}$で${\displaystyle P(t)}$各項目に対して実行${\displaystyle \tau }$で${\displaystyle T_{\text{LT}}}$ ランダムに選択してください${\displaystyle x_{j}\in P(t):x_{i}\neq x_{j}}$${\displaystyle f_{x_{i}}}$:=${\displaystyle f(x_{i})}$${\displaystyle x_{i}[\tau ]}$:=${\displaystyle x_{j}[\tau ]}$もし${\displaystyle f(x_{i})\leq f_{x_{i}}}$それから${\displaystyle x_{i}[\tau ]:=x_{j}[\tau ]}$戻る${\displaystyle P(t)}$

LTGAは典型的な選択演算子を実装せず、代わりに選択は組み換え中に実行されます。同様の考え方は通常、局所探索ヒューリスティクスに適用されており、この意味でLTGAはハイブリッド手法と見なすことができます。要約すると、LTGAの1つのステップは次のように定義されます。

${\displaystyle P(t+1)=R_{\text{LTGA}}(P(t))\circ \alpha _{\text{LTGA}}(P(t))}$