Please use this identifier to cite or link to this item: http://cimat.repositorioinstitucional.mx/jspui/handle/1008/977
OPTIMIZACIÓN CON COMPONENTES INTERDEPENDIENTES EL PROBLEMA DEL LADRÓN VIAJERO
RICARDO NIETO FUENTES
Acceso Abierto
Atribución-NoComercial
Optimización
Algoritmo
En el área de optimización con metaheurísticas, algunos investigadores han sugerido que los modelos utilizados para validar el rendimiento de los optimizadores son demasiado simples al compararse con la complejidad de los problemas reales. Esto es atribuído a que los modelos académicos han omitido la complejidad derivada de la interdependencia que existe entre los subproblemas que componen la mayoría de los problemas reales. El problema del ladrón viajero [3] (Travelling Thief Problem — TTP) es un problema sintético y novedoso, diseñado para modelar la interdependencia presente en los pro- blemas reales. Combina dos problemas clásicos ampliamente estudiados por la academia, el problema del vendedor viajero (Travelling Salesman Problem — TSP) y el problema de la mochila (Knapsack Problem — KP). Desde su publicación, numerosas heurísticas han sido desarrolladas para la solución del TTP, las cuales pueden clasificarse en función de su enfoque en los siguientes grupos: centradas en TSP, codificación completa, sistema CoSolver, exactas y mixtas. Al analizar las características del TTP y los diferentes mecanismos empleados por las distintas estrategias, se hipotetiza que los enfoques actuales son propensos a centrarse rápidamente en una región del espacio de búsqueda, limitando su capacidad para obtener resultados de alta calidad a largo plazo. Este trabajo se enfoca en la familia de heurísticas dentro de la categoría CoSolver, las cuales alternan entre dos etapas de optimización, una enfocada en la mejora del recorrido y otra en la selección de objetos. En base a la hipótesis de trabajo, se proponen dos heurísticas para evitar el sesgo en la exploración del espacio de búsqueda. La primera estrategia consiste en una metaheurística de trayectoria (REStart with Guided Local Search — RESGLS) basada en la búsqueda local guiada (Guided Local Search — GLS), método que penaliza características presentes en el espacio de búsqueda que se hayan explorado en fases anteriores. La segunda consiste en un algoritmo memético (Diversity based Memetic Algorithm — DMA), que incorpora un control explícito de diversidad para forzar la exploración del espacio de búsqueda. Este método, además, incorpora la estrategia basada en la búsqueda local guiada para mejorar la intensificación realizada en cada zona explorada. Ambas propuestas son comparadas frente a algoritmos específicos para el TTP presentes en la literatura. Los resultados obtenidos, indican que los algor
10-12-2018
Tesis de maestría
LENGUAJES DE PROGRAMACIÓN
Versión aceptada
acceptedVersion - Versión aceptada
Appears in Collections:Tesis del CIMAT

Upload archives


File SizeFormat 
TE 703.pdf2.37 MBAdobe PDFView/Open