Diseño e implementación de modelo de search trajectory networks adaptado al sintonizador irace

Abstract

La configuración adecuada de parámetros en algoritmos metaheurísticos es esencial para asegurar su buen rendimiento, dado que estos algoritmos suelen operar en espacios de búsqueda complejos y con alto grado de variabilidad. En este contexto, esta memoria presenta STN-i, un modelo de Search Trajectory Networks adaptado al configurador automático irace, cuyo propósito es representar, visualizar y analizar estructuralmente el proceso de sintonización de parámetros. La propuesta permite modelar configuraciones, relaciones de generación e información estructural, e incluye además una variante denominada merged STN-i para el análisis comparativo entre múltiples ejecuciones. La validación se lleva a cabo sobre tres algoritmos metaheurísticos (MMASQAP, ACOTSP y PSO-X), cinco conjuntos de instancias y distintas condiciones de presupuesto y uso del mecanismo de soft-restart, generando 60 redes STN-i y 30 merged STN-i, construidas a partir de tres discretizaciones del espacio paramétrico. A través de métricas estructurales y visualizaciones mediante layouts de fuerza, se identifican patrones relevantes como trayectorias dominantes, zonas de convergencia y divergencia, y regiones compartidas entre ejecuciones. Los resultados evidencian que STN-i entrega una representación detallada y explicativa del comportamiento de irace, fortaleciendo su análisis, interpretación y comparación estructural en contextos de configuración automática. The proper configuration of parameters in metaheuristic algorithms is essential to ensure their effective performance, as these algorithms typically operate over complex and highly variable search spaces. In this context, this thesis presents STN-i, a Search Trajectory Network model adapted to the automatic configurator irace, aimed at representing, visualizing, and structurally analyzing the parameter tuning process. The proposed model captures configurations, generative relationships, and structural information, and includes a variant called merged STN-i, designed for comparative analysis across multiple runs. Validation is carried out using three metaheuristic algorithms (MMASQAP, ACOTSP, and PSO-X), five instance sets, and varying conditions of computational budget and use of the soft-restart mechanism, resulting in 60 STN-i networks and 30 merged STN-i networks built from three levels of parameter space discretization. Using structural metrics and force-directed visualizations, the model identifies relevant patterns such as dominant trajectories, convergence and divergence zones, and shared regions across executions. The results show that STN-i provides a detailed and explanatory representation of irace’s behavior, enhancing its structural analysis, interpretability, and comparative insight in the context of automatic configuration.