Translate this page

viernes, 2 de enero de 2015

Algoritmos genéticos: resolución de problemas y vida artificial (evolución y algoritmos, parte 2)


¿Puede el mecanismo de la evolución biológica ser reproducido de manera artificial para nuestro beneficio?

En la entrada anterior veíamos que la evolución biológica puede concebirse como un proceso algorítmico en el que el azar de las mutaciones se convierte en complejidad organizada a través de la selección natural. Veremos ahora cómo este algoritmo puede ser ejecutado en programas de ordenador y robots, como forma de dar a estas entidades artificiales capacidades de aprendizaje y resolución de problemas complejos.


Computación evolutiva: algoritmos genéticos


Como vimos en la entrada anterior, ya en 1932 se propuso la idea de que la evolución operaba como un sistema que buscaba los máximos en un 'paisaje adaptativo', y por tanto podía concebirse como un proceso de optimización.


A partir de los años 60 surge el concepto de computación evolutiva. Aprovechando el desarrollo de los primeros ordenadores prácticos, se trató de simular en ellos los mecanismos evolutivos para:
  • Simular el funcionamiento de la evolución y comprobar hipótesis teóricas, por ejemplo de estadística de poblaciones
  • Intentar resolver problemas de optimización fuera del ámbito de la biología (luego veremos varios ejemplos)
La técnica de computación evolutiva más conocida son los algoritmos genéticos. Sus elementos principales son una réplica informática de los elementos que actúan en la evolución biológica:


  • Una forma de representar cada posible solución del problema utilizando una lista de valores numéricos. Esta lista de valores hace el papel del genotipo, de los cromosomas o genes de un individuo que va a evolucionar, pero en lugar de estar escrito en el código genético del ADN está formado por una lista de números que representa una posible solución. Por ejemplo, si se trata de representar la forma de una figura articulada, estos números del genotipo pueden representar los tamaños, posiciones, movimientos, etc. de las diferentes partes de la figura.


  • Dispondremos en cada paso de tiempo (t) de una población de individuos P(t), cada uno con su propio genotipo.


  • Cada individuo o posible solución podrá ser evaluado para obtener un valor numérico de su adaptación o fitness. Por ejemplo, si estamos buscando el diseño de un robot que camine o nade, su adaptación será más alta cuanto menos tiempo necesite para llegar de un sitio a otro, menos energía consuma, etc.


  • Los individuos que tengan un nivel más alto de adaptación son los que se reproducirán para crear individuos de la siguiente generación. Este mecanismo simula la selección natural o artificial.

  • Los descendientes que aparecen en la siguiente generación se forman mediante el cruce de los genotipos de sus 'padres', simulando la reproducción sexual. Es decir, su genotipo se construirá tomando trozos de los genotipos de cada progenitor y uniéndolos. De esta manera, una mejora parcial en un progenitor puede combinarse con otra mejora parcial en un lugar diferente del genotipo de otro progenitor para producir una descendencia con mayor adaptación aún.


  • Además, el genotipo de cada nuevo individuo puede sufrir mutaciones que simulan los errores de transcripción genética que se producen de forma natural. Para generar una mutación no hay más que cambiar al azar alguno de los valores que forman el genotipo del individuo.


  • Por último, un mecanismo de control se encarga de generar una población inicial con genotipos al azar y repetir los mecanismos anteriores hasta que se consiga uno o más individuos con el grado de adaptación deseado, es decir, que sean buenas soluciones al problema de optimización planteado.
El siguiente pseudocódigo resume el proceso:


Aquí tenéis una explicación excelente (en inglés), parte de los cursos gratuitos del MIT:


Y aquí una presentación sencilla en español, con un ejemplo de cálculo de rutas:


También podéis encontrar un curso gratuito en Web.

Resolviendo problemas


Una primera utilidad de los algoritmos genéticos no tiene a primera vista nada que ver con la evolución, sino con la necesidad de buscar una solución para problemas que son intratables mediante métodos matemáticos clásicos, como algunos problemas de optimización

Como vimos en la entrada anterior, la evolución puede verse como un sistema de búsqueda de aquellas combinaciones genéticas que producen fenotipos óptimos (con mayor grado de aptitud). Los algoritmos genéticos pueden utilizarse para resolver problemas en los que existe un número grandísimo de posibles soluciones repartidas en un enorme espacio de búsqueda. Pueden verse, por tanto, como una variante de los métodos numéricos de 'hill climbing' o búsqueda de puntos máximos.


