Uma abordagem alternativa para aplicação do Algoritmo de Colônia de Abelhas Artificial no problema da Mochila Multidimensional Binária.

Abstract

A mochila multidimensional binária é um problema de otimização muito explorado no âmbito da computação. Mesmo sendo um problema conhecido de maneira abrangente, sua solução não é trivial, uma vez que pertence à classe dos problemas $\mathcal{NP}$-difíceis, isto é, não há um algoritmo que forneça uma solução que possa ser verificada em tempo polinomial. Assim, a fim de buscar soluções aproximadas em menor tempo, faz-se uso das meta-heurísticas. Neste trabalho, utilizou-se a meta-heurística do Algoritmo Colônia de Abelhas Artificiais (ABC - do inglês {\itshape Artificial Bee Colony}). Nesse algoritmo iterativo, a colônia é simplificada em três classes de abelhas: as empregadas, as observadoras e as escoteiras. Durante as iterações, elas procuram a melhor solução alcançável, que se refere à fonte de alimento procurada pela colônia. Com base nessa meta-heurística, desenvolveu-se um algoritmo ABC discreto, visto que a mochila multidimensional é de ordem binária e o ABC foi proposto inicialmente para ser aplicado a problemas contínuos, a fim de tentar alcançar bons resultados para a questão proposta. O algoritmo apresentado foi avaliado com base na resolução de problemas de otimização encontrados na literatura. Os resultados obtidos foram armazenados e processados para realizar comparações quantitativas quanto à aplicabilidade do algoritmo no problema proposto. Para comprovar a eficiência, foram calculados as médias e os desvios-padrões dos resultados, a fim de validá-los. Por fim, pode-se dizer que o algoritmo obteve resultados promissores na maioria dos casos testados, aproximando-se de outras meta-heurísticas aplicáveis existentes.