Greedy randomized adaptive search procedure

From Wikipedia, the free encyclopedia

The greedy randomized adaptive search procedure (also known as GRASP) is a metaheuristic algorithm commonly applied to combinatorial optimization problems. GRASP typically consists of iterations made up from successive constructions of a greedy solution and subsequent iterative improvements of it through a local search. The greedy solutions are generated by adding elements to the problem's solution set from a list of elements ranked by a greedy function according to the quality of the solution they will achieve. To obtain variability in the candidate set of greedy solutions, well-ranked candidate elements are often placed in a restricted candidate list, and chosen at random when building up the greedy solution.

[edit] Bibliography

• L. Pitsoulis and M. Resende (2001) Greedy randomized adaptive search procedures, In P.M.Pardalos and M.G.C.Resende, editors, Handbook of Applied Optimization, pp. 168–181, Oxford University Press.
• J.P. Hart and A.W. Shogan (1987) Semi-greedy heuristics: An empirical study. Operations Research Letters, 6:107–114, 1987.