Un algoritmo genético puede encontrar muchas posibles soluciones (genotipos) más o menos óptimos que irán mejorando con el número de iteraciones o ciclos del algoritmo, aunque no tenemos garantizado que se llegue a encontrar la mejor solución posible (máximo global), ya que ésta podría encontrarse en la 'cima' de una 'montaña' aislada o de difícil acceso.


Un ejemplo sencillo de problema de optimización es el que consiste en aproximar una imagen compleja mediante elementos sencillos como círculos. No es que sea algo especialmente útil, pero sirve para demostrar que a partir de un proceso aparentemente azaroso podemos solucionar un problema que es inabordable mediante métodos matemáticos clásicos (ecuaciones, etc.).

En los dos videos siguientes vemos cómo la aproximación con un número constante de círculos va mejorando a medida que progresan las generaciones del algoritmo genético:




En el siguiente vídeo los algoritmos genéticos son utilizados para buscar soluciones novedosas al diseño de turbinas. Un aspecto interesante de estos métodos (y veremos más adelante algunos ejemplos con criaturas artificiales) es que los resultados son muchas veces inesperados, con soluciones que a nadie le hubieran parecido interesantes a priori pero que resultan ser prácticas.


Otro problema de optimización complejo es el diseño de estructuras de soporte en arquitectura. Aunque sabemos estudiar las propiedades físicas de estructuras ya diseñadas, no sabemos resolver de forma matemática el problema inverso: diseñar nuevas estructuras que sean óptimas.


En el siguiente ejemplo tenemos unas criaturas acuáticas simplificadas que tienen que evolucionar para optimizar la cantidad de comida a recoger (los cuadraditos verdes).


Aprendizaje automático


Podemos ver a partir del ejemplo anterior que los algoritmos genéticos funcionan también como un método de aprendizaje automático. A medida que avanzan las generaciones y se produce la selección de las mejores soluciones, el sistema aprende a resolver una tarea de manera más eficiente.

Tenemos aquí el ejemplo de un sencillo vehículo que aprender a conducirse de forma eficiente en un circuito con pendientes:

Y en este otro unas estructuras articuladas que aprenden a ponerse de pie 'ellas solas' mediante un algoritmo genético:


En este caso se trata de aprender a saltar de forma adecuada para evitar una bola. Como siempre vemos la evolución de más generaciones va produciendo una mejora u optimización progresiva.


¿Problemas con las prácticas del carnet de conducir? No pasa nada. Algún día los coches conducirán por ti:


En este capítulo de Redes, Eduard Punset entrevista a Alan Winfield, especialista en robótica colectiva, hablando del aprendizaje de los robots y la relación con el concepto que cultura, una discusión que abordaremos en la entrada siguiente:


Criaturas virtuales


De los ejemplos anteriores resulta inmediato pensar que podemos utilizar algoritmos genéticos para simular la evolución de criaturas virtuales que aprendan a desenvolverse en un entorno simulado. Dicho de otra forma, podemos replicar la evolución en un entorno virtual.

A principios de los 90, William Latham desarrolló lo que llamó Arte Orgánico, utilizando algoritmos genéticos para modelar la evolución espontánea de seres artificiales de apariencia orgánica utilizando sistemas pioneros de animación 3D:


Aquí tenemos a Latham explicando su técnica en una conferencia:


Prácticamente al mismo tiempo, Karl Sims desarrolló técnicas que combinaban redes neuronales artificiales y algoritmos genéticos en su sistema Evolved Virtual Creatures.

Juntando formas muy sencillas de maneras aleatorias, el software de Karl Sims era capaz de hacerles evolucionar para que se movieran sobre el suelo o nadaran, descubriendo formas inesperadas de locomoción. Podemos ver algunos ejemplos de las animaciones originales de Sims en esta conferencia de Daniel Dennett titulada precisamente "¿Es la evolución un proceso algorítmico?":


En esta otra conferencia vemos ejemplos de cómo pueden evolucionar conductas de lucha por un objeto (que puede representar comida, por ejemplo) o de emparejamiento. En esta conferencia además es interesante la última parte, donde se explica cómo los algoritmos evolutivos generan complejidad o entropía negativa. Pero de eso intentaré hablar en otra entrada.


Una versión más reciente del software de Karl Sims es el 3DVCE, que puede descargarse aquí. En el siguiente vídeo podemos ver ejemplos de sus resultados:


Más ejemplos de programas similares:


Como he comentado, un aspecto interesante de estos sistemas de aprendizaje es que pueden descubrir soluciones inesperadas. ¿A quién se le hubiera ocurrido desplazarse de esta manera?


El siguiente paso sería que el algoritmo evolutivo no solamente pueda optimizar la forma de mover una estructura determinada, sino también ir cambiando los elementos que la componen y sus articulaciones:


