estrategia de evolución natural

Dejar${\displaystyle \theta }$denotan los parámetros de la distribución de búsqueda${\displaystyle \pi (x\,|\,\theta )}$y${\displaystyle f(x)}$la función de aptitud evaluada en${\displaystyle x}$NES persigue entonces el objetivo de maximizar la aptitud esperada bajo la distribución de búsqueda.

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

mediante ascenso de gradiente . El gradiente se puede reescribir como

${\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]}$

es decir, el valor esperado de${\displaystyle f(x)}$veces las derivadas logarítmicas en${\displaystyle x}$En la práctica, es posible utilizar la aproximación de Monte Carlo basada en un número finito de${\displaystyle \lambda }$muestras

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

Finalmente, los parámetros de la distribución de búsqueda se pueden actualizar iterativamente.

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

En lugar de utilizar el gradiente estocástico simple para las actualizaciones, NES sigue el gradiente natural , que ha demostrado tener numerosas ventajas sobre el gradiente simple ( vainilla ), por ejemplo:

• La dirección del gradiente es independiente de la parametrización de la distribución de búsqueda.
• Las magnitudes de las actualizaciones se ajustan automáticamente en función de la incertidumbre, lo que a su vez acelera la convergencia en mesetas y crestas.

La actualización de NES es, por lo tanto,

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

dónde${\displaystyle \mathbf {F} }$es la matriz de información de Fisher . La matriz de Fisher a veces se puede calcular con exactitud, de lo contrario se estima a partir de muestras, reutilizando las derivadas logarítmicas.${\displaystyle \nabla _{\theta }\log \pi (x|\theta )}$.

NES utiliza la conformación de aptitud basada en rangos para hacer que el algoritmo sea más robusto e invariante ante transformaciones monótonamente crecientes de la función de aptitud. Para ello, la aptitud de la población se transforma en un conjunto de valores de utilidad .${\displaystyle u_{1}\geq \dots \geq u_{\lambda }}$. Dejar${\displaystyle x_{i}}$denotemos el i ^-ésimo mejor individuo. Reemplazando la aptitud por la utilidad, la estimación del gradiente se convierte en

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

La elección de la función de utilidad es un parámetro libre del algoritmo.

aporte :${\displaystyle f,\;\;\theta _{init}}$ 1 repetición 2 por${\displaystyle k=1\ldots \lambda }$hacer // λ es el tamaño de la población 3. Extraer una muestra${\displaystyle x_{k}\sim \pi (\cdot |\theta )}$ 4 evaluar la aptitud${\displaystyle f(x_{k})}$ 5. Calcular las derivadas logarítmicas.${\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )}$ 6 fin 7. Asignar los servicios públicos${\displaystyle u_{k}}$// basado en el rango 8 estimar la pendiente${\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )}$ 9 estimación${\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 }}$// o calcularlo exactamente 10 parámetros de actualización${\displaystyle \theta \leftarrow \theta +\eta \cdot \mathbf {F} ^{-1}\nabla _ {\theta }J}$// η es la tasa de aprendizaje 11 hasta que se cumpla el criterio de parada