Análisis comparativo de diferentes soluciones alternativas para el problema de la mochila

Abstract

En la actualidad la Computación Evolutiva se usa para buscar soluciones a problemas complejos para los que otras técnicas pueden insumir mucho tiempo y que, por lo general, proveen una única solución óptima. El problema considerado para este análisis, clasificado como NP-duro, es el zeroone knapsack problem, comúnmente conocido como el problema de la mochila. Este es un problema de planificación en el que, dada una mochila con una cierta capacidad y un conjunto de ítems que poseen un peso y un beneficio asociado para ser seleccionado, se busca encontrar planes de carga adecuado para llenar la misma con el mayor número de ítems y a la vez, tratando de lograr un máximo beneficio. Esta presentación muestra un trabajo donde se implementaron diversas soluciones propuestas a este problema por diversos autores: Martello y Toth [12], Michalewicz [13], Olsen [16], Liepins [10], Nakano [15] y Orvosh [17]. Las siguientes secciones muestran un análisis comparativo de la performance alcanzada en cada uno de ellos