Un enfoque de aprendizaje automático para la selección de algoritmos para el cálculo exacto del ancho del árbol
Autores: Slavchev, Borislav; Masliankova, Evelina; Kelk, Steven
Idioma: Inglés
Editor: MDPI
Año: 2019
Acceso abierto
Artículo científico
2019
Un enfoque de aprendizaje automático para la selección de algoritmos para el cálculo exacto del ancho del árbol
Categoría
Ingeniería y Tecnología
Subcategoría
Ingeniería de Software
Palabras clave
Marco de selección de algoritmos
Aprendizaje automático
Cálculo exacto
Anchura del árbol
Metaalgoritmo
Importancia de las características del grafo
Licencia
CC BY-SA – Atribución – Compartir Igual
Consultas: 38
Citaciones: Sin citaciones
Presentamos un marco de selección de algoritmos basado en aprendizaje automático para el cálculo exacto de , un parámetro de gráficos estudiado intensamente que es difícil de calcular. Específicamente, analizamos el rendimiento comparativo de tres algoritmos exactos de treewidth de última generación en una amplia variedad de gráficos y utilizamos esta información para predecir cuál de los algoritmos, en base a gráfico por gráfico, calculará la treewidth más rápidamente. Los resultados experimentales muestran que el meta-algoritmo propuesto supera a los métodos existentes en instancias de referencia en las tres métricas de rendimiento que utilizamos: en resumen, calcula la treewidth más rápido que cualquier algoritmo individual de forma aislada. Analizamos nuestros resultados para obtener información sobre la importancia de las características del gráfico y las fortalezas y debilidades de los algoritmos que utilizamos. Nuestros resultados son una evidencia adicional de las ventajas que se pueden obtener al combinar estratégicamente enfoques de aprendizaje automático y optimización combinatoria dentro de un marco algorítmico híbrido. El modelo de aprendizaje automático que utilizamos es intencionalmente simple para enfatizar que la aceleración ya se puede obtener sin tener que involucrarse en las complejidades completas de la ingeniería de aprendizaje automático. Reflexionamos sobre cómo el trabajo futuro podría ampliar este concepto simple pero efectivo mediante la implementación de modelos de aprendizaje automático más sofisticados.
Descripción
Presentamos un marco de selección de algoritmos basado en aprendizaje automático para el cálculo exacto de , un parámetro de gráficos estudiado intensamente que es difícil de calcular. Específicamente, analizamos el rendimiento comparativo de tres algoritmos exactos de treewidth de última generación en una amplia variedad de gráficos y utilizamos esta información para predecir cuál de los algoritmos, en base a gráfico por gráfico, calculará la treewidth más rápidamente. Los resultados experimentales muestran que el meta-algoritmo propuesto supera a los métodos existentes en instancias de referencia en las tres métricas de rendimiento que utilizamos: en resumen, calcula la treewidth más rápido que cualquier algoritmo individual de forma aislada. Analizamos nuestros resultados para obtener información sobre la importancia de las características del gráfico y las fortalezas y debilidades de los algoritmos que utilizamos. Nuestros resultados son una evidencia adicional de las ventajas que se pueden obtener al combinar estratégicamente enfoques de aprendizaje automático y optimización combinatoria dentro de un marco algorítmico híbrido. El modelo de aprendizaje automático que utilizamos es intencionalmente simple para enfatizar que la aceleración ya se puede obtener sin tener que involucrarse en las complejidades completas de la ingeniería de aprendizaje automático. Reflexionamos sobre cómo el trabajo futuro podría ampliar este concepto simple pero efectivo mediante la implementación de modelos de aprendizaje automático más sofisticados.