| Artículos | 01 NOV 1997

Aplicación de la programación genética

Tags: Histórico
Eloy Anguiano.

En meses anteriores le he dedicado este espacio a la presentación de un determinado tipo de procesos denominados algoritmos genéticos. En particular, en el artículo del mes pasado vimos cómo era posible desarrollar programas que resolviesen un problema a través de la selección, cruces y evolución genética. En este caso lo que vamos a ver es un ejemplo muy conocido de aplicación de estos algoritmos.

En general, el problema esencial de la animación cinematográfica de objetos diseñados por ordenador consiste en la dificultad de, calculando cada uno de los fotogramas necesarios para la animación, conseguir un movimiento realista. Muchas veces, este trabajo es altamente dificultoso y depende básicamente de la habilidad del animador. El caso que voy a presentar este mes es un algoritmo genético desarrollado por L. Gritz y J.K. Kahn para la compañía Pixar.

El problema que pretendían resolver era el siguiente: dada un posición inicial y una posición final de una lámpara de mesa articulada, encontrar un programa que sea capaz de calcular la posición de cada uno de los elementos de la lámpara en un instante determinado. Este programa debería de ser capaz de, además de mover la lámpara entre ambas posiciones, hacerlo de forma que el movimiento sea visualmente lo más natural posible y además rápido y efectivo.

Gritz y Kahn pretendieron abordar este problema, utilizando la programación genética para encontrar este algoritmo capaz de resolver el problema con las condiciones especificadas. Los detalles sobre las condiciones utilizadas para encontrar este programa de forma genética son las que vamos a describir a continuación.

El primer elemento a determinar cuando se está diseñando un algoritmo genético son las variables que pueden intervenir en el resultado. En este caso las variables del movimiento a las que el algoritmo tiene acceso son su posición relativa respecto a la posición final, su velocidad y la fuerza que realiza la lámpara sobre el suelo para llevar a cabo su movimiento. Además de estas variables, las masas y momentos de inercia de cada uno de los elementos móviles de la lámpara son conocidos a priori.

El segundo elemento es la colección de operaciones básicas, que en este caso es tan simple como que sólo son necesarias las siguientes {+,-,*,%,ifltz}. Las tres primeras son la suma, la resta y la multiplicación; la cuarta es la división protegida, que es básicamente la normal, pero de tal forma que si el denominador es nulo entonces el resultado de la división es la unidad; y la última función es la función "if less than zero" (si menor que cero) que tiene tres parámetros, el que se compara con cero, el que se realiza si es menor que cero y el que se realiza en caso contrario.

El tercer elemento es la definición de las cantidades que van a determinar si el programa es bueno o no lo es. En este caso, estas cantidades son de dos tipos, el primer tipo es el que evalúa la distancia entre la posición final obtenida y la deseada que es la variable que calcula la distancia propiamente dicha. El resto son añadidos de estilo que son los siguientes: prima si el movimiento se realiza de forma rápida; prima si la posición final es la posición de reposo; penalización si toca con la cabeza el suelo (es decir, se ha caído y ha ido reptando); penalización si después de llegar a la posición final se sigue moviendo. Uno de los primeros resultados que obtuvieron fue que la evaluación de distancia al objetivo era una cualidad demasiado rigurosa que no permitía que los individuos mejorasen su comportamiento, con lo que hubo que restringir su aplicación sólo a las primeras generaciones como eliminador de comportamientos aberrantes y de tal forma que los evaluadores de estilo se iban introduciendo poco a poco, generación a generación.

El efecto de realizar el proceso de la forma descrita anteriormente es el siguiente: primero, la lámpara aprende cómo llegar al lugar deseado independientemente de cuál sea su estado final; una vez que se encuentran bastantes individuos que "saben" llegar al final, entonces se hace necesario que aprenda de forma más "fina", es decir debe de introducirse el primer criterio de estilo con el fin de que sea capaz de aprender a hacer un movimiento efectivo (que no se dedique a deambular hasta que llega a su destino). El siguiente criterio a introducir es que no se caiga y así hasta que se han introducido todos los criterios de estilo. El cuarto elemento a determinar en un algoritmo genético es el número de individuos, el número de generaciones y el método de evolución generacional seleccionado. Estos autores utilizaron sólo 50 generaciones con 250 individuos. El porcentaje de individuos inalterados era del 10% y el 90% restante eran el resultado de los cruces entre los individuos de la generación precedente. No utilizaron ningún tipo de mutación pues descubrieron que era irrelevante su existencia para el resultado final.

El resultado obtenido es un programa que produce un movimiento a saltos que hace que la lámpara llegue al punto deseado y se pare (como era de esperar). Este movimiento es, por añadidura suave, realista físicamente, eficiente y con una apariencia sorprendentemente orgánica.

El programa obtenido se presenta en notación polaca inversa en las siguientes líneas:

Fx = (-(ifltz a0 pz a2)(% a1 t))

Fy = (-(-(ifltz a0 pz a2)(% a1 t)) (ifltz

(+ a2 15.4963) (ifltz a0 pz a2)

(% a1 a2)))(ifltz (% (- s0 vx)

(+ a2 s0))(% (- s0 vx)(+ a2 s0))

(+ (- a1 a1)(-a1 t)))(% a0 pz)

(% pz a0))))

Fz = (- (ifltz s0 (ifltz (- (% vx a0)

(% vx vx))(-(% vx a0)(-

(+ -28.4382 t) (% a1 t)))

( * 16.5266 s0)) vz)(+ a1 vz)))

Las variables que aparecen en estas fórmulas son las correspondientes a los valores de los sensores de ángulo, fuerza, posición y velocidad. Otro de los resultados sorprendentes es que si se presenta el movimiento de los mejores individuos a lo largo de las distintas generaciones, se tiene la impresión de que existe realmente un aprendizaje por parte de la lámpara para ser capaz de moverse entre un punto y otro. Estos autores consiguieron también, por un proceso similar, que la lámpara pasase por debajo de una barra sujeta entre dos postes sin tirarla y que un brazo humano simulado tocase un punto cualquiera del espacio, incluida su propia nariz. Estos resultados fueron convertidos en una serie de animaciones que, probablemente, muchos de ustedes hayan podido ver en televisión.

Bibliografía

- D.E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, 1989.

- J.H. Holland. Adaptation in Natural and Artificial Systems. Bradford/MIT Press, 1992.

- J.H. Koza. Genetic Programming. Bradford/MIT Press, 1992.

- J.H. Koza. Genetic Programming II. Bradford/MIT Press, 1994.

Eloy.Anguiano@ii.uam.es

Contenidos recomendados...

Comentar
Para comentar, es necesario iniciar sesión
Se muestran 0 comentarios
X

Uso de cookies

Esta web utiliza cookies técnicas, de personalización y análisis, propias y de terceros, para facilitarle la navegación de forma anónima y analizar estadísticas del uso de la web. Consideramos que si continúa navegando, acepta su uso. Obtener más información