Supervivencia de los más aptos; compitiendo para ser mejores: Una experiencia de aprendizaje de Algoritmos Genéticos Héctor Diez Machío
Instituto Nacional de Tecnologías de la Comunicación (INTECO). León.
Miguel V. Carriegos
Departamento de Matemáticas. Universidad de León Resumen Presentamos una experiencia didáctica llevada a cabo durante varios cursos académicos con alumnos de Ingeniería Informática de la Universidad de León. Se trata de aprender de forma directa la asignatura de Algoritmos Genéticos trabajando desde el primer día con el objetivo de diseñar un Algoritmo Genético que proporcione buenas estrategias para jugar un juego de suma cero (habitualmente el Dilema del Prisionero con estrategias de memoria 3). El paradigma de los Algoritmos Genéticos se usa para evaluar a los alumnos pues se fomenta la competencia entre ellos y el intercambio de experiencias con el objetivo de presentar los mejores programas que se evaluarán en función de la bondad de la estrategia que proponen en una sesión o Torneo de todos-contra-todos. Keywords Tecnologías de la información y la comunicación, aprendizaje colaborativo, docencia en ingenierías, metodología docente, Castilla y León. Introducción Las Leyes de la Evolución de Darwin establecen que los mejores individuos son finalmente los ganadores en el “juego de la vida” y que tienen más éxito a la hora de tener descendientes. Así, la Naturaleza proporciona más posibilidades a los individuos más aptos. Este hecho es conocido desde el siglo XIX pero no ha sido utilizado hasta la última mitad del siglo XX para diseñar procedimientos para estudiar otros problemas. Sin duda, una de las trabas principales para que no surgiera antes la posibilidad es que no se disponía de las herramientas computacionales para llevar a cabo simulaciones sobre selección natura. Los Algoritmos Genéticos (A.G.) se designan para recrear las Leyes de Evolución de Darwin con el objetivo de utilizarlas en el estudio de problemas “duros” con una gran variedad de posibles soluciones. De hecho, los A.G. sólo requieren, para su uso, una manera de representar las soluciones del problema dado y una función de aptitud que valore cada posible solución. Así, aesde el punto de vista de la Inteligencia Artificial, se encuadra a los A.G. como herramientas de inteligencia Artificial Subsimbólica. Las aplicaciones de los A.G. incluyen una gran variedad de problemas; desde el diseño de redes a la minería de datos, y desde la teoría de control a la predicción de la estructura de proteínas. Objetivos Nuestro objetivo es proponer un problema real a nuestros estudiantes para que pueda ser resuelto utilizando A.G.. De forma adicional motivamos a nuestros alumnos …. Se pide a los alumnos que resuelvan un ejercicio propuesto al comienzo del curso. El problema es encontrar una buena estrategia para jugar a un juego. Los estudiantes deben mostrar su avances en forma de presentación una o dos veces a lo largo del curso. La motivación adicional es el Torneo: Cada estrategia propuesta es evaluada de forma directa por el comportamiento que presenta al combatir en eel juego con cada una de las demás estrategias, propuestas por los restantes alumnos. Así, los estudiantes compiten todos-contra-todos y obtienen directamente el 40% de su nota directamente por sus resultados en el Torneo. Problemas propuestos La primera y quizá más importante decisión que se debe tomar antes de empezar la práctica es elegir el problema que va a ser propuesto a los alumnos. El problema es habitualmente el encontrar una buena estrategia para jugar un juego lógico. De todas formas, el problema que propongamos debe seguir las siguientes condiciones: Debe ser un problema de optimización, para así poder encontrar buenas soluciones utilizando Algoritmos Genéticos. Aunque no sea estrictamente necesario, es muy conveniente que no sea fácil encontrar soluciones al problema en cuestión utilizando otros programas o de forma deductiva. Así, los alumnos pueden valorar la utilidad de los Algoritmos Genéticos. Debe ser un problema atractivo para los estudiantes: Es más divertido encontrar buenas estrategias para jugar un juego que encontrar el máximo de una función. Debe ser fácilmente programable. Los estudiantes han de implementar el código para jugar al juego dentro de su programa. Y nosotros queremos que los estudiantes empleen el tiempo programando Algoritmos Genéticos, no otros problemas. Es muy interesante que el juego permita cambiar diferentes parámetros sin cambiar la estructura. Por ejemplo, estos parámetros podrían ser las puntuaciones obtenidas durante el juego o las condiciones iniciales. Podemos mantener en secreto estos parámetros hasta el día del Torneo. Esto nos proporciona dos beneficios, los algoritmos programados por los estudiantes van a encontrar soluciones más generales (no hiperespecializadas) y el Torneo va a generar más expectación puesto que los estudiantes no pueden saber, aunque hablen entre ellos, quién será el mejor para la elección particular y secreta de parámetros.
Un ejemplo de posible problema objetivo es el qque hemos tratado en nuestras clases: El Dilema del Prisionero Iterado con Memoria 3. Este pproblema verifica las condiciones anteriores. Además, podemos encontrar estrategias muy buenas utilizando Algoritmos Genéticos1. Por otra parte es un juego atractivo y motivador y se puede ddesarrollar en apenas 50 líneas de código. Además, podemos usar los pesos (recompensas del juego) como parámetros ocultos. Quizá el único pero que se puede poner al uso del Dilema del Prisionero es que es un juego bien conocido y que las estrategias quid-pro-quo obtienen generalmente muy buenos resultados. Obteniendo soluciones Durante la primera clase práctica el juego seleccionado es explicado a los alumnos. Después de esto los alumnos pueden empezar a programar (el juego), aunque no conozcan nada de Algoritmos Genéticos. Como codificar el juego no es parte de los objetivos, podemos incluso proporcionar un pseudocódigo para hacer la tarea más fácil.
En la primera sesión teórica se expone la estructura básica de los Algoritmos Genéticos y de los operadores genéticos fundamentales (selección, cruzamiento y mutación). Así, los alumnos pueden empezar rápidamente con la parte principal de sus programas Durante las siguientes sesiones prácticas los estudiantes seguirán desarrollando sus programas, planteando cuestiones, mostrando sus avances etc. Se les deja libertad para elegir el lenguaje de programación y su propio ritmo de trabajo. La única condición es que el programa que elaboren debe compilar y ejecutarse bajo Linux en los ordenadores del laboratorio. Esto no es muy restrictivo, pues habrá disponibles muchos compiladores: C, C++, Java, Pascal, Pitón, Ruby, Perl, etc. A mitad de curso se pide una exposición de los Trabajos de los estudiantes que, en este momento, deben verificar varias condiciones: El programa debe contener un Algoritmo Genético básico que proporcione una solución al problema propuesto (no importa, en este momento, si la solución es buena o incluso si es “competitiva”). Un requerimiento muy importante desde el punto de vista de la gestión de las prácticas es que los outputs de los programas de los alumnos deben ser archivos en un formato muy rígido. De esta forma sse puede proceder a la evaluación automática en el Torneo sin necesidad de modificaciones. Estos requerimientos deben ser observados en este momento, a mitad de curso. Durante el resto del curso los alumnos pueden dedicar su tiempo a trabajar aspectos del Algoritmo Genético y a refinarlo con mejoras que están siendo presentadas en las clases teóricas. Cuando acaba el curso, los alumnos deben eentregar el código fuente de sus programas, además de una d¡documentación; que debe contener un resumen del Algoritmo Genético que han diseñado, sus parámetros y todas las decisiones importantes que han tomado durante las prácticas. Antes de evaluar esta parte (código y documentación) se comprueba que, efectivamente los programas verifican todas las especificaciones. El Torneo El output de cada programa entregado por los alumnos (y el candidato con el que competirá ; su campeón en el torneo) es un archivo de texto plano que contiene el cromosoma final con la estrategia codificada. Es necesario, por lo tanto ejecutar los programas de todos los alumnos para generar los cromosomas con los que competirán en el Torneo. Este proceso lento y repetitivo se efectúa de un modo automático gracias a las restricciones impuestas a los programas que han de entregar los alumnos. El programa que lo lleva a cabo obtiene los campeones en un proceso de varias horas compilando cada programa de los alumnos y escribiendo el campeón efectivo en un archivo seleccionado. Cuando acaba (usualmente efectúa el trabajo algún día antes del Torneo), tenemos una lista con todos los alumnos y sus campeones obtenidos efectivamente de los programas proporcionados. Ahora el Torneo consiste en enfrentar las estrategias dos a dos y sumar todos los puntos obtenidos de estos enfrentamientos. Obviamente se deben efectuar n(n-1)/2 enfrentamientos, donde n es el número de alumnos. Esto lleva pocos minutos y se efectúa con la utilidad Genetic Unreal Tournement, licenciado como software libre bajo GNU Project y que se puede obtener de forma gratuita en http://matemat icas .un i l eon .e s/GUT La función principal de este programa consiste en leer todos los archivos que contienen las estrategias de los alumnos y hacer que compitan entre sí guardando los resultados. El programa devuelve código HTML con gráficos y demás componentes visuales para mejor explicación de los resultados. Todos los alumnos son convocados el día del Torneo, se compila GUT y se ejecuta con el directorio donde está la lista de campeones carticulares de cada alumno. Los alumnos pueden seguir todo el proceso a través de un proyector y comprobar inmediamente sus resultados a través de la red del laboratorio. Conclusiones Las experiencias que hemos tenido a lo largo de varios años en que hemos planteado el Torneo a alumnos de 4º de Ingeniería Informática en la Universidad de León son muy positivas. Es usual que los alumnos se tomen el Torneo como un reto personal. Además, la fuerte vinculación de la nota final frente a la estricta competencia con sus compañeros no provoca en general recelos entre ellos; más bien parecen aprender pronto que la cooperación es la estrategia ganadora en los juegos de suma cero.
Una encuesta hecha a 29 alumnos mostró su satisfacción general con la asignatura. Más aún, preguntados sobre si les gustaría volver a participar en el futuro (si tuvieran tiempo para hacerlo, y sin ninguna calificación en juego), 21 de los 29 respondieron afirmativamente.
Nota final La experiencia que se detalla en este artículo fue presentada (ver [1]) en el 8th. Internacional Symposium on Computers in Education, 2006. Bibliografía H. Diez-Machío, M. Carriegos. Genetic Unreal Tournament: A toolkit to improve genetic algorithms learning. Proceedings of the 8th. International Symposium on Computers in Education, vol 1. (2006) pp. 304-308. ISBN: 84-9773-301-0. A. Kuri: A solution to the Prisoners Dilemma using an Ecectic Genetic Algorithm. Centro de Investigación en Computación,
21. Serie Roja (1998). A. Kuri, J. Gutiérrez:: The Best Evolutionary Solution to the Iterated Prisoner’s Dilemma. International Congress CIC 2000
(2000), 114-119. M. Mitchell: An Introduction to Genetic Algorithms. MIT Press (1996).
|
