5.3 Programación genética y arte genético Ahora hablemos de un aceramiento un poco diferente a algoritmos genéticos llamado programación genética, que fue desarrollado por John Koza en los 90 En la programación genética, en vez de usar cadenas de números, como hicimos con Robbie el Robot se usan programas representados como árboles sintácticos eso lo explicaré en un momento Esta es una foto de John Koza, dando una conferencia sobre programación genética El ha escrito uno, dos, tres libros sobre este tema se ha vuelto una sub-área muy importante del campo de algoritmos genéticos Entonces, esta es la idea Otra vez, concideremos el problema de Robbie el Robot, y desarrollemos una estrategia de control para él Aquí, en vez de representar su estrategia de control como una cadena de numeros que representan acciones en cada situacion posible, aquí representaremos la estrategia de control como un tipo de árbol. Esto es lo que en las ciencias de la computación se llama un árbol donde tenemos los elementos de un programa representados en términos de nodos y ramas Entonces, este programa particular, es una declaracion "si..entonces...", acá en la raiz y se lee: "si (esta es la condición a considerar), si hay una lata en el Este y el Norte está vacío entonces, el robot se debe mover al Este o, de otro modo, el robot se debe mover al Sur" Esto es lo que este árbol representa, y se le puede ver como un programa común y corriente: Si el Este=lata y el Norte=vacio, entonces debe moverse al Este, en otro caso al Sur Ahora, supongamos que Robbie está en esta situación: y esta es su estrategia, esto es lo que él haria: Él miraría esta condición de "si" y diria "¿hay una lata hacia mi Este y está vacio hacia mi Norte?" Bueno, hay una lata al Este y el Norte está vacio, entonces siguiría esta primera rama: Se movería al Este...Allí va. Bien, ahora, está en una nueva situación Entonces, otra vez sigue esta estrategia Dice: "¿Hay una lata hacia mi Este y está vacio hacia mi Norte?" No. Entonces, sigue la segunda rama para moverse hacia el Sur Y lo vuelve a hacer: No hay una lata hacia el Este y el Norte está ocupado Entonces, se mueve al Sur. Así, esta no es una estrategia muy buena, pero esto es lo que hay para que él la siga Es una representación diferente a la que vimos antes Obviamente, este árbol es muy simple para ser una buena estrategia porque no inlcuye el recojer alguna lata. Consideremos esta estrategia más complicada, que está representada como un árbol más largo, Esto se está volviendo más difícil de entender, pero podemos hacer que Robbie siga esta estrategia. Bien, aquí está y dice: "si mi Norte está vacio y hay una lata hacia mi Este,... Bueno, esto es verdad, entonces, sigo la primera rama" Pero, ahora, esta rama tiene otra declaración "si" Miren esto... Si ambas cosas son verdad: no hay una lata hacia mi Oeste y hay una lata hacia mi Este, entonces Así, esto es verdad. Entonces, seguimos la primera rama de esto Se mueve hacia el Este. Allí está Ahora, estamos en una nueva situación ...Empezamos acá arriba, Decimos: ¿el Norte está desocupado? y... ¿hay una lata al Este? No. Entonces, nos vamos acá, a la última rama y decimos, "si hay una lata en el lugar donde estamos", Sí la hay, entonces recogemos la lata... él lo hace Bien, ahora está en la situación en la que esta condición falla (no es verdad). Entonces vamos aca. No hay una lata donde estamos Entonces, se tiene que mover al Sur. Espero que se entienda la idea de que esto es solamente una forma diferente de expresar una estrategia. Es dificil encontrar un árbol que sea una buena estrategia, pero ese va a ser el trabajo para el algoritmo genético. La única diferencia con lo que hicimos antes es que el algoritmo genético va a evolucionar estos árboles, en vez de las cadenas de números Entonces, funciona de este modo: La población inicial, en vez de cadenas al azar van a ser árboles al azar con algunas restriciones sintácticas Por ejemplo, necesitamos un "Si...Entonces" en la raiz del árbol y algunas otras resticciones. No voy a hablar de los detalles de eso aquí, sólo quiero que tengan una idea general Para calcular la aptitud, es el mismo procedimiento Tenemos a Robbie probando cada una de las estrategias, en diversos escenarios; Calculamos el promedio del puntaje para cada estrategia y, entonces, obtenemos los individuos más aptos, que tienen más descendientes que los menos aptos Eso implementa al operador de "selección". Para realizar la "cruza", a fin de producir hijos, en vez de intercambiar partes de cadenas intercambiamos secciones de árboles. Así, aquí tenemos un ejemplo. Hay dos posibles padres: dos árboles y podemos crear un hijo al tomar una sección de árbol del segundo padre y ponerlo acá Reemplazando al nodo "Mover al Este" Debemos poner esta sección del árbol allá para crear un hijo Que se ve como esto Entonces, aquí está exáctamente lo mismo que el primer padre excepto que el bloque "mover al este" es reemplazado por este otro... bloque "Si...Entonces" Se mantiene como un árbol sintácticamente correcto y se mantiene como estrategia Y esta es la forma como el algoritmo genético es capaz de tomar partes de padres áptos y recombinarlos La mutación comienza cambiando la elección aleatoria de un valor y su reemplazo por otro valor aleatorio por el reemplazo de una sección de árbol por una sección de árbol generada en forma aleatoria Hagámoslo aquí Esta sección de árbol aquí la reemplazo por alguna sección de árbol generada aleatoriamente No implemeté una versión con programación genética para Robby Es algo que a los programadores más avanzados entre ustedes puede interesar Pero sí les puedo hablar sobre un proyecto real con programación genética De hecho, sobre dos de ellos que son muy interesantes El primero es la applicación de la progaramación genética a los gráficos por computadora Esto ha sido desarrollado por mucha gente pero el ejemplo más famoso es el realizado por Karl Sims --Aquí está-- en los 90 El es un artista de los gráficos por computadora y decidió evolucionar programas para producir gráficos por computadora que son estéticamente placenteros Entonces, he aquí cómo funcionan: Los individuos en la población son árboles como los que les mostré excepto que aquí no reprsentan estrategias para un robot virtual, representan ecuaciones que generan un color para cada pixel en una imagen Bien, estos son sólo algunos ejemplos y estos son algunos programas No puedo explicarles cómo trabajan Pueden leer el artículo de Karl Sims, si están interesados Pero podemos seguir con la idea de que podemos representar estos programas como árboles Y cada programa genera un color para cada pixel en la imagen Bien, pueden imaginar la generación de un montón de programas aleatorios que colorean aleatoriamente los pixeles en la imagen La pregunta es ¿cómo definir la función de aptitud? Esto es, ¿cómo definir la aptitud sobre una pintura en particular? Bueno, ahora mismo esto es algo que está fuera del alcance de las computadoras --no lo hacen bien-- Entonces, Karl Sims tuvo que incluir a los humanos: Lo que él hizo fue tomar a algunos humanos como ejemplo y hacer que observaran las pinturas que generó la computadora -- pInturas aleatorias-- y que eligieran la que consideraban la mejor y, entonces, esa sería elegida como padre y cruzada con otros programas aleatorios y mutada para producir nuevos programas que producirían nuevas imágenes que estarían relacionadas con aquella que se eligió Esto se repite, una y otra vez, y el algoritmo genético generará muy bonitos resultados Esto es un jemplo Aquí hay una pintura y aquí el programa que la creó Entonces esto es una colaboración, en cierto sentido, entre el algorítmo genético y el humano donde el humano no se encuentra en el programa pero expresa lo que le gusta y, entonces, el algoritmo genético va y evoluciona ese programa aún más Este es otro ejemplo y otro Aquí hay uno particularmente hermoso Muy parecido a algunas pinturas japonesas, me parece otra y, así, por el estilo Aquí están dos direcciones URLS, a las que tambien pueden ir La primera es el sitio web de Karl Sims donde se encuentran todas estas pinturas y comentarios sobre un montón de proyectos diferentes La segunda es una aplicación que les da la oportunidad de evolucionar esta clase de pinturas por ustedes mismos Una cosa realmente interesante que hizo Karl Sims, en adición a lo que acabo de describir, es instalar una exhibición de museo Esta estuvo en el Centro George Pompidou, en París, donde tenemos una secuencia de monitores --que pueden ver-- cada uno mostrando una pintura diferente del tipo que se pueden observar Y aquí abajo, en el piso, hay sensores Y las personas en la exhibición pueden ir y pararse sobre los sensores si a ellos les gusta una pintura en particular y esa pintura es elegida y, entonces, es evolucionada por el algoritmo genético quizá mezclándola con las otras pinturas elegidas Así, de esta manera, no se trata de una sola persona sino de un grupo completo de personas que trabajan, en cierto sentido, y en conjunto juegan el papel del algoritmo de selección para el algoritmo genético Karl Sims dice al respecto que "Los visitantes de esta exhibición pueden observar el progreso de una evolución simulada por computadora: una evolución de imágenes. Sin embargo, en esta evolución los visitantes no son únicamente observadores: ellos son la causa de la evolución y dirigen su curso." Y sigue: "Una población de imágenes es desplegada por la computadora en un conjunto de 16 pantallas de video. Los visitantes determinan cuáles imágenes sobreviven al pararse en los sensores enfrente de aquellas que consideran las más interesantes y estéticas. Las pinturas que no son seleccionadas son removidas y reemplazadas por las crias de las imágenes osbrevivientes. Las nuevas imágenes son copias y recombinaciones de sus padres, pero con diversas alteraciones. Esta es una evolución artificial en la que los mismos visitantes determinan, en forma interactiva, la 'aptitud' de la pintura al elegir aquella en la que se paran. Conforme este ciclo continúa, la población de imágenes puede progresar hacia más y más interesantes efectos visuales." "Esta instalación interactiva es una colaboración inusual entre humanos y las máquinas: Los humanos proporcionan desiciones con estética visual y la computadora proporciona la habilidad matemática para generar, componer y mutar texturas complejas y patrones. Los visitantes no necesitan entender los tecnicismos ni ecuaciones involucradas. Las computadoras sólo pueden experimentar aleatoriamente sin sentido de la estética --pero la combinación del humano con las habilidades de la máquina permiten la creación de resultados que ninguno de los dos podría obtener por sí solo."