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."