Algoritmo Genético en Python desde 0

Los modelos de optimización es una de las grandes herramientas que usamos los científicos de datos para solucionar problemas: desde la solución de problemas de optimización a encontrar los hiperparámetros óptimos de un modelo.

En este post, vamos a aprender cómo funciona uno de los modelos de optimización más conocido y usado: los algoritmos genéticos. Más concretamente, vamos a ver cómo funciona un algoritmo genético, vamos a aprender a usarlo en Python y además, vamos a programar un algoritmo genético desde 0 en Python.

¿Te suena interesante? ¡Vamos con ello!

Introducción a los algoritmos genéticos y modelos de optimización

Un algoritmo genético es un tipo de algoritmo de optimización estocástico basado en población. ¿Esto qué significa? Básicamente cuando hablamos de modelos de optimización, estos se pueden clasificar en base a:

  1. Cómo se realiza la búsqueda:
    1.  Blind Search: consiste en realizar una búsqueda exhaustiva de todas las opciones posibles, sin tener en cuenta qué resultado hemos tenido previamente.
    2. Guided Search: consiste en utilizar los resultados pasados para guiar al modelo en la búsqueda del óptimo. Asimismo, existen dos tipos de modelos de búsqueda guiada:
      • Single State Search: utiliza valores similares a la primera solución para encontrar el resultado. En casos de poca complejidad (pocos mínimos locales) esta función converge (encuentra el resultado) bastante rápido.
      • Population Based Search: se usa una población de soluciones sobre las que ir mejorando. De esta forma, aunque se tarde más en converger, funciona mejor que los modelos de búsqueda guiada local en los problemas de alta complejidad. 
  2. Si la búsqueda es estocástica o determinista. Las búsquedas estocásticas se realizan de forma estocástica (aleatoria), por lo que al ejecutar el proceso dos veces sobre los mismos datos puede devolver resultados diferentes. Sin embargo, los modelos deterministas siempre devolverán el mismo resultado.

En la siguiente tabla te indico los distitnos tipos de algoritmos de optimización que existen en base a las dos variables previamente mencionadas:

DeterministicStocastic
Blind SearchBlind Search Grid SearchMonte Carlo
Single-State SearchTabu Search Hill ClimbingSimulated Annealing
Population Based SearchGenetic Algorithm Genetic Programming Differential Evolution Particle Swarm Estimation of Distribution

Como puedes ver, el algoritmo genético es un algoritmo que usa una búsqueda basada en una población y que además dicha búsqueda es estocástica. Pero , ¿por qué ocurre esto? ¿Cómo funciona en realidad un algoritmo genético? ¡Veámoslo!

Cómo funciona un algoritmo genético

Como su propio nombre indica, los algoritmos genéticos se llaman así porque simulan el comportamiento que se da en la naturaleza, al igua que a las redes neuronales se les llama así por su similitud con las neuronas.

Si quieres aprender cómo funciona una red neuronal, te recomiendo este post donde programo una red neuronal paso a paso.

Más concretamente, cada candidato a solución, en los algoritmos genéticos recibe el nombre de individuo. Por su parte, el genotipo,genoma o cromosoma denota la estructura de datos presente en un individuo. Un gen es una posición dentro de dicha estructura de datos y, el dato concreto, recibe el nombre de alelo.

Así pues, partimos de una serie de individuos, cada uno con unos alelos (dat0s) diferentes. Como es lógico, no todos los individuos serán igual de buenos a la hora de optimizar nuestro objetivo (al igual que no todos los primeros humanos estaban igual de bien adaptados a su entorno). Por tanto, cada individuo se evalua con una función, llamada fenotipo o fitness.

Una vez calculado el fitness de cada individuo, se realizará un proceso de selección de individuo (más adelante entramos más en detalle en este apartado). La idea es sencilla, nos quedaremos con aquellos individuos que mejor fitness tengan.

Una vez se haya hecho la selección de individuos, los individuos se juntarán entre ellos para obtener desdendencia, es decir, generar nuevos individuos. Este proceso se conoce como breeding (crianza) y la generación de nuevos individuos surge mediante los operadores genéticos, como son el crossover y la mutation.

Por su parte, crossover involucra la combinación de dos individuos, mientras que la mutation implica realizar un cambio sobre un individuo actual.

Teniendo esto en cuenta, los algoritmos genéticos se basan en:

  1. Iniciar un montón de individuos diferentes, cada uno con alelos (valores) diferentes. Este conjunto de individuos es la población de la que partimos.
  2. Cada uno de estos individuos, se evaluará calculando su fitness.
  3. Se hará una selección de individuos que «sobreviven», es decir, que llegarán a tener descendencia.
  4. Los individuos supervivientes tendrán descendencia y se volverá al paso 2, de forma iterativa.

Así pues, ahora que entiendes a rasgos generales cómo funciona un algoritmo genético, entraremos más en detalle para ver dos cuestiones importantes: cómo se realiza la selección de los individuos y cómo se realiza la generación de nuevos individuos.

Cómo realizar la selección de individuos

Existen diferentes maneras de realizar la selección de individuos:

  1. Método de la ruleta: consiste en que la probabilizad de breeding sea proporcional al fitness, es decir, que cuanto mejor sea tu fitness, más probable es que seas elegido. La forma de calcular la probabilidad del individuo se da dividiendo su fitness entre la suma total de fitness lograda.
  2. Ranking: aunque el método de la ruleta parezca sólido, el problema se da cuando muchos individuos tienen probabilidades parecidas. En estos casos, es posible que no se coja al mejor individuo. Así pues, el método de ranking consiste en ordenar a los individuos en base al fitness, de tal forma que se elijan los N indivudios que mejor fitness hayan tenido.
  3. Selección de estado estacionario: consiste en eliminar una serie de individuos con mal fitness y que estos sean reemplazados por la crianza a partir de los individuos con mejores fitness.
  4. Selección basada en torneo: se crean parejas de forma aleatoria y de cada pareja se seleccionará aquel que tenga mejor fitness.
  5. Elitismo: se basa en realizar reproducciones parciales, es decir, que los individuos con mejor fitness tengan una descendencia que sea exactamente igual que ellos.

Cómo obtener nuevos individuos mediante crossover

Existen tres formas principales de criar nuevos individuos mediante crossover:

  1. Cruce de un punto: consiste en partir en dos los alelos de los padres. El hijo se llevará la un trozo de los alelos de un padre y el otro trozo del otro padre.
  1. Cruce de varios puntos: sigue la misma idea del punto anterior, solo que ahora los alelos se parten en 3 o más grupos y el hijo se compondrá de combinaciones de dichas partes. 
  2. Cruce uniforme: cada alelo se elegirá de uno de los padres de forma aleatoria, creando al hijo como una selección aleatorio de los valores de los padres.
  3. Crossover the listas ordenadas: este sistema de crossover se utiliza cuando no todos los chromosomas son soluciones válidas y básicamente permite añadir una serie de condiciones al crossover.

Ahora que ya sabemos cómo se generan nuevos individuos en los algoritmos genéticos gracias al crossover, veamos cómo se crean nuevos individuos mediante mutación:

Cómo obtener nuevos individuos mediante mutación

Cuando hablamos de mutación, existen dos grandes formas de realizar una mutación en un gen:

  1. Mutacion aleatoria: consiste en mutar, de forma aleatoria, un alelo (un valor).
  2. Shrink: consiste en sumar un valor aleatorio de una distribución normal (u otro tipo de distribución, como una distribución uniforme), a uno de los valores del individuo.

Perfecto, con esto ya sabes cómo funciona un algoritmo genético. Ahora, veamos cómo usar un algoritmo genético en Python.

Cómo usar un algoritmo genético en Python con PyGAD

Para usar un algoritmo genético en Python contamos con la librería PyGAD, la cual permite crear algoritmos genéticos de una forma sencilla. Se trata de una librería muy utilizada, porque se puede usar con Keras y Pytorch, los dos principales frameworks de Deep Learning y, además, soporta el uso de diferentes tipos de crossovers, mutaciones y selección.

Si PyGAD te resulta util y de interés, puedes realizar donaciones para apoyar y ayudar a mantener el proyecto. En este enlace te explican cómo puedes hacerlo.

Así pues, lo primero de todo es instalar PyGAD, lo cual puedes hacer con el siguiente comando:

pip install pygad

Teniendo esto, vamos a solucionar un problema relativamente sencillo: encontrar los pesos que deben recibir distintos valores para que la suma de la multiplicación de dichos pesos por los valores devuelva un número concreto.

Para ello, usaremos la función GA de la librería PyGAD. A esta función deberemos indicarle una serie de parámetros, como el número de iteraciones que tiene que hacer, cuántos individuos forman la población o el tipo de mutación o crossover a aplicar.

Además, debemos indicarle también la función para medir el fitness. Dicha función deberá recibir como input una solución y un índice de solución (este segundo no se suele usar) y devolver un valor de fitness.

Dicho esto, veamos, ahora sí, cómo solucionar un problema de optimización sencillo con PyGAD:

import pygad
import numpy

inputs = [0.4,1,0,7,8]
desired_output = 32

def fitness_func(solution, solution_idx):
    output = numpy.sum(solution*inputs)
    fitness = 1.0 / (numpy.abs(output - desired_output) + 0.000001)
    
    return fitness

ga_instance = pygad.GA(num_generations=100,
                       sol_per_pop=10,
                       num_genes=len(inputs),
                       num_parents_mating=2,
                       fitness_func=fitness_func,
                       mutation_type="random",
                       mutation_probability=0.6)

ga_instance.run()

ga_instance.plot_fitness()

