The greedy randomized adaptive search procedure (also known as GRASP) is a

metaheuristic In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimizati ...

algorithm commonly applied to

combinatorial optimization Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combi ...

problems. GRASP typically consists of iterations made up from successive constructions of a greedy

randomized In common usage, randomness is the apparent or actual lack of pattern or predictability in events. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual rand ...

solution and subsequent iterative improvements of it through a local search. The greedy randomized 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'' (RCL), and chosen at random when building up the solution. This kind of greedy randomized construction method is also known as a semi-greedy heuristic, first described in Hart and Shogan (1987). GRASP was first introduced in Feo and Resende (1989). Survey papers on GRASP include Feo and Resende (1995), and Resende and Ribeiro (2003). There are variations of the classical algorithm, such as the Reactive GRASP. In this variation, the basic parameter that defines the restrictiveness of the RCL during the construction phase is self-adjusted according to the quality of the solutions previously found. There are also techniques for search speed-up, such as cost perturbations, bias functions, memorization and learning, and local search on partially constructed solutions.

References

See also