Frameworks basados en metaheurísticas para resolver el problema de la mochila

Abstract

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.