Estrategias de evolución desde cero en Python

Estrategias de evolución es un algoritmo de optimización global estocástico.

Es un algoritmo evolutivo relacionado con otros, como el algoritmo genético, aunque está diseñado específicamente para la optimización continua de funciones.

En este tutorial, descubrirá cómo implementar el algoritmo de optimización de estrategias de evolución.

Después de completar este tutorial, sabrá:


Recomendado: ¿Qué es el Big data?.


  • Evolution Strategies es un algoritmo estocástico de optimización global inspirado en la teoría biológica de la evolución por selección natural.
  • Existe una terminología estándar para las estrategias de evolución y dos versiones comunes del algoritmo denominadas (mu, lambda) -ES y (mu + lambda) -ES.
  • Cómo implementar y aplicar el algoritmo Evolution Strategies a funciones objetivas continuas.

Empecemos.

Estrategias de evolución desde cero en Python

Estrategias de evolución desde cero en Python
Foto de Alexis A. Bermúdez, algunos derechos reservados.

Descripción general del tutorial

Este tutorial se divide en tres partes; son:

  1. Estrategias de evolución
  2. Desarrollar un (mu, lambda) -ES
  3. Desarrollar un (mu + lambda) -ES

Estrategias de evolución

Las estrategias de evolución, a veces denominadas estrategia de evolución (singular) o ES, es un algoritmo de optimización global estocástico.

La técnica fue desarrollada en la década de 1960 para ser implementada manualmente por ingenieros para diseños de arrastre mínimo en un túnel de viento.

La familia de algoritmos conocida como Evolution Strategies (ES) fue desarrollada por Ingo Rechenberg y Hans-Paul Schwefel en la Universidad Técnica de Berlín a mediados de la década de 1960.

– Página 31, Fundamentos de metaheurística, 2011.

Evolution Strategies es un tipo de algoritmo evolutivo y está inspirado en la teoría biológica de la evolución por medio de la selección natural. A diferencia de otros algoritmos evolutivos, no utiliza ninguna forma de cruce; en cambio, la modificación de las soluciones candidatas se limita a los operadores de mutación. De esta manera, las Estrategias de Evolución se pueden considerar como un tipo de escalada estocástica paralela.

El algoritmo involucra una población de soluciones candidatas que inicialmente se generan aleatoriamente. Cada iteración del algoritmo implica primero evaluar la población de soluciones y luego eliminar todas menos un subconjunto de las mejores soluciones, lo que se conoce como selección de truncamiento. Las soluciones restantes (los padres) se utilizan como base para generar una serie de nuevas soluciones candidatas (mutación) que reemplazan o compiten con los padres por una posición en la población para su consideración en la próxima iteración del algoritmo (generación).

Hay una serie de variaciones de este procedimiento y una terminología estándar para resumir el algoritmo. El tamaño de la población se conoce como lambda y el número de padres seleccionados en cada iteración se denomina mu.

El número de hijos creados a partir de cada padre se calcula como (lambda / mu) y los parámetros deben elegirse de modo que la división no tenga resto.

  • mu: El número de padres seleccionados en cada iteración.
  • lambda: Tamaño de la población.
  • lambda / mu: Número de hijos generados por cada padre seleccionado.

Se utiliza una notación entre corchetes para describir la configuración del algoritmo, p. Ej. (mu, lambda) -ES. Por ejemplo, si mu = 5 y lambda = 20, entonces se resumiría como (5, 20) -ES. Una coma (,) que separa el mu y lambda parámetros indica que los hijos reemplazan a los padres directamente en cada iteración del algoritmo.

  • (mu, lambda) -ES: Una versión de las estrategias de evolución donde los niños reemplazan a los padres.

Una separación más (+) de los parámetros mu y lambda indica que los niños y los padres juntos definirán la población para la siguiente iteración.

  • (mu + lambda) -ES: Una versión de las estrategias de evolución donde los niños y los padres se suman a la población.

Un algoritmo de escalada estocástico se puede implementar como una estrategia de evolución y tendría la notación (1 + 1) -ES.

Este es el algoritmo ES símil o canónico y hay muchas extensiones y variantes descritas en la literatura.

Ahora que estamos familiarizados con Evolution Strategies, podemos explorar cómo implementar el algoritmo.

Desarrollar un (mu, lambda) -ES

En esta sección, desarrollaremos un (mu, lambda) -ES, es decir, una versión del algoritmo donde los niños reemplazan a los padres.

Primero, definamos un problema de optimización desafiante como la base para implementar el algoritmo.

La función Ackley es un ejemplo de una función objetivo multimodal que tiene un único óptimo global y múltiples óptimos locales en los que una búsqueda local puede atascarse.

Como tal, se requiere una técnica de optimización global. Es una función objetivo bidimensional que tiene un óptimo global en [0,0], que se evalúa como 0.0.

El siguiente ejemplo implementa el Ackley y crea un gráfico de superficie tridimensional que muestra los óptimos globales y múltiples óptimos locales.

La ejecución del ejemplo crea el gráfico de superficie de la función Ackley que muestra la gran cantidad de óptimos locales.

Gráfico de superficie 3D de la función multimodal de Ackley

Gráfico de superficie 3D de la función multimodal de Ackley

Generaremos soluciones candidatas aleatorias, así como versiones modificadas de soluciones candidatas existentes. Es importante que todas las soluciones candidatas estén dentro de los límites del problema de búsqueda.

