Selección automática de algoritmo a lo largo del tiempo para el problema del vendedor viajero.

Abstract

Los problemas de optimización combinatoria están presentes en muchas aplicaciones del mundo real, por ejemplo, en el despliegue de recursos en la nube, en la búsqueda de caminos óptimos para empresas de transporte, en el diseño computacional de proteínas, en la construcción de microchips o en la asignación de los mejores horarios posibles para las clases en colegios y universidades. Aunque muchos de estos problemas son NP-hard, necesitan ser resueltos de tal manera de encontrar una solución tan buena y tan rápida como sea posible. En muchos casos, una pequeña mejora en la calidad de la solución se traduce en el ahorro de millones de dólares o en un aumento de la productividad. Para muchos problemas de optimización combinatoria existe un amplio número de publicaciones que presentan nuevos enfoques de solución y reportan avances en el área. Sin embargo, la mayoría de las mejoras en el rendimiento se relacionan a un conjunto de datos específico o a una caracterización del problema. En la mayoría de los casos, cuando probamos con datos distintos, esta mejora de rendimiento desaparece (Teorema No free lunch [1]). Por lo tanto, en el mundo real se utiliza una combinación de distintas técnicas o algoritmos que resuelven el problema dependiendo de las características de la instancia [2]. La combinación de distintos algoritmos que resuelven un problema de optimización combinatoria se puede llevar a cabo en la práctica mediante un oráculo predictor que nos indique a partir de un portafolio de algoritmos cuál de ellos es el mejor para resolver una instancia dada, por lo tanto, lo que llamaremos un metasolver corresponde a un algoritmo compuesto de dos etapas: primero una etapa predictora en donde se escoge el mejor algoritmo y luego la resolución de la instancia con el algoritmo seleccionado. El problema de escoger el mejor algoritmo posible para una instancia específica de un problema ha sido establecido en la comunidad de machine learning y es conocido como Auto matic Algorithm Selection Problem (AASP) [3]. En general, este problema es visto como un problema de clasificación [4] cuyo objetivo es aprender el comportamiento de distintos solvers sobre un conjunto de instancias y generalizar sobre instancias desconocidas. Dada una instancia específica, la predicción del modelo entrega el algoritmo (desde ahora solver) que se espera que obtenga la mejor solución.