Aplicación del algoritmo de duelistas al problema de la mochila multidimensional.

Abstract

El problema de la mochila multidimensional, conocido en el idioma inglés como “Multidimensional knapsack problem”, es un problema de optimización combinatoria de complejidad computacional NP-Hard. Este problema consiste en, dado un conjunto finito de elementos, seleccionar un subconjunto de elementos con el máximo valor posible, mientras se cumple simultáneamente con una lista de restricciones. El problema de la mochila multidimensional destaca por la simpleza de su formulación y por el número de aplicaciones prácticas que posee, entre las que se encuentra la selección de carga para transporte, la selección de un portafolio de activos de inversión, la selección de proyectos, el diseño de sistemas computacionales, y otros temas de gestión. En el presente informe de investigación, se expone un estado del arte sobre los distintos métodos aplicados al problema de la mochila multidimensional, los algoritmos exactos, las heurísticas, y las metaheurísticas, junto con el estudio de la aplicación del algoritmo de duelistas. Este último, es un algoritmo metaheurístico propuesto por Biyanto et al. en el año 2015, inspirado en las características, condiciones y la capacidad de aprendizaje de los seres humanos cuando se enfrentan en sucesivos duelos o competencias, situación que también aplica a los enfrentamientos que ocurren entre otros seres vivos, tanto individualmente como en grupos. Tras diseñar una parametrización para el algoritmo de duelistas, esta metaheurística se aplicó a algunas de las instancias de prueba del problema de la mochila multidimensional existentes en la literatura, obtenidas desde la Biblioteca de Investigación de Operaciones (OR-Library). Los resultados de la aplicación muestran que el algoritmo de duelistas entrega soluciones de muy alta calidad, cercanas a la solución óptima o igual a esta en algunos casos, y en tiempos computacionales razonables. Además, el algoritmo de duelistas tuvo un mejor desempeño promedio que otras metaheurísticas, tales como GRASP, Meta-RaPS y Simulated annealing. Sin embargo, tuvo un peor desempeño que un algoritmo genético.