La simplicidad matemática puede ser la base de la velocidad de la evolución.

Los informáticos recurren a la biología evolutiva en busca de inspiración para encontrar soluciones óptimas en conjuntos de dimensiones astronómicas

Al estudiar los vastos espacios de posibles soluciones al problema, nos enfrentamos al hecho de que la mayoría de los caminos serán callejones sin salida. Pero la evolución puede haber encontrado formas de aumentar las posibilidades de éxito.

A los creacionistas les encanta insistir en que la evolución tendría que recolectar hasta 300 aminoácidos en el orden correcto, solo para crear una sola proteína humana de tamaño mediano. Y dado que en cada posición se podría localizar uno de los 20 aminoácidos posibles, parecería que hay más de ^20,300 opciones de búsqueda, que es muchos órdenes de magnitud más alta que la cantidad de átomos en el Universo observable. Incluso si encontramos redundancia debido a que algunas de estas opciones serán equivalentes, la probabilidad de que la evolución tropezara con la combinación correcta por accidente y mutaciones aleatorias parece monstruosamente pequeña, incluso con miles de millones de años transcurridos.

El principal inconveniente de tales argumentos es que la evolución no experimentó estas secuencias por casualidad: el proceso de selección natural eliminó lo innecesario. Además, es probable que la naturaleza haya descubierto otras soluciones, formas de reducir una gran cantidad de probabilidades a pequeños subconjuntos estudiables que tienen más probabilidades de proporcionar soluciones útiles.

Los informáticos tienen problemas similares, que incluyen encontrar soluciones óptimas entre las muchas opciones de tamaño astronómico. Algunos de ellos recurren a la biología en busca de inspiración, a pesar del hecho de que los biólogos mismos solo están tratando de entender cómo resulta en la naturaleza.

Los algoritmos genéticos, métodos de optimización que han sido populares durante varias décadas, utilizan los principios de la selección natural para crear nuevos diseños (para robots, medicamentos y sistemas de transporte, entre otras cosas), entrenar redes neuronales o cifrar y descifrar datos. Esta tecnología comienza con el hecho de que las soluciones aleatorias al problema se consideran algunos "organismos" que tienen ciertas características, o elementos que están "genéticamente" definidos en su código. Estas soluciones no son particularmente buenas, pero luego sufren varias mutaciones aleatorias (y, a veces, otros cambios que copian el proceso de mezcla genética) y producen la segunda generación de organismos, que a su vez prueban su idoneidad para resolver el problema. Como resultado, después de muchas repeticiones, este proceso lleva a la aparición de una persona o decisión extremadamente bien adaptada.

Algunos expertos llevan este método al siguiente nivel, haciendo programación genética para obtener programas que puedan escribir programas y producir soluciones efectivas (aquí los "genes" pueden ser líneas de código). Este objetivo resultó ser especialmente difícil de lograr, porque los investigadores tienen que considerar ciertos tipos de datos y estructuras, así como muchas otras condiciones.

Curiosamente, estos métodos de pensamiento basados ​​en la evolución (en particular, la programación genética) se cruzan conceptualmente con una teoría matemática que siempre ha estado en algún lugar de la periferia de la biología y la informática. Recientemente, algunos científicos han estado tratando de usarlo para comprender cómo la evolución, natural y artificial, puede funcionar de manera eficiente, crear algo nuevo y aprender a aprender. Lo principal aquí fue un concepto especial de complejidad, aleatoriedad e información, que no tenía aplicaciones prácticas, hasta hoy.

Monos detrás de los teclados

Esta teoría, inventada en la década de 1960, funciona con lo que se llama información algorítmica. Comienza con una forma intuitiva de pensar sobre la probabilidad y la complejidad: la idea de que para algunos datos de entrada será más difícil computacionalmente describir cómo crear algo que crearlo. Tome la analogía conocida con un mono, presionando las teclas al azar. Las posibilidades de que imprima los primeros 15,000 dígitos del número π son ridículamente pequeñas, y disminuyen exponencialmente a medida que aumenta el número de dígitos.

Pero si interpretamos las pulsaciones de teclas como texto aleatorio para un programa de computadora que muestra el número π, entonces las posibilidades de éxito o "probabilidad algorítmica" se mejoran radicalmente. El código para mostrar los primeros 15,000 dígitos del número π en el lenguaje C, por ejemplo, puede reducir un total de hasta 133 caracteres.

En otras palabras, la teoría algorítmica de la información dice que la probabilidad de proporcionar algunos tipos de datos de salida es mucho mayor cuando los procesos aleatorios operan al nivel del programa que describe estos datos que al nivel de los datos en sí, ya que el programa será corto. En este sentido, las estructuras complejas, por ejemplo, los fractales, son mucho más fáciles de obtener por accidente.

Sin embargo, pronto surgió un problema con este enfoque: los matemáticos descubrieron que la complejidad algorítmica (también conocida como complejidad de Kolmogorov , llamada así por Andrei Nikolaevich Kolmogorov , uno de los fundadores de la teoría) de los datos de salida dados, la longitud del programa más corto posible que los producirá, no puede calcularse . Por lo tanto, los informáticos no pueden encontrar la manera perfecta de comprimir una cadena u otro objeto.


La complejidad algorítmica de la red de la izquierda es alta, porque para describirla, debe enumerar todos los bordes que conectan los vértices. En el medio, la complejidad es menor, porque al describir esta red, podemos escribir que el vértice A se conecta a todos los demás. La red correcta tiene la menor dificultad, ya que su descripción consiste en el hecho de que todos los vértices están conectados en pares por bordes.

Como resultado, la teoría algorítmica de la información se desarrolló principalmente en el campo de las matemáticas puras, donde se utiliza para estudiar teoremas relacionados y determinar los conceptos de aleatoriedad y estructura. Su uso práctico parecía inaccesible. "Matemáticamente, esta es una medida de complejidad simple y hermosa", dijo el famoso matemático Gregory Chaitin, uno de los fundadores de la teoría, que trabajó en el Centro IBM Thomas J. Watson y la Universidad Federal de Río de Janeiro. "Pero desde el punto de vista de la aplicabilidad en el mundo real, parecía inexpugnable".

Pero esto no lo hizo retroceder. Esperaba que esta teoría pudiera usarse para formalizar la idea de que el ADN se comporta como un programa. En 2012, publicó un libro donde describió cómo la evolución puede representarse como un paseo aleatorio por el espacio del programa. Las mutaciones que ocurren a lo largo de este camino, escribió, no están sujetas a una distribución de probabilidad estadísticamente aleatoria; obedecen a una distribución basada en la complejidad de Kolmogorov. Pero no pudo verificarlo.

Ahora, algunos científicos esperan revivir esta teoría en este contexto y conectarla con la biología y la informática al mismo tiempo.

El deseo de simplicidad.

Héctor Zenil , especialista en TI en el Instituto Karolinska en Suecia, es uno de los que están tratando de revivir esta teoría. Trabaja junto con otros investigadores para utilizar la complejidad de Kolmogorov como medida para analizar la complejidad de las redes biológicas, por ejemplo, las redes reguladoras de genes o la interacción de proteínas en las células. Los investigadores estiman aproximadamente el contenido algorítmico de la red (el valor exacto no es computable), luego mutan la red y verifican cuánto afectó la complejidad de Kolmogorov. Esperan que este método les dé una idea de la importancia relativa de los diversos elementos de la red y de su respuesta funcional a los cambios intencionales.


El famoso matemático Gregory Chaitin, uno de los fundadores de la teoría algorítmica de la información.

En un trabajo reciente publicado en arxiv.org, describieron que si hace que la red se mueva hacia aumentar la complejidad de Kolmogorov, introduciendo mutaciones que hacen que el programa que describe la red crezca, esto generalmente conduce a un aumento en el número de funciones que puede realizar red, al tiempo que lo hace más sensible a las perturbaciones. Cuando forzaron a la red a simplificarse, las funciones disminuyeron y la estabilidad aumentó.

