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 . 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.
El procedimiento general es el siguiente: la distribución de búsqueda parametrizada se usa 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 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. NES luego 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, convergencias prematuras y efectos no deseados derivados de una determinada parametrización. Todo el proceso se repite hasta que se cumple un criterio de parada.
Todos los miembros de la familia NES funcionan según los mismos principios. Difieren 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 muy beneficioso modelar la matriz de covarianza completa. En 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 de colas más pesadas (como Cauchy, a diferencia de 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.
Denotemos los parámetros de la distribución de búsqueda y la función de aptitud evaluada en . NES luego persigue el objetivo de maximizar la aptitud esperada bajo la distribución de búsqueda
es decir, el valor esperado de multiplicar 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
En lugar de usar el gradiente estocástico simple para las actualizaciones, NES sigue el gradiente natural , que ha demostrado poseer numerosas ventajas sobre el gradiente simple ( vainilla ), por ejemplo: