INFORMACIÓN
WHAT IS IT?
Robby the Robot es un robot virtual que se mueve por una habitación y recoge latas. Este modelo demuestra el uso de un algoritmo genético (GA, siglas en inglés) para desarrollar estrategias de control para Robby. El GA comienza con estrategias generadas aleatoriamente y luego usa la evolución para mejorarlas.
HOW IT WORKS
Como trabaja Robby: El mundo de Robby es un cuadrado de 10×10 que contiene latas dispersas al azar. Su objetivo es recoger tantas como pueda.
7 acciones: En cada tic de tiempo, Robby puede realizar una de las siete acciones: moverse en una de las cuatro, direcciones cardinales, moverse en una dirección aleatoria, tomar una lata o quedarse quieto.
Recompensas y penalizaciones: Cuando Robby toma una lata, obtiene una recompensa. Si intenta coger una lata donde no la hay, o choca contra una pared, se le penaliza. Su puntuación al final de una carrera es la suma de estas recompensas y penalizaciones. Cuanto mayor sea su puntuación, mejor lo ha hecho.
5 lugares 243 situaciones: Para decidir qué acción realizar, Robby detecta su entorno. Puede ver el contenido del cuadrado en el que se encuentra y los cuatro cuadrados vecinos. Cada cuadrado puede contener una pared, una lata o ninguna de las dos. Eso significa que sus sensores pueden estar en una de 3^5 = 243 combinaciones posibles.
Estrategia: Una «estrategia» para Robby especifica una de sus siete posibles acciones para cada una de esas 243 situaciones posibles en las que puede encontrarse.
(Nota avanzada: si realmente hace los cálculos, se dará cuenta de que algunas de esas 243 situaciones resultan ser «imposibles», por ejemplo, Robby nunca se encontrará en una situación en la que todas las direcciones cardinales contengan paredes. Esto es no hay problema; el algoritmo genético esencialmente ignora las situaciones «imposibles» ya que Robby nunca las encuentra).
CÓMO FUNCIONA EL ALGORITMO GENÉTICO
Existen muchas variaciones posibles en el concepto básico de un algoritmo genético. Aquí está la variante particular implementada en este modelo.
Comenzamos con un conjunto de estrategias generadas aleatoriamente. Cargamos cada estrategia en Robby a su vez, y luego ejecutamos esa estrategia en una serie de arreglos de latas generados aleatoriamente («entornos»).
Calificamos a Robby según su desempeño en cada entorno. Si Robby golpea una pared, pierde 5 puntos. Si coge una lata con éxito, gana 10 puntos. Si intenta coger una lata, pero no hay ninguna, pierde 1 punto. La puntuación media de Robby en todos estos entornos se considera la «aptitud» (fitness) de esa estrategia.
Una vez que hemos medido la idoneidad del conjunto actual de estrategias, construimos la próxima generación de estrategias. Cada nueva estrategia tiene dos padres. Elegimos al primer padre eligiendo 15 padres candidatos al azar, luego elegimos el que tiene la mayor aptitud. Repetimos esto para elegir al segundo padre. Cada par de padres crea dos nuevos hijos mediante el cruce y la mutación (ver más abajo). Seguimos repitiendo este proceso hasta que tengamos suficientes hijos nuevos para completar la población (configurable mediante el control deslizante ‘population-size’, tamaño de la población.). Esta «generación» de nuevos hijos reemplaza a la generación anterior. Luego calculamos de manera similar el fitnes, la aptitud, de la generación actual, elegimos a los padres y creamos una nueva generación. Este proceso continúa mientras se presiona el botón go-forever o es controlado por el control deslizante ‘number-of-generations’ cuando se presiona el botón ‘go-n-generations’.
Para combinar las estrategias de dos padres, usamos el report «crossover». Elegimos un punto de cruce aleatorio y combinamos la primera parte de la estrategia del primer padre con la segunda parte de la estrategia del otro padre. Por ejemplo, si el punto de cruce seleccionado es 50, usamos las primeras 50 entradas de la estrategia del primer padre y las últimas 193 entradas de la estrategia del segundo padre. (Cada estrategia está en un orden fijo). Además del cruce, las estrategias de los hijos están sujetas a una mutación aleatoria ocasional (configurable por el control deslizante mutation-rate), en la que una acción de la estrategia es reemplazada por otra acción elegida al zar.
HOW TO USE IT
Presione setup para crear el grupo inicial de estrategias aleatorias. Presione go-forever para iniciar la ejecución del algoritmo genético, o go-n-generations para ejecutar el algoritmo genético durante un número fijo de generaciones (configurable mediante el control deslizante number-of-generations).
En la vista del mundo, verá el conjunto de estrategias (representadas por iconos de «persona»). Las estrategias son heterogéneas. La diversidad en su estado físico se visualiza mediante el color y la posición en el eje x. Su color es un tono de rojo, escalado por su forma física. Es más claro cuando el estado físico es bajo y más oscuro cuando está alto. Además, la idoneidad de una estrategia determina dónde se encuentra a lo largo del eje x, con las estrategias menos adecuadas a la izquierda y las estrategias más adecuadas a la derecha. Otro aspecto de la diversidad es la diferencia entre las estrategias. Esta diferencia se mide contando la frecuencia de cada una de las 7 acciones básicas en la estrategia, la distribución de alelos ‘allele-distribution’ formando un vector de 7 dimensiones y luego calculando la distancia euclidiana entre dos de esos vectores. Una de las estrategias con mayor fitness, aptitud, se coloca en el centro del eje y. Las otras estrategias se colocan en ubicaciones cuya distancia desde el centro a lo largo del eje y es proporcional a la diferencia entre su estrategia y la estrategia ganadora. Todo esto toma bastante tiempo para mostrarse, por lo que para ejecuciones largas de GA, querrá mover el control deslizante de velocidad hacia la derecha o desmarcar la casilla de verificación «Actualizar la vista» para obtener resultados más rápido. En cualquier momento que desee pausar el algoritmo y ver cómo se comporta la mejor estrategia actual, presione go-forever y espere a que termine la generación actual. Vuelva a marcar «actualizar la vista” para ver las actualizaciones, si lo desmarcó antes. A continuación, presione view-robby’s-environment. Esto muestra la cuadrícula en la que se mueve Robby, con una nueva distribución aleatoria de latas. Luego, presione step-thru-best-strategy. Cada vez que presione este botón, Robby utilizará la mejor estrategia de la última generación para tomar una acción en el entorno actual. Siga presionando el botón step-thru-best-strategy para ver cómo funciona la estrategia. En cualquier momento puede presionar view-robby’s-environment nuevamente para comenzar de nuevo con un nuevo entorno de latas. Si desea volver a la vista de las estrategias presiones el botón “view-strategies”.
THINGS TO NOTICE
El rendimiento de Robby mejora gradualmente. ¿Cuánto tiempo se tarda en llegar a un estado físico medio o alto? ¿Cómo se comporta normalmente Robby con una estrategia totalmente aleatoria? ¿Cómo se comporta una vez que ha tenido lugar alguna evolución?
¿El rendimiento de Robby finalmente se estabilizará? ¿Cómo se comporta con las estrategias que finalmente evolucionan? En el camino hacia la meseta final, ¿hubo alguna vez mesetas temporales?
THINGS TO TRY
Varíe la configuración de los controles deslizantes POPULATION-SIZE y MUTATION-RATE. ¿Cómo afectan estos a la mejor aptitud de la población, así como a la velocidad de evolución?
EXTENDING THE MODEL
Agregue un control deslizante crossover rate para una tasa de cruce, es decir, para la probabilidad de que dos
padres creen descendencia por cruce. Si no se cruzan, simplemente se clonan a sí mismos (y luego la descendencia clonada sufre una posible mutación). (Deberá cambiar el procedimiento crossover).
Agregue un control deslizante para el tamaño del torneo. ¿Cómo afecta la variación del tamaño del torneo a la
evolución de las estrategias de Robby?
Pruebe diferentes reglas para seleccionar a los padres de la próxima generación. ¿Qué conduce a la evolución más rápida? ¿Existe alguna vez una compensación entre la rápida evolución al principio y la eficacia de las estrategias ganadoras al final? Intente utilizar la contigüidad espacial como factor para seleccionar qué individuos se aparean. Intente entrenar a Robby para que realice una tarea algo más difícil.
NETLOGO FEATURES
El comando de ejecución run es clave aquí. Un cromosoma es una lista de cadenas, strings donde cada cadena es un nombre de procedimiento. Hacer un run (llamar a ejecutar) a esa cadena es ejecuta el procedimiento que
corresponde. Para representar estrategias de forma compacta, utilizamos símbolos Unicode (como flechas).
Para medir la similitud entre diferentes estrategias, usamos la lista de primitivas de alto nivel map y reduce.
MODELOS RELACIONADOS
Simple Genetic Algorithm
INTERFAZ
Referencias y lecturas complementarias
1.- Artículo «Sistema ternario«