Como podemos ver, el fitness obtenido por nuestro modelo, al principio, era muy bajo. Sin embargo, a medida que pasan las generaciones, el fitness ha ido mejorando, hasta llegar a una solución óptima en la generación 90.

Llegar a la solución óptima, implica que no hay solución mejor posible, y es por ello por lo que el fitness no ha variado.

Ahora, veamos usos más complejos del algoritmo genético en Python, tales como problemas de optimización más complicados o el entrenamiento de redes neuronales en Keras. ¡Vamos con ello!

Cómo solucionar problemas de optimización complejos con algoritmos genéticos en Python

Cómo entrenar redes neuronales con algoritmos genético en Pyhon

A partir de la versión 2.8.0 de PyGAD, se introdujo el módulo kerasga (Keras Genetic Algorithms), el cual incluye diversas funciones adaptadas a Keras para entrenar redes neuronales usando Algoritmos Genéticos.

Carga de Datos

Lo primero de todo que tenemos que hacer es obtener unos datos. Para ello, usaremos el dataset load_breast_cancer ofrecido por sklearn. Además, vamos a visualizar las primeras observaciones, por si no estás familiarizado con el dataset:

from sklearn.datasets import load_breast_cancer

diabetes = load_breast_cancer(as_frame = True)
data = diabetes['data']
target = diabetes['target']

data.head()

Ahora que tenemos los datos cargados, vamos a separarlos entre train y test, usando la función train_test_split ofrecida por sklearn.

Si no conoces la librería Sklearn en profundidad, te recomiendo que leas este post donde te explico la librería en detalle.

from sklearn.model_selection import train_test_split

seed = 1234
x_train, x_test, y_train, y_test = train_test_split(data, target, random_state=seed)

Creación de la red neuronal

Con estos datos, vamos a crear una red neuronal sencilla usando Keras.

En este sentido, creo importante remarcar que el objetivo de este ejemplo no es encontrar la mejor predicción posible, sino enseñar a optimizar redes neuronales en base a algoritmos genéticos.

Asi pues, he escodigo una estructura bastante sencilla compuesta por dos capas intermedias con 12 y 8 neuronas cada una.

from keras.models import Sequential
from keras.layers import Dense, Input

model = Sequential()
model.add(Input(x_train.shape[1]))
model.add(Dense(8, activation = 'relu'))
model.add(Dense(1, activation = 'sigmoid'))

Optimización de red neuronal con algoritmo genético

Ahora que tenemos el modelo creado, es cuando entra en acción la ejecución del modelo usando el algoritmo genético como optimizador del modelo.

Para ello, los pasos son los siguientes:

  1. Crear un modelo optimizador en base a nuestro modelo optimizador.
  2. Dada la solución propuesta por el algoritmo genético, implementarla en nuestra red neuronal
  3. Hacer la predicción con el modelo y calcular el fitness de la predicción.

Así pues, lo primero de todo es crear un algoritmo genético compatible con Keras. Para ello, la librería pygad cuenta con la función KerasGA.

Esta función únicamente cuenta con dos parámetros:

  • model: modelo de Keras que queremos que optimice.
  • num_solutions: indica el número de soluciones a usar en la población. Cada una de estas soluciones contará con unos parámetros del modelo diferentes.

Así pues, creamos el modelo optimizador.

from pygad import kerasga

keras_ga = kerasga.KerasGA(
    model = model,
    num_solutions = 15
)

Hecho esto, podemos obtener los pesos propuestos por nuestro algoritmo genético mediante la función model_weights_as_matrix del módulo kerasga. Una vez tengamos los pesos, podremos aplicárselo a nuestro modelo mediante el método set_weights.

Asimismo, aprovecharemos esta misma función para realizar las predicciones.

Por último, vamos a calcular el fitness de las predicciones. En este sentido, es importante tener en cuenta una cosa, y es que la capacidad predictica de un modelo de clasificación se mide mediante la entropía.

La entropía mide el «desorden» de nuestras predicciones, por lo que cuanto menor sea la entropía, mejor funciona el modelo.

Sin embargo, nuestro algoritmo genético se basa en calcular el fitness del modelo. En este caso, cuanto mayor sea el fitness, mejor es el modelo.

Así pues, vamos a invertir la entropía, de tal forma que maximizar el fitness implique reducir la entropía:

from keras.losses import BinaryCrossentropy

def fitness_func(solution, solution_idx ):
  global model

  # Get the weights from the model
  weights = kerasga.model_weights_as_matrix(
      model= model,
      weights_vector= solution
      )
  
  # Set the weights
  model.set_weights(weights = weights)

  # Make the prediction
  prediction = model.predict(x_train)

  # Calculate fitness
  entropy = BinaryCrossentropy()(y_train, prediction)
  fitness = 1/(entropy.numpy() + 0.0001)

  return fitness

Con esto ya podríamos entrenar nuestra red neuronal con un algoritmo genético. Sin embargo, suele ser recomendable añadir un callback al proceso de aprendizaje, de tal forma que vayamos sabiendo qué tal va aprendiento nuestra red neuronal.

