32.8 GRASP¶

Parte 4 · Algoritmi euristici · Capitolo 32 · Capitolo 32: Metaeuristiche · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Metaeuristiche · App: TSP: simulated annealing e tabu search

La greedy randomized adaptive search procedure (indicata con \(GRASP\)) è un metodo multi-start: a ogni iterazione costruisce una soluzione con un algoritmo greedy randomizzato, che sceglie l'elemento successivo a caso fra i candidati migliori (la restricted candidate list, RCL) invece di prendere sempre il migliore, e migliora la soluzione con una ricerca locale. Si restituisce il miglior ottimo locale trovato.

Lo pseudocodice di \(GRASP\) per il KP, con l'algoritmo greedy randomizzato per efficienza e KPLOCALSEARCH, è il seguente:

Algoritmo: GRASP per il KP

Input: istanza del KP \(p[1..n]\), \(w[1..n]\), \(c\); parametro \(\alpha\in[0,1]\); numero di iterazioni \(maxIter\)

Output: migliore soluzione trovata

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)\) ▹ costruzione ricerca locale

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\) ▹ capacità residua

10while qualche oggetto con \(x[j]=0\) ha \(w[j]\le rc\) do

11\(e_{\max}\), \(e_{\min} :=\) massimo e minimo di \(p[j]/w[j]\) su questi oggetti candidati

12\(RCL :=\) candidati con \(p[j]/w[j] \ge e_{\max} - \alpha\,(e_{\max}-e_{\min})\), per \(p[j]/w[j]\) non crescente

13\(j :=\) l'elemento di \(RCL\) in posizione \(1+\lfloor \textsc{Rand}()\cdot |RCL|\rfloor\)

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

15end

16return \(x\)

Esegui in Colab:Python C++

La \(GRASP\) è stata introdotta da Feo e Resende (1989) per il problema del set covering e presentata come metaeuristica generale in Feo e Resende (1995). La costruzione randomizzata con una restricted candidate list è quella del capitolo «Euristiche costruttive».
La RCL è definita da una soglia sul punteggio greedy, controllata da \(\alpha\):

KP (massimizzare l'efficienza \(p_j/w_j\) degli oggetti che entrano):

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

TSP (minimizzare la distanza dall'ultima città \(\ell\) del giro parziale):

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

Con \(\alpha=0\) la RCL contiene solo i candidati migliori, e la costruzione è l'algoritmo greedy: ogni iterazione costruisce la stessa soluzione (a meno di pareggi), e la \(GRASP\) è una sola ricerca locale. Con \(\alpha=1\) la RCL contiene tutti i candidati, e la costruzione è casuale. I valori intermedi danno soluzioni diverse (diversificazione) e buone (una buona partenza per la ricerca locale, che poi intensifica).
Le iterazioni della \(GRASP\) sono indipendenti: niente viene appreso dall'una all'altra, e le iterazioni si possono eseguire in parallelo. Alcune estensioni aggiungono memoria: la GRASP reattiva adatta \(\alpha\) ai risultati, e il path relinking esplora le soluzioni fra due ottimi locali buoni.

Esempio 32.8: \(GRASP\) sull'istanza di riferimento del KP

Con \(\alpha=\frac12\) e \(seed=2\) (numeri casuali \(0.0000\), \(0.2631\), \(0.5112\), \(0.9173\)) eseguiamo due iterazioni. Le efficienze sono \(\frac{10}{5}=2\), \(\frac74=1.75\), \(\frac63=2\), \(\frac43\approx 1.33\).

Iterazione 1. Con \(rc=9\) tutti gli oggetti entrano: \(e_{\max}=2\), \(e_{\min}=\frac43\), la soglia è \(2-\frac12\cdot\frac23=\frac53\approx 1.67\), e \(RCL=(1,3,2)\). Con \(u=0.0000\) si sceglie il primo elemento: l'oggetto \(1\), \(rc=4\). I candidati sono gli oggetti \(2\), \(3\), \(4\), la soglia è ancora \(\frac53\), \(RCL=(3,2)\), e \(u=0.2631\) sceglie la posizione \(1+\lfloor 2\cdot 0.2631\rfloor=1\): l'oggetto \(3\), \(rc=1\), e nessun oggetto entra. La costruzione dà \(\{1,3\}\), di profitto \(16\); KPLOCALSEARCH fa uscire l'oggetto \(3\) ed entrare l'oggetto \(2\): \(\{1,2\}\), profitto \(17\).

Iterazione 2. \(RCL=(1,3,2)\) e \(u=0.5112\) sceglie la posizione \(1+\lfloor 3\cdot 0.5112\rfloor=2\): l'oggetto \(3\), \(rc=6\). I candidati sono gli oggetti \(1\), \(2\), \(4\), la soglia è \(\frac53\), \(RCL=(1,2)\), e \(u=0.9173\) sceglie la posizione \(2\): l'oggetto \(2\), \(rc=2\). La costruzione dà \(\{2,3\}\), di profitto \(13\), una soluzione diversa e peggiore di quella greedy; la ricerca locale fa uscire l'oggetto \(3\) ed entrare l'oggetto \(1\): \(\{1,2\}\), profitto \(17\).

\(GRASP(I)=17=z(I)\). Su questa istanza piccola ogni partenza porta all'ottimo; su istanze più grandi partenze diverse portano a ottimi locali diversi.

32.8.1 GRASP per il TSP, e l'effetto di \(\alpha\)¶

Per il TSP la costruzione randomizzata è l'euristica nearest neighbour con una RCL: dall'ultima città \(\ell\) del giro parziale, la città successiva si sceglie a caso fra le città non visitate la cui distanza da \(\ell\) è al più \(d_{\min}+\alpha(d_{\max}-d_{\min})\), e la ricerca locale è TWOOPTLS.
La tabella riporta i risultati della \(GRASP\) con \(20\) iterazioni su TSP20 e su KP20, per \(10\) esecuzioni (\(seed=1,\dots,10\)): valore minimo, medio e massimo della soluzione migliore, e numero di esecuzioni che raggiungono l'ottimo.

	TSP20 (\(z(I)=291\))				KP20 (\(z(I)=521\))
\(\alpha\)	min	media	max	ottime	min	media	max	ottime
\(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\)

Con \(\alpha=0\) tutte le iterazioni sono uguali: il risultato è l'ottimo locale raggiunto dalla soluzione greedy (\(319\) per TSP20, \(514\) per KP20), in ogni esecuzione. Basta un po' di randomizzazione per raggiungere l'ottimo in ogni esecuzione su queste istanze; con \(\alpha=1\) le costruzioni sono casuali, e su KP20 un'esecuzione manca l'ottimo.

Avanti: 32.9 Large neighbourhood search