Diseño e implementación paralela de un sintonizador de parámetros

Abstract

La optimización es la capacidad de resolver problemas de forma eficiente, lo que es asociado a la elección de la mejor opción dentro de un conjunto de posibles alternativas. La toma de esta decisión es aplicable en diversos ámbitos de nuestra vida diaria, como la producción y distribución de periódicos, el diseño de rutas para sistemas de transporte, la asignación de puertas de vuelo, entre otros. No obstante, debido a la complejidad NP-difícil de muchos de estos problemas, su solución a menudo requiere el uso de metaheurísticas. Si bien estas técnicas permiten obtener soluciones de alta calidad en un tiempo razonable, surgen desafíos al tener que determinar los valores adecuados para sus parámetros. Para abordar esta problemática se introducen los sintonizadores de parámetros, técnicas que han sido propuestas en la literatura para obtener valores adecuados exitosamente. Sin embargo, su uso emplea grande tiempos de ejecución al considerar: (1) un espacio de búsqueda enorme; y (2) múltiples ejecuciones del algoritmo objetivo en el proceso de sintonización. En este contexto, se presenta PEVOCA, una versión en paralelo del sintonizador Evolutionary Calibrator (EVOCA), diseñada para reducir su tiempo de ejecución sin comprometer la calidad de las soluciones obtenidas. PEVOCA implementa una arquitectura MIMD para obtener las aptitudes individuales de cada configuración, al hacer uso de hebras concurrentes por medio de la programación en multiprocesadores. Se evaluó sintonizando dos algoritmos: un Algoritmo Genético para resolver NK-landscapes (GA-NK) y un Algoritmo de Optimización de Colonias de Hormigas para resolver el problema de la Mochila Multidimensional (AK). Además, se ha logrado determinar en qué casos esta implementación no ofrece beneficios en comparación a su versión secuencial. En específico, este escenario se presenta cuando la sincronización de las hebras concurrentes es mayor que la ejecución de las múltiples instancias del algoritmo objetivo, en cuyo caso, los tiempos globales son significativamente inferiores a los casos complejos. Sin embargo, independientemente de si se genera una mejora, se han obtenido las mismas configuraciones para ambas implementaciones. Todo ello demuestra la eficiencia y eficacia de PEVOCA, como una herramienta prometedora para la búsqueda de configuraciones adecuadas. Optimization is the ability to efficiently solve problems, which is associated with selecting the best option from a set of possible alternatives. Making such decisions is applicable in various aspects of our daily lives, such as newspaper production and distribution, designing routes for transportation systems, allocating flight gates, among others. However, due to the NP-hard complexity of many of these problems, their solutions often require the use of metaheuristics. Although these techniques enable obtaining high-quality solutions in a reasonable time, challenges arise when determining suitable parameter values. To address this issue, parameter tuners are introduced, which are techniques proposed in the literature to successfully obtain appropriate values. Nevertheless, their use implies considerable execution times due to (1) an extensive search space and (2) multiple runs of the objective algorithm in the tuning process. In this context, PEVOCA is presented, a parallel version of the Evolutionary Calibrator (EVOCA) tuner designed to reduce its execution time without compromising the quality of the solutions obtained. PEVOCA implements a MIMD architecture to assess individual fitness values for each configuration by utilizing concurrent threads through multiprocessor programming.Two algorithms were evaluated using the tuning process: a Genetic Algorithm to solve NK-landscapes (GA-NK) and an Ant Colony Optimization Algorithm to solve the Multidimensional Knapsack Problem (AK). Additionally, it has been determined under which circumstances this implementation does not provide benefits compared to its sequential implementation. Specifically, this scenario occurs when the synchronization of concurrent threads is higher than the execution of multiple instances of the target algorithm, in which case the overall times are significantly lower than complex cases. However, regardless of whether an improvement is achieved, the same configurations have been obtained for both im plementations. All of this demonstrates the efficiency and effectiveness of PEVOCA as a promising tool for searching suitable configurations.