Saltar al contenido
Machine learning

Algoritmo genético simple desde cero en Python

3 de marzo de 2021

los algoritmo genético es un algoritmo de optimización global estocástico.

Puede ser uno de los algoritmos de inspiración biológica más populares y más conocidos, junto con las redes neuronales artificiales.

El algoritmo es un tipo de algoritmo evolutivo y realiza un procedimiento de optimización inspirado en la teoría biológica de la evolución mediante selección natural con representación binaria y operadores simples basados ​​en recombinación genética y mutaciones genéticas.

En este tutorial, descubrirá el algoritmo de optimización del algoritmo genético.

Después de completar este tutorial, sabrá:

  • El algoritmo genético es un algoritmo de optimización estocástico inspirado en la evolución.
  • Cómo implementar el algoritmo genético desde cero en Python.
  • Cómo aplicar el algoritmo genético a una función objetiva continua.

Empecemos.

Algoritmo genético simple desde cero en Python

Algoritmo genético simple desde cero en Python
Foto de Magharebia, algunos derechos reservados.

Descripción general del tutorial

Este tutorial se divide en cuatro partes; son:

  1. Algoritmo genético
  2. Algoritmo genético desde cero
  3. Algoritmo genético para OneMax
  4. Algoritmo genético para la optimización continua de funciones

Algoritmo genético

El algoritmo genético es un algoritmo estocástico de optimización de búsqueda global.

Está inspirado en la teoría biológica de la evolución por medio de la selección natural. Específicamente, la nueva síntesis que combina la comprensión de la genética con la teoría.

Los algoritmos genéticos (algoritmo 9.4) se inspiran en la evolución biológica, donde los individuos más aptos tienen más probabilidades de transmitir sus genes a la siguiente generación.

– Página 148, Algoritmos de optimización, 2019.

El algoritmo utiliza análogos de una representación genética (cadenas de bits), aptitud (evaluaciones de funciones), recombinación genética (cruce de cadenas de bits) y mutación (voltear bits).

El algoritmo funciona creando primero una población de un tamaño fijo de cadenas de bits aleatorias. El bucle principal del algoritmo se repite durante un número fijo de iteraciones o hasta que no se observe ninguna mejora adicional en la mejor solución en un número determinado de iteraciones.

Una iteración del algoritmo es como una generación evolutiva.

Primero, la población de cadenas de bits (soluciones candidatas) se evalúa utilizando la función objetivo. La evaluación de la función objetivo para cada solución candidata se toma como la adecuación de la solución, que puede minimizarse o maximizarse.

Luego, los padres se seleccionan en función de su estado físico. Una solución candidata dada se puede utilizar como padre cero o más veces. Un enfoque simple y efectivo para la selección implica dibujar k candidatos de la población de forma aleatoria y seleccionando al miembro del grupo con la mejor aptitud. A esto se le llama selección de torneo donde k es un hiperparámetro y se establece en un valor como 3. Este enfoque simple simula un esquema de selección proporcional a la aptitud más costoso.

En la selección del torneo, cada padre es el más apto de los k cromosomas elegidos al azar de la población.

– Página 151, Algoritmos de optimización, 2019.

Los padres se utilizan como base para generar la próxima generación de puntos candidatos y se requiere un padre para cada puesto en la población.

Luego, los padres se toman en parejas y se utilizan para crear dos hijos. La recombinación se realiza mediante un operador de cruce. Esto implica seleccionar un punto de división aleatorio en la cadena de bits, luego crear un hijo con los bits hasta el punto de división del primer padre y desde el punto de división hasta el final de la cadena del segundo padre. Este proceso luego se invierte para el segundo hijo.

Por ejemplo los dos padres:

  • padre1 = 00000
  • parent2 = 11111

Puede resultar en dos hijos cruzados:

  • niño1 = 00011
  • niño2 = 11100

Esto se llama cruce de un punto y hay muchas otras variaciones del operador.

