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, İtalya, 10 - 12 Ekim 2007, cilt.4729, ss.490-492 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 4729
  • Doi Numarası: 10.1007/978-3-540-75555-5_47
  • Basıldığı Şehir: Naples
  • Basıldığı Ülke: İtalya
  • Sayfa Sayıları: ss.490-492
  • Anahtar Kelimeler: quadratic multiple knapsack problem, genetic algorithm, combinatorial optimization
  • Eskişehir Osmangazi Üniversitesi Adresli: Evet

Özet

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.