GRASP

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 recherche locale.

La caractéristique de la méthode GRASP est sa phase de construction d’une solution. Pour ce faire, l’algorithme maintient à jour une liste de fragments de solutions possibles (RCL, restricted candidate list). La solution se construit pas à pas en allant choisir des éléments (dans notre cas, ce sont les gains de combiner de mailles en zones) dans la liste RCL. Cette liste est triée, c’est la partie gloutonne de l’algorithme.

Un élément est tiré aléatoirement parmi les meilleures possibilités de la liste RCL, c’est la partie aléatoire de l’algorithme. Grâce à la partie aléatoire, la phase de construction permet donc de faire varier la forme des solutions générées mais celles-ci sont de bonnes qualités puisque le choix aléatoire se fait parmi un ensemble de bons candidats. La recherche locale s’applique sur la solution réalisable résultant de la phase de construction afin de voir s’il est encore possible d’améliorer cette solution.

Deux points sont à remarquer :
  • la RCL est mise à jour avec des éléments sélectionnés en fonction d’une heuristique spécifique adaptée au problème considéré.
  • le choix d’un élément dans la RCL pour construire la solution est aléatoire.
Greedy Randomized Adaptive Search Procedure GRASP

 

Partager