Por favor, use este identificador para citar o enlazar este ítem:
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 | |
| Aparece en las colecciones: | Tesis del CIMAT |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| TE 703.pdf | 2.37 MB | Adobe PDF | Visualizar/Abrir |