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

Abstract

A pesar de su simplicidad operacional los AGs paralelos están controlados por múltiples parámetros que afectan a la eficiencia y a la calidad de las soluciones encontradas. Fijar estos parámetros correctamente, buscando un equilibrio entre ellos, es fundamental para obtener buenas soluciones rápidamente intentado no desaprovechar recursos de computación. Concretamente, algunos de los parámetros a determinar son el número y el tamaño de las poblaciones y la frecuencia de intercambio entre ellas. Habitualmente estos 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 y ser una guía para elegir los valores adecuados con los que obtener soluciones eficientes y de alta calidad. Este documento combina la teoría con los resultados experimentales con los que se puede apreciar el efecto de los diversos parámetros. Para elaborar la investigación se ha desarrollado un tipo de algoritmo genético paralelo conocido como modelo de islas (Island Model) y se ha implementado usando PGApack, librería de dominio público que permite programar gran diversidad de algoritmos genéticos. Este modelo se ejecutará bajo una arquitectura de tipo SIMD con paso de mensajes 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á una topología en anillo. [ABSTRACT]However, despite of their operational simplicity, parallel GAs are controlled by many parameters that affect to efficiency and quality of their search. Setting these parameters correctly is crucial to obtain good solutions quickly. In particular, some of these parameters are the number and size of populations and the exchange rate between these. Typically the parameters are found by systematic experimentation. The goal of this study is to obtain some conclusions and references to tune the parameters and provide a guide to choose their values correctly, which find efficient solutions with high quality. This document combines theory and experimental results in order to allow the user can appreciate the effect of different parameters. For prepare the investigation, we have developed a kind of parallel GAs known as Island Model that we have implemented using PGAPACK, a public library for programming GAs. This model will run in SIMD architecture with a message passing paradigm which can be launched up to 8 processors (islands) in parallel. The communications among processors is realized with MPI and we have implemented the algorithm with a ring topology.