La siguiente función es un ejemplo de un callback típico:

fitness_evol = []

def callback_generation(ga_instance):
  global fitness_evol
  fitness_evol.append(ga_instance.best_solution()[1])
  generation = ga_instance.generations_completed
  
  if generation % 1 == 0:
    print(f"Generation {generation}. Fitness: {ga_instance.best_solution()[1]}")

Con todo lo anterior, ya podemos entrenar nuestra red neuronal usando algoritmos genéticos:

from pygad import GA

num_generations = 5
num_parents_mating = 5
initial_population = keras_ga.population_weights

ga_optimizer = GA(
    num_generations=num_generations, 
    num_parents_mating=num_parents_mating, 
    initial_population=initial_population,
    fitness_func=fitness_func,
    on_generation=callback_generation
    )

ga_optimizer.run()
Generation 1. Fitness: 0.17774870093706102
Generation 2. Fitness: 0.17774870093706102
Generation 3. Fitness: 0.17779069834927677
Generation 4. Fitness: 0.18384278893734354
Generation 5. Fitness: 0.3925076183040464

Con esto ya tendríamos nuestro modelo entrenado. Así pues, vamos a ver qué tal se ha ido comportando:

import seaborn as sns

sns.lineplot(
    x = range(len(fitness_evol)),
    y = fitness_evol
)

Por último, vamos a ver qué tal se comporta el nuestra red neuronal sobre datos nuevos:

from sklearn.metrics import confusion_matrix, auc
import numpy as np

pred = model.predict(x_test)
classes=np.argmax(pred,axis=1)
confusion_matrix(y_test, classes)

array([[50,  5],
       [8,  80]])

Como ves, hemos entrenado nuestra red neuronal, de una forma sencilla, usando algoritmos genéticos. Sin embargo, los algoritmos genéticos se pueden usar para mucho más. Veamos ahora cómo solucionar problemas de optimiazción complejos con algoritmos genéticos en Python.

Problemas de optimización con algoritmos genéticos en Python

Para ver el potencial de los algoritmos genéticos, vamos a resolver un problema clásico de optimización: encontrar el valor óptimo de producción de unos productos para maximizar el beneficio de la empresa, dadas una serie de constraints.

En este sentido, los contrainst aplicados por la empresa son los siguientes:

  • Se deben producir al menos 10 unidades de cada producto.
  • Existe un número máximo de materiales a utilizar. No se podrá consumir más cantidad que dicho límite.
  • Cada producto genera un beneficio diferente.

Para poder solucionar problemas de optimización con algoritmos genéticos en Python lo primero de todo es codificar nuestra función que nos calcule el fitness.

Será en la función del cálculo del fitness donde deberemos codificar todos esos constraints. Así pues, lo primero de todo, creamos dicha función:

margin = np.array([2, 2.5])
material_consumption = np.array([2,3]) 
material_max = 500

def fitness_func(solution, solution_idx):

  solution_added = solution + 50
  calculated_margin = np.sum(solution_added*margin)
  material_consumed = np.sum(solution_added*material_consumption)
  
  if material_consumed> material_max:
    return 0
  
  else:
    return calculated_margin

# Comprobamos con una posible solucion
print(f"Fitness for correct scenario: {fitness_func(np.array([0, 0]), '')}") 
print(f"Fitness for incorrect scenario: {fitness_func(np.array([0, 1]), '')}") 
Fitness for correct scenario: 225.0
Fitness for incorrect scenario: 227.5

Ahora que tenemos nuestra función de fitness codificada, vamos a ejecutar nuestro algoritmo genético:

ga_instance = pygad.GA(num_generations=1000,
                       sol_per_pop=10,
                       num_genes=2,
                       num_parents_mating=2,
                       fitness_func=fitness_func,
                       mutation_type="random",
                       mutation_probability=0.6
                       )

ga_instance.run()

ga_instance.plot_fitness()

Por último, podemos comprobar cuál es la solución propuesta por nuestro algoritmo genético:

ga_instance.best_solution()[0] + 50
array([136.82320846,  75.43757807])

Genial, en este tutorial ya hemos visto qué es un algoritmo genético y cómo poder usarlo en Python. Sin embargo, en este último apartado vamos a entrenar más en profundidad. Para ello, vamos a programar un algoritmo genético desde cero. ¿Te suena interesante? ¡Vamos con ello!

Cómo programar un algoritmo genético desde cero en Python

Si queremos programar un algoritmo genético desde cero, tendremos que:

  1. Crear una población de n individuos.
  2. Codificar las diferentes maneras en las que se genera descendencia.

Así pues, empezamos por lo primero: definir una población. Para ello, vamos a incluir una cuestión que considero ayuda bastante a la hora de converger, que consiste en definir una serie de límites que pueden recibir cada uno de los valores clave.

Así pues, lo primero de todo creamos dicha población.

Programar la creación de una población de un algoritmo genético

Para programar nuestro algoritmo genético en Python, usaremos una clase. Así pues, la creación de la población se hará en la inicialización de dicha clase.

Dicho esto, para facilitar que el algoritmo converga de una forma más rápida, voy a crear dos tipos de inicialización de la población:

  1. Inicialización aleatoria de los alelos. Simplemente se crearán valores aleatorios que se deberán ir optimizando. Este tipo de inicialización se hará si el parámetro gene_limits es nulo.
  2. Inicialización limitada ed los alelos. Consiste en incluir unos límites para cada uno de nuestros alelos, de tal forma que lo valores se incialicen de forma aleatoria dentro de dichos límites. Este tipo de inicialización se hará si el parámetro gene_limits no es nulo.

Dicho esto, programo la inicialización aleatoria de la población:

import numpy as np


class GeneticAlgorithm:
  def __init__(self, n_variables, n_genes, random_state = None, gene_limits = None):

    self.n_variables = n_variables
    self.n_genes = n_genes
    self.gene_limits = gene_limits 
    self.random_state = random_state
    
    # Create the population
    if self.gene_limits is not None:
      
      # Check that both vectors have the same length
      assert len(self.gene_limits) == self.n_variables

      limits = [np.random.uniform(limit[0], limit[1], self.n_genes)
        for limit in self.gene_limits] 

    else:
      limits = [np.random.random(self.n_genes)
        for limit in range(self.n_variables)]
      
    # Convert list of limits to list of solutions
    self.population = list(zip(*limits))
        
ga = GeneticAlgorithm(
    n_variables = 2,
    n_genes = 10
)

ga.population
[(0.3248594341550495, 0.7747988337644331),
 (0.9641753689879542, 0.2728028066671938),
 (0.7745274418319132, 0.2833543446404905),
 (0.8258487102100652, 0.9961554551162345),
 (0.034136970844815595, 0.7000431609346188),
 (0.9956365394402079, 0.6007170537947054),
 (0.5622396252894827, 0.6793736336026693),
 (0.16433824493155325, 0.579682515374066),
 (0.15570018999931567, 0.46125127275801037),
 (0.5544543502640932, 0.8094380724657084)]

Genial, ahora que tenemos una población, pasamos al siguiente paso: calcular el fitness.

Calcular el fitness del algoritmo genético

Partiendo de una población, tenemos que permitir a nuestro algoritmo genético recibir una función de fitness. Además, internamente usaremos dicha función de fitness para calcular el fitness de cada una de las soluciones.

Así pues, ampliaremos el código anterior, incluyendo un nuevo parámetro fitness_func el cual recibe como input una solución y devuelve un valor de fitness.

Asimismo, crearé un método llamado get_fitness_scores, que devuelva el fitness score de la solución actual. Esto facilitará el uso del fitness score a lo largo del algoritmo.

Dicho esto, extendamos el código anterior incluyendo el fitness:

import numpy as np
import inspect

class GeneticAlgorithm:
  def __init__(
      self, n_variables, n_genes, mutation_type = 'random', random_state = None, 
      gene_limits = None, fitness_func = None):

    assert mutation_type in ['random']

    self.n_variables = n_variables
    self.n_genes = n_genes
    self.gene_limits = gene_limits 
    self.mutation_type = mutation_type
    self.random_state = random_state
    self.fitness_func = fitness_func
 
    # Create the population
    if self.gene_limits is not None:
      
      # Check that both vectors have the same length
      assert len(self.gene_limits) == self.n_variables

      limits = [np.random.uniform(limit[0], limit[1], self.n_genes)
        for limit in self.gene_limits] 

    else:
      limits = [np.random.random(self.n_genes)
        for limit in range(self.n_variables)]
      
    # Convert list of limits to list of solutions
    self.population = list(zip(*limits))
  
  def get_fitness_scores(self):
    scores = [self.fitness_func(ind) for ind in self.population]
    return np.array(scores)

def fitness_func(solution):
  solution = np.array(solution)
  solution_added = solution + 50
  calculated_margin = np.sum(solution_added*margin)
  material_consumed = np.sum(solution_added*material_consumption)
  
  if material_consumed> material_max:
    return 0
  
  else:
    return calculated_margin

ga = GeneticAlgorithm(
    n_variables = 2,
    n_genes = 10,
    fitness_func= fitness_func
)

fitness_scores = ga.get_fitness_scores()
fitness_scores
array([228.53122328, 227.3974419 , 226.11156266, 227.45136065,
       225.92371642, 226.86141269, 228.93654237, 228.35770696,
       226.48405291, 227.82272666])

Ahora que podemos evaluar cada individuo de la población, pasamos a la siguiente fase: hacer la selección de individuos.

Cómo programar la selección de individuos de un algoritmo genético

Una vez podemos evaluar la función, vamos a crear el sistema de selección de nuestros mejores candidatos.

En este sentido, vamos a crear un sistema que permita realizar diferentes dos tipos de procesos de selección: el método de ranking y el método de torneo.

Para el método del ranking simplemente tenemos que devolver los índices de aquella población con los k mejores resultados en términos de fitness. Como podemos ver, se añade a nuestro algoritmo un nuevo parámetro, que se refiere al número de individuios elegidos para obtener descendencia.

Respecto al torneo, crearemos tantas parejas aleatorias como número de genes de población queremos y de cada pareja elegiremos al valor más alto.

Veamos nuestros sistemas de selección en acción:

def ranking_selection(scores, k):
    if k is None:
      raise ValueError('K must not be none if type ranking is selected.')
    
    ind = np.argpartition(scores, k)[-k:]

    return ind

def tournament_selection(scores, k, n_candidates):
  candidates = [np.random.randint(0, len(scores), 3) for i in range(3)]
  tournament_winner = [np.argmax(scores[tournament]) for i, tournament in enumerate(candidates)]
  ind = [tournament[tournament_winner[i]] for i, tournament in enumerate(candidates)]

  return np.array(ind)

def gene_selection(scores, type, k, n_candidates = None):

  if type not in ['ranking','tournament']:
    raise ValueError('Type should be ranking or tournament')
  
  if type == 'ranking':
    ind = ranking_selection(scores, k)
  elif type == 'tournament':
    ind = tournament_selection(scores, k, n_candidates)
  else:
    pass

  return ind


ranking_selection = gene_selection(scores= fitness_scores,
               type = 'ranking',
               k = 3
               )

tournament_selection = gene_selection(scores= fitness_scores,
               type = 'tournament',
               k = 3,
               n_candidates = 11
               )

print(f"""
Ranking selection results: {ranking_selection}
Tournament selection results: {tournament_selection}
""")
Ranking selection results: [7 6 0]
Tournament selection results: [7 0 6]

Ahora que tenemos creada la selección, vamos a crear el sistema de generación de nuevas generaciones.

Cómo programar la generación de descendencia

De cara a generar nuevas generaciones, vamos a permitir que nuestro modelo permita usar tanto el crossover como la mutación. Así pues, contaremos con otro parámetro (transformation_type) que nos indique el tipo de transformación a aplicar.

Respecto al crossover, vamos a permitir dos tipos de crossovers: el crossover uniforme y el crossover en un punto.

En cualquiera de los dos casos, es importante tener en cuenta que a partir de los dos padres se generarán dos nuevos hijos. Así pues, el número de parejas a generar deberá ser la mitad del total de individuos en la población.

def crossover(parent1, parent2, crossover_type):

  # Check crossover type
  if crossover_type not in ['uniform', 'one_point']:
    raise ValueError('crossover_type should be one of uniform, one_point or multi_point')
  
  if crossover_type == 'one_point':
    index = np.random.choice(range(len(parent1)))
    children = [parent2[:index] + parent1[index:], parent1[:index] + parent2[index:]]

  elif crossover_type == 'uniform':
    parents = list(zip(*[parent1,parent2]))
    children1 = tuple([np.random.choice(element) for element in parents])
    children2 = tuple([np.random.choice(element) for element in parents])
    children = [children1, children2]
  else:
    pass

  return children

children_uniform = crossover(
    ga.population[0],
    ga.population[1],
    crossover_type = 'uniform'
    )

children_onepoint = crossover(
    ga.population[0],
    ga.population[1],
    crossover_type = 'one_point'
    )

print(f"""
Children Uniform: {children_uniform}
Children One Point: {children_onepoint}
""")
Children Uniform: [(0.8750958900239486, 0.6664701872724336), (0.8750958900239486, 0.7124125982046803)]
Children One Point: [(0.8750958900239486, 0.7124125982046803), (0.36563321798453374, 0.6664701872724336)]

Ahora que tenemos programado el crossover, vamos a pasar a programar la mutación. Tal como hemos visto anteriormente, existen dos tipos de mutaciones:

  1. Bit string: consiste en la modificación de uno de los alelos de forma aleatoria.
  2. Shrink: consiste en la adicion de un valor de una distribución normal a uno de los alelos.

En este caso, los resultados obtenidos son diferentes al crossover, y es que, si bien en el crossover generamos dos descendientes, en la mutación únicamente generaremos un descendiente.

Nota: en ocasiones se permite que la mutación shrink reciba una media y desviación típica para añadir datos aleatorios de una distribución normal con dicha media y desviación típica. Aunque no lo implemente, es una extensión que se podría llegar a hacer.

def mutation(individual, mutation_type):

  if mutation_type not in ['bitstring', 'shrink']:
    raise ValueError('mutation_type should be one of bitstring or shrinkg')
  
  # Get index of individual to modify
  index = np.random.choice(len(individual))

  # Convert individual to list so that can be modified
  individual_mod = list(individual)

  if mutation_type == 'bitstring':      
    individual_mod[index] = 1 - individual_mod[index]
  
  else:
    individual_mod[index] = individual_mod[index] + np.random.rand()
  
  # Convert indivudal to tuple
  individual = tuple(individual_mod)

  return individual

mutation_bitstring = mutation(ga.population[0], mutation_type = 'bitstring')
mutation_shrink = mutation(ga.population[0], mutation_type = 'shrink')


print(f"""
Mutation bitstring: {mutation_bitstring}
Mutation shrink: {mutation_shrink}
""")
Mutation bitstring: (0.12490410997605139, 0.7124125982046803)
Mutation shrink: (0.9867255774541429, 0.7124125982046803)

Con esto ya tendríamos todos los ingredientes de nuestro algoritmo genético. Por último, queda juntar todos los ingredientes para crear nuestro algoritmo genético.

Programar la evolución en los algoritmos genéticos

De cara a crear la evolución de nuestro algoritmo genético, simplemente debemos poner en conjunto todos los puntos anteriores, lo cual lo haré con el método optimize.

En este sentido, he incluido ciertas cuestiones, relevantes, como el valor best_fitness_evolution el cual va guardando el mejor resultado de fitness de cada generación.

Asimismo, también he creado un método, llamado view_fitness_evolution, el cual permite visualizar la evolución del mejor fitness obtenido, tal como hemos visto previamente con PyGAD.

Así pues, el código final para generar un algoritmo genético en Python es el siguiente:

import numpy as np
import inspect
from tqdm import tqdm
import matplotlib.pyplot as plt

class GeneticAlgorithm:
  def __init__(
      self,
      n_variables,
      n_genes,
      n_iterations,
      transformation_type = None,
      mutation_type = None,
      crossover_type = None,
      gene_selection_type = None,
      n_selected_individuals = None,
      n_candidates = None,
      random_state = None, 
      gene_limits = None,
      fitness_func = None
      ):

    # Make validations
    if transformation_type not in ['mutation', 'transformation']:
      raise ValueError('transformation_type should be one of mutation or transformation.')

    self.n_variables = n_variables
    self.n_genes = n_genes
    self.gene_limits = gene_limits 
    self.transformation_type = transformation_type
    self.mutation_type = mutation_type
    self.random_state = random_state
    self.fitness_func = fitness_func
    self.n_iterations = n_iterations
    self.gene_selection_type = gene_selection_type
    self.n_selected_individuals = n_selected_individuals
    self.n_candidates = n_candidates
    self.crossover_type = crossover_type
    self.best_fitness_evolution = []

    # Asserts 
    # Check that fitness function is a function
    assert callable(fitness_func)
 
    # Create the population
    if self.gene_limits is not None:
      
      # Check that both vectors have the same length
      assert len(self.gene_limits) == self.n_variables

      limits = [np.random.uniform(limit[0], limit[1], self.n_genes)
        for limit in self.gene_limits] 

    else:
      limits = [np.random.random(self.n_genes)
        for limit in range(self.n_variables)]
      
    # Convert list of limits to list of solutions
    self.population = np.array(list(zip(*limits)))

  def get_fitness_scores(self):
    scores = [self.fitness_func(ind) for ind in self.population]
    scores = np.array(scores)
    return scores 

  def __append_best_score(self, scores):
    best_score = np.max(scores)
    self.best_fitness_evolution.append(best_score)
    return 'Ok'


  def __ranking_selection(self, k):
      if k is None:
        raise ValueError('K must not be none if type ranking is selected.')
      
      ind = np.argpartition(self.get_fitness_scores(), k)[-k:]
      return ind

  def __tournament_selection(self, k, n_candidates):
    candidates = [np.random.randint(0, len(self.get_fitness_scores()), 3) for i in range(3)]
    tournament_winner = [np.argmax(self.get_fitness_scores()[tournament]) for i, tournament in enumerate(candidates)]
    ind = [tournament[tournament_winner[i]] for i, tournament in enumerate(candidates)]

    return np.array(ind)

  def gene_selection(self, gene_selection_type, k, n_candidates = None):

    if gene_selection_type not in ['ranking','tournament']:
      raise ValueError('Type should be ranking or tournament')
    
    if gene_selection_type == 'ranking':
      ind = self.__ranking_selection(k)
    elif gene_selection_type == 'tournament':
      ind = self.__tournament_selection(k, n_candidates)
    else:
      pass

    return ind
  
  def __crossover(self, parent1, parent2, crossover_type):
    
    # Check crossover type
    if crossover_type not in ['uniform', 'one_point']:
      raise ValueError('crossover_type should be one of uniform, one_point or multi_point')
    
    if crossover_type == 'one_point':
      index = np.random.choice(range(len(parent1)))
      children = parent2[:index] + parent1[index:], parent1[:index] + parent2[index:]

    elif crossover_type == 'uniform':
      parents = list(zip(*[parent1,parent2]))
      children1 = tuple([np.random.choice(element) for element in parents])
      children2 = tuple([np.random.choice(element) for element in parents])
      children = children1, children2
    else:
      pass

    return children


  def __mutation(self, individual, mutation_type):

    if mutation_type not in ['bitstring', 'shrink']:
      raise ValueError('mutation_type should be one of bitstring or shrinkg')
    
    # Get index of individual to modify
    index = np.random.choice(len(individual))

    # Convert individual to list so that can be modified
    individual_mod = list(individual)

    if mutation_type == 'bitstring':      
      individual_mod[index] = 1 - individual_mod[index]
    
    else:
      individual_mod[index] = individual_mod[index] + np.random.rand()
    
    # Convert indivudal to tuple
    individual = tuple(individual_mod)

    return individual

  def optimize(self):
    
    for i in tqdm(range(self.n_iterations)):

      # Calculate fitness score
      scores = self.get_fitness_scores()

      # Append best score
      _ = self.__append_best_score(scores)

      # Make Selection
      selected_genes = self.gene_selection(
          gene_selection_type = self.gene_selection_type,
          k = self.n_selected_individuals,
          n_candidates = self.n_candidates
          )
      
      # Get selected population
      selected_population = self.population[selected_genes.tolist()]
      

      # Make transformations (mutation/crossover)
      if self.transformation_type == 'mutation':
        transformed_genes_index = np.random.choice(
            range(len(selected_population)),
            self.n_genes
            )
        

        new_population = [self.__mutation(selected_population[i], self.mutation_type)
          for i in transformed_genes_index]
      
      else:
        # Get pairs of parents
        parents_pairs = np.random.choice(
            selected_genes,
            (int(self.n_genes/2),2)
            )
        
        # For each pair, make crossover
        new_population = [self.__crossover(self.population[parents[0]],
                                           self.population[parents[1]],
                                           crossover_type=self.crossover_type
                                           )
          for parents in parents_pairs]
        
        # Unnest population
        new_population = [child for children in new_population for child in children]
      
      # Set new population as population
      self.population = np.array(new_population)
    
    # When n_iterations are finished, fitness score
    scores = self.get_fitness_scores()

    # Append best score
    _ = self.__append_best_score(scores)

    # Get the result where the result is the best
    best_score_ind =np.argpartition(scores, 0)[0]
    
    best_solution = self.population[best_score_ind]

    return (best_solution, self.best_fitness_evolution[-1])

  def view_fitness_evolution(self):
    plt.plot(
        range(len(self.best_fitness_evolution)),
        self.best_fitness_evolution
    )

