Please use this identifier to cite or link to this item: http://repositorio.udec.cl/jspui/handle/11594/5850
Title: Aplicación del algoritmo de duelistas al problema de la mochila multidimensional.
Authors: Medina Durán, Rosa, supervisora de grado
Villarroel Olavarría, Nicolás Ignacio
Keywords: Algoritmos -- Estudio y Enseñanza;Algoritmos Genéticos;Programación de la Producción;Heurística;Programación (Matemáticas);Optimización Combinatoria
Issue Date: 2019
Publisher: Universidad de Concepción, Facultad de Ingeniería, Departamento de Ingeniería Industrial.
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.
Description: Memoria de título para optar al Título de Ingeniero Civil Industrial.
URI: http://repositorio.udec.cl/jspui/handle/11594/5850
metadata.dc.source.uri: https://go.openathens.net/redirector/udec.cl?url=http://tesisencap.udec.cl/concepcion/villarroel_o_n/index.html
Appears in Collections:Ingeniería Industrial - Tesis Pregrado

Files in This Item:
File Description SizeFormat 
Villarroel Olavarría, Nicolás Iignacio.pdf132,05 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.