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

Vista sencilla de ítem
dc.contributor.advisorGatica, Gustavo
dc.contributor.authorArroyo Bravo, Jecar
dc.contributor.editorFacultad de Ciencias Exactas
dc.date.accessioned2018-08-17T18:42:04Z
dc.date.available2018-08-17T18:42:04Z
dc.date.issued2018
dc.descriptionTesis (Ingeniero Físico, Magíster en Gestión de Proyectos Científicos y Tecnológicos)es_ES
dc.description.abstractSi 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.es_ES
dc.identifier.urihttp://repositorio.unab.cl/xmlui/handle/ria/6670
dc.language.isoeses_ES
dc.publisherUniversidad Andrés Belloes_ES
dc.subjectMinería de Datoses_ES
dc.subjectProblema del Vendedor Viajeroes_ES
dc.subjectOptimización Combinatoriaes_ES
dc.titleAná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 datoses_ES
dc.typeTesises_ES
Archivos
Bloque original
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
a122818_Arroyo_J_Analisis_del_impacto_en_la_2018_tesis.pdf
Tamaño:
1.66 MB
Formato:
Adobe Portable Document Format
Descripción:
TEXTO COMPLETO EN ESPAÑOL
Descargar
Bloque de licencias
Mostrando 1 - 1 de 1
No hay miniatura disponible
Nombre:
license.txt
Tamaño:
1.71 KB
Formato:
Item-specific license agreed upon to submission
Descripción:
Descargar
Colecciones
FCE - Trabajos de Titulación Post-Grado