Por último vamos a probarlo, tanto aplicando mutation como aplicando crossover para ver qué resultados devuelve. Primero de todo, aplicamos mutation:

ga = GeneticAlgorithm(
  n_variables = 2,
  n_genes = 10,
  n_iterations = 50,
  transformation_type = 'mutation', #transformation
  mutation_type = 'shrink',
  #crossover_type = 'uniform',
  gene_selection_type = 'ranking',
  n_selected_individuals = 3,
  #n_candidates = None,
  #random_state = None, 
  #gene_limits = None,
  fitness_func = fitness_func
  )

print(ga.optimize())
ga.view_fitness_evolution()
100%|██████████| 50/50 [00:00<00:00, 722.95it/s]
(array([20.04435671, 20.8440738 ]), 319.9215965956338)
Genetic Algorithm Mutation

Por último aplicamos crossover:

ga = GeneticAlgorithm(
  n_variables = 2,
  n_genes = 10,
  n_iterations = 50,
  transformation_type = 'transformation',
  crossover_type = 'uniform',
  gene_selection_type = 'ranking',
  n_selected_individuals = 3,
  fitness_func = fitness_func
  )

print(ga.optimize())
ga.view_fitness_evolution()
100%|██████████| 50/50 [00:00<00:00, 693.67it/s]
(array([0.97573885, 0.93485633]), 229.28861852920954)
Genetic Algorithm Crossover

Como podemos ver en ambos casos el modelo funciona correctamente, mejorando el fitness en cada iteración.

Conclusión

Sin duda alguna los algoritmos genéticos son modelos de optimización muy utilizados que deben estar entre las herramientas que usa todo científico de datos.

En este post has podido aprender qué es un algoritmo genético, cómo funciona y cómo usarlo de forma sencilla en Python, tanto para modelos de optimización como para optimización de hiperparámetros.

Además, has podido ver cómo se programa un algoritmo genético desde cero en Python. La idea no es que, cuando tengas que usar un algoritmo genético lo escribas desde cero, sino que haya servido para asentar el funcionamiento de este algoritmo.

Así pues, espero que este post te haya resultado interesante. Si ha sido así, te animo a que te suscribas para estar al tanto de todos los posts que voy subiendo. En cualquier caso, ¡nos vemos en el siguiente!