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.
Bibliographie
- J.P. Hart and A.W. Shogan (1987) Semi-greedy heuristics: An empirical study. Operations Research Letters, 6:107–114, 1987.
- T.A. Feo and M.G.C. Resende (1989) A probabilistic heuristic for a computationally difficult set covering problem. Operations Research Letters, 8:67–71, 1989.
- T.A. Feo and M.G.C. Resende (1995) Greedy randomized adaptive search procedures. J. of Global Optimization, 6:109–133, 1995.
- L. Pitsoulis and M. G. C. Resende (2002) Greedy randomized adaptive search procedures. In P. M. Pardalos and M. G. C. Resende, editors, Handbook of Applied Optimization, p. 168–181, Oxford University Press.
- M. G. C. Resende and C. C. Ribeiro (2003) Greedy randomized adaptive search procedures. In F. Glover and G. Kochenberger, editors, Handbook of Metaheuristics, p. 219–249, Kluwer Academic Publishers, 2003.
- P. Festa and M. G. C. Resende (2002) GRASP: An annotated bibliography. In C. C. Ribeiro and P. Hansen, editors, Essays and Surveys on Metaheuristics, p. 325–367, Kluwer Academic Publishers, 2002.