Cómputo multi-núcleo aplicado a algoritmos genéticos.

Abstract

Se presenta la paralelización de un Algoritmo Genético (AG) en diferentes arquitecturas multinúcleo para la optimización de la trayectoria del movimiento de un brazo robótico de dos grados de libertad. La aplicación se llevó a cabo utilizando la versión 4 del toolbox de cómputo paralelo de MatLab R2008a, bajo los sistemas operativos GNU/Linux y Windows XP. Las computadoras utilizadas cuentan con arquitectura de dos y cuatro núcleos. La aplicación simula el movimiento de un brazo de robot con dos articulaciones que va de un punto a otro evitando colisiones con un obstáculo, el AG busca la ruta más corta creando una población de 32 individuos donde cada individuo representa una posible solución al problema. Se analizó el AG y se identificó a la etapa del cálculo de la aptitud como módulo de alto rendimiento, la cual fue paralelizada exitosamente. Se muestra cómo un AG que toma mucho tiempo en resolver un problema de optimización, se puede transformar en un Algoritmo Genético Paralelo (AGP), reduciendo significativamente el tiempo de ejecución del mismo conforme crece el número de núcleos. La aplicación se desarrolló de tal manera que se pueda ejecutar bajo cualquier sistema operativo que soporte MatLab, con cualquier procesador multi-núcleo sin la necesidad de modificar o adaptar el sistema, cumpliendo con las propiedades de portabilidad y escalabilidad. Finalmente, se presenta el incremento en el rendimiento alcanzado por parte del AGP con relación al AG original, así como una estimación del ahorro en el tiempo de ejecución que pudiera alcanzar la aplicación para un máximo de 30 núcleos. __________________________________

This work presents the parallelization of a genetic algorithm (GA) in different multi-core architectures to optimize the movement path of a robotic arm with two degrees of freedom. The application was implemented using the parallel computing toolbox v. 4 included in MatLab R2008a under the GNU / Linux and Windows XP operating systems. The computers architecture used for this work have two and four cores. The application simulates the movement of a robot arm with two articulations that goes from one point to another avoiding collision with an obstacle; the GA seeks the shortest route within a population of 32 individuals where each individual represents a possible solution to the problem. The GA was analyzed and it was identified the stage of the calculation of fitness as a high performance module, which was successfully parallelized. It is shown how GA that takes a long time to resolve an optimization problem can be transformed into a parallel genetic algorithm (PGA), significantly reducing the execution time as the number of cores grows. The application was developed so that it can run under any operating system that supports MatLab, with any multi-core processor without the necessity to modify or adapt the system in compliance with the properties of portability and scalability. Finally, it is presented the speedup achieved by the PGA in relation to the original GA, as well as an estimated speedup that the application could reach for a maximum of 30 cores.