El problema es muy sencillo: tenemos un laberinto, y deseamos que nuestro algoritmo genético encuentre la salida
Empecemos importando los paquetes necesarios y creando el laberinto:
In [1]:
%matplotlib inline
import laberinto.algen as ag
import laberinto.laberinto as lab
import numpy as np
import matplotlib.pyplot as plt
In [2]:
mapa1 = lab.Map()
Pintemos el laberinto!
In [3]:
mapa1.draw_tablero()
Queda chulo, ¿verdad?
Ahora viene una cuestión interesante: ¿Cómo definimos un camino a partir de un genoma?
Existen varias maneras, pero probablemente la mas simple sea esta:
Para cada casilla, el genoma nos designa una dirección, en la que un viajero intentaría moverse una vez que ha llegado a esa casilla.
Veamos cómo quedaría:
In [4]:
mapa1.create_camino()
ejemplo = mapa1.list_caminos[0]
ag.calculate_traits(ejemplo, ejemplo.dict_genes)
lab.calculate_performances(ejemplo)
ejemplo.draw_directions()
Un viajero que intentara seguir estas indicaciones, estaría en un buen apuro. ¡Incluso algunas flechas apuntan a las paredes! Necesitaremos ser un poco flexibles para recorrerlo:
Si la dirección de la casilla le dice que intente atravesar una pared, el viajero intentará otra dirección aleatoria.
El viajero tendrá una cantidad limitada de pasos.
Probémoslo!
In [5]:
ejemplo.draw_directions()
ejemplo.draw_path()
...La verdad es que como camino, no es gran cosa...
Pero no es suficiente con decir que es "malo", tenemos que ir más allá: tenemos que evaluar el camino objetivamente con una serie de reglas para poder usar el algoritmo genético:
Cuando el viajero choque con una pared, el camino recibirá una pequeña penalización.
Si hay dos casillas que se apuntan mutuamente, el viajero quedará atrapado, por lo que también penalizamos volver a la casilla de la que se partió en el turno anterior.
Queremos llegar a la salida de la derecha, por lo que beneficiaremos a los caminos que dejen al viajero más a la derecha.
Si un camino conduce a la salida, le daremos una gran bonificación para no perderlo
¡Probemos con estas reglas un algoritmo genético!
In [6]:
lab.calculate_fitness(ejemplo)
ejemplo.fitness
Out[6]:
Ya tenemos un valor numérico, lancemos el algoritmo!
In [7]:
lab.avanzar(mapa1)
lab.draw_all(mapa1)
Llegados a este punto, lo más probable es que el algoritmo haya encontrado un bucle o una salida. Si no, puedes volver a ejecutar la celda superior para avanzar unas generaciones más.
Todos los caminos de la última generación están representados como líneas rojas semitransparentes, de modo que las casillas más atravesadas van acumulando capas de rojo. Además, el mejor camino encontrado se muestra destacado en azul.
También puedes correr el algoritmo desde el principio si añades "mapa1 = lab.Map()" antes de "lab.avanzar(mapa1)".
Si pruebas a ejecutarlo varias veces, observarás lo antes comentado, cuando alcanza la salida, todo genial, pero si llega a un bucle, ¿Qué podemos hacer para sacarlo de ahí?
La respuesta es, obviamente, añadir Neurotoxinas Letales al laberinto. Pero no de cualquier manera!
Supongamos que cada persona que va recorriendo el laberinto a dejando a su paso un olor fétido que hace que todos los demás prefieran no tener que pasar por allí. ¿Cómo crees que eso afectaría a los bucles?
La manera de implementar este efecto es añadir al mapa una capa de profundidad, una matriz adicional que expresa la cantidad de veneno, feromona negativa o mal olor que hay en cada casilla. Después, al analizar nuestro camino, contaremos también la cantidad de veneno que hemos atravesado para puntuar la calidad del camino dentro del algoritmo.
Comprobémoslo!
Ejecuta de nuevo el algoritmo, pero ahora añadiendo veneno. Ejecútalo varias veces! ¿Aparecen bucles con la misma frecuencia?
In [8]:
mapa2 = lab.Map(veneno=1)
lab.avanzar(mapa2)
lab.draw_all(mapa2)
Sin embargo, abusar de las neurotoxinas letales también puede tener problemas, ¡Quién lo hubiera adivinado!
¡Prueba con la configuración siguiente!
In [9]:
mapa2 = lab.Map(veneno=100)
lab.avanzar(mapa2)
lab.draw_all(mapa2)
Si te interesa investigar más este efecto, puedes repasar la teoría sobre el dilema exploración-explotación de la parte de teoría.
¿Qué pasaría si el laberinto cambiara a la vez que se resuelve?
Examina el código. Observa la matriz que describe al laberinto, prueba a cambiar los valores y observa cómo cambia la reoresentación del laberinto. ¿Qué pasaría si la matriz cambiara con el tiempo, por ejemplo, cada 50 o 100 turnos? ¿Podrías hacer que las soluciones posibles se vayan alternando? También puedes probar a cortar los bucles...
Existe un ejercicio muy interesante que se puede hacer basado en esa tarea:
Cambia el código para que las posibles salidas del laberinto se alternen con el tiempo. Observa los resultados, comprueba cuánto tarda el algoritmo en encontrar la nueva salida.
Ahora, introduce en la función de mérito un parámetro que premie a individuos cuyo genoma sea diferente al de los demás. Observa la diferencia en el tiempo de adaptación para el laberinto cambiante.
¿Cómo crees que esto se extrapola al mundo biológico? ¿Cómo crees que influye la diversidad genética en la resistencia a plagas y enfermedades de una especie?
In [ ]:
In [ ]:
Siro Moreno, Aeropython, 19 de Noviembre de 2015
Basado en el ejercicio 'Labyrinth' del paquete Evolife del profesor Jean Louis Dessalles.
In [ ]: