Algoritmo metaheurístico paralelo usando CUDA para solucionar problemas 0/1 Knapsack basado en el procedimiento de búsqueda del pescador

El problema 0/1 knapsack (P01K) es un problema de optimización combinatoria NP-complejo, en el cual el tiempo de solución es demasiado alto o inviable para grandes dimensiones, este tiempo puede ser reducido con el uso de Metaheurísticas Paralelas usando la GPU (MPG). Con 21 instancias del problema de diferentes dimensiones (100 a 10000) y tres diferentes tipos (no correlacionados, débilmente correlacionados y fuertemente correlacionados), se compararon diez metaheurísticas, cuatro secuenciales seleccionadas de estado del arte (MDSFL, MopGA, SBHS y SLC), cuatro MPG implementadas en base a las secuenciales, una propuesta PMG PBFSPG y su versión secuencial SBFSPG, usando las medidas tasa de éxito, número de evaluaciones de la función objetivo y tiempo de ejecución para cada una de las soluciones. De las metaheurísticas secuenciales estudiadas SBFSP es la mejor metaheurística secuencial resolviendo el 66.67% de las instancias de prueba con una tasa de éxito del 100%, en un tiempo máximo de 30 minutos, de las MPG aquella basada en MDSFL (PMDSFLG) es la mejor MPG resolviendo el 85.71% de las instancias de prueba con una tasa de éxito del 100% con un tiempo máximo de 40 segundos mientras PBFSP resuelve 80.95%, sin embargo al incrementar el tiempo de ejecución PBFSP resuelve el 100%, mientras PMDSFL se mantiene. La estrategia de metaheurísticas basadas en penalización como en MopGA y SLC no son una buena solución para problemas de mediana y grandes dimensiones, mientras una estrategia basada en reparación como en SBFSP, MDSFL, SBHS, y PBFSPG es escalable para grandes dimensiones además el uso de PMG reduce el tiempo de ejecución como en PBFSP respecto a SBFSP en promedio un 88.56%.

• Autores: Dulcey Moran, Hernán Guillermo; Ortega Ruiz, Johny Andrés
• Tipo de recurso: Trabajo de grado de pregrado
• Fecha de publicación: 2016
• Institución: Universidad del Cauca
• Repositorio: Repositorio Unicauca
• Idioma: spa
• OAI Identifier: oai:repositorio.unicauca.edu.co:123456789/1741
• Acceso en línea: http://repositorio.unicauca.edu.co:8080/xmlui/handle/123456789/1741
• Palabra clave: CUDA; Metaheurística; Penalización; Problema 0/1 knapsack; Reparación; GPU
• License: https://creativecommons.org/licenses/by-nc-nd/4.0/