¿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.

Anuncios

Deje un comentario

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s