A genetic algorithm for the quadratic multiple knapsack problem

SARAÇ T., SİPAHİOĞLU A.

2nd International Symposium on Brain, Vision and Artificial Intelligence, Naples, Italy, 10 - 12 October 2007, vol.4729, pp.490-492 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 4729
  • Doi Number: 10.1007/978-3-540-75555-5_47
  • City: Naples
  • Country: Italy
  • Page Numbers: pp.490-492
  • Keywords: quadratic multiple knapsack problem, genetic algorithm, combinatorial optimization
  • Eskisehir Osmangazi University Affiliated: Yes

Abstract

The Quadratic Multiple Knapsack Problem (QMKP) is a generalization of the quadratic knapsack problem, which is one of the well-known combinatorial optimization problems, from a single knapsack to k knapsacks with (possibly) different capacities. The objective is to assign each item to at most one of the knapsacks such that none of the capacity constraints are violated and the total profit of the items put into the knapsacks is maximized. In this paper, a genetic algorithm is proposed to solve QMKP. Specialized crossover operator is developed to maintain the feasibility of the chromosomes and two distinct mutation operators with different improvement techniques from the non-evolutionary heuristic are presented. The performance of the developed GA is evaluated and the obtained results are compared to the previous study in the literature.