GRASP (english version)

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 greedy construction followed by a local search.

The characteristic of the GRASP method is its phase of constructing a solution. To do this, the algorithm maintains a list of possible restricted candidate lists (RCLs). The solution is built step by step by going to choose elements (in our case, it is the gains of combining mesh in zones) in the list RCL. This list is sorted, it’s the greedy part of the algorithm.

An element is randomly drawn from the best possibilities of the RCL list, it is the random part of the algorithm. Thanks to the random part, the construction phase makes it possible to vary the form of the generated solutions but these are good qualities since the random choice is made among a set of good candidates. The local search applies to the feasible solution resulting from the construction phase to see if it is still possible to improve this solution.

Two points are worth noting:
  • the RCL is updated with elements selected according to a specific heuristic adapted to the problem considered.
  • the choice of an element in the RCL to build the solution is random.

The algorithm in french: