Trabajo Práctico Final#

Trabajo Práctico Final alternativo

Es posible proponer otro proyecto como trabajo final. En ese caso, se debe escribir una consigna con los requerimientos y funcionalidades a implementar, y mandarla por mail a los docentes de su grupo. Ellos determinarán si la propuesta es o no viable. Procuren decidir esto a la brevedad, para maximizar el tiempo disponible para el desarrollo del trabajo.

Programando la evolución#

Introducción#

En el 2013, un grupo de desarrolladores independientes lanzó un juego llamado “Flappy Bird”. El juego se volvió increíblemente popular debido a su simplicidad y dificultad. El objetivo del juego es controlar un pájaro que vuela entre una serie de tuberías sin chocar con ellas. El jugador debe tocar la pantalla para hacer que el pájaro vuele más alto y soltar para que baje. A pesar de su simplicidad, el juego es extremadamente desafiante y requiere mucha práctica para dominarlo. El juego fue retirado de las tiendas de aplicaciones por su creador debido a su adictividad, pero su legado perdura.

Algoritmos Genéticos#

Los algoritmos genéticos son una técnica de optimización inspirada en la evolución biológica. Se basan en el concepto de selección natural y evolución para encontrar soluciones a problemas complejos. En la naturaleza, los organismos más aptos tienen más probabilidades de sobrevivir y reproducirse, transmitiendo sus genes a las generaciones futuras. De manera similar, en los algoritmos genéticos, las soluciones más aptas son seleccionadas y combinadas para generar nuevas soluciones, con la esperanza de que estas nuevas soluciones sean aún más aptas.

En este caso vamos a estar trabajando con la siguiente función para decidir si un pájaro aletea o no:

\[ w_0 + w_1 * \Delta y + w_2 * \Delta y ^ 2 + w_3 * \Delta x + w_4 * \Delta x ^ 2 + w_5 * v_y > 0 \]

Donde:

\(w_0, w_1, w_2, w_3, w_4, w_5\) son los pesos que definen el comportamiento del pájaro. Estos pesos son los “genes” que serán optimizados mediante el algoritmo genético.
\(\Delta y\) es la diferencia en altura entre el pájaro y la próxima tubería.
\(\Delta x\) es la distancia horizontal entre el pájaro y la próxima tubería.
\(v_y\) es la velocidad vertical del pájaro.

Si la expresión es verdadera, el pájaro aletea; de lo contrario, no lo hace.

La “aptitud” de un pájaro podría medirse en función de su distancia recorrida. De esta manera, el algoritmo genético se encargaría de encontrar los pesos óptimos que permitan al pájaro recorrer la mayor distancia posible evitando las tuberías en su camino.

Un algoritmo genético típico consta de varios pasos clave:

Inicialización de la población: Se genera una población inicial de pájaros de manera aleatoria. En este caso, la población inicial serían varios pájaros con diferentes configuraciones de pesos al azar.
Evaluación de la aptitud: Se evalúa cada pájaro en función de un criterio de aptitud predefinido. En este caso, la aptitud de un pájaro podría medirse en función de su capacidad para recorrer la mayor distancia posible evitando las tuberías en su camino.
Selección: Se seleccionan pájaros según su aptitud. Hay varias estrategias de selección, una puede ser seleccionar los n mejores pájaros. Otra puede ser seleccionar pájaros al azar, pero con una probabilidad proporcional a su aptitud. Esta selección serán los padres que se utilizarán para generar nuevos pájaros. Un pájaro podría o no ser seleccionado más de una vez. En este caso, se podrían seleccionar algunos pájaros entre todos los pájaros, pero con una probabilidad proporcional a su aptitud.
Cruce: Entre los pájaros seleccionados, se combinan los genes para generar nuevos pájaros. En este caso, se podría cruzar los pájaros de dos en dos. Esto significa que se tomarían dos pájaros, se seleccionarían los genes de uno u otro pájaro con cierta probabilidad, y se generaría un pájaro nuevo a partir de ellos.
Mutación: Con una cierta probabilidad, se introducen cambios aleatorios en los pájaros para así explorar nuevas combinaciones de pesos que no se habían considerado previamente. En este caso, la mutación podría consistir en cambiar un peso de un pájaro por otro al azar.
Repetición: Los pasos de evaluación, selección, cruce y mutación se repiten durante varias épocas (iteraciones) hasta que se alcanza un criterio de parada (por ejemplo, un número máximo de épocas o una solución satisfactoria).

Objetivo#

El objetivo de este trabajo práctico es implementar un algoritmo genético en Python para encontrar la mejor combinación de pesos para lograr que los pájaros vuelen lo más lejos posible. También se desea visualizar los resultados del algoritmo genético mediante gráficos que muestren la evolución de la aptitud de los pájaros, la importancia de los pesos, y otros aspectos relevantes del proceso de optimización.

Desarrollo#

Visualización del Juego#

