algoritmos geneticos python

Algoritmos genéticos en Python

Algoritmos genéticos son  procesos para buscar soluciones a un problema concreto,replicando la forma biológica de la evolución de las especies.

Es reconocida como una técnica de inteligencia artificial, inspirada en la teoría de la evolución que formuló Charles Darwin donde sólo los más aptos sobreviven en un medio específico.

Población

La forma de aplicarlo es creando un conjunto de propuestas como solución al problema, cada solución será un individuo de la población. Los algoritmos genéticos tienen como punto de partida un conjunto de soluciones aleatorio.

algoritmos geneticos python

Generación

Una generación en un algoritmo genético es una población diferente, donde en cada generación se realiza una evaluación para determinar cuál es la solución que más se acerca a lo óptimo.

algoritmos geneticos python

Evaluación y reproducción

Los mejores individuos de cada generación se reproducen mientras que los peores mueren, de esta forma en la siguiente generación permanecerán los genes de una solución “buena”.

algoritmos geneticos python

Mutación

Al crear una nueva generación los individuos sufren de mutación, que realmente es lo que aporta nuevas soluciones posibles al problema y a lo largo del tiempo se encontrará la mejor.

algoritmos geneticos python

Algoritmos genéticos: Ser o no ser

Pero basta de teoría, realicemos un ejemplo con el famoso problema “Ser o no ser”, donde comenzamos con una generación aleatoria y deben encontrar la solución para conseguir el texto To be or not to be.

La implementación será con Python 3 usando un poco de programación orientada a objetos.

Clase DNA

Para guardar los genes de cada individuo usaré una clase DNA para controlar su comportamiento en el programa.

Para poder crear DNA nuevo a partir de un conjunto de datos añadimos como parámetros en el constructor las variables sizegenSet.

Además cada DNA debe tener su propio score fitness para poder seleccionar el mejor DNA en cada generación.


class DNA(object):
    genes = np.array([])
fitness = 0 def __init__(self, size, genSet): """Genera un arreglo de caracteres aleatorios""" self.genes = np.array(random.sample(genSet, size))

La mutación de los genes es la parte más importante de los algoritmos genéticos, ya que sin esta las generaciones nunca evolucionarían a mejores versiones y al final la población nunca alcanzará su objetivo.

Dentro de la misma clase añadiremos un método para mutar el DNA del objeto, de esta forma será más sencillo hacer esta acción si es seleccionado para mutación.


# Class DNA
    .
    .
    def mutate(self, parentA, parentB, genSet, mutation_rate):
        """Cruza con 2 padres"""
        # Arreglo base para nuevos genes
        newGenes = np.zeros(parentA.genes.shape[0])
        # Se selecciona punto medio de forma aleatoria
        midPoint = random.randint(0, parentA.genes.shape[0])
        for ix in range(len(self.genes)): # Para cada gen...
            # Probabilidad del 10% de mutación en cada gen
            if random.random() < mutation_rate:
                # La mutación es un caracter aleatorio
                newGenes[ix] = random.sample(genSet, 1)[0]
            else:
                # Usa el gen del padre A o B según el pivote
                if ix < midPoint:
                    newGenes[ix] = parentA.genes[ix]
                else:
                    newGenes[ix] = parentB.genes[ix]
                
        self.genes = newGenes

Para la clase DNA es suficiente, pasemos a la clase de la población…

Clase Population

Esta clase nos servirá para administrar todos los DNA de cada individuo, así como hacer las nuevas generaciones o llamar las mutaciones necesarias.


class Population:
    # Atributo para guardar los DNA
    pop = np.array([])
    def __init__(self, target, maxPop, genSet, mutation):
        # Conjunto de genes posibles para la población
        self.genSet = np.array(map(lambda x: ord(x), genSet))
        # Frase objetivo
        self.target = np.array(map(lambda x: ord(x), target))   
        # Población máxima     
        self.maxPop = maxPop
        # Mejor puntuación de fitness
        self.biggest = 0
        # Fitness promedio de la población
        self.avg_fitness = 0
        # Porcentaje de mutación
        self.mutation_rate = mutation
        
        # Creación aleatoria de la población inicial
        while self.pop.shape[0] < maxPop:
            self.pop = np.append(self.pop, 
                                 DNA(self.target.shape[0], 
                                 self.genSet))

En este punto tenemos la población inicial, ahora para poder saber a qué individuos seleccionar de esta primer generación necesitamos calcular el fitness, crearemos el método calculate_fitness para hacer esta tarea.


# Class Poblation
    .
    .
    def calculate_fitness(self):
        """La suma de los caracteres correctos son el fitness"""
        # Posición del mayor fiteness
        self.biggest = 0
        # Posición del segundo mayor fitness
        self.second = 0
        # Fitness promedio
        self.avg_fitness = 0
        # Por cada individuo...
        for ix in range(self.pop.shape[0]):
            # current fitness
            # Cuenta los caracteres correctos
            cf = (self.pop[ix].genes == self.target).sum()
            self.pop[ix].fitness = cf
            # Suma el promedio de sus aciertos
            self.avg_fitness+= float(cf) / self.target.shape[0]            
            # Actualiza los 2 mejores si es que ocurre
            if cf > self.pop[self.biggest].fitness:
                self.biggest = ix
            elif cf > self.pop[self.second].fitness:
                self.second = ix
        # Calcula el promedio de fitness general
        self.avg_fitness /= self.pop.shape[0] 
        self.avg_fitness *= 100.0

Si ya tenemos la posibilidad de calcular el fitness de la generación actual ahora es momento de seleccionar los mejores y crear la nueva generación, crearemos un método next_generation para realizarlo…


