Advertisement
Published in:
2010 | OriginalPaper | Chapter
A Swarm Intelligence Approach to the Quadratic Multiple Knapsack Problem
Authors : Shyam Sundar, Alok Singh
Published in: Neural Information Processing. Theory and Algorithms
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In this paper we present an artificial bee colony (ABC) algorithm to solve the quadratic multiple knapsack problem (QMKP) which can be considered as an extension of two well known knapsack problems viz. multiple knapsack problem and quadratic knapsack problem. In QMKP, profit values are associated not only with individual objects but also with pairs of objects. Profit value associated with a pair of objects is added to the total profit if both objects of the pair belong to the same knapsack. The objective of this problem is to assign each object to at most one knapsack in such a way that the total weight of the objects in each knapsack should not exceed knapsack’s capacity and the total profit of all the objects included into the knapsacks is maximized. We have compared our approach with three genetic algorithms and a stochastic hill climber. Computational results show the effectiveness of our approach.