Las estrategias de evolución natural ( NES ) son una familia de algoritmos de optimización numérica para problemas de caja negra . De espíritu similar 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: la distribución de búsqueda parametrizada se utiliza para producir un lote de puntos de búsqueda y la función de aptitud se evalúa en cada uno de esos puntos. Los parámetros de la distribución (que incluyen 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 , esta 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 mayor aptitud esperada. 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 la incertidumbre. Este paso es crucial, ya que evita oscilaciones, convergencias prematuras y efectos no deseados derivados de una parametrización determinada. Todo el proceso se reitera hasta que se cumple un criterio de parada.
Todos los miembros de la familia NES operan sobre la base de los mismos principios. Se diferencian en el tipo de distribución de probabilidad y el método de aproximación de gradiente utilizado. Los diferentes espacios de búsqueda requieren diferentes distribuciones de búsqueda; por ejemplo, en baja dimensionalidad puede ser muy beneficioso modelar la matriz de covarianza completa. En las dimensiones altas, 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 más pesadas (como Cauchy , en contraposición a la gaussiana). Surge una última distinción entre distribuciones en las que podemos calcular analíticamente el gradiente natural y distribuciones más generales en las que necesitamos estimarlo a partir de muestras.
Gradientes de búsqueda
Dejar denotar los parámetros de la distribución de búsqueda y la función de aptitud evaluada en . Luego, NES persigue el objetivo de maximizar la aptitud esperada bajo la distribución de búsqueda
a través del ascenso en pendiente . El degradado se puede reescribir como
es decir, el valor esperado deveces 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
- .
Finalmente, los parámetros de la distribución de búsqueda se pueden actualizar de forma iterativa.
Ascenso en gradiente natural
En lugar de utilizar el gradiente estocástico simple para las actualizaciones, NES sigue el gradiente natural , que se ha demostrado que posee 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.
Por lo tanto, la actualización de NES es
- ,
dónde 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.
Modelado de fitness
NES utiliza el modelado de aptitud basado en rango para hacer que el algoritmo sea más robusto e invariante bajo 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. Dejardenotar el i ésimo mejor individuo. Reemplazando la aptitud con la utilidad, la estimación del gradiente se convierte en
- .
La elección de la función de utilidad es un parámetro libre del algoritmo.
Pseudocódigo
entrada : 1 repetición 2 para do // λ es el tamaño de la población 3 sacar muestra 4 evaluar la aptitud 5 calcular derivadas logarítmicas 6 fin 7 asignar las utilidades // basado en el rango 8 estima el gradiente 9 estimación // o calcularlo exactamente 10 parámetros de actualización // η es la tasa de aprendizaje11 hasta que se cumpla el criterio de parada
Ver también
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 degradado natural . Congreso Internacional de Aprendizaje Automático (ICML).
- T. Glasmachers, T. Schaul, Y. Sun, D. Wierstra y J. Schmidhuber (2010). Estrategias de evolución natural exponencial . Conferencia de Computación Genética y Evolutiva (GECCO).
- T. Schaul, T. Glasmachers y J. Schmidhuber (2011). Grandes dimensiones y colas pesadas para estrategias de evolución natural . Conferencia de Computación Genética y Evolutiva (GECCO).
- T. Schaul (2012). Las estrategias de evolución natural convergen en las funciones de la esfera . Conferencia de Computación Genética y Evolutiva (GECCO).