Algunas notas sobre “Scaling Genetic Algorithms using MapReduce”

En esta publicación, los autores (Abhishek Verma, Xavier Llor`, David E. Goldberg y Roy H. Campbell) porponen la utilización del framework MapReduce (en particular con la implementación de Hadoop) para implementar GA paralelos. Fijan posición en que la implementación tradicional basada en MPI requiere mucho conocimiento sobre la máquina donde se monta, y que, por el contrario, MapReduce permite un nivel de escalabilidad que no introduce ningún cuello de botella.

En particular, se enfocan en las variantes tradicionales y sencilla de los GA para brindar una implementación de referencia.

De los pasos del algoritmo clásico genético, la evaluación de los fitness tiene una analogía directa con la función Map, la cuál evaluará el fitness del individuo y guardará track (en un counter) del mejor individuo, finalmente persistiéndolo en el HDFS, el proceso cliente (el que inició la tarea MapReduce) chequea recurrentemente en este archivo si se ha alcanzado el criterio de convergencia.

Para poder implementar la selección distribuida, hay que tener control o mantener estado global, lo cual es un tanto complejo en MapReduce, por lo que el único componente que puede realizar este tipo de tarea es el Partitioner. El problema puntual por el cual no conviene utilizar la implementación por defecto es que durante la etapa de Shuffling (el momento en el que el framework reparte, mezcla y distribuye las emisiones de los mappers a los reducers) es porque utiliza una función de hash sobre la key (módulo la cantidad de reducers) para distribuir la carga, generando inconvenientes de convergencia del GA. Por otro lado, mientras el algoritmo genético pogrese, muchos individuos serán iguales, por lo que serán tratados por el mismo reducer, con la reducción de performance que esto implicaría. Es por eso que los autores utilizaron un partitioner especial que en vez de utilizar un hash, utiliza un número pseudoaleatorio cuya semilla es (mapperId * time).

El mecanismo de selección que han utilizado es el de torneo, ya que es el único que puede implementarse con facilidad en MapReduce, ya que la ruleta implicaría el mantenimiento de un estado global y un par de iteraciones más. Para esto han decidido tomar individuos al azar y ver quien es el ganador n veces (n es el tamaño de la población) del torneo para someterlo a la cruza. La operación de crossover se realiza en conjunto con la selección de dos individuos.

El tipo de crossover que utilizaron es el uniforme.

Cuando las poblaciones son muy grandes, la inicialización serial de los individuos tomó mucho tiempo, por lo que decidieron agregar una tanda de procesamiento map reduce en el que el map genera un individuo al azar y el reduce es trivial.

Las medidas de performance que realizaron fueron hechas con la implementación de un problema trivial utilizado para benchmark llamado OneMax Problem que consiste en encontrar la máxima cantidad de 1’s en los cromosomas de los individuos, es decir, un individuo tal que todos sus alelos sean 1’s. El análisis realizado arrojó que:

  • Análisis de convergencia: Para 104 variables, converge en 220 iteraciones con un promedio de 149 segundos por iteración.
  • Escalabilidad con carga constante por nodo: Incrementando la cantidad de recursos, no cambia el tiempo de procesamiento por iteración.
  • Escalabilidad con carga constante general: Fijaron la cantidad de variables en 50.000 e incrementaron el número de mappers, logrando una reducción del tiempo de iteración. Aunque el speed-up general queda limitado por la ley de Amdahl (“la mejora obtenida en el rendimiento de un sistema debido a la alteración de uno de sus componentes está limitada por la fracción de tiempo que se utiliza dicho componente”) dado el overhead de Hadoop (unos 10 segundos para iniciar y terminar un job).
  • Escalabilidad con incrementos en el tamaño del problema: Utilizaron el máximo de recursos y fueron incrementando el número de variables, logrando un incremento razonable con incrementos de población superlineales (n log n).

El gran inconveniente de trabajar con MPI en clústers standard es la poca tolerancia a fallos del framework. MapReduce no tiene este inconveniente. Introducen ciertas críticas a la implementación llamada MRPGA respecto a la escalabilidad.

Otros enfoques han tratado de modificar MapReduce para que se parezca a algo más consumible desde los GA, lo interesante de este trabajo es que no han intentado martillar MapReduce, sino todo lo contrario.

Como línea de investigación proponen comparar rendimientos con MPI y demostrar la importancia de GA escalables en las aplicaciones prácticas.

Por otro lado cabe destacar que no se proveen detalles de la implementación a bajo nivel, de modo que mucho se puede conjeturar sobre la implementación específica que han realizado, y que no se han aventurado a explorar alternativas un poco más complejas que el GA básico.

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