2005 · 58 citations · 31 references
Natural SciencesMathematicsDesign OptimizationMulti-criteria Decision MakingOptimizationCombinatorial OptimizationGenetic AlgorithmsGreedy AlgorithmsMulti-objective OptimizationMultiobjective OptimizationPareto Optimality0-1 Knapsack ProblemGraspGreedy Randomized Adaptive Search ProcedureKnapsack ProblemsLocal SearchLocal Search AlgorithmsMulti-objective Combinatorial OptimizationPareto Optimal Set
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.
31
Greedy Randomized Adaptive Search Procedures
Thomas A. Feo, Maurício G. C. Resende · Journal of Global Optimization · 1995 · 2.7K citations
David M. Ridley, Harold Jordaan · Journal of Clinical Ultrasound · 1986 · 864 citations