Análise da aplicação do Algoritmo de Colônia de Abelhas Artificial no problema da Mochila Multidimensional Binária.

Abstract

The multidimensional binary knapsack problem is a widely explored optimization challenge within the realm of computing. Despite its familiarity, finding a solution is not straightforward, as it falls within the class of NP-hard problems, implying the absence of an algorithm that can deliver a solution verifiable within polynomial time. Consequently, to seek approximate solutions in reduced time, metaheuristics come into play. In this study, the Artificial Bee Colony (ABC) metaheuristic algorithm was employed. This iterative algorithm simplifies the colony into three classes of bees: employed, onlookers, and scouts. Throughout the iterations, they aim to discover the best achievable solution, equating to the food source sought by the colony. Drawing from this metaheuristic, a discrete ABC algorithm was developed, given the binary nature of the multidimensional knapsack, even though the original ABC was primarily proposed for continuous problems, to pursue favorable outcomes for the specified challenge. The presented algorithm was evaluated based on optimization problems found in literature. The obtained results were stored and processed for quantitative comparisons regarding the algorithm's applicability to the proposed problem. To substantiate its efficiency, averages and standard deviations of the outcomes were calculated for validation. Ultimately, it can be affirmed that the algorithm achieved promising results in the majority of the tested cases, approaching the performance of other applicable existing metaheuristics.