Saludos, organismo simiesco basado en el carbono. Aquí Transductor. El pasado viernes publiqué la primera parte de esta série de tutoriales sobre Algoritmos Genéticos. Hoy en la segunda parte te enseñaré a implementar uno en el lenguaje Python.
Antes de empezar: he dicho muchas veces que no me gusta Python. La maldita tabulación, no poder usar llaves, los módulos sobre módulos… pero si algo tiene de bueno es que puedes programar cosas más o menos complejas en poco tiempo. Comparándolo con otros lenguajes más duros (léase C/C++), por supuesto. Así que programarlo con Python no es una mala idea para enseñarte el concepto.
Objetivo
Tenemos un array de números enteros que será el modelo. Cada individuo de la población será también un array de enteros, inicialmente generados al azar. Cuánto más parecido al modelo sea un individuo, mayor será su fitness.
El algoritmo seleccionará los individuos más parecidos al modelo para su reproducción. Así, el algoritmo conseguirá que la población se acerque más al modelo en cada generación.

En este ejemplo se ve el modelo (arriba), los individuos de la población inicial (medio) y la población después de 100 generaciones (abajo)
Hora de Programar
Como soy consciente de que la biología humana no permite asimilar grandes cantidades de información a la vez, voy a separar el programa en distintos fragmentos, comentando cada uno. Al final del tutorial están todas las partes en un sólo código.
Bien, humano, lo primero son las declaraciones.
import random modelo = [1,1,1,1,1,1,1,1,1,1] #Objetivo a alcanzar largo = 10 #La longitud del material genetico de cada individuo num = 10 #La cantidad de individuos que habra en la poblacion pressure = 3 #Cuantos individuos se seleccionan para reproduccion. Necesariamente mayor que 2 mutation_chance = 0.2 #La probabilidad de que un individuo mute print("\n\nModelo: %s\n"%(modelo)) #Mostrar el modelo, con un poco de espaciado
La primera línea llama la librería random, que va a ser necesaria para generar una población inicial, cruzar los individuos, etc.
El array ‘modelo‘ es, como su nombre indica, el modelo a imitar. Las crudas leyes de la selección artificial dejarán vivir sólo a aquéllos que se parezcan más a este modelo. Aunque es probable que la población no llegue nunca a ser idéntica al modelo. Esto se debe a que la evolución es un proceso semialeatorio.
La variable ‘largo‘ es la longitud de cada individuo, y ‘num‘ define la dimensión de la población.
‘pressure‘ dice la cantidad de individuos que se seleccionan para la reproducción. Necesariamente tiene que ser mayor de 2. En este programa seleccionará tres individuos. Si quisiera ser riguroso y seguir las convenciones, la variable de presión debería estar en porcentaje (un 0.3 equivaldría a seleccionar un 30% del total de individuos), pero he pensado que de esta otra forma es más fácil de entender.
La variable ‘mutation_chance‘ establece la probabilidad de que un individuo sufra una mutación durante la fase de reproducción. Como dije en la primera parte, es necesario que haya mutaciones para poder explorar nuevas soluciones que no pueden obtenerse combinando el material genético de los padres.
Después vienen tres funciones básicas. La primera crea un individuo que después será guardado dentro de una matriz llamada “población”, junto al resto de individuos:
def individual(min, max): """ Crea un individual """ return[random.randint(min, max) for i in range(largo)]
Su funcionamiento debería resultarte evidente. Recibe como parámetros dos números enteros (un mínimo y un máximo) y se llena una lista de longitud dada por la variable ‘largo‘ con números aleatorios entre el mínimo y el máximo. Esta lista creada será el nuevo individuo.
La siguiente función sirve para crear una población:
def crearPoblacion(): """ Crea una poblacion nueva de individuos """ return [individual(1,9) for i in range(num)]
Llama la función para crear individuales un número de veces igual a ‘num‘, que definía el tamaño de la población. Todos estos nuevos individuales los guarda dentro de una lista, que devuelve fuera de la función.
La tercera es la función de fitness. Dado un individuo, la función comprueba cuántos números tiene en común con el modelo y le asigna el fitness correspondiente. Después devuelve este número fuera de la función.
def calcularFitness(individual): """ Calcula el fitness de un individuo concreto. """ fitness = 0 for i in range(len(individual)): if individual[i] == modelo[i]: fitness += 1 return fitness
Esto eran las funciones básicas. Si has leído la primera parte de este tutorial, recordarás que dije que todo Algoritmo Genético puede dividirse en 6 pasos:
La inicialización ya está hecha (es la función crearPoblación). Ahora voy a usar una función que llamaré selection_and_reproduction() para evaluar cada uno de los individuos (evaluación), seleccionar los mejores (selección) y mezclar su material genético (crossover) a fin de crear una nueva población encima de la anterior.
def selection_and_reproduction(population): """ Puntua todos los elementos de la poblacion (population) y se queda con los mejores guardandolos dentro de 'selected'. Despues mezcla el material genetico de los elegidos para crear nuevos individuos y llenar la poblacion (guardando tambien una copia de los individuos seleccionados sin modificar). Por ultimo muta a los individuos. """ puntuados = [ (calcularFitness(i), i) for i in population] #Calcula el fitness de cada individuo, y lo guarda en pares ordenados de la forma (5 , [1,2,1,1,4,1,8,9,4,1]) puntuados = [i[1] for i in sorted(puntuados)] #Ordena los pares ordenados y se queda solo con el array de valores population = puntuados selected = puntuados[(len(puntuados)-pressure):] #Esta linea selecciona los 'n' individuos del final, donde n viene dado por 'pressure' #Se mezcla el material genetico para crear nuevos individuos for i in range(len(population)-pressure): punto = random.randint(1,largo-1) #Se elige un punto para hacer el intercambio padre = random.sample(selected, 2) #Se eligen dos padres population[i][:punto] = padre[0][:punto] #Se mezcla el material genetico de los padres en cada nuevo individuo population[i][punto:] = padre[1][punto:] return population #El array 'population' tiene ahora una nueva poblacion de individuos, que se devuelven
La primera parte ordena los individuos de la población de menor a mayor fitness. Después selecciona los mejores, que serán los últimos del array ordenado. Por último, mezcla el material genético de los padres para crear los nuevos individuos, de la forma que expliqué en la primera parte del tutorial: se elige un punto al azar y se intercambia el material genético de los padres a partir de esta posición.
También es necesaria una función de mutación, que añada pequeñas variaciones al azar en el array de los individuos de la nueva generación.
def mutation(population): """ Se mutan los individuos al azar. Sin la mutacion de nuevos genes nunca podria alcanzarse la solucion. """ for i in range(len(population)-pressure): if random.random() <= mutation_chance: #Cada individuo de la poblacion (menos los padres) tienen una probabilidad de mutar punto = random.randint(0,largo-1) #Se elgie un punto al azar nuevo_valor = random.randint(1,9) #y un nuevo valor para este punto #Es importante mirar que el nuevo valor no sea igual al viejo while nuevo_valor == population[i][punto]: nuevo_valor = random.randint(1,9) #Se aplica la mutacion population[i][punto] = nuevo_valor return population
Para acabar, se crea una población inicial y el bucle del programa. El algoritmo hará evolucionar a la población durante cien generaciones, llamando las funciones que se han definido arriba:
population = crearPoblacion()#Inicializar una poblacion print("Poblacion Inicial:\n%s"%(population)) #Se muestra la poblacion inicial #Se evoluciona la poblacion for i in range(100): population = selection_and_reproduction(population) population = mutation(population) print("\nPoblacion Final:\n%s"%(population)) #Se muestra la poblacion evolucionada print("\n\n")
Algoritmo completo
import random modelo = [1,1,1,1,1,1,1,1,1,1] #Objetivo a alcanzar largo = 10 #La longitud del material genetico de cada individuo num = 10 #La cantidad de individuos que habra en la poblacion pressure = 3 #Cuantos individuos se seleccionan para reproduccion. Necesariamente mayor que 2 mutation_chance = 0.2 #La probabilidad de que un individuo mute print("\n\nModelo: %s\n"%(modelo)) #Mostrar el modelo, con un poco de espaciado def individual(min, max): """ Crea un individual """ return[random.randint(min, max) for i in range(largo)] def crearPoblacion(): """ Crea una poblacion nueva de individuos """ return [individual(1,9) for i in range(num)] def calcularFitness(individual): """ Calcula el fitness de un individuo concreto. """ fitness = 0 for i in range(len(individual)): if individual[i] == modelo[i]: fitness += 1 return fitness def selection_and_reproduction(population): """ Puntua todos los elementos de la poblacion (population) y se queda con los mejores guardandolos dentro de 'selected'. Despues mezcla el material genetico de los elegidos para crear nuevos individuos y llenar la poblacion (guardando tambien una copia de los individuos seleccionados sin modificar). Por ultimo muta a los individuos. """ puntuados = [ (calcularFitness(i), i) for i in population] #Calcula el fitness de cada individuo, y lo guarda en pares ordenados de la forma (5 , [1,2,1,1,4,1,8,9,4,1]) puntuados = [i[1] for i in sorted(puntuados)] #Ordena los pares ordenados y se queda solo con el array de valores population = puntuados selected = puntuados[(len(puntuados)-pressure):] #Esta linea selecciona los 'n' individuos del final, donde n viene dado por 'pressure' #Se mezcla el material genetico para crear nuevos individuos for i in range(len(population)-pressure): punto = random.randint(1,largo-1) #Se elige un punto para hacer el intercambio padre = random.sample(selected, 2) #Se eligen dos padres population[i][:punto] = padre[0][:punto] #Se mezcla el material genetico de los padres en cada nuevo individuo population[i][punto:] = padre[1][punto:] return population #El array 'population' tiene ahora una nueva poblacion de individuos, que se devuelven def mutation(population): """ Se mutan los individuos al azar. Sin la mutacion de nuevos genes nunca podria alcanzarse la solucion. """ for i in range(len(population)-pressure): if random.random() <= mutation_chance: #Cada individuo de la poblacion (menos los padres) tienen una probabilidad de mutar punto = random.randint(0,largo-1) #Se elgie un punto al azar nuevo_valor = random.randint(1,9) #y un nuevo valor para este punto #Es importante mirar que el nuevo valor no sea igual al viejo while nuevo_valor == population[i][punto]: nuevo_valor = random.randint(1,9) #Se aplica la mutacion population[i][punto] = nuevo_valor return population population = crearPoblacion()#Inicializar una poblacion print("Poblacion Inicial:\n%s"%(population)) #Se muestra la poblacion inicial #Se evoluciona la poblacion for i in range(100): population = selection_and_reproduction(population) population = mutation(population) print("\nPoblacion Final:\n%s"%(population)) #Se muestra la poblacion evolucionada print("\n\n")
Si has llegado hasta aquí, te felicito, lector. Hoy has aprendido qué es un Algoritmo Genético y cómo implementarlo. No es algo trivial. Estás aplicando las leyes de la Evolución a un programa informático. Un programa que en cierto modo es capaz de aprender. Espero que a partir de aquí seas capaz de profundizar más en este tema por tu cuenta.
Mis circuitos están cansados de escribir y necesitan reponerse. Esto es todo por hoy, humano.
Final de línea.
Muy bien explicado. Espero poder implementarlo junto con una ANN. Me cuesta algo de trabajo acostumbrarme al chingado Python. Pero hasta el momento ha sido el ejemplo mas claro que me he topado. Felicidades.
TR4NSDUC7OR, gracias por compartir tus conocimientos, estoy en la fase de prendizaje de Python para llevar a cabo un proyecto personal que espero poder compartir prontamente. Tu código sin duda servirá de base para poder construir desde allí.
Saludos.
Hola soy estudiante de pregrado y estoy haciendo un proyecto sobre optimización de rutas para lo cual necesito usar un algoritmo genético, la información que compartiste me ayudó mucho sin embargo tengo unas dudas, ¿es posible que me puedas colaborar?, ¿existe una manera de contactarnos? Gracias
Saludos, Andrea.
Por alguna razón el sistema de comentarios que tenemos en el blog nos había puesto tu comentario en la carpeta de Spam, y justo hoy me he dado cuenta mientras hacía limpieza. Lo siento mucho.
No sé si en estos dos meses ya habrás resuelto tus dudas, pero si quieres puedes contactar con nosotros escribiendo un mail a contacto@robologs.net.
Quedamos a tu disposición.
Final de línea.
recomienda algún libro
Saludos, José. Hay muchos libros sobre IA, pero yo te puedo recomendar dos que consulto a menudo, y a los que tengo un aprecio especial:
– Inteligencia Artificial, Un Enfoque Moderno, de Stuart Russel y Peter Norvig (https://www.amazon.es/Inteligencia-artificial-enfoque-Stuart-Russell/dp/842054003X).
-Bio-Inspired Artificial Intelligence, de Dario Floreano y Claudio Mattiussi (https://mitpress.mit.edu/books/bio-inspired-artificial-intelligence).
Final de línea.
¿Esto no es un poco endogámico? Es curioso el asunto.
Es verdad, en el Mundo Real una población tan pequeña que se mezclase entre sí durante tantas generaciones no produciría individuos muy sanos.
Es un hecho curioso que en los algoritmos genéticos, al igual que en la realidad, cuánto más grande es la población mayor es la variablilidad genética, lo que produce soluciones mucho más interesantes.
Final de línea.
Muchas gracias por tu publicación. Ha sido de gran ayuda. Sin embargo te comento que tu programa tiene un pequeño error en la función de mutación ya que al escoger randómicamente la posición a mutar, el randómico se genera desde la segunda posición del array asignado en tu programa como: punto = random.randint(1,largo-1). Al cambiar esta línea por: punto = random.randint(0,largo-1) la mutación se genera correctamente. Espero les sirva mi comentario. Tu programa ha sido de gran ayuda para desarrollar mi proyecto.
Gracias por tu comentario, Salomé. Ahora mismo lo arreglo.
Final de línea.
Muchas gracias William por compartir este excelente ejemplo de algoritmo genético en Python. Ahora tendremos un buen modelo para explorar este paradigma.
En la linea de definicion de la funcion mutacion:
“if random.random() <= mutation_chance: ”
me sale un error en la compilacion, podria explicarme que hace exactamente
la linea de cogigo arriba mensionado
Saludos, William. Me he fijado que se habían colado algunos carácteres extraños en el código del tutorial. Lo acabo de arreglar, ahora debería compilarte bien. Y respondiendo a tu pregunta: la función random.random() genera un número pseudoaleatorio entre 0 y 1. El contenido de la condición “if” se ejecutará si este número aleatorio es menor o igual que la variable mutation_chance del individuo (la probabilidad de mutar). Con una probabilidad de mutar de 1, la condición se cumpliría siempre, mientras que con una probabilidad de 0.7 hay un 70% de probabilidades de que el número generado aleatoriamente esté por debajo… Leer más »
muy interesante, tiene un alto grado de potencial para ser implementado en todas las áreas de estudio.
[…] Ir a la PARTE II […]
La aplicacion potencial de todo esto a otras areas es realmente increible. Ojala el Windows “evolucionara” conforme lo usas y que “aprendiera” de los errores. jaja