分布推定アルゴリズム

分布推定アルゴリズム（ EDA ）は、確率モデル構築遺伝的アルゴリズム（PMBGA）とも呼ばれ、 ^{[1]有望な候補ソリューションの明示的な確率モデルを構築してサンプリングすることで最適解の探索を導く}確率的最適化手法です。最適化は、許容ソリューションに対する無情報事前分布をエンコードするモデルから始まり、グローバル最適解のみを生成するモデルで終わる、確率モデルの一連の増分更新と見なされます。 ^{[2] [3] [4]}

EDA は進化的アルゴリズムのクラスに属します。EDA と従来のほとんどの進化的アルゴリズムの主な違いは、進化的アルゴリズムが1 つ以上の変動演算子によって定義された暗黙の分布を使用して新しい候補ソリューションを生成するのに対し、EDA はベイジアン ネットワーク、多変量正規分布、または別のモデル クラスによってエンコードされた明示的な確率分布を使用することです。他の進化的アルゴリズムと同様に、EDA はベクトルからLISPスタイルの S 式までのさまざまな表現で定義された最適化問題を解決するために使用でき、候補ソリューションの品質は多くの場合、1 つ以上の目的関数を使用して評価されます。

EDA の一般的な手順は、次のとおりです。

t  := 0
モデルM(0)を初期化して、許容解に対する均一分布を表現する
（終了条件が満たされていない）間、P  := サンプリングによって N>0 の候補ソリューションを生成 M( t 
    ) F
     : = P 内のすべての候補ソリューションを評価
    M(t + 1) := adjust_model( P , F , M( t ))
     t  := t + 1

最適化において明示的な確率モデルを使用することで、EDA は、従来の進化的アルゴリズムや従来の最適化手法のほとんどにとって非常に困難であった最適化問題、たとえば高レベルのエピスタシスを伴う問題^[要出典]を、実行可能に解決できるようになりました。それにもかかわらず、EDA の利点は、これらのアルゴリズムが最適化の専門家に、解決する問題に関する多くの情報を明らかにする一連の確率モデルを提供することです。この情報は、次に、ローカル検索の問題固有の近傍演算子を設計したり、同様の問題に対する EDA の将来の実行にバイアスをかけたり、問題の効率的な計算モデルを作成したりするために使用できます。

たとえば、集団が長さ 4 のビット文字列で表現される場合、EDA は、4 つの確率 (p1、p2、p3、p4) の単一のベクトルを使用して有望なソリューションの集団を表すことができます。ここで、p の各コンポーネントは、その位置が 1 である確率を定義します。この確率ベクトルを使用すると、任意の数の候補ソリューションを作成できます。

このセクションでは、さまざまなレベルの複雑さを持ついくつかのよく知られた EDA によって構築されたモデルについて説明します。世代における集団、選択演算子、モデル構築演算子、およびサンプリング演算子が常に想定されます。 ${\displaystyle P(t)}$${\displaystyle t}$${\displaystyle S}$${\displaystyle \alpha}$${\displaystyle \beta}$

最も単純なEDAは、決定変数が独立していると仮定します。つまり、単変量EDAは単変量統計のみに依存し、多変量分布は単変量確率分布 の積として因数分解する必要があります。${\displaystyle p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})}$${\displaystyle N}$

${\displaystyle D_{\text{Univariate}}:=p(X_{1},\dots ,X_{N})=\prod _{i=1}^{N}p(X_{i}).}$

このような因数分解はさまざまな EDA で使用されています。次に、そのいくつかについて説明します。

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,}$

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

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

CGA ^[7]も単変量分布で定義される暗黙の集団に依存している。各世代で、2つの個体がサンプリングされる。集団は適応度の降順でソートされ、が最良解、 が最悪の解となる。CGAは単変量確率を次のように推定する。 ${\displaystyle t}$${\displaystyle x,y}$${\displaystyle P(t)=\beta _{2}(D(t))}$${\displaystyle P(t)}$${\displaystyle S_{{\text{Sort}}(f)}(P(t))}$${\displaystyle u}$${\displaystyle v}$

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

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

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

一変量モデルは効率的に計算できますが、多くの場合、GA よりも優れたパフォーマンスを提供できるほど代表的ではありません。このような欠点を克服するために、EDA コミュニティでは二変量分解の使用が提案されました。これにより、変数のペア間の依存関係をモデル化できます。二変量分解は次のように定義できます。ここで、 にはに依存する可能性のある変数が含まれます(つまり ) 。 ${\displaystyle \pi _{i}}$${\displaystyle X_{i}}$${\displaystyle |\pi _{i}|=1}$

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

二変量分布と多変量分布は通常、確率的グラフィカル モデル(グラフ) として表され、エッジは統計的依存性 (または条件付き確率) を示し、頂点は変数を示します。データから PGM の構造を学習するには、リンケージ学習が使用されます。

MIMIC ^[8]は、変数間の連続的な依存関係を表す連鎖状のモデルで結合確率分布を因数分解する。これは、真の確率分布、すなわち に対するカルバック・ライブラー・ダイバージェンスを最小化するような決定変数の順列を求める。MIMICは分布をモデル化する 。${\displaystyle r:i\mapsto j}$${\displaystyle x_{r(1)}x_{r(2)},\dots ,x_{r(N)}}$${\displaystyle \pi _{r(i+1)}=\{X_{r(i)}\}}$

${\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]は、二変量分布の結合確率分布を因数分解します。まず、ランダムに選択された変数がグラフのノードとして追加され、グラフ内の変数の1つに最も従属する変数が、まだグラフに存在しない変数の中から選択されます。この手順は、残りの変数がグラフ内のどの変数にも依存しなくなるまで繰り返されます（しきい値に従って検証されます）。

結果として得られるモデルは、ノード をルートとする複数のツリーを持つフォレストです。ルート以外の変数を考慮すると、BMDA は、ルート変数を独立してサンプリングできる一方で、その他すべての変数は親変数に条件付けられる必要がある因数分解分布を推定します。 ${\displaystyle \Upsilon _{t}}$${\displaystyle I_{t}}$${\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)).}$

EDA 開発の次の段階は、多変量因数分解の使用でした。この場合、結合確率分布は通常、限られたサイズのいくつかのコンポーネントに因数分解されます。 ${\displaystyle |\pi _{i}|\leq K,~\forall i\in 1,2,\dots ,N}$

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

多変量分布をエンコードする PGM の学習は計算コストの高いタスクであるため、EDA では二変量統計から多変量統計を推定するのが一般的です。このような緩和により、PGM を多項式時間で構築できますが、このような EDA の一般性も制限されます。 ${\displaystyle N}$

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 は、リンク セットを識別する手順を表す「リンク ラーニング」という用語を普及させました。リンク ラーニング手順は、(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 の改善が不可能になるまで繰り返され、リンケージ モデルが生成されます。ECGA は具体的な集団で動作するため、ECGA によってモデル化された因数分解分布を使用すると、次のように記述できます。 ${\displaystyle T_{\text{eCGA}}}$

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

BOA ^{[11] [12] [13]}はベイジアンネットワークを使用して有望なソリューションをモデル化してサンプリングします。ベイジアンネットワークは有向非巡回グラフであり、ノードは変数を表し、エッジは変数のペア間の条件付き確率を表します。変数の値は、で定義される他の変数の最大値に条件付けることができます。BOAは、因数分解された結合分布をエンコードしたPGMを構築します。このPGMでは、ネットワークのパラメータ、つまり条件付き確率が、最大尤度推定量を使用して選択された母集団から推定されます。 ${\displaystyle x_{i}}$${\displaystyle K}$${\displaystyle \pi _{i}}$

${\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とは異なります。リンクは、確率分布が関連付けられていないリンクセットの集合であるため、から直接新しいソリューションをサンプリングする方法はありません。リンクモデルは、セットファミリー（FOS） として保存されるリンクツリーです。${\displaystyle T}$${\displaystyle T}$

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

リンクツリー学習手順は、階層型クラスタリングアルゴリズムであり、次のように機能します。各ステップで、最も近い2 つのクラスターがマージされ、この手順は 1 つのクラスターのみが残るまで繰り返され、各サブツリーはサブセットとして保存されます。 ${\displaystyle i}$${\displaystyle j}$${\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}$

アルゴリズム遺伝子プール最適混合
   入力: サブセットの族と母集団
   出力: 母集団.
    for each in do for each in do 
           choose a random  := := if then return${\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))}$

• 確率集団（PC）^{[16] [17]}
• 学習を伴うヒルクライミング（HCwL）^[18]
• 多変量正規分布の推定アルゴリズム (EMNA) ^{[引用が必要]}
• ベイジアンネットワーク推定アルゴリズム（EBNA）^[要出典]
• 正規分布のベクトルによる学習を用いた確率的山登り法（SHCLVND）^[19]
• 実数コード化PBIL ^[要出典]
• 利己的遺伝子アルゴリズム（SG）^[20]
• コンパクト差分進化（cDE）^[21]とその変種^{[22] [23] [24] [25] [26] [27]}
• コンパクト粒子群最適化（cPSO）^[28]
• コンパクトバクテリア採餌最適化（cBFO）^[29]
• 確率的増分プログラム進化（PIPE）^[30]
• ガウスネットワーク推定アルゴリズム（EGNA）^[要出典]
• 閾値収束による多変量正規分布推定アルゴリズム^[31]
• 依存構造マトリックス遺伝的アルゴリズム（DSMGA）^{[32] [33]}

• CMA-ES
• クロスエントロピー法
• 蟻コロニー最適化アルゴリズム