Una gran variedad de problemas del mundo real pueden ser formulados de tal forma que sea necesario encontrar el óptimo global (o la mejor aproximación a él) de una función sujeta a varios parámetros o variables de decisión en un espacio de búsqueda continuo. Este tipo de problemas son conocidos como problemas de optimización global (OG) y varias técnicas han sido desarrolladas para su solución, siendo mayormente aplicadas las metaheurísticas debido las diversas restricciones de uso de los métodos exactos (por ejemplo, aquellos basados en el gradiente de la función a optimizarse). Dentro del mundo de las metaheurísticas existe una familia de algoritmos, llamados evolutivos (AEs), los cuales han sido aplicados a problemas de OG por décadas, destacándose el algoritmo de evolución diferencial (ED). La ED es un algoritmo bio-inspirado, basado en población y de naturaleza estocástica cuyo primer paso es inicializar una población de forma aleatoria. Después, durante generaciones (empleando dos operadores especiales), guía a los individuos hacia un óptimo global. Sin embargo, existe evidencia experimental indicando que el rendimiento de la ED (y de las metaheurísticas en general) se deteriora drásticamente al aumentar la dimensionalidad del problema, particularmente cuando el problema cuenta con cientos o miles de variables. Este tipo de problemas son denominados de optimización global a gran escala (OGGE). Se han propuesto varios algoritmos para la resolución de problemas a gran escala. Las propuestas que mejores resultados han mostrado generalmente siguen un enfoque de diseño basado en descomposición (divide y vencerás) o un enfoque de diseño sin descomposición pero basado en el concepto de hibridación el cual consiste en combinar las mejores características de dos o más algoritmos para formar uno nuevo buscando que supere a cualquiera de sus componentes. La ED ha sido empleada en ambos casos, destacándose su uso en algoritmos híbridos como componente de búsqueda global (exploración) el cual usualmente está acoplado a un componente de búsqueda local (explotación). En estos casos, la etapa de explotación es generalmente manejada por un método de búsqueda local puro (no basado en población) el cual puede o no estar basado en el uso del gradiente. Respecto a su uso en algoritmos basados en descomposición, la ED se suele emplear como optimizador para resolver los subproblemas.
En esta tesis proponemos un nuevo algoritmo basado en la evolución diferencial, particularmente en una de sus variantes adaptativas conocida como evolución diferencial empleando adaptación de parámetros basado en el historial de éxito (SHADE, por sus siglas en inglés). La nueva propuesta no sigue un enfoque de diseño basado en descomposición ya que consideramos relevante la tarea de escalar la ED a problemas de alta dimensionalidad sin recurrir al paradigma divide y vencerás. Así mismo, la idea subyacente al nuevo diseño no es explotar el potencial de combinar a la ED con otros métodos sino el potencial de combinar diferentes variantes de la ED. Como resultado, la nueva propuesta (denominada GL-SHADE) integra dos poblaciones que colaboran entre sí durante el proceso de optimización; la primera de ellas cambia acorde con un esquema de evolución especializado en búsqueda global mientras que la segunda población evoluciona de acuerdo con un esquema especializado en búsqueda local. La interacción entre poblaciones es llevada a cabo mediante un operador sencillo de migración. Adicionalmente, la implementación de GL-SHADE es llevada a cabo mediante el uso de GPUs con el fin de acelerar su tiempo de ejecución promedio. Los resultados experimentales obtenidos (se emplea el conjunto de funciones de prueba CEC’13 LSGO) indican que la nueva propuesta es competitiva con respecto a algoritmos del estado del arte en el área de OGGE además de exhibir un desempeño superior al del mejor algoritmo no basado en descomposición e híbrido conocido hasta el momento (el cual hace uso de la ED como componente de búsqueda global). Adicionalmente, los estudios estadísticos elaborados muestran que el algoritmo de GLSHADE exhibe un mejor desempeño que cualquiera de sus bloques constructores indicando que la combinación adecuada de diferentes estrategias de evolución es capaz de potenciar el motor de búsqueda tanto como la combinación de la ED con diferentes algoritmos. Finalmente, las pruebas de tiempo efectuadas sobre las implementaciones en paralelo (CUDA) y secuencial (C++) de GL-SHADE indican que la aceleración alcanzada depende del problema de prueba adoptado como función objetivo. No obstante, en la mayoría de los casos la implementación paralela de GL-SHADE logra una aceleración de al menos 2x respecto a su implementación secuencial.
Abstract
A great variety of world problems can be formulated in such a way that it is necessary to find the global optimum (or the best approximation to it) of a function subject to several decision variables on a continuous search space. These are known as global optimization (GO) problems and several techniques have been developed to solve them. Metaheuristics have been mostly applied in them, given the many restrictions for using exact methods (e.g., those requiring the gradient of the function to be optimized). Within the realm of metaheuristics the so-called evolutionary algorithms (EAs) have been applied to GO problems for decades, from which differential evolution (DE) has been widely adopted. DE is a stochastic, population-based, bio-inspired algorithm whose first step is to initialize a population randomly. Then, for generations (using two special operators), it guides individuals toward a global optimum. However, there is experimental evidence indicating that the performance of DE (and of metaheuristics in general) deteriorates drastically when increasing the dimensionality of the problem, particularly when the problem has hundreds or thousands of variables. These are known as large-scale global optimization (LSGO) problems. Several algorithms have been proposed for solving large-scale problems. The proposals that have shown the best results generally follow a design based on decomposition (divide-and-conquer) or a design based on the concept of hybridization, which consists of combining the best characteristics of two or more algorithms to form a new one aiming to overcome any of its single components. DE has been adopted in both cases, highlighting its use in hybrid algorithms as a global search component (exploration) which is usually coupled to a local search component (exploitation). In these cases, the exploitation stage is generally managed by a pure (non-population based) local search method which may or may not be gradient-based. Regarding its use in decomposition-based algorithms, it has been adopted as an optimizer to solve subproblems.
In this thesis we propose a new algorithm based on differential evolution, particularly in one of its adaptive variants known as differential evolution using the adaptation of parameters based on the history of success (SHADE). The new proposal does not follow a decomposition-based design approach as we aimed to scale DE to high dimensionality problems without resorting on the divide-and-conquer paradigm. Likewise, the idea behind the new design is not to exploit the potential of combining DE with other methods, but the potential to combine different DE variants. As a result, the new proposal (called GL-SHADE) integrates two populations that collaborate with each other during the optimization process. The first of them changes according to a scheme specialized in global search while the second population evolves according to a scheme specialized in local search. The interaction between populations is carried out using a simple migration operator. Furthermore, the implementation of GL-SHADE is carried out using GPUs in order to speed up its average execution time. The experimental results obtained (the set of test functions CEC’13 LSGO was adopted) indicate that the new proposal is competitive with respect to several state-of-the-art LSGO algorithms. Additionally, the proposed approach has a better performance than that of the best algorithm known so far, which is not based on decomposition and is hybrid (it makes use of DE as a global search component). Additionally, the statistical studies carried out show that the proposed GL-SHADE algorithm exhibits a better performance than any of its building blocks, indicating that the appropriate combination of different evolution strategies is capable of enhancing the search engine analogously to the combination of DE with different methods. Finally, the tests carried out on the GL-SHADE parallel (CUDA) and sequential (C++) implementations indicate that the speed up achieved depends on the test problem adopted. However, in most cases, a speed up of at least 2x was achieved when comparing the execution time of the sequential and parallel implementations of GL-SHADE.
