A GRASP Algorithm for the Multi-Objective Knapsack Problem

In this article, we propose a greedy randomized adaptive search procedure (GRASP) to generate a good approximation of the efficient or Pareto optimal set of a multi-objective combinatorial optimization problem. The algorithm is based on the optimization of all weighted linear utility functions. In each iteration, a preference vector is defined and a solution is built considering the preferences of each objective. The found solution is submitted to a local search trying to improve the value of the utility function. In order to find a variety of efficient solutions, we use different preference vectors, which are distributed uniformly on the Pareto frontier. The proposed algorithm is applied for the 0/1 knapsack problem with r = 2, 3, 4 objectives and n = 250, 500, 750 items. The quality of the approximated solutions is evaluated comparing with the solutions given by three genetic algorithms from the literature.