自然進化戦略

させて${\displaystyle \theta }$探索分布のパラメータを表す${\displaystyle \pi (x\,|\,\theta )}$そして${\displaystyle f(x)}$適合度関数は次のように評価されます。${\displaystyle x}$NESは、探索分布の下で期待される適応度を最大化するという目的を追求します。

${\displaystyle J(\theta )=\operatorname {E} _{\theta }[f(x)]=\int f(x)\;\pi (x\,|\,\theta )\;dx}$

勾配上昇法によって。勾配は次のように書き換えることができます。

${\displaystyle \nabla _{\theta }J(\theta )=\nabla _{\theta }\int f(x)\;\pi (x\,|\,\theta )\;dx}$

${\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;dx}$

${\displaystyle =\int f(x)\;\nabla _{\theta }\pi (x\,|\,\theta )\;{\frac {\pi (x\,|\,\theta )}{\pi (x\,|\,\theta )}}\;dx}$

${\displaystyle =\int {\Big [}f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta ){\Big ]}\;\pi (x\,|\,\theta )\;dx}$

${\displaystyle =\operatorname {E} _{\theta }\left[f(x)\;\nabla _{\theta }\log \pi (x\,|\,\theta )\right]}$

つまり、期待値は${\displaystyle f(x)}$対数微分を掛けた${\displaystyle x}$実際には、有限個のモンテカルロ近似を使用することが可能です。${\displaystyle \lambda }$サンプル

${\displaystyle \nabla _{\theta }J(\theta )\approx {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }f(x_{k})\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )}$。

最後に、探索分布のパラメータを反復的に更新することができる。

${\displaystyle \theta \leftarrow \theta +\eta \nabla _{\theta }J(\theta )}$

NESは、更新に単純な確率的勾配を使用する代わりに、自然勾配に従います。自然勾配は、単純な（バニラ）勾配に比べて多くの利点があることが示されています。例：

• 勾配の方向は、探索分布のパラメータ化とは無関係である。
• 更新された数値は不確実性に基づいて自動的に調整され、それによって高原や尾根での収束が加速される。

NESのアップデートは

${\displaystyle \theta \leftarrow \theta +\eta \mathbf {F} ^{-1}\nabla _{\theta }J(\theta )}$、

どこ${\displaystyle \mathbf {F} }$はフィッシャー情報行列です。フィッシャー行列は、場合によっては正確に計算できますが、そうでない場合は、対数微分を再利用してサンプルから推定されます。${\displaystyle \nabla _{\theta }\log \pi (x|\theta )}$。

NESは、アルゴリズムの堅牢性を高め、適応度関数の単調増加変換に対して不変にするために、ランクベースの適応度整形を利用します。この目的のために、集団の適応度は一連の効用値 に変換されます。${\displaystyle u_{1}\geq \dots \geq u_{\lambda }}$。 させて${\displaystyle x_{i}}$i^番目に優れた個体を表す。適合度を効用に置き換えると、勾配推定値は次のようになる。

${\displaystyle \nabla _{\theta }J(\theta )=\sum _{k=1}^{\lambda }u_{k}\;\nabla _{\theta }\log \pi (x_{k}\,|\,\theta )}$。

効用関数の選択は、アルゴリズムの自由パラメータである。

入力:${\displaystyle f,\;\;\theta _{init}}$ 1 回繰り返し 2 つで${\displaystyle k=1\ldots \lambda }$do // λは個体群のサイズです 3 サンプルを描画${\displaystyle x_{k}\sim \pi (\cdot |\theta )}$ 4. フィットネスを評価する${\displaystyle f(x_{k})}$ 5. 対数微分を計算する${\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )}$ 6 終了 7 ユーティリティを割り当てる$u_k$// ランクに基づく 8. 勾配を推定する${\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )}$ 9 推定${\displaystyle \mathbf {F} \leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }\nabla _{\theta }\log \pi (x_{k}|\theta )\nabla _{\theta }\log \pi (x_{k}|\theta )^{\top }}$// または正確に計算する 10個の 更新パラメータ${\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _{\theta }J}$// ηは学習率です 停止条件が満たされるまで 11回繰り返す