zbMATH — the first resource for mathematics

Greedy randomized adaptive search procedures. (English) Zbl 1102.90384
Glover, Fred (ed.) et al., Handbook of metaheuristics. Boston, MA: Kluwer Academic Publishers (ISBN 1-4020-7263-5/hbk). Int. Ser. Oper. Res. Manag. Sci. 57, 219-249 (2003).
Summary: GRASP is a multi-start metaheuristic for combinatorial problems, in which each iteration consists basically of two phases: construction and local search. The construction phase builds a feasible solution, whose neighborhood is investigated until a local minimum is found during the local search phase. The best overall solution is kept as the result. In this chapter, we first describe the basic components of GRASP. Successful implementation techniques and parameter tuning strategies are discussed and illustrated by numerical results obtained for different applications. Enhanced or alternative solution construction mechanisms and techniques to speed up the search are also described: Reactive GRASP, cost perturbations, bias functions, memory and learning, local search on partially constructed solutions, hashing, and filtering. We also discuss in detail implementation strategies of memory-based intensification and post-optimization techniques using path-relinking. Hybridizations with other metaheuristics, paral lelization strategies, and applications are also reviewed.
For the entire collection see [Zbl 1058.90002].

90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
68W20 Randomized algorithms
90C10 Integer programming