Se debe implementar la interfaz gráfica del juego utilizando la librería pygame. La interfaz debe mostrar el pájaro (o los pájaros), las tuberías y el fondo del juego. La interfaz debe actualizarse en tiempo real para mostrar el movimiento del pájaro y las tuberías. El juego también debe tener música y efectos de sonido para mejorar la experiencia del usuario. Se desea que esta visualización esté conectada al algoritmo genético, de manera que se pueda ver cómo los pájaros con diferentes configuraciones de pesos se desempeñan en el juego en tiempo real.

Ejemplo simple de como podría verse el juego codeado por la cátedra

Estos son algunos recursos que pueden ser útiles para el desarrollo de la interfaz:

Constantes del juego#

Se usaron las siguientes constantes en el desarrollo del juego como aparece en el video de ejemplo:

WIDTH, HEIGHT = 1000, 600 # Tamaño de la ventana
PANEL_WIDTH = 280 # Ancho del panel lateral
GAME_WIDTH = WIDTH - PANEL_WIDTH # Ancho del área de juego

FPS = 60 # Frames por segundo
MAX_TIME = 120  # 2 minutos en segundos

GRAVITY = 0.5 # Fuerza de gravedad (aumenta la velocidad vertical del pájaro por 0.5 cada frame)
FLAP_STRENGTH = -10 # Fuerza del aleteo (disminuye la velocidad vertical del pájaro por 10 cada aleteo)
PIPE_WIDTH = 70 # Ancho de las tuberías
PIPE_GAP = 200  # Tamaño del hueco inicial entre las tuberías
MIN_PIPE_GAP = 150  # Tamaño mínimo del hueco entre las tuberías
PIPE_SPEED = 6 # Velocidad de las tuberías (o velocidad horizontal del pájaro)
BIRD_SIZE = 30

Puede elegir estas variables libremente, pero se recomienda no alejarse demasiado de estos valores para evitar que el juego sea demasiado fácil o demasiado difícil.

Implementación del Algoritmo Genético#

Para implementar el algoritmo genético, se deben implementar los pasos clave mencionados anteriormente, pero pueden decidir qué otros pasos agregar para mejorar el rendimiento del algoritmo (o que pasos sacar, justificando su decisión). Antes de comenzar a implementar el algoritmo, usted consulta en el Laboratorio Organizado de Genética e Inteligencia Artificial (LOGIA) y le proporcionan las siguientes recomendaciones:

Que la población inicial sea de 100 pájaros.
Que la función de aptitud de los pájaros se base en la distancia recorrida.
Terminar forzadamente la época si su ejecución supera los 2 minutos o el pajaro supero cierto umbral de distancia. Esto evitaría que un pájaro “perfecto” deje al algoritmo trabado indefinidamente.
Que la cantidad de épocas (repeticiones/iteraciones) sea de al menos 100, pero mientras desarrolla el algoritmo, puede probar con menos épocas para chequear que todo funcione bien y acelerar el proceso.
También podría implementar un criterio de parada adicional, como por ejemplo, si mitad de la población alcanza un tiempo de vuelo mayor a un umbral predefinido o alguna aptitud determinada.
Que haga una selección de pájaros a cruzar de manera aleatoria, pero que los pájaros más aptos tengan más probabilidades de ser seleccionados.
Que el cruce se realice de manera uniforme, es decir, que cada gen del hijo provenga de uno de los padres con probabilidad del 50%.
Que la mutación se realice con una probabilidad del 10% por gen, es decir, que cada gen tenga un 10% de probabilidad de mutar.

Pero también le advierten que, si bien estos son buenos consejos, usted es libre de modificarlos y adaptarlos según su propia estrategia y conocimiento, y también evaluando cómo afectan al rendimiento del algoritmo.

Entrega#

El trabajo se realizará en grupos de no más de cuatro estudiantes. El desarrollo del trabajo se realizará en un repositorio privado de Github que debe ser compartido a los docentes de la materia (pueden encontrar los usuarios de los docentes aquí). La entrega del trabajo se realizará subiendo el link del repositorio a la tarea correspondiente en el campus del curso. La fecha de entrega se encuentra en la misma tarea y en el calendario del curso.

Se recuerda a los estudiantes que las entregas deben ser un producto original de cada estudiante, por lo que se les pide revisar la sección 6 del programa de la materia y el Código de Honor y Ética.

Evaluación#

A diferencia de los trabajos prácticos anteriores, este trabajo práctico tiene una nota numérica individual asociada. La misma será definida por los docentes de la materia y se basará en la calidad del trabajo entregado y en la defensa oral del mismo.

Para aprobar, es fundamental que el código se ejecute correctamente sin lanzar excepciones; cumpliendo con los requerimientos de la consigna. Además, se evaluará la calidad del código y la calidad de los comentarios y documentación. Cualquier detalle adicional que agreguen será tenido en cuenta para la nota final.

La defensa oral se realizará en la semana de finales de la materia. En la misma, se les pedirá a los estudiantes que presenten su trabajo y respondan preguntas sobre el mismo. La defensa oral es obligatoria y es un requisito para aprobar la materia.