Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.udec.cl/jspui/handle/11594/5508
Título : Selección automática de algoritmos anytime para coloreo de grafos.
Autor : Asín Achá, Roberto Javier; supervisor de grado
Ortega Cárcamo, Daniel Antonio
Palabras clave : Optimización Combinatoria;Aprendizaje de Máquina;Coloreo de Grafos
Fecha de publicación : 2021
Editorial : Universidad de Concepció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.
Descripción : Tesis para optar al grado de Magíster en Ciencias de la Computación.
URI : http://repositorio.udec.cl/jspui/handle/11594/5508
Aparece en las colecciones: Ingeniería Informática y Ciencias de la Computación - Tesis Magister

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Tesis Seleccion Automatica de algoritmos.Image.Marked.pdf4,64 MBAdobe PDFVista previa
Visualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons