GRASP
摘要
GRASP (greedy randomized adaptive search procedures) is a multi-start metaheuristic designed to find high-quality solutions for combinatorial optimization problems. Each iteration of GRASP typically consists of two phases: a construction phase, where a feasible solution is built, and a local search phase, which begins from the constructed solution and performs iterative improvements until a locally optimal solution is achieved. While the construction phase is usually based on a randomized greedy algorithm, other construction methods have also been explored. Repeated use of the construction procedure generates diverse starting solutions for the local search. This chapter provides an overview of GRASP, outlining its fundamental components and various enhancements to the basic approach, such as Reactive GRASP, intensification strategies, and random-key GRASP.