A GENETIC ALGORITHM FOR THE MULTIDIMENSIONAL KNAPSACK-PROBLEM

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