¿Y entonces, para qué GA con MapReduce?

MapReduce es un framework para procesamiento de grandes volúmenes de datos en paralelo. Google tiene una patente sobre el concepto en EEUU, aunque sería discutible, ya que está inspirado en las operaciones Map y Reduce de Lisp y otros lenguajes funcionales.

El enfoque llamado BigData (también acuñado por Google) habla de manejar grandes volúmenes de datos. Los grandes volúmenes de datos no asustan a los motores de bases de datos relacionales tradicionales (RDBMS), lo que si acaba por dejarlos inutilizados es la complejidad de las relaciones… Facebook no podría montar una red social en forma de grafo de orden 5000 (cantidad máxima de amigos) eficientemente si sólo dependiera de RDBMS.

MapReduce podría ser el nivel más bajo de lenguaje utilizado para explotar estas bases de datos. No es conveniente hacer comparaciones, como muchos autores han hecho con herramientas OLAP, ya que es lo mismo que comparar un Audi Quattro R8 con el termo Lumilagro con el que estoy cebando mate. No hay mejor, ni peor… No tienen nada que ver, no me imagino extrayendo agua del radiador del Audi para hacer mate ni viajar a 300km/h con mi termo (salvo en caída libre, lo dicho, tiene ventajas el termo).

Lo que si nos interesa es que podemos escribir software, demostrar su correctitud y completitud (si no usamos lo que se llama combiners) y ponerlo a ejecutar en forma paralela sin atender demasiado al mecanismo de paralelismo. Eso si, tenemos que pensar nuestros algoritmos en términos de pipelines de operaciones map y reduce… Si sirve de consuelo, peor les va a los muchachos de la computación cuántica…

Hay otros métodos de ejecución en paralelo que permiten un manejo “más” nativo de los algoritmos como tantas implementaciones MPI que existen, pero requieren un conocimiento más exhaustivo sobre la arquitectura en la que están corriendo, no son agnósticos de la plataforma.

Por otro lado, existen varias implementaciones de MapReduce (tanto comerciales como libres) y existen en el mundo centenares de clusters MapReduce en funcionamiento. De hecho, herramientas como Hadoop (la elegida para hacer mi implementación por simplicidad, documentación y licencia). Por tanto expresar nuestro software en términos de MapReduce, habilita que lo podamos correr en la nube (ya sea comercial o académica), o que construyamos un clúster a partir de hardware obsoleto. Incluso si queremos invertir en hardware, es claro que es mucho más barato comprar 100 dispositivos de X procesamiento que uno de 100X procesamiento. Incluso se están utilizando las placas de video para paralelizar operaciones (lo que entiendo que es explotable en Hadoop).

Sobre paralelismo en algoritmos genéticos (de ahora en más, PGA), hay ríos de tinta escritos, investigaciones e implementaciones desde hace 30 años. Sobre implementaciones con MapReduce, muy poco:

Genetic Algorithms by using MapReduce 

Fei Teng y Doga Tuncay de la Universidad de Indiana proponen implementar el problema OneMax (maximizar los 1 en una cadena de bits) sobre Hadoop y Twister demostrando mayor performance con la implementación de la iteratividad con Twister.

Parallelization of genetic algorithms using Hadoop Map-Reduce

Dino Kečo y Abdulhamit Subasi de la Universidad Burch de Sarajevo también abordan el problema de implementar una solución para OneMax en MapReduce (con Hadoop), focalizándose en cómo encajar el paralelismo que necesita la solución específica de este problema con GAs en el esquema de MapReduce.

An Extension of MapReduce for Parallelizing Genetic Algorithms

Chao Jin, Christian Vecchiola y Rajkumar Buyya de la Universidad de Melbourne utilizaron una grila de procesamiento Microsoft (con Aneka) para construir una extensión del modelo de procesamiento MapReduce para que encaje mejor con los problemas que hay para compatibilizar los PGA con MapReduce. Parece una buena solución que se aparta de la norma y requiere de la presencia de este nuevo producto en los clúster MapReduce en vez de las implementaciones standard.

Scaling Populations of a Genetic Algorithm for Job Shop Scheduling Problems using MapReduce

Di Wei Huang y Jimmy Lin de la Universidad de Maryland se propusieron demostrar que para solucionar Job Shop Scheduling Problem con GA conviene agrandar el tamaño de las poblaciones y para eso utilizaron MapReduce con excelentes resultados. La implementación fue específica e iterativa para este problema, por lo que no es muy general, pero la conclusión es asombrosa. Llegaron a operar con poblaciones de 107 individuos. E incluso concluyen que la cantidad de generaciones necesarias se disminuye notablemente con este enfoque.

A Parallel Genetic Algorithm Based on Hadoop MapReduce for the Automatic Generation of JUnit Test Suites

Linda Di Geronimo, Filomena Ferrucci, Alfonso Murolo y Federica Sarro de la Universidad de Salerno proponen utilizar PGA para generar suites de pruebas unitarias que maximicen ciertas métricas de pruebas unitarias (como branch coverage, code coverage y otras).

Scaling Simple and Compact Genetic Algorithms using MapReduce

Abhishek Verma, Xavier Llora, David E. Goldberg y Roy H. Campbell de la Universidad de Illinois proponen estudiar las perspectivas de escalabilidad que puede ofrecer la implementación de PGA con MapReduce. Para eso toman una implementación simple (la más simple posible) de algoritmo genético y realizan experimentos con hasta 108 variables.

Analogías y comentarios de la lectura de Griffiths et al. (Capítulo 21 y final)

La genética evolutiva es presentada con una serie de preguntas que vale la pena explorar:

¿Cuáles son los principios básicos del mecanismo darwiniano de la evolución?

La explicación de la evolución se basa en un modelo de las variaciones de la población en el que sus individuos varían, estando el mecanismo de variación evolutiva basado en 3 principios que analizados en conjunto proveen un mecanismo para la evolución a lo largo del tiempo en los atributos de una población:

  1. El principio de variación, que establece que entre individuos de una población hay variantes en morfología, fisiología y comportamiento
  2. El principio de herencia, que establece que la descendencia se parece a sus padres más de lo que se parece a otros individuos sin parentesco
  3. El principio por el cual algunas variaciones son más exitosas que otras en el ámbito de la supervivencia y la procreación.

¿Cuáles son los roles de la selección natural y otros procesos de la evolución, y cómo interactúan entre sí?

La variación hereditaria requerida por la teoría de Darwin aparece por mutación, cambios cromosomales y por la introducción de nuevo ADN en el genoma (por duplicación del ADN ya presente o por transposición de ADN de otros organismos). La migración de individuos entre poblaciones incrementa la variación dentro de poblaciones, a la vez que decrementa las diferencias entre poblaciones. Uno de los efectos de la migración es introducir nuevas mutaciones (favorables) en una población, permitiendo una evolución más rápida de la que ocurriría si las poblaciones estuvieran totalmente aisladas y tuvieran que esperar la chance que que ocurra esta mutación favorable. Si los portadores de una nueva mutación tienen un mejor desempeño (supervivencia o reproductiva) que otros genotipos que  los de la población (promedio), estos nuevos genotipos incrementarán las frecuencia de la variantes y pueden eventualmente llegar a convertirse en una variante característica de la población. También conviene destacar que si un nuevo genotipo es selectivamente ventajoso, puede incluso no difundirse si la población es lo suficientemente pequeña como para que la aleatoriedad cause la pérdida de la nueva variante.

¿Cómo aparecen nuevas especies?

Las diferentes especies aparecen de poblaciones que están separadas por una barrera geográfica que previene el intercambio de genes entre ellas. De este modo cada población adquirirá (probablemente) mutaciones no compartidas con la otra población, el devenir aleatorio genético causará la fijación de dichas mutaciones en una población (y su pérdida en la otra), incluso las diferencias ecológicas entre las dos locaciones puede dar como resultado que un genotipo sea beneficioso en una locación, pero perjudicial en la otra. Eventualmente una población se puede volver tan distinta genéticamente a la otra, que no pueda producirse una diferencia entre un individuo de una población y un individuo de la otra, constituyendo estas poblaciones nuevas especies.

¿Cuán diferentes son los genomas de los distintos tipos de organismos?

Los genomas pueden diferir tanto en la cantidad total de ADN, como en la organización de sus genes en los cromosomas, pero hay una notable similitud en las proteínas que son codificadas por los genomas de formas muy divergentes.

¿Cómo aparecen las novedades evolutivas?

Aparecen a partir de 3 tipos de cambios en el genoma:

  1. Mutación del ADN existente
  2. Cambios en el ADN regulatorio
  3. Evolución de nuevo ADN extranumerario que se agregue al genoma por duplicación o transposición.

Analogías y comentarios de la lectura de Griffiths et al. (Capítulo 19)

Tanto en genética como en GA se estudian los procesos genéticos (herencia, mutaciones) que afectan a un individuo, cuando se cambia el foco al estudio de lo que sucede genéticamente en una o varias poblaciones de individuos, se habla de genética de poblaciones, que enfoca su estudio en la composición genética de las poblaciones y en los cambios en dicha composición, tanto en el tiempo como geográficamente hablando.

Uno de los puntos de interés en la genética de poblaciones es el estudio del efecto de las migraciones de individuos de una población a otras. En GA paralelos hay enfoques de desarrollo autónomo de poblaciones con intercambios de individuos (con buen fitness) entre ellas.

