Diseño e implementación de criterios de aceptación para la configuración automática de algoritmos utilizando irace

Abstract

Las metaheurísticas requieren definir parámetros adecuados, ya que su rendimiento depende drásticamente de los valores asignados a los parámetros. El algoritmo irace es un método de configuración de algoritmos que utiliza eficazmente los recursos computacionales disponibles para buscar valores de parámetros adecuados. Sin embargo, irace puede sufrir de convergencia prematura, evaluando configuraciones de parámetros que son similares entre sí en términos de sus valores. Este trabajo propone una estrategia para aumentar la exploración realizada por irace utilizando dos algoritmos de clustering, grid-based y k-medoids. La idea es agrupar configuraciones élite según las áreas del espacio de parámetros y seleccionar configuraciones de estos grupos para influir en el muestreo de nuevas configuraciones. Para evaluar nuestra propuesta, configuramos el conocido marco de optimización de colonia de hormigas considerando tres escenarios: un escenario homogéneo (TSP con 2000 ciudades), un escenario ligeramente menos homogéneo (TSP con 1000-3000 ciudades) y un escenario heterogéneo (QAP con dos niveles de dispersión). Los resultados muestran que incluir nuestra estrategia permite aumentar el nivel de exploración de irace y en algunos casos, obtener mejores resultados, alcanzando configuraciones que son estructuralmente diferentes, pero con compensaciones de rendimiento dependientes del escenario.Metaheuristics require defining appropriate parameters, as their performance drastically depends on the values assigned to the parameters. The irace algorithm is a well-known and powerful algorithm configuration method that effectively utilizes available computational resources to automatically search for suitable parameter values. However, irace can suffer from premature convergence, suggesting and evaluating parameter configurations that are similar to each other in terms of their parameter values. This work proposes a strategy to increase the exploration performed by irace using two clustering algorithms, grid-based and k-medoids. The idea is to group elite configurations according to the areas of the parameter space to which they belong and to select parent configurations from these groups, influencing the sampling of new configurations and extending the exploration iv capabilities of irace. To evaluate our proposal, we configure the well-known Ant Colony Optimization framework considering three scenarios: a omogeneous scenario (TSP instances with 2000 cities), a slightly less homogeneous scenario (TSP instances with 1000-3000 cities), and a heterogeneous scenario (QAP instances with two levels of dispersion). The results show that including our strategy allows increasing the level of exploration of irace and in some cases obtaining better results, reaching configurations that are structurally different but have scenario-dependent performance trade-offs.