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

El algoritmo de la vida: genes, memes y evolución cultural (parte 1)

¿Cómo es posible que la organización y la complejidad propia de la vida se haya generado espontáneamente? ¿Puede el mismo mecanismo de evolución replicarse en otros ámbitos, o es específico de la biología?

Para abordar estas preguntas, a lo largo de varias entradas, vamos a recurrir a la idea de que la evolución es en realidad un proceso algorítmico, o mejor dicho, el resultado de un proceso algorítmico cuyas características explican los fenómenos evolutivos.

La evolución como algoritmo

Un algoritmo es una secuencia de instrucciones o reglas que describen de forma inequívoca un procedimiento para realizar una tarea.

Los algoritmos frecuentemente se implementan o ponen en práctica en programas informáticos que traducen las instrucciones a un lenguaje comprensible por el ordenador, sin embargo cualquier procedimiento inequívoco formado por etapas ordenadas y relacionadas puede considerarse un algoritmo (por ejemplo, un proceso de compra de suministros en la administración pública o las reglas de enjuiciamiento criminal), y es representable en forma de diagrama de flujo o diagrama de proceso:

Un algoritmo no tiene por qué ser determinista. Una instrucción puede decir "haz esto o aquello", o "elige entre A y B con una probabilidad X para A y una probabilidad Y para B". De esta manera se pueden formalizar y simular fenómenos naturales como el crecimiento de las plantas, la erosión del terreno, las olas, etc.

¿Qué proceso produce la evolución biológica? Charles Darwin y Alfred Russel Wallace coincidieron en que la evolución de las especies se produce al seleccionarse de forma natural ciertas variaciones que se propagan de una generación a otra por reproducción, de manera que los más aptos para la supervivencia se reproducen y pasan a su descendencia las características seleccionadas.

La teoría de Darwin y Wallace, más tarde comprobada de múltiples formas, tenía un gran mérito dado que en su tiempo se desconocía el mecanismo de la herencia genética, aunque sabían que había alguna forma de heredar características de un organismo a otro.

El excelente y divertido divulgador científico Bill Nye explica en este vídeo la idea central de la evolución por selección natural utilizando emojis:

¿Podemos considerar la selección natural como un algoritmo? Esta es la visión de autores como el filósofo Daniel Dennett y el biólogo evolutivo Richard Dawkins, y se ha visto reforzada como veremos por la implementación de este tipo de algoritmo en programas informáticos y sistemas físicos que aprenden, como los robots autónomos.

Dennett y Dawkins explican en sus obras como la forma en que opera la selección natural como proceso causal es suficiente para explicar las complejas características que observamos en los seres vivos, incluidos los humanos.

Dennett (y otros autores posteriormente) dan explicaciones basadas en la selección natural incluso para fenómenos como el libre albedrío y la consciencia. La idea de la evolución por selección natural sería así la 'gran unificadora' que permite concebir la relación causal entre el mundo físico, el mundo de la vida y el mundo de la consciencia y la intencionalidad:

La idea de la evolución como algoritmo se basa en que la selección natural combina dos tendencias aparentemente contrapuestas:

• Por un lado hay una fuente de azar y variabilidad: la mutación genética durante la reproducción. En muchas historias de ciencia-ficción de los años 50 y 60 las mutaciones (producidas por la radiactividad) son suficientes para hacer aparecer una raza de hormigas gigantes, un monstruo como Godzilla o una raza de superhombres, pero esta interpretación es totalmente errónea. La mutación no es suficiente para la evolución. 

Muchas críticas superficiales de la evolución se basan en el argumento de que el azar no puede crear algo tan complejo como un ser vivo, y eso es cierto, pero no invalida la explicación por selección natural. Esas críticas se olvidan de un segundo componente, o no comprenden su potencia:

• Un proceso de selección que elimina la gran mayoría de las mutaciones y deja solamente aquellas que suponen una ventaja para los individuos que las llevan. Esta selección natural se produce por el sencillo mecanismo de que los más aptos para reproducirse tendrán más descendencia con su mutación favorable, que así se irá extendiendo por la población. Este componente de la evolución es lo que convierte el azar en necesidad, parafraseando el famoso título de Jacques Monod:

Dawkins explica en este antiguo pero interesante vídeo cómo los dos componentes se combinan con el tiempo para dar su potencia a la evolución.

El algoritmo que subyace a la evolución podría resumirse, por tanto, en los siguientes pasos:

• Evaluación y selección: cada individuo, según su mayor o menor aptitud para sobrevivir y reproducirse, genera descendientes.

• El material genético de los descendientes proviene del cruce del material de sus progenitores (en la reproducción sexual), a lo cual se añaden posibles mutaciones o cambios aleatorios.

• Los descendientes entran a formar parte de la nueva población de individuos, y el ciclo continúa indefinidamente.

La evolución: un sistema de optimización dinámica

Según la definición de algoritmo, estos se definen para resolver problemas, generando una o más soluciones. Encontes, ¿cuál es el problema que el algoritmo de la evolución pretendería resolver?

Imaginemos que tuviéramos una forma de calcular la 'aptitud' de un individuo (su capacidad de sobrevivir y reproducirse) y darle un valor numérico. Podríamos representar esta aptitud dibujando una curva o superficie donde el eje vertical representa cuán apto es cada individuo y los ejes horizontales representarían diferentes variantes genéticas, diferentes posibles individuos (existan realmente o no).

Esta representación conceptual se llama paisaje adaptativo (fitness landscape) y fue introducida ya en 1932.

No debemos interpretar esta función de adaptación como un cálculo que podamos realizar realmente. Se trata de una construcción conceptual. En la práctica existirían tantos puntos en la superficie como posibles individuos con diferentes combinaciones genéticas, un número astronómicamente inmenso. Por otra parte, cada especie o población en un área determinada tendría diferentes paisajes adaptativos según su relación con el entorno y con otras especies. El contenido genético no es en sí mismo suficiente para determinar la aptitud.

En el mundo natural es la propia realidad competitiva entre los individuos de la misma especie, de diferentes especies y del medio, la que decide cuán apto es cada individuo (por el sencillo mecanismo de dejarle vivir y reproducirse en mayor o menor cantidad).

Lo que es importante es darse cuenta de que el objetivo del algoritmo evolutivo es conseguir que los individuos de diferentes especies alcancen posiciones más altas (mayores valores de aptitud) en sus respectivos paisajes adaptativos.

En forma gráfica, el objetivo de la evolución es conseguir combinaciones genéticas que vayan 'subiendo' por la superficie del paisaje, como si buscaran las cumbres, los puntos de mayor adaptación y aptitud. Es un proceso de búsqueda sin fin.

Desde este punto de vista el algoritmo evolutivo resolvería un problema de optimización, tratando de encontrar los valores (combinaciones genéticas) con los que se consiguen los máximos de una magnitud (la aptitud o adaptación).

Dada la complejidad de la interacción entre genes y entre genotipo y fenotipo, y las relaciones entre individuos, especies y entorno, es imposible predecir cuáles van a ser las combinaciones genéticas más adaptativas. Encontrarlas es precisamente el objeto de la evolución por selección natural.

Veremos en otra entrada posterior que la potencia de los algoritmos evolutivos para resolver problemas de optimización puede ser aprovechada para encontrar soluciones muy útiles en una variedad de campos prácticos.

Sin embargo, hay varios factores que convierten a la evolución en algo más que un problema de optimización clásico:

• El paisaje adaptativo real no es estático sino dinámico. La aptitud de una combinacion genética va cambiando en función del entorno físico, de la población en la que se encuentra y de las características de los individuos de otras especies (como en los procesos de coevolución), y todas estas relaciones son también dinámicas. En realidad la evolución va optimizando con el tiempo toda la combinación de relaciones entre las especies y con el entorno, de manera que todos evolucionan conjuntamente.

• La unidad de selección o aptitud es difícil de definir. ¿Qué es lo que realmente selecciona y optimiza la evolución: genes, células, individuos, grupos de individuos, especies, ecosistemas? Cada una de estas respuestas tiene sus adeptos. Personalmente creo que la evolución opera a todos estos niveles interrelacionados. Por tanto, no se puede decir que la solución al problema de optimización sea una combinación genética específica, sino que esta solución 'óptima' depende de su presencia en un determinado grupo, entorno, etc.

• En el modelo clásico de evolución son los genes los responsables de almacenar la información que determina la aptitud de un individuo. Sin embargo, durante la evolución van apareciendo otros mecanismos de almacenamiento y reproducción de información: primero, la memoria individual en el cerebro, luego la memoria colectiva y la transmisión cultural de conocimientos en los primates superiores, y más tarde con los humanos los sistemas de memoria masivos; el lenguaje escrito, la imprenta y los soportes electrónicos. La evolución biológica basada en información genética va dando paso así, como veremos en siguientes entradas, a la evolución cultural basada en información memética, con reglas de aptitud y un paisaje adaptativo totalmente diferentes.

Expandiremos este tema en las siguientes entradas. 

Hasta la próxima,

    Salvador