Distribución equilibrada del esfuerzo de cómputo en algoritmos genéticos paralelos

摘要

A pesar de su simplicidad operacional los AGs paralelos están controlados por múltiplesudparámetros que afectan a la eficiencia y a la calidad de las soluciones encontradas. Fijarudestos parámetros correctamente, buscando un equilibrio entre ellos, es fundamental paraudobtener buenas soluciones rápidamente intentado no desaprovechar recursos deudcomputación. Concretamente, algunos de los parámetros a determinar son el número yudel tamaño de las poblaciones y la frecuencia de intercambio entre ellas. Habitualmenteudestos parámetros se obtienen tras una experimentación sistemática. El objetivo de este estudio es servir de referencia a la hora de fijar estos parámetros yudser una guía para elegir los valores adecuados con los que obtener soluciones eficientesudy de alta calidad. Este documento combina la teoría con los resultados experimentalesudcon los que se puede apreciar el efecto de los diversos parámetros.udPara elaborar la investigación se ha desarrollado un tipo de algoritmo genético paraleloudconocido como modelo de islas (Island Model) y se ha implementado usando PGApack,udlibrería de dominio público que permite programar gran diversidad de algoritmosudgenéticos. Este modelo se ejecutará bajo una arquitectura de tipo SIMD con paso deudmensajes que permitirá la ejecución de hasta 8 procesos (islas) en paralelo. La comunicación entre procesos se realiza a través de MPI y el algoritmo simulará unaudtopología en anillo.ud[ABSTRACT]However, despite of their operational simplicity, parallel GAs are controlled by manyudparameters that affect to efficiency and quality of their search. Setting these parametersudcorrectly is crucial to obtain good solutions quickly. In particular, some of theseudparameters are the number and size of populations and the exchange rate between these.udTypically the parameters are found by systematic experimentation. The goal of this study is to obtain some conclusions and references to tune theudparameters and provide a guide to choose their values correctly, which find efficientudsolutions with high quality. This document combines theory and experimental results inudorder to allow the user can appreciate the effect of different parameters.udFor prepare the investigation, we have developed a kind of parallel GAs known asudIsland Model that we have implemented using PGAPACK, a public library forudprogramming GAs. This model will run in SIMD architecture with a message passingudparadigm which can be launched up to 8 processors (islands) in parallel. Theudcommunications among processors is realized with MPI and we have implemented theudalgorithm with a ring topology.ududud