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},
}