Las fuentes de variaciones genéticas admitidas en la genética de poblaciones son las mutaciones (que de hecho, su taza es bastante baja como para contabilizar cambios genéticos en las poblaciones y en las especies), las recombinaciones y las migraciones de individuos.

Analogías y comentarios de la lectura de Griffiths et al. (Capítulo 15)

En este capítulo se habla sobre cambios cromosomales en gran escala, como por ejemplo los que ocurren en humanos cuando se da el síndrome de Down, que es provocado por la presencia de un cromosoma extranumerario en un par específico del genoma humano.

Un poliploide es un organismo que posee más de dos conjuntos de cromosoma apareados y es común en plantas y raro en animales. Incluso esta condición en plantas no es constantes, pudiendo ser organismos que durante ciertos procesos son haploides, luego diploides, más tarde triploides y finalmente diploides.

Me cuesta ver en qué tipos de procesos (hablando en términos de GA) puede ser de utilidad un esquema poliploide. Aunque reconozco que mi cortedad de genio no debería constituir ningún impedimento para estudiarlo.

Analogías y comentarios de la lectura de Griffiths et al. (Capítulo 14)

En términos de lo que se puede determinar “caja negra”, las mutaciones del ADN en las células ocurren de manera muy similar a las de los GA. Por “caja negra” entiendo un proceso sobre el que no conocemos detalles, pero sí las entradas y sus salidas. Esta analogía va más allá del proceso de mutación en sí, sino que abarca al alcance de la misma, ya que tanto en GA como en las células, la mutación es un proceso aleatorio, ya que cualquier alelo en cualquier célula puede mutar en cualquier momento. Obviamente, en los organismos hay mecanismos que pueden alentar las mutaciones como ciertos químicos y ciertas radiaciones… No estaría mal evaluar qué podría pasar si nuestros algoritmos se estancan en óptimos locales y consideramos “irradiarlos” para ver si logramos hacerlos salir de allí. En términos reales, esto se ha logrado modificando parámetros que generalmente son constantes como la probabilidad de mutación de un alelo o en sí la distribución (generalmente uniforme) de dicha probabilidad.

Si bien la mutación es un proceso que según Gregorio Chaitin tiene una responsabilidad fundamental en la creatividad biológica, se considera que la mayoría de las veces ocurre con un resultado “malo”, es decir que la célula o el organismo en cuestión no prospera.

Los mecanismos de reparación biológica de errores o mutaciones son extraordinarios, todo un mecanismo de paridades y CRC avant la lettre (bastante adelantado, millones de años contra un par de décadas). Los mismos son muy complejos y conviene decir que estos mecanismos se disponen en capas del proceso de replicación, los sistemas de reparación de errores de paridad en la replicación están ubicados a nivel de la función de verificación de lectura en la polimerasa. Los mecanismos de reparación ocurren cuando ya la nueva cadena fue sintetizada.

En GA contamos con mecanismos de reparación o normalización de cromosomas, ya que es probable, como en la naturaleza, que cualquier cromosoma generado al azar pueda pertenecer a un individuo válido.  Es también claro que este tipo de mecanismos puede actuar a la hora de la generación de un nuevo individuo, o cuando ya fueron generados, analogando la idea de verificación o reparación en las células.

 

 

Analogías y comentarios de la lectura de Griffiths et al. (Capítulo 13)

Si bien se puede considerar que la genómica dinámica de los elementos transportables dentro de un mismo cromosoma (o a otros cromosomas) no tiene un punto de contacto con los GA, hay ciertos factores que pueden analizarse.

Existen en la naturaleza elementos genéticos que pueden “moverse” (aotónomos o no autónomos) dentro del genoma de una especie. Aproximadamente la mitad de los elementos del genoma humano tienen dicha capacidad.

Dentro del ámbito de las procariotas, los elementos genéticos móviles son los que proveen a las bacterias de resistencia a las drogas.

El mecanismo mediante el cual ocurren estos movimientos (difieren entre procariotas y eucariotas) es fascinante y recomiendo su estudio.

Una nota que despertó cierta curiosidad en mi tiene que ver con la linealidad con la que solemos pensar la complejidad. Es decir, a más bytes, solemos asignar mayor complejidad. En genómica se cita a la paradoja del valor C, que refiere a la ausencia de relación entre el tamaño del genoma y la complejidad biológica. Dado que los genes toman una pequeña proporción del genoma de los organismos multicelulares, el tamaño del genoma generalmente se corresponde con la cantidad de secuencias de elementos transportables más que con el contenido de los genes. Esto me recuerda a los spandrels de San Marcos, artículo en el que Stephen Jay Gould en el que demuestra la sobrevaluación que observaba la selección natural por el nivel de adaptabilidad del entorno de los individuos de una especie.

