Tesis
Selección automática de algoritmos anytime para coloreo de grafos.
Autor
Ortega Cárcamo, Daniel Antonio
Institución
Resumen
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.