Para lograr esto, desarrollaremos una función para verificar si una solución candidata está dentro de los límites de la búsqueda y luego la descartaremos y generaremos otra solución si no lo está.

los in_bounds () La función siguiente tomará una solución candidata (punto) y la definición de los límites del espacio de búsqueda (límites) y devolverá Verdadero si la solución está dentro de los límites de la búsqueda o Falso en caso contrario.

Luego podemos usar esta función al generar la población inicial de “justicia” (p.ej. lambda) soluciones candidatas aleatorias.

Por ejemplo:

A continuación, podemos iterar sobre un número fijo de iteraciones del algoritmo. Cada iteración implica primero evaluar cada solución candidata en la población.

Calcularemos las puntuaciones y las almacenaremos en una lista paralela separada.

A continuación, debemos seleccionar “muLos padres con las mejores puntuaciones, las más bajas en este caso, ya que estamos minimizando la función objetivo.

Haremos esto en dos pasos. Primero, clasificaremos las soluciones candidatas en función de sus puntajes en orden ascendente, de modo que la solución con el puntaje más bajo tenga un rango de 0, la siguiente tenga un rango de 1, y así sucesivamente. Podemos usar una doble llamada de la función argsort para lograr esto.

Luego usaremos los rangos y seleccionaremos aquellos padres que tengan un rango por debajo del valor “mu. ” Esto significa que si mu se establece en 5 para seleccionar 5 padres, solo se seleccionarán aquellos padres con un rango entre 0 y 4.

Luego podemos crear hijos para cada padre seleccionado.

Primero, debemos calcular el número total de hijos a crear por padre.

Luego podemos iterar sobre cada padre y crear versiones modificadas de cada uno.

Crearemos niños utilizando una técnica similar a la utilizada en la escalada estocástica. Específicamente, cada variable se muestreará utilizando una distribución gaussiana con el valor actual como la media y la desviación estándar proporcionada como “Numero de pie”Hiperparámetro.

También podemos comprobar si cada padre seleccionado es mejor que la mejor solución vista hasta ahora para poder devolver la mejor solución al final de la búsqueda.

Los hijos creados se pueden agregar a una lista y podemos reemplazar la población con la lista de hijos al final de la iteración del algoritmo.

Podemos unir todo esto en una función llamada es_comma () que realiza la versión en coma del algoritmo de estrategia de evolución.

La función toma el nombre de la función objetivo, los límites del espacio de búsqueda, el número de iteraciones, el tamaño del paso y los hiperparámetros mu y lambda y devuelve la mejor solución encontrada durante la búsqueda y su evaluación.

A continuación, podemos aplicar este algoritmo a nuestra función objetivo de Ackley.

Ejecutaremos el algoritmo para 5000 iteraciones y usaremos un tamaño de paso de 0.15 en el espacio de búsqueda. Usaremos un tamaño de población (lambda) de 100 padres seleccionados de 20 (mu). Estos hiperparámetros se eligieron después de un poco de prueba y error.

Al final de la búsqueda, informaremos la mejor solución candidata encontrada durante la búsqueda.

Al unir esto, el ejemplo completo de la aplicación de la versión en coma del algoritmo Evolution Strategies a la función objetivo de Ackley se enumera a continuación.

Running the example reports the candidate solution and scores each time a better solution is found, then reports the best solution found at the end of the search.

Nota: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see that about 22 improvements to performance were seen during the search and the best solution is close to the optima.

No doubt, this solution can be provided as a starting point to a local search algorithm to be further refined, a common practice when using a global optimization algorithm like ES.

Now that we are familiar with how to implement the comma version of evolution strategies, let’s look at how we might implement the plus version.

Develop a (mu + lambda)-ES

The plus version of the Evolution Strategies algorithm is very similar to the comma version.

The main difference is that children and the parents comprise the population at the end instead of just the children. This allows the parents to compete with the children for selection in the next iteration of the algorithm.

This can result in a more greedy behavior by the search algorithm and potentially premature convergence to local optima (suboptimal solutions). The benefit is that the algorithm is able to exploit good candidate solutions that were found and focus intently on candidate solutions in the region, potentially finding further improvements.

We can implement the plus version of the algorithm by modifying the function to add parents to the population when creating the children.

The updated version of the function with this addition, and with a new name es_plus() , is listed below.

We can apply this version of the algorithm to the Ackley objective function with the same hyperparameters used in the previous section.

The complete example is listed below.

Running the example reports the candidate solution and scores each time a better solution is found, then reports the best solution found at the end of the search.

Nota: Your results may vary given the stochastic nature of the algorithm or evaluation procedure, or differences in numerical precision. Consider running the example a few times and compare the average outcome.

In this case, we can see that about 24 improvements to performance were seen during the search. We can also see that a better final solution was found with an evaluation of 0.000532, compared to 0.001147 found with the comma version on this objective function.

Further Reading

This section provides more resources on the topic if you are looking to go deeper.

Papers

Books

Articles

Resumen

In this tutorial, you discovered how to implement the evolution strategies optimization algorithm.

Specifically, you learned:

  • Evolution Strategies is a stochastic global optimization algorithm inspired by the biological theory of evolution by natural selection.
  • There is a standard terminology for Evolution Strategies and two common versions of the algorithm referred to as (mu, lambda)-ES and (mu + lambda)-ES.
  • How to implement and apply the Evolution Strategies algorithm to continuous objective functions.

Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.