Volviendo al hilo de los GA, no veo una correlación directa entre genes transportables, aunque hay algo a investigar que me hace ruido. Estamos siempre trabajando bajo la idea de que los GA funcionan dado que se basan en la mejora contínua de elementos constitutivos (building blocks) consentidos por el teorema de los esquemas… Qué pasa si esos building blocks pueden funcionar en otros loci… A priori no parece ser muy sensato analizarlo sin antes establecer mínimamente una uniformidad en la representación, si mi primer gen lo represento como una cadena de bits y el segundo gen como una cadena de caracteres unicode no parece que fuera esto a tener sentido (ni siquiera estaría hablando estrictamente en términos de GA). Creo que se puede desarrollar este tema. A investigar….

Analogías y comentarios de la lectura de Griffiths et al. (Capítulo 9)

Sobre las proteínas y su síntesis sólo marcaré algunos puntos que me causaron singular curiosidad.

Las secuencias lineales de nucleótidos en los genes determinan la secuencia lineal de los aminoácidos en las proteínas que se sintetizan en la célula.

En el código genético, los nucleótidos, son especies de letras que representan distintos aminoácidos, esto se expresa en el ARN mensajero, en donde podemos ver con cuántas letras armamos una “palabra” (codón). Existen 20 aminoácidos en las proteínas que se sintetizan en las células, por tanto, estas “palabras” tienen que poder representar uno de los aminoácidos posibles. Como el sistema opera en base 4 (C, G, A, U… En el ARN es U, en el ADN, T) vamos a necesitar 3 letras, con las que podríamos expresar 64 aminoácidos. Muchas de las “palabras” que sobran no se consideran inválidas, sino que son usadas para dar otra forma de “expresar” un mismo aminoácido, de modo que el código es de cierta manera redundante. Es decir que el mismo aminoácido puede ser especificado por 2 o más “palabras”.

Cabe destacar que la lectura de este código en la célula no se solapa, es decir, se toman ventanas de a 3 “letras”. Y aquí hay una analogía bastante interesante con la informática… Muchas veces, quienes hemos programado, hemos cometido errores (o han habido situaciones excepcionales) en los que nuestro código va leyendo una secuencia y por algún motivo, se desplaza… Ejemplo:

leer (Oracion o) {
   int i=0;
   Palabras ps=new Palabra[o.length()/3];
   while (i+3<o.length()){
      Palabra p=o[i]+o[i+1]+o[i+2];
      i+=3; // Punto crítico!!!!
   }
 }

En el anterior pseudo código vemos un programa que lee las palabras de una oración de 3 en 3. Si en donde pusimos “Punto crítico!!!” ocurre un error mediante el cual en vez de sumar 3, sumamos 2, todo nuestro código se desfasa y lee cualquier incongruencia… Es una frustración que después de décadas de programar nos pase esto… Pero momento… A la naturaleza a veces le pasa también! (consuelo de tontos!)…

Es notable el mecanismo por el cual los aminoácidos son llevados al ribosoma (que es donde se comienza a sintetizar una proteína en la célula, algo realmente asombroso). Aquí entra en juego otro tipo de ARN que es el tARN o ARN de transferencia (el anterior era el mARN o ARN Mensajero), que es el encargado de “traerle” al ribosoma el aminoácido que requiere el codón que se está decodificando (el mecanismo es bastante complejo y tiene que ver con distintos tipos de moléculas de tARN, cada uno especial para cada aminoácido que posee un anticodón que se aparea con el codón correspondiente).

Es notable que el código posee una estructura concreta, pero que transmite datos y meta-datos (datos acerca de los datos) a la vez. Es decir, no hay otra manera de hablar que con el lenguaje… Por más Bertrand Russell que tengamos para desambiguar, tenemos este lenguaje y punto… Nos tenemos que arreglar con nuestro lenguaje para hablar en distintos niveles del mismo… No hay otra! Ejemplo de esto son las secuencias de Shine-Dalgarno (en células procariotas) que no son ni más ni menos que mensajes “in-band” (ver esta analogía) que demarcan el comienzo de la transcripción para sintetizar la proteína, una especie de BOF (begin of file)…

Repasando, el mARN funciona como un plano para la proteína (de forma lineal), el tARN es una especie de instrumentista quirúrgico que trae el aminoácido solicitado, y hasta allí tenemos ensamblado un tren de aminoácidos (polipéptido), luego hay un proceso de elongación y de terminación, en el cual se espera una palabra de “stop” (UGA, UAA o UAG), es decir que hace millones de años que existe el EOF o incluso el \n!!!

Finalmente las proteínas deben tomar su forma definitiva tridimensional (lo que es importante para su funcionamiento), lo que implica la actuación de unas proteínas llamadas chaperonas (quizás por su acompañamiento de proteínas más “jóvenes”) en especies de complejos o máquinas en donde se les da su forma final…