Análisis de los parámetros de la biblioteca Lin-Kernighan mediante el diseño de un experimento computacional y su incidencia en los buenos resultados
Cargando...
Archivos
Fecha
2018
Autores
Cuellar Vistoso, Nelson
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
Los problemas de optimización deben enfrentar el obstáculo del costo computacional, de modo de hacer viable su resolución en un tiempo prudente. Sin embargo, la principal dificultad radica en que, si el costo computacional crece exponencialmente, hace inviable la resolución mediante un algoritmo lento, es decir, uno que recorra todas las soluciones posibles, entonces se recurre a la heurística para encontrar una alternativa a los algoritmos exactos resolviendo el problema en muchos menos pasos.
La heurística se conoce como un conjunto de métodos o técnicas para resolver un problema. La palabra heurística es de origen griego εὑρίσκειν [26] que significa “hallar, inventar”.
El problema del agente viajero o “Travelling Salesman Problem” (TSP) fue planteado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es un problema np-completo que computacionalmente es de una alta complejidad, y existen heurísticas y métodos exactos conocidos para encontrar soluciones. En palabras simpes, puede definirse como, dado una lista de ciudades con las distancias entre ellas conocidas, ¿Cuál es la ruta más corta visitar todas las ciudades una sola vez y volver a la ciudad inicial?
En los tipos de problema como el del TSP, nos enfrentamos a una barrera muy común para todo ser vivo: El tiempo. No se puede esperar toda la vida para resolución de un problema mediante un algoritmo exacto, de modo que, hallar técnicas heurísticas que faciliten una discriminación de algunas “variables”, posibilitaría realizar estos cálculos computacionales en un tiempo prudente.
Las técnicas heurísticas, de inteligencia artificial y otras con enfoques de evolución y comportamiento natural, han constituido en los últimos años las herramientas matemáticas principales para abordar el problema [28]. Sin embargo, en la bibliografía disponible se constata que, a pesar de los logros obtenidos, los mejores trabajos reflejados no satisfacen aún plenamente los requerimientos actuales de la industria. Esta realidad determina la necesidad de búsqueda de nuevos de procedimientos de solución a este problema que aseguren la obtención de mejores distribuciones [3].
La complejidad de resolver el TSP, un problema NP-hard, radica en cuando uno considera el número de rutas posibles. Para un problema simétrico de “c” ciudades hay (��−2)!2 posibles rutas. Esta relación factorial, hace que, para un número no tan grande de ciudades, las combinaciones posibles implican un costo computacional elevado, al tener que verificar una por una cual tiene el menor tiempo total. Por ejemplo, de haber solo 15 ciudades, el número de rutas posibles es aproximadamente 3.11��109.
Notas
Tesis (Ingeniero Físico)
Palabras clave
Minería de Datos, Optimización Combinatoria