Implementación de un algoritmo de evolución diferencial paralelo basado en unidades de procesamiento gráfico

Abstract

In this thesis the implementation of a Differential Evolution algorithm (ED) based parallel graphics processing units (GPUs) is presented. Applying the latest technology GPUs and CUDA programming environment allows to exploit the inherent parallelism in the differential evolutionary algorithm and reduce the computational effort associated with operations such as creating the initial population, evaluation of individuals, mutation and selection. The algorithm ED implemented in this thesis is a tool of global optimization, which is based on a search strategy that involves some level of greed, this through the inclusion of information about the best solution obtained at each iteration and derecombinación removal operation. This parallel implementation based on graphics processing units is evaluated with a set of optimization problems used as a reference in the literature. These problems involve the location and the calculation of global minimum of functions such as Rosenbrock function, Griewank and Ackley. A novel definition of the mutant vectors, in which the constant values ??of the control variables is replaced by random values ??is proposed. Moreover, implementation of the operation within the algorithm passes is omitted, getting through these two variants reducing the problems associated tuning parameters algorithm execution. Moreover, the effect of variation in the population size is analyzed in terms of accuracy, efficiency, and computation times acceleration factors. Significant improvements were reported in terms of execution times on two implementations programmed in C and executed on the CPU.

En esta tesis se presenta la implementación de un algoritmo de Evolución Diferencial (ED) paralelo basado en Unidades de Procesamiento Grafico (GPUs). La aplicación de la tecnología de ultima generación de las GPUs y el entorno de programación CUDA permiten explotar el paralelismo inherente en el algoritmo diferencial evolutivo y reducir el esfuerzo computacional asociado a operaciones tales como la creación de la población inicial, la evaluación de los individuos, la mutación y la selección. El algoritmo de ED implementado en esta tesis es una herramienta de optimización global, la cual está basada en una estrategia de búsqueda que involucra cierto nivel de voracidad, esto a través de la inclusión de información acerca de la mejor solución obtenida a cada iteración y la eliminación de la operación de recombinación. Esta implementación paralela basada en unidades de procesamiento gráfico se evalúa con un conjunto de problemas de optimización usados como referencia en la literatura especializada. Estos problemas involucran la localización y el cálculo del mínimo global de funciones tales como la función de Rosenbrock, Griewank y Ackley. Se propone una definición novedosa de los vectores mutantes, en la cual se sustituye los valores constantes de las variables de control por valores aleatorios. Además, se omite la implementación de la operación de cruza dentro del algoritmo, consiguiendo a través de estas dos variantes la reducción de los problemas asociados a la sintonización de los parámetros de ejecución del algoritmo. Por otra parte, el efecto de la variación en el tamaño de población es analizado en términos de precisión, eficacia, tiempos de cómputo y factores de aceleración. Se reportan mejoras significativas en términos de tiempos de ejecución con respecto a dos implementaciones programadas en C y ejecutadas en la CPU.