La informática de la evolución: una introducción a los algoritmos genéticos

Foto de Hal Gatewood en Unsplash

Siendo un científico de la computación con un interés en la evolución y los procesos biológicos, el tema de los algoritmos genéticos y, en términos más generales, la computación evolutiva es para mí lo que es una tienda de golosinas para un niño de 5 años: el cielo. La mera posibilidad de poder fusionar dos de mis intereses de una manera tan fluida ha sido extremadamente estimulante, y sería un error para mí mantener todo este conocimiento y emoción para mí.

Entonces, en un intento de probar algunos de mis aprendizajes hasta ahora, y compartir mis hallazgos con el resto del mundo, he decidido reunir una serie de artículos sobre este tema.

En esta publicación, proporcionaré una breve introducción a los algoritmos genéticos y explicaré cómo imitan los mismos procesos naturales que han tenido lugar en la Tierra durante miles de millones de años.

Vida en la Tierra

En los últimos 3.500 millones de años, la madre naturaleza, el tiempo del padre, la evolución y la selección natural han colaborado juntos para producir todas las formas de vida especializadas que vemos hoy en la tierra: como la planta carnívora Venus Flytrap; el pez volador atlántico que habita en el océano; murciélagos que usan ecolocalización; jirafas de cuello largo; guepardos súper rápidos, bailando abejas melíferas; y, por supuesto, realmente suyo, el Homo sapiens inteligente de la calle.

Venus Flytrap es una planta carnívora que se alimenta principalmente de insectos y arácnidos.Algunos murciélagos usan la ecolocalización para navegar y cazar presas y, contrariamente a la creencia popular, los murciélagos en realidad no son ciegos; una especie de murciélagos conocida como The Flying Foxes en realidad tiene mejor vista que los humanos.Los peces voladores no pueden volar de la misma manera que las aves, sin embargo, estos peces pueden hacer saltos poderosos y autopropulsados ​​fuera del agua donde sus largas aletas en forma de alas les permiten deslizarse por distancias considerables por encima de la superficie del agua.

No es necesario decir que la vida en la Tierra es uno de los experimentos más exitosos que se haya realizado en nuestro universo, si no el más importante; y a juzgar por los impresionantes resultados de este experimento, está claro que la evolución está claramente en algo.

Recientemente, los humanos, solo uno de los muchos productos finales de este proceso, nos dimos cuenta de que también podíamos aprovechar este enfoque ingenioso para la resolución progresiva de problemas, y desde la década de 1950, informáticos, genetistas, matemáticos y biólogos, hemos intentado imitar estos procesos biológicos a través de la implementación de simulaciones por computadora. Con el objetivo de producir soluciones óptimas para problemas difíciles, no triviales, de manera eficiente.

El relojero ciego

Uno de los primeros libros que encontré que despertó mi interés en el campo de la biología evolutiva fue The Blind Watchmaker, de Richard Dawkins. En este libro, Richard Dawkins explica cómo mecanismos complejos como la ecolocalización (un proceso que usan los murciélagos para navegar, cazar y buscar comida, también conocido como bio-sonar), estructuras complejas como telarañas (que las arañas usan para atraer y atrapar a sus presas), y Los instrumentos complejos como el ojo humano (esos dos objetos esféricos que está utilizando actualmente para leer este artículo) son simplemente el resultado de miles, si no millones de años de evolución y adaptación.

La evolución progresiva del ojo humano. Lo que comenzó como células fotosensibles simples, se convirtió en un instrumento complejo que a menudo damos por sentado. Los primeros animales con algo parecido a un ojo vivieron hace unos 550 millones de años. Y, según los cálculos de un científico, solo tomaría 364,000 años para que un ojo similar a una cámara evolucione de un parche sensible a la luz.

Aunque estas maravillas de la naturaleza dan la impresión de que fueron construidas con un propósito desde el primer momento (es decir, por un 'creador' consciente), en realidad son solo el resultado de iteraciones tras iteraciones de prueba y error, agrupadas con siempre -cambiar la presión de selección (es decir, un cambio en el clima, el hábitat o el comportamiento y las capacidades de los depredadores o presas). Entonces, aunque pueden parecer y comportarse como el resultado de una ingeniería precisa y progresista, en realidad son el resultado de un proceso completamente ciego, un proceso que no sabe de antemano cuál sería la "solución" perfecta.

¿Qué son los algoritmos genéticos y por qué los necesitamos?

Los algoritmos genéticos son una técnica utilizada para generar soluciones de alta calidad para la optimización y los problemas de búsqueda, que se basan en procesos biológicos fundamentales. Estos algoritmos se utilizan en situaciones en las que el rango posible de soluciones es muy grande, y donde los enfoques más básicos para la resolución de problemas, como la búsqueda exhaustiva / fuerza bruta, consumirían demasiado tiempo y esfuerzo.

El problema del vendedor ambulante hace la siguiente pregunta: “Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad y regresa a la ciudad de origen?” Es un problema NP-difícil en Optimización combinatoria.

Podemos utilizar algoritmos genéticos para proporcionar soluciones de alta calidad a este problema, a un costo mucho menor que las técnicas de resolución de problemas más primitivas, como la búsqueda exhaustiva, que requeriría que permute todas las soluciones posibles.

¿Cómo funcionan los algoritmos genéticos?

Un algoritmo funciona iterando a través de una serie de pasos, hasta que alcanza un punto de terminación predefinido. Cada iteración del algoritmo genético produce una nueva generación de posibles soluciones, lo que, en teoría, debería ser una mejora con respecto a la generación anterior.

Los pasos son los siguientes:

1. Crear una población inicial de N posibles soluciones (la sopa primordial)

El primer paso del algoritmo es crear un grupo inicial de soluciones que sirvan como soluciones base en la generación 0. Cada solución en esta población inicial llevará un conjunto de cromosomas, que están formados por una colección de genes, donde cada gen se asigna a una de las posibles variables del problema. Es importante que las soluciones en la población inicial se creen con genes asignados al azar, para tener un alto grado de variación genética.

2. Clasifique las soluciones de la población según su estado físico (supervivencia del más apto, parte 1).

En este paso, el algoritmo debe ser capaz de determinar qué hace que una solución sea más "adecuada" que otra. Esto está determinado por la función fitness. El objetivo de la función de aptitud es evaluar la viabilidad genética de las soluciones dentro de la población, colocando a aquellos con los rasgos genéticos más viables, favorables y superiores en la parte superior de la lista.

En el problema del vendedor ambulante, la función de aptitud podría ser un cálculo de la distancia total recorrida por la solución. Donde una distancia más corta equivale a una mayor aptitud.

3. Elimine las soluciones más débiles (supervivencia del más apto, parte 2)

En este paso, el algoritmo elimina las soluciones menos adecuadas de la población. El "más apto" no significa necesariamente el más fuerte, el más rápido o el más feroz, como suelen suponer los humanos. La supervivencia del más apto simplemente significa que cuanto mejor equipado esté un organismo para sobrevivir en su entorno, más probabilidades tendrá de vivir lo suficiente para reproducirse y propagar sus genes a la próxima generación.

Los pasos 3 y 4 se conocen colectivamente como selección.

4. Genere las soluciones más fuertes (supervivencia del más apto, parte 3)

Las soluciones restantes se combinan entre sí para aparearse y reproducir la descendencia. Durante este proceso, en su forma más básica, cada padre contribuirá con un% de sus genes (en la naturaleza es una división 50/50) a cada uno de sus descendientes, donde P1 (G)% + P2 (G)% = 100 % El proceso de determinar cuál de los genes de los padres será heredado por la descendencia se conoce como cruce.

5. Mutar los genes de la descendencia (mutación)

La descendencia contendrá un porcentaje de los genes de la "madre" y un porcentaje de los genes de los "padres" y ocasionalmente habrá una "mutación" de uno o más de estos genes. Una mutación es esencialmente una anomalía genética, un error de copia que hace que uno o más de los genes de la descendencia difieran de los genes que heredó de sus padres. En algoritmos genéticos, en algunos casos una mutación aumentará la aptitud de la descendencia, en otros casos, la reducirá.

Es importante tener en cuenta que no es necesario que haya una mutación con cada descendencia, la frecuencia de mutación requerida también puede ser un parámetro del algoritmo.

En algoritmos genéticos, la selección, el crossover y la mutación se conocen como operadores genéticos.

6. Terminación

Los pasos 2 a 5 se repetirán hasta un punto de terminación predefinido. Este punto de terminación puede ser uno de los siguientes:

  1. Tiempo máximo / asignación de recursos alcanzada.
  2. Número fijo de generaciones han pasado.
  3. La aptitud de la solución dominante no puede ser superada por ninguna generación futura.

Convergencia de soluciones

1. Óptimo global

En la situación ideal, la solución más adecuada tendrá el mayor valor de condición física posible, es decir, será la solución óptima, lo que significa que no habrá necesidad de continuar con el algoritmo y producir más generaciones.

2. Óptimo local

En algunos casos, si los parámetros del algoritmo no son razonables, la población puede tender a una convergencia prematura sobre una solución menos óptima, que no es el óptimo global que buscamos, sino más bien local. Una vez aquí, continuar el algoritmo y producir más generaciones puede ser inútil.

Óptimo global versus óptimo local

¿Qué pasaría si no hubiera mutaciones?

