Greedy Randomized Adaptive Search Procedure

The greedy randomized adaptive search procedure, known as GRASP, is a metaheuristic algorithm for combinatorial optimization problems that runs as a sequence of independent iterations, each producing one candidate solution and then trying to improve it. Each iteration has two phases, a construction phase that builds a solution element by element, ranking the remaining candidate elements by a greedy quality measure at each step and choosing the next element at random from a short restricted list of the best-ranked candidates rather than always taking the single best one, which is what makes the construction randomized rather than purely greedy, followed by a local search phase that explores the neighborhood of the constructed solution for nearby improvements; the best solution found across all of the independent iterations is kept as the final answer. Thomas Feo and Mauricio Resende introduced GRASP in 1989, building on an earlier semi-greedy construction technique described by Hart and Shogan in 1987, and later variants such as reactive GRASP adjust the size of the restricted candidate list automatically based on the quality of solutions found so far.