A Genetic Algorithm for the Multidimensional Knapsack Problem

A Genetic Algorithm for the Multidimensional Knapsack Problem. Chu, P. & Beasley, J. J Heuristics, 4(1):63–86, Kluwer Academic Publishers, 1998.
doi abstract bibtex

In this paper we present a heuristic based upon genetic algorithms for the multidimensional knapsack problem. A heuristic operator which utilises problem-specific knowledge is incorporated into the standard genetic algorithm approach. Computational results show that the genetic algorithm heuristic is capable of obtaining high-quality solutions for problems of various characteristics, whilst requiring only a modest amount of computational effort. Computational results also show that the genetic algorithm heuristic gives superior quality solutions to a number of other heuristics.

@Article{chu98genetic,
  author    = {Chu, P.C. and Beasley, J.E.},
  title     = {A Genetic Algorithm for the Multidimensional Knapsack Problem},
  journal   = {J Heuristics},
  year      = {1998},
  volume    = {4},
  number    = {1},
  pages     = {63--86},
  issn      = {1381-1231},
  abstract  = {In this paper we present a heuristic based upon genetic algorithms for the multidimensional knapsack problem. A heuristic operator which utilises problem-specific knowledge is incorporated into the standard genetic algorithm approach. Computational results show that the genetic algorithm heuristic is capable of obtaining high-quality solutions for problems of various characteristics, whilst requiring only a modest amount of computational effort. Computational results also show that the genetic algorithm heuristic gives superior quality solutions to a number of other heuristics.},
  doi       = {10.1023/A:1009642405419},
  keywords  = {genetic algorithms; multidimensional knapsack; multiconstraint knapsack; combinatorial optimisation},
  owner     = {Sebastian},
  publisher = {Kluwer Academic Publishers},
  timestamp = {2014.04.01},
}

Downloads: 0