  


A GRASP algorithm for the multiobjective knapsack problem
Dalessandro Vianna (dalessandroucamcampos.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 multiobjective 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, multiobjective 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  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  