32.8 GRASP¶

Part 4 · Heuristic algorithms · Chapter 32 · Chapter 32: Metaheuristics · Lecture notes, volume 4 (PDF) · Slides (1/2) · Slides (2/2) · Exercises: Metaheuristics · App: TSP: simulated annealing and tabu search

The greedy randomized adaptive search procedure (denoted by \(GRASP\)) is a multi-start method: at every iteration it builds a solution with a randomized greedy algorithm, which chooses the next element at random among the best candidates (the restricted candidate list, RCL) instead of always taking the best one, and improves the solution with a local search. The best local optimum found is returned.

The pseudo-code of \(GRASP\) for the KP, with the randomized greedy algorithm by efficiency and KPLOCALSEARCH, reads as follows:

Algorithm: GRASP for the KP

Input: KP instance \(p[1..n]\), \(w[1..n]\), \(c\); parameter \(\alpha\in[0,1]\); number of iterations \(maxIter\)

Output: best solution found

1Function GRASP(\(p, w, c, \alpha, maxIter\))

2\(zbest := -1\)

3for \(it := 1\) to \(maxIter\) do

4\(x := \textsc{RandomizedGreedy}(p, w, c, \alpha)\) \(x := \textsc{KPLocalSearch}(x)\) ▹ construction local search

5if \(\sum_j p[j]x[j] > zbest\) then \(best := x\); \(zbest := \sum_j p[j]x[j]\)

6end

7return \(best\)

8Function RandomizedGreedy(\(p, w, c, \alpha\))

9\(x := (0,\dots,0)\); \(rc := c\) ▹ residual capacity

10while some item with \(x[j]=0\) has \(w[j]\le rc\) do

11\(e_{\max}\), \(e_{\min} :=\) maximum and minimum of \(p[j]/w[j]\) over these candidate items

12\(RCL :=\) candidates with \(p[j]/w[j] \ge e_{\max} - \alpha\,(e_{\max}-e_{\min})\), by non-increasing \(p[j]/w[j]\)

13\(j :=\) the element of \(RCL\) in position \(1+\lfloor \textsc{Rand}()\cdot |RCL|\rfloor\)

14\(x[j] := 1\); \(rc := rc - w[j]\)

15end

16return \(x\)

Run in Colab:Python C++

\(GRASP\) was introduced by Feo and Resende (1989) for the set covering problem and presented as a general metaheuristic in Feo and Resende (1995). The randomized construction with a restricted candidate list is the one of the chapter «Constructive heuristics».
The RCL is defined by a threshold on the greedy score, controlled by \(\alpha\):

KP (maximize the efficiency \(p_j/w_j\) of the items that fit):

\[ RCL=\Big\{j \text{ candidate}: \tfrac{p_j}{w_j}\ \ge\ e_{\max}-\alpha\,(e_{\max}-e_{\min})\Big\}. \]

TSP (minimize the distance from the last city \(\ell\) of the partial tour):

\[ RCL=\big\{j \text{ unvisited}: d_{\ell j}\ \le\ d_{\min}+\alpha\,(d_{\max}-d_{\min})\big\}. \]

With \(\alpha=0\) the RCL contains only the best candidates, and the construction is the greedy algorithm: every iteration builds the same solution (up to ties), and \(GRASP\) is a single local search. With \(\alpha=1\) the RCL contains all the candidates, and the construction is random. Intermediate values give solutions that are different (diversification) and good (a good start for the local search, which then intensifies).
The iterations of \(GRASP\) are independent: nothing is learnt from one to the next, and the iterations can be run in parallel. Extensions add memory: reactive GRASP adapts \(\alpha\) to the results, and path relinking explores the solutions between two good local optima.

Example 32.8: \(GRASP\) on the KP reference instance

With \(\alpha=\frac12\) and \(seed=2\) (random numbers \(0.0000\), \(0.2631\), \(0.5112\), \(0.9173\)) we perform two iterations. The efficiencies are \(\frac{10}{5}=2\), \(\frac74=1.75\), \(\frac63=2\), \(\frac43\approx 1.33\).

Iteration 1. With \(rc=9\) all items fit: \(e_{\max}=2\), \(e_{\min}=\frac43\), the threshold is \(2-\frac12\cdot\frac23=\frac53\approx 1.67\), and \(RCL=(1,3,2)\). With \(u=0.0000\) the first element is chosen: item \(1\), \(rc=4\). The candidates are items \(2\), \(3\), \(4\), the threshold is again \(\frac53\), \(RCL=(3,2)\), and \(u=0.2631\) chooses position \(1+\lfloor 2\cdot 0.2631\rfloor=1\): item \(3\), \(rc=1\), and no item fits. The construction gives \(\{1,3\}\), of profit \(16\); KPLOCALSEARCH swaps item \(3\) out and item \(2\) in: \(\{1,2\}\), profit \(17\).

Iteration 2. \(RCL=(1,3,2)\) and \(u=0.5112\) chooses position \(1+\lfloor 3\cdot 0.5112\rfloor=2\): item \(3\), \(rc=6\). The candidates are items \(1\), \(2\), \(4\), the threshold is \(\frac53\), \(RCL=(1,2)\), and \(u=0.9173\) chooses position \(2\): item \(2\), \(rc=2\). The construction gives \(\{2,3\}\), of profit \(13\), a different and worse solution than the greedy one; the local search swaps item \(3\) out and item \(1\) in: \(\{1,2\}\), profit \(17\).

\(GRASP(I)=17=z(I)\). On this small instance every start leads to the optimum; on larger instances different starts lead to different local optima.

32.8.1 GRASP for the TSP, and the effect of \(\alpha\)¶

For the TSP the randomized construction is the nearest neighbour heuristic with an RCL: from the last city \(\ell\) of the partial tour, the next city is chosen at random among the unvisited cities whose distance from \(\ell\) is at most \(d_{\min}+\alpha(d_{\max}-d_{\min})\), and the local search is TWOOPTLS.
The table reports the results of \(GRASP\) with \(20\) iterations on TSP20 and on KP20, for \(10\) runs (\(seed=1,\dots,10\)): minimum, average and maximum value of the best solution, and number of runs that reach the optimum.

	TSP20 (\(z(I)=291\))				KP20 (\(z(I)=521\))
\(\alpha\)	min	average	max	optimal	min	average	max	optimal
\(0\)	\(319\)	\(319.0\)	\(319\)	\(0\)	\(514\)	\(514.0\)	\(514\)	\(0\)
\(0.1\)	\(291\)	\(291.0\)	\(291\)	\(10\)	\(521\)	\(521.0\)	\(521\)	\(10\)
\(0.25\)	\(291\)	\(291.0\)	\(291\)	\(10\)	\(521\)	\(521.0\)	\(521\)	\(10\)
\(0.5\)	\(291\)	\(291.0\)	\(291\)	\(10\)	\(521\)	\(521.0\)	\(521\)	\(10\)
\(1\)	\(291\)	\(291.0\)	\(291\)	\(10\)	\(519\)	\(520.8\)	\(521\)	\(9\)

With \(\alpha=0\) all the iterations are the same: the result is the local optimum reached from the greedy solution (\(319\) for TSP20, \(514\) for KP20), in every run. A little randomization is enough to reach the optimum in every run on these instances; with \(\alpha=1\) the constructions are random, and on KP20 one run misses the optimum.

Next: 32.9 Large neighbourhood search