El cruce se aplica de manera probabilística para cada par de padres, lo que significa que, en algunos casos, las copias de los padres se toman como hijos en lugar del operador de recombinación. El cruce se controla mediante un hiperparámetro establecido en un valor grande, como 80 por ciento o 90 por ciento.

Crossover es la característica distintiva del algoritmo genético. Implica mezclar y combinar partes de dos padres para formar hijos. Cómo se hace esa mezcla y combinación depende de la representación de los individuos.

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

La mutación implica invertir bits en soluciones candidatas para niños creados. Normalmente, la tasa de mutación se establece en 1 / L, dónde L es la longitud de la cadena de bits.

Cada bit de un cromosoma con valor binario normalmente tiene una pequeña probabilidad de ser invertido. Para un cromosoma con m bits, esta tasa de mutación generalmente se establece en 1 / m, lo que produce un promedio de una mutación por cromosoma infantil.

– Página 155, Algoritmos de optimización, 2019.

Por ejemplo, si un problema utiliza una cadena de bits con 20 bits, entonces una buena tasa de mutación predeterminada sería (1/20) = 0.05 o una probabilidad del 5 por ciento.

Esto define el procedimiento de algoritmo genético simple. Es un campo de estudio extenso y existen muchas extensiones para el algoritmo.

Ahora que estamos familiarizados con el procedimiento de algoritmo genético simple, veamos cómo podríamos implementarlo desde cero.

Algoritmo genético desde cero

En esta sección, desarrollaremos una implementación del algoritmo genético.

El primer paso es crear una población de cadenas de bits aleatorias. Podríamos usar valores booleanos Cierto y Falso, valores de cadena «0» y «1», o valores enteros 0 y 1. En este caso, usaremos valores enteros.

Podemos generar una matriz de valores enteros en un rango usando la función randint (), y podemos especificar el rango como valores que comienzan en 0 y menos de 2, p. Ej. 0 o 1. También representaremos una solución candidata como una lista en lugar de una matriz NumPy para simplificar las cosas.

Se puede crear una población inicial de cadena de bits aleatoria de la siguiente manera, donde «n_pop«Es un hiperparámetro que controla el tamaño de la población y»n_bits”Es un hiperparámetro que define la cantidad de bits en una única solución candidata:

A continuación, podemos enumerar un número fijo de iteraciones del algoritmo, en este caso, controladas por un hiperparámetro llamado «nitro“.

El primer paso en la iteración del algoritmo es evaluar todas las soluciones candidatas.

Usaremos una función llamada objetivo() como función objetivo genérica y la llamaremos para obtener una puntuación de aptitud, que minimizaremos.

A continuación, podemos seleccionar los padres que se utilizarán para crear hijos.

El procedimiento de selección del torneo se puede implementar como una función que toma la población y devuelve un padre seleccionado. los k El valor se fija en 3 con un argumento predeterminado, pero puede experimentar con diferentes valores si lo desea.

Entonces podemos llamar a esta función una vez para cada posición en la población para crear una lista de padres.

Entonces podemos crear la próxima generación.

Esto primero requiere una función para realizar el cruce. Esta función tomará dos padres y la tasa de cruce. La tasa de cruce es un hiperparámetro que determina si el cruce se realiza o no, y si no, los padres se copian en la siguiente generación. Es una probabilidad y normalmente tiene un valor grande cercano a 1.0.

los Transversal() la función a continuación implementa el cruce usando un sorteo de un número aleatorio en el rango [0,1] para determinar si se realiza el cruce, luego seleccione un punto de división válido si se va a realizar el cruce.

También necesitamos una función para realizar la mutación.

Este procedimiento simplemente invierte bits con una probabilidad baja controlada por el «r_mut”Hiperparámetro.

A continuación, podemos recorrer la lista de padres y crear una lista de hijos que se utilizarán como la próxima generación, llamando a las funciones de cruce y mutación según sea necesario.

Podemos unir todo esto en una función llamada algoritmo genético() que toma el nombre de la función objetivo y los hiperparámetros de la búsqueda, y devuelve la mejor solución encontrada durante la búsqueda.

