Greedy randomized adaptive search procedure
- Greedy randomized adaptive search procedure
-
Greedy randomized adaptive search procedure est une métaheuristique, c'est-à-dire un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile 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 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ésultante de la phase de construction afin de voir s'il est encore possible d'améliorer cette solution.
Références
- 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, pp. 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, pp. 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, pp. 325–367, Kluwer Academic Publishers, 2002.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Greedy randomized adaptive search procedure de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Greedy randomized adaptive search procedure — The greedy randomized adaptive search procedure (also known as GRASP) is a metaheuristic algorithm commonly applied to combinatorial optimization problems. GRASP typically consists of iterations made up from successive constructions of a greedy… … Wikipedia
Tabu search — is a mathematical optimization method, belonging to the class of local search techniques. Tabu search enhances the performance of a local search method by using memory structures: once a potential solution has been determined, it is marked as… … Wikipedia
GRASP — Greedy Randomized Adaptive Search Procedure (Computing » Databases) * General Responsibility Assignment Software Patterns (Computing » General) * Graphical Representation And Analysis Of Surface Properties (Academic & Science » Physics) *… … Abbreviations dictionary
Metaheuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… … Wikipédia en Français
Méta-heuristique — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… … Wikipédia en Français
Métaheuristique — Une métaheuristique est un algorithme d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence artificielle) pour lesquels on ne… … Wikipédia en Français
Métaheuristiques — Métaheuristique Les métaheuristiques forment une famille d’algorithmes d’optimisation visant à résoudre des problèmes d’optimisation difficile (souvent issus des domaines de la recherche opérationnelle, de l ingénierie ou de l intelligence… … Wikipédia en Français
List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… … Wikipedia
Búsqueda tabú — Saltar a navegación, búsqueda Para otros usos de este término, véase Búsqueda. La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de … Wikipedia Español
GRASP — may refer to:* GRASP (multimedia authoring software), a multimedia authoring software * GRASP (SAT solver), a SAT instance solver * GRASP (Object Oriented Design) * Greedy randomized adaptive search procedure * Given, Required, Analysis, Solution … Wikipedia
