Algunas notas sobre “A Survey of Parallel Genetic Algorithms”

En esta publicación de 1998, Erick Cantú-Paz hace hincapié en la facilidad de implementar GA paralelos y en sus ganancias en rendimiento. Para eso intenta colectar, organizar y presentar las publicaciones más representativas en este aspecto. Sin embargo se va a centrar en las investigaciones en donde los GA tengan múltiples poblaciones independientes.

Haciendo un paneo por la historia de los enfoques paralelos en GA, destaca el trabajo de Betke de 1976, en donde describió una implementación paralela de GA convencionales. Otro estudio interesante fue el de Grefenstette de 1981 que propuso mapear las arquitecturas paralelas existentes con GA, trabajando en 4 prototipos distintos, siendo uno de ellos el primer prototipo del enfoque de poblaciones múltiples, siendo el prototipo que más tardíamente se implementó (1987).

Luego de una breve introducción describiendo someramente el mecanismo de los GA, pasa a clasificar los GA paralelos:

    1. Global single-population master-slave GA: Donde existe una única población, pero el procesamiento de la evaluación del fitness es altamente distribuida. Cada individuo puede competir y cruzarse con cualquier otro. Se dice que el algoritmos es sincrónico si debe esperar la evaluación de todos los fitness (procesados en paralelo). Hay posibilidades de implementación asincrónica, pero en esos casos el mecanismo de GA no funciona de manera tradicional. La mayoría de las implementaciones son sincrónicas y reducen la velocidad de evaluación al tiempo de evaluación más lento de cada generación. Pueden ser implementados en modelos de memoria compartida, como de memoria distribuida. Cabe destacar que para paralelizar el proceso de selección habrá obstáculos por el overhead de comunicación, aunque Branke en 1997 paralelizó distintos tipos de selección global en una grilla 2D de procesadores mostrando que sus algoritmos eran óptimos para la topología utilizada (O(\sqrt{n}) en una grilla de \sqrt{n} x \sqrt{n}). La cruza y la mutación pueden ser fácilmente paralelizables utilizando la misma idea que para la evaluación del fitness. En conclusión, son fácilmente implementables y pueden ser un método eficiente y se puede aplicar la teoría disponible para los GA tradicionales.
    2. Single-population fine-grained GA: Consiste en una población espacialmente estructurada, en donde la selección y cuza se restringen a una pequeña vecindad del individuo. Manderick y Spiessens (1989) observaron que el rendimiento se degradaba a medida que el tamaño de la vecindad aumentaba. También pudieron demostrar que para un tamaño de subpoblaciones s y un largo de cromosoma l, la complejidad de tiempo del algoritmo es O(s+l) u O(s(log s)+l) pasos dependiendo del esquema de selección utilizado. Una conclusión interesante es que no se puede determinar una regla general para comparar el método fine-grained con el coarse-grained, aunque en 1992 Gordon, Whitley y Böhm demostraron que el camino crítico de un GA fine-grained es más corto que el de GA de población múltiple, aunque no incluyeron consideraciones de comunicaciones.
    3. Multiple-population (multiple-deme) coarse-grained GA: Son los más sofisticados, dado que consisten en varias subpoblaciones que intercambian individuos entre si eventualmente (migración). Cabe destacar que los efectos de la migración todavía no han sido comprendidos enteramente. Introduce cambios en el esquema de funcionamiento de los GA tradicionales. Tienen una analogía con el enfoque llamado “modelo de isla” de la genética de poblaciones. Una observación interesante sobre los estudios realizados en este ambiente relevan ciertas preguntas de interés: ¿Cuál es el ancho de banda de comunicaciones necesario para hacer que se comporten como GA global?¿Cuál es el costo de estas comunicaciones?¿Es el costo de las comunicaciones lo suficientemente pequeño como para hacer de esta una alternativa viable para el diseño de GA paralelos? Otro de los parámetros estudiados (particulamente en la investigación de Tanese en donde comparaba el rendimiento de un GA serial con respecto a la implementación paralela con y sin costo de comunicación) es el de la frecuencia de migración de individuos. En la misma investigación encontró que una implementación de múltiple población (r poblaciones de n individuos, sin costo de comunicación) encontraba soluciones de la misma calidad que la implementación serial con una población de r.n individuos. Los parámetros que controlan la migración de individuos son:
  • La topología que define las conexiones entre las subpoblaciones.
  • Una tasa de migración que controla cuántos individuos deben migrar
  • Un intervalo de migración que afecta a la frecuencia de las migraciones

Una de las conclusiones tiene una implicancia biológica notable: hay cambios favorables en los cromosomas que se extienden más rápido en poblaciones más pequeñas que en las más grandes.

  1. GA Paralelos Jerárquicos: Es una combinación de múltiples poblaciones y procesamiento maestro-esclavo. Dentro de esta rama hay investigadores que han combinado métodos. Este enfoque puede reducir el tiempo de ejecución más que cualquiera de las otras técnicas por si sola.

Probablemente el primer intento de fundamentar teóricamente el rendimiento de un GA paralelo fue una publicación de Pettey y Leuze de 1989, en donde se describe una derivación del teorema de los esquemas para GA paralelos. Una cuestión teórica muy importante es poder determinar si (y bajo qué condiciones) un GA paralelo puede encontrar una mejor solución que un GA serial. Hay dos observaciones en el trabajo de Starkweather (et al.):

  • Las subpoblaciones relativamente aisladas pueden converger a diferentes soluciones, y la migración y recombinación pueden combinar soluciones parciales. Se especula que por esto los GA paralelos con baja tasas de migración pueden encontrar mejores soluciones para funciones separables.
  • Si la recombinación de soluciones parciales resulta en individuos con fitness más pobre (quizás porque la función no sea separable), entonces los GA seriales pueden tener una ventaja.

La migración se considera sincrónica cuando en un determinado momento migran todos los individuos que se esperaba que migren. Hay un enfoque asincrónico. Hay enfoques que utilizan la migración asincrónica tanto cuando las subpoblaciones tienden a converger como cuando convergen totalmente. De esta manera surge una pregunta muy interesante: ¿Cuál es el mejor momento para migrar?

Topología de las comunicaciones: Es un factor fundamental en los GA paralelos. Si la topología tiene una conectividad densa, se supone que las buenas soluciones se expandirán más rápido a lo largo de las poblaciones. Por otro lado, si la topología es más rala, lo harán más lento, permitiendo la aparición de diferentes soluciones. La línea general de implementación dice que la topología de comunicación debe ser estática a lo largo de toda la ejecución. El enfoque de topología dinámica es utilizado cuando puede determinarse a qué subpoblación conviene más que migre un individuo.

Entre los avances más recientes para la fecha de publicación, el autor señala:

  • Se concluyo que la cantidad óptima de workers para el enfoque GA paralelo Global es S*=\sqrt{\dfrac{nT_{f}}{T_{c}}} donde n es el tamaño de la población, Tf es el tiempo que toma hacer una evaluación de fitness y Tc es el tiempo de comunicación. El speed-up óptimo es 0.5 S*.
  • Cuando las subpoblaciones están aisladas, el speed-up no es tan significante.
  • El speed-up es mucho mejor cuando las subpoblaciones están comunicadas.
  • Se puede determinar un número óptimo de subpoblaciones (asociado al tamaño de las mismas) que maximiza el speed-up.
  • Hay varios problemas que todavía no han sido resueltos, entre ello:
      • Determinar la tasa de migración que hace que las subpoblaciones distribuidas se comporten como una única población global.
      • Determinar la topología de comunicaciones adecuada que permita la combinación de buenas soluciones, pero que no resulte en un costo excesivo de comunicación.
      • Encontrar si hay un número óptimo de subpoblaciones que maximice la confiabilidad del GA.
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