Frameworks basados en metaheurísticas para resolver el problema de la mochila
Fecha
2019-03-04Autor
Jiménez-Castellano, Isela
Hernández-Ocaña, Betania
Hernández-Torruco, José
Chávez-Bosquez, Oscar
Metadatos
Mostrar el registro completo del ítemResumen
Actualmente existen frameworks que permiten reutilizar código diseñado ex profeso para resolver diversos
problemas, entre los que destacan aquellos que implementan metaheurísticas para resolver problemas de optimización. El
problema de la mochila es uno de los ejemplos de optimización clásicos usado a menudo como problema de prueba debido a
su sencillez y al mismo tiempo su complejidad: pertenece a la categoría de problemas NP-Completos, considerados difíciles
computacionalmente. En este artículo se implementaron los algoritmos de tres frameworks de metaheurísticas de diferentes
familias para resolver una variante del problema: el problema de la mochila 0-1. Los frameworks seleccionados fueron: JACOF
(Algoritmos de Colonia de Hormigas), JAMES (Algoritmos basados en Trayectoria), y MOEA (Algoritmos Evolutivos). Se
desarrolló un prototipo de software incluyendo las metaheurísticas más representativas de cada framework y se utilizaron como
benchmark un conjunto de instancias públicas del problema. Se diseñó un factor de finalización común para los algoritmos
de cada framework, y a partir del diseño experimental se ejecutaron 30 pruebas por algoritmo cuyos resultados demuestran
que JAMES obtienen mejores soluciones, aunque con mayor desviación estándar. Sin embargo, MOEA es el framework más
sencillo de implementar, ya que implica menos líneas de código necesarias para resolver el problema. Software frameworks allow the reuse of code designed for diverse problem-solving. Frameworks implementing
metaheuristics for optimization problem solving are among the most interesting ones. The Knapsack Problem is one of the
classic optimization examples commonly used as a benchmark as it is a simple yet complex problem: it belongs to the NPComplete
complexity class, considered more difficult than NP problems in general. In this paper, we implemented algorithms
from three metaheuristics frameworks of different families in order to solve a form of the problem: the Knapsack Problem
0-1. The selected frameworks were JACOF (Ant Colony Optimization), JAMES (Trajectory-based Algorithms), and MOEA
(Evolutionary Algorithms). We develop a software prototype including the most representative algorithms of each framework
to solve a public benchmark set of the problem. We designed one stop criteria for all algorithms, and we perform 30 runs per
algorithm to conclude that JAMES obtained the best results, although with higher standard deviation. However, MOEA is the
most easy-to-implement framework, since it requires fewer lines of code to solve the problem.