A primera vista, las mutaciones pueden parecer una parte innecesaria e irrelevante del proceso. Pero sin este aspecto fundamental de aleatoriedad, la evolución por selección natural estaría completamente restringida a la variedad genética establecida por la población inicial, y no habría nuevos rasgos introducidos en la población después de eso. Esto dificultaría severamente las capacidades de resolución de problemas de la naturaleza, y la vida en la tierra no podría "adaptarse" a su entorno, al menos no físicamente.

Si este fuera el caso en nuestro algoritmo genético, en algún momento de nuestra simulación, las generaciones futuras de la población no podrían explorar parte del espacio de solución que sus predecesores no exploraron. Una simulación sin mutaciones restringiría severamente la variación genética dentro de la población y, en la mayoría de los casos, dependiendo de la población inicial, nos impediría alcanzar un óptimo global.

Sin mutaciones, no tendríamos mutantes, y sin mutantes, no tendríamos la franquicia X-men.

¿Qué pasaría si el tamaño de la población no fuera lo suficientemente grande?

Hace poco estuve en el Santuario de Vida Silvestre Jukani en Plettenberg, donde tuve el privilegio de conocer a un tigre blanco. Era un animal verdaderamente majestuoso. Era grande, parecía feroz y también estaba 80% ciego y empeoraba progresivamente con el paso de los años.

¿Por qué estaba ciego? Porque es producto de generaciones de endogamia. Estos tigres blancos solo se producen cuando dos tigres que llevan un gen recesivo que controla el color del pelaje se crían juntos. Por lo tanto, para garantizar la continuación de estos tigres en cautiverio, las personas han estado criando estos tigres dentro de una población muy limitada para mostrarlos en los circos, exhibirlos en zoológicos o mantenerlos como mascotas domésticas.

Pero uno de los efectos negativos de la endogamia es que limita severamente la variación genética dentro de la especie, lo que aumenta progresivamente las posibilidades de que los rasgos recesivos nocivos se transmitan a la descendencia.

El tigre blanco que conocí en el Jukani Wildlife Sanctuary en abril de 2019. Se ve majestuoso, pero está sufriendo.

Incluso en la naturaleza, la endogamia puede ser un problema enorme. En las últimas décadas, la población de rinocerontes en el sur de África se ha visto significativamente afectada por la caza furtiva, y si el tamaño de la población alcanza un número lo suficientemente bajo, significaría que mantener la diversidad genética de estas especies de rinocerontes amenazadas sería extremadamente difícil. Entonces, incluso si la caza furtiva no los lleva completamente a la extinción, la endogamia podría hacerlo.

Foto de redcharlie en Unsplash.

Por supuesto, los humanos no son ajenos a la endogamia. Un famoso resultado de la endogamia continua dentro de nuestra propia especie es Charles (Carlos) II de España.

“El rey de los Habsburgo Carlos II de España fue degenerado tristemente con una enorme cabeza deforme. Su mandíbula de los Habsburgo sobresalía tanto que sus dos hileras de dientes no podían encontrarse; no pudo masticar. Su lengua era tan grande que apenas podía hablar. Su intelecto fue igualmente deshabilitado ".

El rey de los Habsburgo Carlos II de España. Su padre era el tío de su madre, convirtiendo a Charles en su hijo, sobrino nieto y primo hermano respectivamente.

La "endogamia" en nuestro algoritmo genético significa esencialmente la obtención de soluciones que tienen una composición genética muy similar, que, afortunadamente, en este caso, no daría lugar a una descendencia con una predisposición a cualquier anormalidad física. Pero si la población es muy pequeña y si todas las soluciones comparten una composición genética muy similar, la aptitud de las futuras generaciones de la población se verá severamente restringida. Lo que significa que podría llevar mucho más tiempo converger en una solución globalmente óptima si llegamos allí.

La endogamia no siempre es algo malo, solo depende de la etapa de la simulación en la que se encuentre. En etapas muy avanzadas de la simulación, a medida que la población converge hacia un óptimo global / local, obviamente es muy difícil evitar la endogamia, porque , en algunos casos, muchas de las soluciones dominantes serán muy similares entre sí y, por lo tanto, compartirán muchos de los mismos rasgos genéticos.

Terminando

Muy bien, eso debería cubrir lo básico. Si tiene alguna pregunta, solicitud o mutaciones genéticas para contribuir, deje un comentario a continuación.

En la próxima publicación, profundizaremos en un código a medida que veamos cómo se desempeña cada uno de los operadores genéticos descritos anteriormente en el mundo de la programación. Utilicé el lenguaje de programación Ruby para la simulación de software en la que trabajé, y en él, muestro cómo en solo unas pocas generaciones, un algoritmo genético puede producir una palabra o frase predefinida a partir de una colección inicial de galimatías completas y completas. Todo el código estará alojado en Github.