Selección automática de algoritmos anytime para coloreo de grafos.

Abstract

Las distintas técnicas de solución a problemas de optimización combinatoria permiten abordar problemas computacionalmente difíciles. Sin embargo, de manera general, la pertinencia de cada técnica depende de cada escenario específico. Este escenario puede estar compuesto por una instancia particular del problema y de recursos computacionales concretos. Dependiendo de la combinación de estos factores, no es trivial identificar cuál de las técnicas de solución es la más adecuada. Debido a lo anterior, en esta tesis se propone desarrollar un “oráculo”, basado en técnicas de machine learning, capaz de discriminar, dentro de un portafolio de alternativas, cuál es la más adecuada para solucionar una instancia específica considerando un tiempo límite de ejecución concreto. El dominio de aplicación de este oráculo es el Problema de Coloreo de Grafos, que es un problema ampliamente estudiado y que presenta interés tanto a nivel teórico como práctico. En la presente investigación se presenta el trabajo desarrollado en relación a la generación de datos de entrenamiento y validación, la caracterización de instancias y el proceso completo de aprendizaje de máquina asociado a estos datos. Se propusieron, desarrollaron y evaluaron diversos modelos de aprendizaje, basados tanto en clasificación como en regresión. Estos modelos fueron optimizados de acuerdo a diferentes métricas y se analizaron sus resultados para discriminar la alternativa más adecuada a la tarea. Finalmente, el modelo más apropiado fue evaluado en un escenario tipo competencia y se pudieron extraer conclusiones respecto a la efectividad y utilidad práctica del enfoque propuesto. Entre los modelos generados, el más adecuado corresponde a un modelo de clasificación, guiado por la métrica GM. Para éste se identificó un conjunto significativo (mínimo) de características de entrada, con el objetivo de disminuir lo más posible el tiempo necesario de predicción, sin perder calidad en la recomendación del método de solución más adecuado. Los resultados nos permiten concluir que es posible desarrollar modelos de aprendizaje efectivos para la tarea. Sin embargo, en el caso específico de coloreo de grafos, su utilidad práctica es limitada, debido al nivel de dominancia que tienen los solvers Head y HybridEA a lo largo del conjunto de datos. Otro desafío importante es minimizar el tiempo necesario para extraer las características de entrada de los modelos de aprendizaje y hacer el cómputo necesario para la predicción del oráculo.