Soluciones cercanas al optimo para el problema del ladrón viajero a través de un algoritmo genético paralelo implementado en unidades de procesamiento grafico (gpus)

El problema del ladrón viajero (Traveling Thief Problem - TTP) es un nuevo e importante problema de optimización combinatoria que combina dos problemas destacados de la clase NP-Hard; los cuales son el problema del agente viajero (Traveling Salesman Problem - TSP) y el problema de la mochila (Knapsack Problem – KP). El TTP se ha intentado resolver mediante diferentes algoritmos y heurísticas; en la investigación propuesta en este documento se buscará una implementación sobre GPUs de un algoritmo genético paralelo para encontrar soluciones cercanas al óptimo por medio del uso exhaustivo del hardware de multiprocesamiento y el uso adecuado de los espacios de memoria. Los problemas puestos a prueba corresponden a destacados problemas de la literatura (Benchmark Problems) y los resultados de la ejecución serán comparados contra otros resultados documentados hasta ahora para determinar la validez de nuestro algoritmo

• Autores: Wisk, Sebastian
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2023
• Institución: Universidad Distrital Francisco José de Caldas
• Repositorio: RIUD: repositorio U. Distrital
• Idioma: spa
• OAI Identifier: oai:repository.udistrital.edu.co:11349/39119
• Acceso en línea: http://hdl.handle.net/11349/39119
• Palabra clave: Problema del ladrón viajero (TTP); Unidad de Procesamiento Grafico (GPU); Arquitectura unificada de dispositivos de cómputo (CUDA); Algoritmos geneticos paralelos; Maestría en Ciencias de la Información y las Comunicaciones -- Tesis y disertaciones académicas; Optimización combinatoria; Algoritmo genético paralelo; Benchmark problems; Traveling Thief Problem (TTP); Graphics Processing Unit (GPU); Compute Unified Device Architecture (CUDA); Parallel genetic algorithms
• License: Attribution-NonCommercial-NoDerivatives 4.0 Internacional