Como uno puede ver observando en el mundo real a un animal recién nacido que intenta andar o mantenerse en pie al nacer, no es trivial realizar estas tareas. Requieren un sistema de control muy sofisticado y un proceso de aprendizaje que puede durar minutos o meses (nuestro caso).

Los algoritmos genéticos, muchas veces en combinación con redes neuronales simuladas, se han utilizado para estudiar estos procesos aparentemente sencillos pero que requieren un aprendizaje por prueba y error. Mediante estas técnicas, las criaturas artificiales puede aprender lo que nosotros hacemos de forma inconsciente:



Incluso parece que es posible aprender virtualmente a columpiarse:



Robots que evolucionan


Las técnicas anteriores de evolución y aprendizaje en criaturas virtuales pueden aplicarse también a seres físicos. Concretamente, se utilizan para que los robots puedan aprender a moverse, conducir y realizar otras tareas, en lo que se ha denominado Robótica Evolutiva.

Como hemos visto en el caso de las criaturas virtuales, se suelen combinar dos métodos de aprendizaje automático: los algoritmos genéticos y las redes neuronales artificiales. El segundo método sirve sobre todo para aprender la parte perceptiva y de control motor.


Aquí tenemos una versión española de la araña robótica más común de cuatro patas, y podemos ver cómo probando diferentes movimientos va poco a poco aprendiendo a controlar su desplazamiento:


Esta versión más sofisticada, de seis patas, ha aprendido a mantenerse estable en diferentes situaciones:


Esta tecnología puede desarrollarse hasta conseguir resultados tan espeluznantes como los de la empresa Boston Dynamics, recientemente adquirida por Google.


Vida artificial


Combinando la aportación de los algoritmos genéticos al software y el hardware de las criaturas artificiales, podemos considerarlos como una herramienta esencial para el desarrollo de la vida artificial no biológica, en dos sentidos:
  • Como método de aprendizaje automático, los algoritmos genéticos son una forma para que las criaturas artificiales se entrenen y desarrollen adaptaciones individuales al entorno real o virtual en el que 'viven'.
  • Como mecanismo de evolución, permiten que sucesivas generaciones de las formas de vida artificial vayan mejorando y diversificándose.



En la evolución biológica, en contra de las teorías pre-darwinianas de Lamarck, las adaptaciones que los individuos consiguen durante sus vidas NO se transmiten a su descendencia. Sin embargo, en una criatura artificial nada nos impide combinar los dos elementos anteriores, aprendizaje individual y mejora de una generación a otra.


El sueño de Lamarck podría por tanto cumplirse para las criaturas artificiales: los caracteres adquiridos por una criatura artificial SI podrían transmitirse a su descendencia, lo que haría que la evolución de estas criaturas fuera mucho más rápida que la evolución biológica. 

Quizás algún día no muy lejano llegaremos a ver compañeros robóticos tan evolucionados como éste:


Pero de momento su comportamiento no es el resultado de un proceso de aprendizaje y evolución automática, sino de la mente calenturienta de un humano:



Para evolución artificial ultrarrápida, este impresionante anuncio de Saturn:


Otras aplicaciones


¿Para qué querríamos criaturas artificiales que evolucionen solas? En la Tierra ciertamente podrían ser un peligro, pero podrían constituir una herramienta poderosa para la conquista del cosmos, sobre todo si pudieran replicarse para transformar un planeta o asteroide inhabitable en un mundo apto para los humanos.


Es la idea de las sondas autorreplicantes, que propuso inicialmente el famoso matemático John Von Neumann. El problema sería cómo controlar posteriormente a estas criaturas evolucionadas, si se convirtieran en una amenaza para nosotros. 


Una aplicación muy curiosa y útil que me ha sorprendido es la de encontrar y arreglar errores en programas de ordenador. Si los algoritmos genéticos pueden resolver este problema, ¡desde luego demostrarán su utilidad! (mi entusiasmo no tiene que ver con el hecho de que me dedique a desarrollar software, ja, ja).


Y como sucede con otros métodos algorítmicos, siempre parece haber alguien que los encuentra útiles para producir música de forma automática:




Vemos que el campo para la aplicación de algoritmos evolutivos es muy amplío.

Cabe preguntarse ahora si además de los seres vivos, las criaturas virtuales y los robots, también las ideas y productos de la cultura humana evolucionan de la misma forma. ¿En qué consiste exactamente la llamada 'evolución cultural'? Hablaré de ello en la próxima entrada.

Hasta entonces,

    Salvador




1 comentario: