GRASP

Greedy Randomized Adaptive Search Procedure (GRASP)

The Greedy Randomized Adaptive Search Procedure (GRASP) algorithm is a metaheuristic introduced by Feo and Resende in 1989.

Its operation is based on the repetition of two phases: a gluttonous construction followed by a local search.

The characteristic of the GRASP method is its phase of building a solution. To do this, the algorithm maintains an updated list of fragments of possible solutions (RCL, restricted candidate list). The solution is built step by step by going to choose elements (in our case, they are the gains of combining meshes in zones) in the list RCL. This list is sorted, it's the greedy part of the algorithm.

An element is drawn randomly from the best possibilities of the RCL list, it is the random part of the algorithm. Thanks to the random part, the construction phase therefore makes it possible to vary the shape of the solutions generated, but these are of good quality since the random choice is made among a set of good candidates. Local research is applied to the feasible solution resulting from the construction phase in order to see if it is still possible to improve this solution.

Two points should be noted:
  • the RCL is updated with selected elements according to a specific heuristic adapted to the problem considered.
  • the choice of an element in the RCL to build the solution is random.
Greedy Randomized Adaptive Search Procedure GRASP