Escudo de la República de Colombia
Sistema Nacional de Biliotecas - Repositorio Institucional Universidad Nacional de Colombia Biblioteca Digital - Repositorio Institucional UN Sistema Nacional de Bibliotecas UN

Heurística inspirada en el análisis sistémico del “Vecino más cercano”, para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio

Pérez Rave, Jorge Iván (2011) Heurística inspirada en el análisis sistémico del “Vecino más cercano”, para solucionar instancias simétricas TSP, empleando una base comparativa multicriterio. Maestría thesis, Universidad Nacional de Colombia, Sede Medellín.

Texto completo

[img] PDF - Versión Aceptada
Available under License Creative Commons Attribution Non-commercial No Derivatives.

1MB

Resumen

Esta tesis aporta evidencia que respalda al pensamiento sistémico como un pertinente campo de inspiración para el desarrollo de nuevos métodos de optimización heurística. Se delimita el alcance a la resolución del TSP simétrico como referente internacional de prueba que es. Se desarrollaron dos métodos: Sacrificio Cortoplacista Adaptativo 2-opt (SCA_2opt) y una versión mejorada (SCA_2_opt_r), los cuales son fruto del análisis sistémico de la regla vecino más cercano, encontrándole el arquetipo “Soluciones contraproducentes”. El SCA se basa en que el viajero renuncie en un momento dado a una ciudad inmediatamente cercana y se traslade hacia la segunda más cercana disponible, luego, el viajero continúa con la regla del vecino más cercano; cada que se realiza el SCA (búsqueda global) se efectúa una búsqueda local 2_opt. Las dos heurísticas resultan prometedoras en el balance entre eficacia y eficiencia en comparación con las heurísticas: vecino más cercano, Inserción más barata y 2-opt, y con 19 metaheurísticas en las categorías: Colonia de hormigas, Algoritmos genéticos, Enfriamiento simulado y Otras./Abstract. This thesis provides evidence that supports the relevant systems thinking as a field of inspiration for the development of new heuristic optimization methods. It delineates the scope of the resolution of the symmetric TSP as an international benchmark proves it. Two methods were developed: Adaptive short-term sacrifice 2-opt (SCA_2opt) and an enhanced version (SCA_2_opt_r), which are based on analysis systemic nearest neighbor rule, finding the archetypal "Solutions counterproductive ". The SCA is based on the traveler resign at any time a nearby town immediately and move to the second nearest available Of course, the traveler continues with the nearest neighbor rule, each SCA is performed (global search) is performed a local search 2_opt. The two heuristics are promising in the balance between effectiveness and efficiency compared to the heuristics: nearest neighbor, cheapest insertion and 2-opt, and with 19 metaheuristics in categories: ant colony, genetic algorithms, simulated annealing and Othe.

Tipo de documento:Tesis/trabajos de grado - Thesis (Maestría)
Colaborador / Asesor: Jaramillo Álvarez, Gloria Patricia
Palabras clave:Sacrificio cortoplacista adaptativo; Optimización Combinatoria; Metaheurísticas; Pensamiento sistémico; Heurística; Instancias simétricas TSP / Adaptive short-term sacrifice; Optimization combinatorics, Metaheuristics, Systems thinking; Heuristics; Symmetric TSP instances
Temática:0 Generalidades / Computer science, information & general works
Unidad administrativa:Sede Medellín > Facultad de Minas > Escuela de Sistemas
Código ID:5443
Enviado por : Biblioteca Sede Medellín Universidad Nacional de Colombia
Enviado el día :05 Dec 2011 20:09
Ultima modificación:05 Dec 2011 20:09
Ultima modificación:05 Dec 2011 20:09
Exportar:Clic aquí
Estadísticas:Clic aquí
Compartir:

Solamente administradores del repositorio: página de control del ítem

Vicerrectoría de Investigación: Número uno en investigación
Indexado por:
Indexado por Scholar Google WorldCat DRIVER Metabiblioteca OAIster BASE BDCOL Registry of Open Access Repositories SNAAC Red de repositorios latinoamericanos eprints Open archives La referencia Tesis latinoamericanas OpenDOAR CLACSO
Este sitio web se ve mejor en Firefox