分布推定アルゴリズムの評価 - 百科事典

配布推定アルゴリズム (EDA)
このセクションでは、複雑さの異なる多くのEDAが構築するモデルについて説明します。以下の通りと仮定しています：世代



t


{\displaystyle t}

、選択オペレータ



S


{\displaystyle S}

、モデル構築オペレータ



α


{\displaystyle \alpha }

、およびサンプリングオペレータ



β


{\displaystyle \beta }

。


単変数分解
最も単純なEDAは、決定変数が独立していると仮定して、すなわち



p
(
X
1
,
X
2
)
=
p
(
X
1
)
⋅
p
(
X
2
)


{\displaystyle p(X_{1},X_{2})=p(X_{1})\cdot p(X_{2})}

。したがって、単変数EDAは単変数統計に依存しており、多元分布は



N


{\displaystyle N}

つの単変数確率分布の積として分解する必要があります。

D
(
Univariate
)
:=
p
(
X
1
,
…
,
X
N
)
=
∏
i
=
1
…
N
p
(
X
i
)
.

このような分解は多くのEDAで使用されており、その一部を以下に説明します。



= 単変数边际分布アルゴリズム (UMDA) =
UMDAは、選択された集団



S
(
P
(
t
)
)


{\displaystyle S(P(t))}

から边际確率を推定するオペレータ



α
U
M
D
A


{\displaystyle \alpha _{UMDA}}

を使用する単純なEDAです。以下のように仮定すると、

S
(
P
(
t
)
)


{\displaystyle S(P(t))}

には

λ


{\displaystyle \lambda }

要素があると仮定します。

α
U
M
D
A
{\displaystyle \alpha _{UMDA}}

は次の確率を生成します：

p
(
t
+
1
)
(
X
i
)
=
1
λ
∑
x
∈
S
(
P
(
t
)
)
x
i
,
∀
i
∈
1
,
2
,
…
,
N
.

UMDAの各ステップは以下のように説明できます：

D
(
t
+
1
)
=
α
U
M
D
A
∘
S
∘
β
λ
(
D
(
t
)
)
.




= 人群ベースのインクリメンタルラーニング (PBIL) =
PBILは、モデルによって人口を暗黙に表現し、新しい解をサンプリングし、モデルを更新します。各世代で、

μ


{\displaystyle \mu }

人間がサンプリングされ、

λ
≤
μ


{\displaystyle \lambda \leq \mu }

が選択されます。その後、以下のようにモデルを更新します：

p
(
t
+
1
)
(
X
i
)
=
(
1
−
γ
)
p
(
t
)
(
X
i
)
+
(
γ
/
λ
)
∑
x
∈
S
(
P
(
t
)
)
x
i