Greedy randomized adaptive search procedure
# Greedy randomized adaptive search procedure

Greedy randomized adaptive search procedure (GRASP) est une métaheuristique, c'est-à-dire un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (au sens de la théorie de la complexité) pour lesquels on ne connaît pas de méthode classique plus efficace.

Introduite dans l'article Feo and Resende (1989), cette métaheuristique produit une solution réalisable. Elle est exécutée un certain nombre de fois et la meilleure solution trouvée est gardée. Pour produire une solution, deux phases sont exécutées l'une à la suite de l'autre : la première consiste en une phase de construction qui est suivie d'une phase de recherche locale.

## Fonctionnement

Comme le dit le nom de l'algorithme, la phase de construction combine les méthodes gloutonnes et aléatoires. La construction d'une solution se déroule par étapes et à chacune de celles-ci, l'ensemble des morceaux de solution qu'il est possible d'ajouter est placé dans une liste appelée RCL (Restricted Candidate List). Cette liste est triée, c'est la partie gloutonne de l'algorithme. Mais ce n'est pas nécessairement le meilleur morceau qui est ajouté à la solution courante. On tire aléatoirement parmi les meilleurs possibilités le morceau à ajouter, c'est la partie aléatoire de l'algorithme.

Grâce à la partie aléatoire, la phase de construction permet donc de varier la forme des solutions générées mais celles-ci sont quand même de bonne qualité, puisque le choix aléatoire se fait parmi un ensemble de bons candidats. La recherche locale s'applique sur la solution réalisable résultante de la phase de construction afin de voir s'il est encore possible d'améliorer cette solution.