Sin embargo, no está claro si la complejidad de Kolmogorov puede desempeñar un papel más importante que una simple herramienta, por ejemplo, como cree Chaytin, como la principal fuerza impulsora del cambio. A pesar de todos los problemas, la información algorítmica parece una teoría atractiva para la biología. Tradicionalmente, para describir la dinámica evolutiva, se utilizaron las matemáticas en el campo de la genética de poblaciones : modelos estadísticos que describen la frecuencia de los genes en la población. Sin embargo, la genética de poblaciones tiene sus propias limitaciones: no describe el origen de la vida y otros procesos biológicos transitorios básicos, ni la aparición de genes completamente nuevos. "En esta hermosa teoría matemática, la idea de la creatividad biológica se perdió de alguna manera", dijo Chaitin. Pero si tenemos en cuenta la información algorítmica, dijo, "entonces la creatividad naturalmente encaja en el panorama general".

Además de la idea de que el proceso evolutivo mejora con el tiempo y aumenta la eficiencia. "Estoy convencido de que la evolución es aprender", dijo Daniel Polanyi , especialista en TI y profesor de inteligencia artificial en la Universidad de Hertfordshire en Inglaterra. "No me sorprenderá si esto se puede expresar a través de una disminución asintótica de la complejidad algorítmica".

Zenil y el equipo decidieron probar experimentalmente las consecuencias biológicas y computacionales de la influencia de la plataforma de complejidad algorítmica. Utilizando la misma técnica para estimar la complejidad que usaron para analizar y perturbar redes, llevaron a cabo la "evolución" de redes genéticas artificiales hacia objetivos específicos: matrices de ceros y unos que denotan interacciones genéticas, eligiendo mutaciones que produjeron matrices con Menos complejidad algorítmica. En otras palabras, hicieron una selección a favor de estructuras más grandes.


Héctor Zenil, Especialista en Informática, Instituto Caroline

Recientemente, publicaron resultados en la revista Royal Society Open Science, de lo que se deduce que, en comparación con mutaciones estadísticamente aleatorias, su selección de mutaciones condujo a una aceleración significativa del desarrollo de redes hacia soluciones. También aparecieron otras características, por ejemplo, estructuras constantes y regulares: secciones de matrices que ya habían alcanzado un cierto grado de simplicidad, que las nuevas generaciones difícilmente podrían mejorar. "Las regiones individuales eran más o menos susceptibles a las mutaciones simplemente porque ya habían alcanzado un cierto nivel de simplicidad", dijo Zenil. "Era muy similar a los genes". Esta memoria genética ha ayudado a que las grandes estructuras emerjan más rápido: los investigadores creen que se deduce que mutaciones algorítmicamente probables pueden conducir a brotes de diversidad y extinción.

"Esto significa", dijo Zenil, "que será bastante fructífero considerar los procesos computacionales en el estudio de la evolución". Espera utilizar esta comprensión de la aleatoriedad y la complejidad para identificar las vías de intercambio que pueden ser más susceptibles a las mutaciones, o para entender por qué ciertas interacciones genéticas pueden asociarse con enfermedades como el cáncer.

Evolución del programa

Zenil espera entender si la evolución biológica funciona según las mismas reglas computacionales, pero la mayoría de los expertos tienen dudas. No está claro qué mecanismo natural podría ser responsable de una estimación aproximada de la complejidad algorítmica o de forzar el desarrollo de mutaciones a propósito. Además, "creer que la vida está completamente codificada en cuatro letras estaría mal", dijo Giuseppe Longo , matemático del Centro Nacional de Investigación Científica de Francia. "El ADN es extremadamente importante, pero no tiene sentido fuera de la célula, el organismo o el ecosistema". Otras interacciones funcionan, y el uso de información algorítmica no puede cubrir toda esta complejidad.

Sin embargo, este concepto despertó cierto interés, en particular porque tales puntos de vista sobre la evolución y los procesos computacionales tienen algo en común, al menos un tema común, con el objetivo de la programación genética, para obtener un programa que pueda evolucionar.

Ya había alusiones bastante intrigantes a la conexión potencial entre las ideas de Chaitin y Zenil relacionadas con la complejidad de Kolmogorov y los métodos de programación genética. Por ejemplo, en 2001, un equipo de investigadores informó que la complejidad de la producción de un programa genético está limitada por la complejidad de Kolmogorov del programa original.

Pero en su mayor parte, la complejidad de Kolmogorov no jugó un papel en los intentos de los informáticos para comprender estas ideas. Intentaron otras formas de cambiar la genética y las mutaciones. Algunos grupos cambiaron la velocidad de las mutaciones, otros obligaron al sistema a atender mutaciones que reemplazaron grandes fragmentos de código. "La gente ha ideado docenas, y posiblemente cientos, de diferentes versiones de mutaciones y genotipos", dijo Lee Spector , un especialista en TI en Hampshire College en Massachusetts. Spector dirigió recientemente un equipo que demostró los beneficios de agregar y eliminar mutaciones en todo el genoma del cuerpo sobre el reemplazo directo de un gen con otro. Este nuevo tipo de operador genético aumentó exponencialmente el número de caminos a través del espacio de búsqueda genética y finalmente condujo a mejores soluciones.


Lee Spector, especialista en informática en Hampshire College, Massachusetts

Sin embargo, muchos investigadores fueron en la dirección opuesta, en busca de formas inteligentes de acelerar el proceso, reduciendo el campo de búsqueda, pero sin limitarlo tanto que la búsqueda perdería resultados óptimos. Una idea era hacer de la simplicidad una meta: en la década de 1960, Eugene Wigner señaló "la efectividad irrazonable de las matemáticas en las ciencias naturales", y los científicos de la computación descubrieron que los modelos a menudo más simples y elegantes son más eficientes y más aplicables. "La pregunta es", dijo Spector, "¿este hecho nos dice algo profundo sobre la estructura del Universo, o no?" ¿Y nos será útil?

También advierte que los intentos de impulsar la evolución de los programas a la simplicidad pueden ser destructivos: los programas gratificantes por brevedad pueden reducir lo que parece basura ahora, pero pueden ser útiles para las generaciones futuras, dando como resultado soluciones óptimas sacrificadas. "Y estamos atrapados", dijo.

Sin embargo, la simplicidad sigue siendo un objetivo seductor, que, además, ha demostrado su utilidad. En un artículo publicado el año pasado, Spector y sus colegas descubrieron que si se reduce el tamaño de los programas, a veces solo en un 25% de la duración original, después de aplicar técnicas de programación genética, los programas se adaptaron mejor a los nuevos datos y podrían usarse en una gama más amplia de información general. problemas

En particular, debido a esto, supervisa el trabajo en el campo de la teoría de la información algorítmica, aunque dice que su impacto en esta área de investigación aún no se ha visto.

Aprendiendo de la vida

Quizás el equipo de Zenil dio el primer paso en la búsqueda de esta influencia; sin embargo, para una aplicación realista de su trabajo, primero deben probar su método en otros tipos de problemas de búsqueda.

Y, sin embargo, "demostraron de manera convincente la necesidad de restricciones basadas en la estructura", dijo Larisa Albantakis , neurocientífica de la Universidad de Wisconsin, que también trabajó para acelerar los algoritmos genéticos al limitar el espacio de búsqueda. "La naturaleza está estructurada, y si tomas esto como punto de partida, sería una tontería intentar probar todas las mutaciones homogéneas posibles". Y agregó: "Todo lo que tiene sentido para nosotros está estructurado de alguna manera".

Y aunque Spector es escéptico de que el trabajo de Zenil se pueda aplicar a algo que no sea resolver un problema específico que estudió, "la teoría de la información que subyace a sus conceptos es algo intrigante y potencialmente muy importante", dijo. "Me parece interesante en parte porque de alguna manera parece extraño". Quizás hay ideas que los camaradas de nuestra comunidad desconocen ”. De hecho, la información algorítmica se relaciona con una amplia gama de ideas que algunos expertos en programación genética pueden no incluir en su trabajo, por ejemplo, la naturaleza ilimitada de la evolución.

"Tengo un fuerte sentido de algo importante en esta área", dijo Spector. Sin embargo, agregó, hasta ahora "existe una gran distancia entre su trabajo y sus aplicaciones prácticas".

"La idea de imaginar la vida como un programa en evolución es muy fructífera", dijo Chaitin, aunque su valor aún es demasiado pronto para determinarlo. Ya sea que hablemos de la vida artificial o biológica, "necesitamos ver hasta dónde podemos llegar".