Análisis del impacto en la calidad de la solución de los parámetros de la biblioteca LKH para la resolución del problema del vendedor viajero mediante técnicas de minería de datos
Cargando...
Archivos
Fecha
2018
Autores
Profesor/a Guía
Facultad/escuela
Idioma
es
Título de la revista
ISSN de la revista
Título del volumen
Editor
Universidad Andrés Bello
Nombre de Curso
Licencia CC
Licencia CC
Resumen
Si poseo una lista de ciudades conociendo la distancia entre cada una de ellas, donde se desea responder ¿Cuál es la ruta óptima, para visitar cada ciudad una y sólo una vez, finalizando en el punto de partida? Este cuestionamiento es llamado el problema del vendedor viajero o traveling salesman problem (TSP por sus siglas en inglés). Con el tiempo se ha vuelto un típico problema de optimización combinatoria, la importancia del TSP es la diversidad de aplicaciones en distintas disciplinas, lo que ayuda a formular problemas del mundo real utilizando como base el TSP. Entre algunas aplicaciones prácticas se encuentran en las áreas de logística de transporte, robótica, electrónica, control, secuenciamiento de genes, astronomía, economía, entre otros.
Se plantea el origen y formulación teórica del TSP, exponiendo algunos algoritmos existentes que resuelven el TSP.
Para cumplir los objetivos planteados se utiliza el algoritmo heurístico de Lin-Kernighan (LKH), el cuál es considerado uno de los algoritmos más exitosos que genera soluciones factibles para el TSP, utilizando la biblioteca LKH en 4 instancias de distintas simetrías seleccionadas de la literatura, donde se analiza la influencia de los parámetros de LKH en la calidad soluciones, todo esto mediante técnicas de minería de datos.
La configuración de parámetros a utilizar será equivalente para los 4 experimentos, seleccionando un conjunto de parámetros relevantes, llevando a una minimización de recursos computacionales utilizada para este fin.
Utilizando los modelos de Regresión Lineal, Arboles de Decisión y Maquina de Soporte Vectorial, son aplicados a las bases de datos generadas por LKH realizando un análisis con un método de selección de atributos y otro sin selección de atributos, comparando ambos resultados. Los resultados obtenidos muestran los métodos de mejor y peor desempeño, discriminando mediante el porcentaje de clasificación correcta de los datos, además se observaron las diferencias entre los análisis con selección de atributos y sin selección de atributos, notando que los modelos aplicados experimentaron diferencias sustanciales en la precisión para clasificar correctamente los datos. Se identifica cuales parámetros tienen un impacto en la calidad de las soluciones y en el tiempo de cómputo para las instancias TSP.
Notas
Tesis (Ingeniero Físico, Magíster en Gestión de Proyectos Científicos y Tecnológicos)
Palabras clave
Minería de Datos, Problema del Vendedor Viajero, Optimización Combinatoria