Estrategia de evolución natural

Las estrategias de evolución natural ( NES ) son una familia de algoritmos de optimización numérica para problemas de caja negra . Similares en espíritu a las estrategias de evolución , actualizan iterativamente los parámetros (continuos) de una distribución de búsqueda siguiendo el gradiente natural hacia una mayor aptitud esperada.

Método

El procedimiento general es el siguiente: se utiliza la distribución de búsqueda parametrizada para producir un lote de puntos de búsqueda y se evalúa la función de aptitud en cada uno de esos puntos. Los parámetros de la distribución (que incluyen los parámetros de estrategia ) permiten que el algoritmo capture de forma adaptativa la estructura (local) de la función de aptitud. Por ejemplo, en el caso de una distribución gaussiana , esto comprende la media y la matriz de covarianza . A partir de las muestras, NES estima un gradiente de búsqueda en los parámetros hacia una aptitud esperada más alta. Luego, NES realiza un paso de ascenso de gradiente a lo largo del gradiente natural , un método de segundo orden que, a diferencia del gradiente simple, renormaliza la actualización con respecto a la incertidumbre. Este paso es crucial, ya que evita oscilaciones, convergencia prematura y efectos no deseados derivados de una parametrización dada. Todo el proceso se reitera hasta que se cumple un criterio de detención.

Todos los miembros de la familia NES operan con base en los mismos principios. Se diferencian en el tipo de distribución de probabilidad y el método de aproximación de gradiente utilizado. Diferentes espacios de búsqueda requieren diferentes distribuciones de búsqueda; por ejemplo, en baja dimensionalidad puede ser altamente beneficioso modelar la matriz de covarianza completa. En altas dimensiones, por otro lado, una alternativa más escalable es limitar la covarianza solo a la diagonal . Además, los espacios de búsqueda altamente multimodales pueden beneficiarse de distribuciones de colas más pesadas (como Cauchy , en oposición a la gaussiana). Una última distinción surge entre distribuciones donde podemos calcular analíticamente el gradiente natural y distribuciones más generales donde necesitamos estimarlo a partir de muestras.

Buscar gradientes

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

${\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 multiplicado por las derivadas logarítmicas en . En la práctica, es posible utilizar la aproximación de Monte Carlo basada en un número finito de muestras ${\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 )}$.

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

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

Ascenso de gradiente natural

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 ( vanilla ), 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.

Por lo tanto, la actualización de NES es

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

donde 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 \mathbf {F} }$ ${\displaystyle \nabla _{\theta }\log \pi (x|\theta )}$

Modelado físico

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

${\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.

Pseudocódigo

aporte : ${\displaystyle f,\;\;\theta _{init}}$1 repetición 2 para  hacer ${\displaystyle k=1\ldots \lambda }$   // λ es el tamaño de la población 3 muestras de extracción ${\displaystyle x_{k}\sim \pi (\cdot |\theta )}$ 4 evaluar la aptitud física ${\displaystyle f(x_{k})}$ 5 Calcular derivadas logarítmicas ${\displaystyle \nabla _{\theta }\log \pi (x_{k}|\theta )}$ 6 final 7 asignar las utilidades  ${\displaystyle u_{k}}$ // según el rango 8 estimar el gradiente ${\displaystyle \nabla _{\theta }J\leftarrow {\frac {1}{\lambda }}\sum _{k=1}^{\lambda }u_{k}\cdot \nabla _{\theta }\log \pi (x_{k}|\theta )}$ 9 estimar  ${\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 aprendizaje11 hasta que se cumpla el criterio de detención

Véase también

• Computación evolutiva
• Estrategia de evolución de la adaptación de la matriz de covarianza (CMA-ES)

Bibliografía

• D. Wierstra, T. Schaul, J. Peters y J. Schmidhuber (2008). Estrategias de evolución natural. Congreso IEEE sobre Computación Evolutiva (CEC).
• Y. Sun, D. Wierstra, T. Schaul y J. Schmidhuber (2009). Búsqueda estocástica utilizando el gradiente natural. Conferencia internacional sobre aprendizaje automático (ICML).
• T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra y J. Schmidhuber (2010). Estrategias de evolución natural exponencial. Conferencia sobre computación genética y evolutiva (GECCO).
• T. Schaul, T. Glasmachers y J. Schmidhuber (2011). Dimensiones elevadas y colas pesadas para estrategias de evolución natural. Conferencia sobre computación genética y evolutiva (GECCO).
• T. Schaul (2012). Las estrategias de evolución natural convergen en funciones esféricas. Conferencia sobre computación genética y evolutiva (GECCO).

Enlaces externos

• Colección de implementaciones de NES en diferentes lenguajes