# Class Poblation
    .
    .
    def next_generation(self):
        """Repoblar con método elitista, sólo los 2 mejores"""        
        # Genes de los mejores
        parentA =  self.pop[self.biggest]
        parentB =  self.pop[self.second]
        # Para cada nuevo individuo
        for ix in range(self.pop.shape[0]):
            child = DNA(parentA.genes.shape[0], self.genSet)
            # Cruza los genes de los 2 padres
            child.mutate(parentA, 
                        parentB, 
                        self.genSet, 
                        self.mutation_rate)
            # Nuevo individuo en la población
            self.pop[ix] = child

Ahora sólo necesitamos una condición que nos permita saber si ya alcanzamos la meta, añadiremos un método evaluate simplemente para verificar esto…


# Class Poblation
    .
    .
    def evaluate(self):
        """Regresa verdadero si aún no es correcto"""
        best_genes = self.pop[self.biggest].genes
        return not (best_genes == self.target).all()
Ahora añadiremos un método especial __str__ para imprimir todos los genes de la población

Uso del las clases

Guardaremos las clases en un archivo llamado Genetics.py y crearemos un nuevo en el mismo directorio, main.py.

Comenzaremos con importar las librerías necesarias y las clases que acabamos de crear.


# main.py

# Nuestras clases
import Genetics

# Para generar la lista de genes
import string

# Para operaciones de algebra lineal
import numpy as np

# Para visualizar el avance de la población
from matplotlib import pyplot as plt
Vamos a definir entonces los parámetros del algoritmo:

# main.py

# Lista de caractéres para los genes
genSet = string.letters + string.punctuation + " " + string.digits        

# Frase objetivo
target = "To be or not to be."    

# Población máxima de individuos por generación
maxPop = 500

# Porcentaje de mutación del 1%
mutation = 0.01

# Primera generación de la población
population = Genetics.Population(target, maxPop, genSet, mutation)

# Lista para tener historial de todas las generaciones
generations = np.array([])

# Contador de generaciones
generation = 1

Ya tenemos todas las variables necesarias para comenzar el algoritmo, el ciclo de un algoritmo genético es el siguiente:

  1. Generación de población
  2. Evaluación
  3. Selección de los mejores
  4. Cruza de genes
  5. Mutación

Y estos pasos se repiten una y otra vez hasta alcanzar el objetivo o un número máximo de iteraciones predefinido.


# main.py

# Mientras no se alcance el objetivo
while population.evaluate():
    # Evaluar
    population.calculateFitness()

    # Selección, cruce de genes y mutación
    population.nextGeneration()

    # Guardar generación en el historial
    generations = np.append(generations,
                     np.array([population.avg_fitness]))
    print(f"Generation: {generation}")
    print(f"Average fitness:{population.avg_fitness:.2f}%")
    print("Best Genes:", 
          "".join(
              list(map(lambda g: chr(int(g)), 
              population.pop[population.biggest].genes))
          ))
    # Siguiente generación
    generation+=1

Una vez terminado el ciclo tendremos la generación que ha superado la prueba, vamos a visualizar los resultados…


# main.py

# Creamos la gráfica del fitness del historial
plt.plot(range(generations.shape[0]), generations)

# Eje x es la generación
plt.xlabel("Generación")

# Eje y es el fitness promedio de la generación
plt.ylabel("Average fitness")

# Título de la gráfica
plt.title("Learning path")
# Muestra una cuadrícula en la gráfica
plt.grid()
# Muestra la gráfica
plt.show()
    
print("="*20)
print(f"Final generation: {generation}")
print("Genes: ", 
      "".join(
         map(lambda x: chr(int(x)),                                 
         population.pop[population.biggest].genes
))

Resultados:

Los resultados del algoritmo ejecutando el script main.py son los siguientes…
Average fitness: 1.12%
Genes: TfDxK!7P Yo+A,m=:\#
Generation: 2
Average fitness: 10.53%
Genes: TfDxK!Ud Yo+A,m=:\#
Generation: 3
Average fitness: 16.73%
Genes: TfDxK!UW Yo+A,m :\#
...
...
...
Generation: 30
Average fitness: 78.18%
Genes: To*be or 4o+ to 0\.
Generation: 31
Average fitness: 78.08%
Genes: To be or /o+ to 0\.
Generation: 32
Average fitness: 78.14%
Genes: To be or /o+ to 0\.
...
...
...
Generation: 76
Average fitness: 93.69%
Genes: To be or no+ to be.
Generation: 77
Average fitness: 96.08%
Genes: To be or not to be.
====================
Final generation: 78
Genes:  To be or not to be.
Podemos ver como la primera generación tiene puros genes aleatorios y poco a poco los mejores genes persisten para al final lograr el objetivo.

Veamos la gráfica del aprendizaje genético.
algoritmos geneticos python

Experimento

Para entender la importancia de la mutación te propongo que corras el algoritmo con el porcentaje en 0 y comentes en este post tus resultados, estoy seguro que te va a sorprender ver lo cercano a la realidad que es este algoritmo.

Conclusión

Los algoritmos genéticos son una excelente forma de solucionar problemas que no tenemos idea de como resolverlos pero sí sabemos en donde queremos estar o el estado final una vez resuelto.

Este tipo de algoritmos son comúnmente usados con redes neuronales que facilitan y optimizan los valores de una red, de esta forma es como logran hacer que una IA pueda jugar flappy bird sin equivocarse.

 

 

Puedes encontrar una versión de este código en mi github:

https://github.com/Fidelopez/Genetic-Algorithms/tree/master/To_be_or_not_to_be

Si te gustó mi contenido puedes revisar mi publicación sobre regresión lineal.

One thought to “Algoritmos genéticos en Python”

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *