Greedy Randomized Adaptive Search Procedure (GRASP)

L’algorithme Greedy Randomized Adaptive Search Procedure (GRASP) est une métaheuristique introduite par Feo et Resende en 1989.

Son fonctionnement se base sur la répétition de deux phases : une construction gloutonne suivit par une 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


To share
%d bloggers like this: