A Comparation between Bee Swarm Optimization and Greedy Algorithm for the Knapsack Problem with Bee Reallocation

摘要

The Knapsack Problem is a classical combinatorial problem which can be solved in many ways. One of these ways is the Greedy Algorithm which gives us an approximated solution to the problem. Another way to solve it is using the Swarm Intelligence approach, based on the study of actions of individuals in various decentralized systems. Optimization algorithms inspired on the intelligent behavior of honey bees are among the most recently introduced population based techniques. In this paper, a novel hybrid algorithm based on Bees Algorithm and Particle Swarm Optimization is applied to the Knapsack Problem, although the combination of BA and PSO is given by BSO, Bee Swarm Optimization, this algorithm uses the velocity vector, the collective memories of PSO and the search based on the BA, in this case we introduce another way to use the bee algorithm in the PSO using the bees reallocation. The obtained results are much better when compared to those provided by the Greedy Algorithm.