Ahora que hemos desarrollado una implementación del algoritmo genético, exploremos cómo podríamos aplicarlo a una función objetivo.

Algoritmo genético para OneMax

En esta sección, aplicaremos el algoritmo genético a un problema de optimización basado en cadenas binarias.

El problema se llama OneMax y evalúa una cadena binaria en función del número de unos en la cadena. Por ejemplo, una cadena de bits con una longitud de 20 bits tendrá una puntuación de 20 para una cadena de todos unos.

Dado que hemos implementado el algoritmo genético para minimizar la función objetivo, podemos agregar un signo negativo a esta evaluación para que los valores positivos grandes se conviertan en valores negativos grandes.

los onemax () La función siguiente implementa esto y toma una cadena de bits de valores enteros como entrada y devuelve la suma negativa de los valores.

A continuación, podemos configurar la búsqueda.

La búsqueda se ejecutará durante 100 iteraciones y usaremos 20 bits en nuestras soluciones candidatas, lo que significa que la aptitud óptima será -20.0.

El tamaño de la población será 100 y usaremos una tasa de cruce del 90 por ciento y una tasa de mutación del 5 por ciento. Esta configuración se eligió después de un poco de prueba y error.

A continuación, se puede llamar a la búsqueda y notificar el mejor resultado.

Al unir esto, el ejemplo completo de la aplicación del algoritmo genético a la función objetivo de OneMax se enumera a continuación.

Recomendado:  Hopper, barrido de amperios Pruebas de entrenamiento MLPerf

Ejecutar el ejemplo informará el mejor resultado a medida que se encuentre en el camino, luego la mejor solución final al final de la búsqueda, que esperaríamos que sea la solución óptima.

Nota: Sus resultados pueden variar dada la naturaleza estocástica del algoritmo o procedimiento de evaluación, o las diferencias en la precisión numérica. Considere ejecutar el ejemplo varias veces y compare el resultado promedio.

En este caso, podemos ver que la búsqueda encontró la solución óptima después de aproximadamente ocho generaciones.

Algoritmo genético para la optimización continua de funciones

Optimizar la función OneMax no es muy interesante; es más probable que deseemos optimizar una función continua.

Por ejemplo, podemos definir la función de minimización x ^ 2 que toma variables de entrada y tiene un óptimo en f (0, 0) = 0.0.

Podemos minimizar esta función con un algoritmo genético.

Primero, debemos definir los límites de cada variable de entrada.

Tomaremos el «n_bits” hyperparameter as a number of bits per input variable to the objective function and set it to 16 bits.

This means our actual bit string will have (16 * 2) = 32 bits, given the two input variables.

We must update our mutation rate accordingly.

Next, we need to ensure that the initial population creates random bitstrings that are large enough.

Finally, we need to decode the bitstrings to numbers prior to evaluating each with the objective function.

We can achieve this by first decoding each substring to an integer, then scaling the integer to the desired range. This will give a vector of values in the range that can then be provided to the objective function for evaluation.

los decode() function below implements this, taking the bounds of the function, the number of bits per variable, and a bitstring as input and returns a list of decoded real values.

We can then call this at the beginning of the algorithm loop to decode the population, then evaluate the decoded version of the population.

Tying this together, the complete example of the genetic algorithm for continuous function optimization is listed below.

Running the example reports the best decoded results along the way and the best decoded solution at the end of the run.

Note: 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 the algorithm discovers an input very close to f(0.0, 0.0) = 0.0.

Further Reading

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

Books

API

Artículos

Resumen

In this tutorial, you discovered the genetic algorithm optimization.

Specifically, you learned:

  • Genetic algorithm is a stochastic optimization algorithm inspired by evolution.
  • How to implement the genetic algorithm from scratch in Python.
  • How to apply the genetic algorithm to a continuous objective function.

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

Recomendado: Una supercomputadora de dominio específico para el entrenamiento de redes neuronales profundas