A GRASP algorithm for the multi-objective knapsack problem
Dalessandro Vianna (dalessandroucam-campos.br)
Abstract: 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 applied for the 0/1 knapsack problem with r objective functions. This problem is formulated as r classic 0/1 knapsack problems. n items, each one with r costs and r weights, have to be inserted in r knapsacks with different capacities in order to maximize the r total costs (objectives). The algorithm is based on a weighted scalar function (linear combination of the objectives), for it is necessary to define a preference or weight for each objective. At each iteration of the algorithm, 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 its weighted scalar 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 tested on problems 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 two genetic algorithms from the literature.
Keywords: algorithm, multi-objective combinatorial optimization, knapsack problem.
Category 1: Combinatorial Optimization (Meta Heuristics )
Citation: Accepted for the XXIV SCCC
Download: [Compressed Postscript]
Entry Submitted: 08/30/2004
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|