GRASP: Greedy Randomized Adaptive Search Procedure

GRASP, or Greedy Randomized Adaptive Search Procedure, is a multi-start metaheuristic designed to solve combinatorial optimization problems. It combines the greedy construction of solutions with randomization and local search, offering a balance between exploration and exploitation of the search space.

Overview

Each iteration of GRASP consists of two main phases:

1. Construction Phase: A feasible solution is greedily built using randomized decisions.
2. Local Search Phase: The constructed solution is then improved through a local search procedure.

The best solution found over all iterations is kept as the final result.

1. Construction Phase

In the construction phase, the solution is built one element at a time. Instead of always choosing the best possible element (as in pure greedy algorithms), GRASP uses a Restricted Candidate List (RCL) that includes good candidates based on a greedy function. A candidate from this list is selected at random to be added to the partial solution.

This introduces diversification into the search process, allowing the algorithm to explore multiple regions of the solution space.

Pseudocode Example:

Initialize empty solution S
while S is incomplete:
    Evaluate all candidate elements using a greedy function
    Build RCL with top candidates (based on quality threshold α)
    Randomly select one candidate from RCL
    Add selected candidate to S

The parameter α (alpha) controls the greediness vs. randomness balance:

• α = 0 → purely greedy
• α = 1 → purely random

2. Local Search Phase

Once a complete solution is constructed, a local search is applied to try to improve it by exploring its neighborhood.

The local search continues until no better solution can be found within the neighborhood of the current solution (i.e., it reaches a local optimum).

Pseudocode Example:

function LocalSearch(S):
    repeat:
        Find best neighbor S' of S
        if S' better than S:
            S ← S'
        else:
            return S

3. GRASP Algorithm

Complete GRASP Framework:

function GRASP(max_iterations):
    best_solution ← ∅
    for i from 1 to max_iterations:
        S ← GreedyRandomizedConstruction()
        S ← LocalSearch(S)
        if S better than best_solution:
            best_solution ← S
    return best_solution

Why Use GRASP?

• Simplicity: GRASP is relatively easy to implement.
• Effectiveness: It performs well on a wide range of problems.
• Customizable: Construction and local search strategies can be tailored to specific problems.
• Parallelizable: Independent iterations make it suitable for parallel computation.

Applications

GRASP has been successfully applied to many combinatorial problems, including:

• Traveling Salesman Problem (TSP)
• Graph Coloring
• Job Shop Scheduling
• Set Covering
• Vehicle Routing

Example: GRASP for the Set Covering Problem

Problem Definition

Given a universe of elements and a collection of subsets, the goal is to find the smallest number of subsets whose union covers the entire universe.

Construction Strategy

• At each step, choose a subset that covers the largest number of uncovered elements.
• Use RCL to randomize the choice.

Local Search Strategy

• Try removing or replacing subsets to reduce the total number of subsets while maintaining coverage.

References

• Feo, T. A., & Resende, M. G. C. (1995). Greedy randomized adaptive search procedures. Journal of Global Optimization.
• Resende, M. G. C., & Ribeiro, C. C. (2016). Optimization by GRASP. Springer.

Conclusion

GRASP is a powerful and adaptable metaheuristic that effectively balances greedy construction and randomized search with local improvement. Its modular design makes it ideal for tackling various NP-hard optimization problems in a robust and efficient manner.

If you’re looking for a fast, flexible, and effective heuristic method, GRASP is a great starting point.