Greedy randomized adaptive search procedure (original) (raw)
A meta-heurística GRASP (Greedy Randomized Adaptive Search Procedure) é um algoritmo comumente aplicado a problemas de otimização combinatória. Como diversos métodos construtivos, a aplicação do GRASP consiste em criar uma solução inicial e depois efetuar uma para melhorar a qualidade da solução. Seu diferencial para outros métodos está na geração dessa solução inicial, baseada nas três primeiras iniciais de sua sigla em inglês: gulosa (Greedy), aleatória (Randomized) e adaptativa (Adaptive).
| Property | Value |
|---|---|
| dbo:abstract | 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 randomized solution and subsequent iterative improvements of it through a local search. The greedy randomized solutions are generated by adding elements to the problem's solution set from a list of elements ranked by a greedy function according to the quality of the solution they will achieve. To obtain variability in the candidate set of greedy solutions, well-ranked candidate elements are often placed in a restricted candidate list (RCL), and chosen at random when building up the solution. This kind of greedy randomized construction method is also known as a semi-greedy heuristic, first described in Hart and Shogan (1987). GRASP was first introduced in Feo and Resende (1989).Survey papers on GRASP include Feo and Resende (1995), and Resende and Ribeiro (2003). There are variations of the classical algorithm, such as the Reactive GRASP. In this variation, the basic parameter that defines the restrictiveness of the RCL during the construction phase is self-adjusted according to the quality of the solutions previously found.There are also techniques for search speed-up, such as cost perturbations, bias functions, memorization and learning, and local search on partially constructed solutions. (en) 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. (fr) A meta-heurística GRASP (Greedy Randomized Adaptive Search Procedure) é um algoritmo comumente aplicado a problemas de otimização combinatória. Como diversos métodos construtivos, a aplicação do GRASP consiste em criar uma solução inicial e depois efetuar uma para melhorar a qualidade da solução. Seu diferencial para outros métodos está na geração dessa solução inicial, baseada nas três primeiras iniciais de sua sigla em inglês: gulosa (Greedy), aleatória (Randomized) e adaptativa (Adaptive). (pt) |
| dbo:wikiPageID | 1804034 (xsd:integer) |
| dbo:wikiPageLength | 3797 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1059809808 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Metaheuristic dbc:Combinatorial_optimization dbr:Constructive_cooperative_coevolution dbr:Cooperative_coevolution dbr:Simulated_annealing dbr:Combinatorial_optimization dbr:Tabu_search dbc:Greedy_algorithms dbr:Local_search_(optimization) dbr:Greedy_algorithm dbr:Randomized_algorithm |
| dbp:wikiPageUsesTemplate | dbt:Combin-stub dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Combinatorial_optimization dbc:Greedy_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software |
| rdfs:comment | A meta-heurística GRASP (Greedy Randomized Adaptive Search Procedure) é um algoritmo comumente aplicado a problemas de otimização combinatória. Como diversos métodos construtivos, a aplicação do GRASP consiste em criar uma solução inicial e depois efetuar uma para melhorar a qualidade da solução. Seu diferencial para outros métodos está na geração dessa solução inicial, baseada nas três primeiras iniciais de sua sigla em inglês: gulosa (Greedy), aleatória (Randomized) e adaptativa (Adaptive). (pt) 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 randomized solution and subsequent iterative improvements of it through a local search. The greedy randomized solutions are generated by adding elements to the problem's solution set from a list of elements ranked by a greedy function according to the quality of the solution they will achieve. To obtain variability in the candidate set of greedy solutions, well-ranked candidate elements are often placed in a restricted candidate list (RCL), and chosen at random when building up the solution. This kind of greedy randomized construction method is also (en) 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. (fr) |
| rdfs:label | Greedy randomized adaptive search procedure (en) Greedy randomized adaptive search procedure (fr) GRASP (pt) |
| owl:sameAs | freebase:Greedy randomized adaptive search procedure wikidata:Greedy randomized adaptive search procedure dbpedia-fr:Greedy randomized adaptive search procedure dbpedia-pt:Greedy randomized adaptive search procedure https://global.dbpedia.org/id/2tiTv |
| prov:wasDerivedFrom | wikipedia-en:Greedy_randomized_adaptive_search_procedure?oldid=1059809808&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Greedy_randomized_adaptive_search_procedure |
| is dbo:wikiPageDisambiguates of | dbr:Grasp_(disambiguation) |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Metaheuristic dbr:Constructive_cooperative_coevolution dbr:Tabu_search dbr:Grasp_(disambiguation) |
| is foaf:primaryTopic of | wikipedia-en:Greedy_randomized_adaptive_search_procedure |