32.9 Large neighbourhood search¶
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 large neighbourhood search (indicata con \(LNS\)) migliora una soluzione distruggendone una parte e riparandola: un metodo di distruzione toglie alcuni elementi (oggetti, città, lavori) dalla soluzione corrente, un metodo di riparazione li reinserisce, e la nuova soluzione sostituisce quella corrente se è soddisfatto un criterio di accettazione. L'intorno di una soluzione è l'insieme di tutte le soluzioni che distruzione e riparazione possono produrre, ed è grande.
- Lo pseudocodice di \(LNS\) per il TSP, che toglie \(q\) città casuali e le reinserisce con l'inserimento più economico (cheapest insertion), è il seguente:
Algoritmo: Large neighbourhood search per il TSP
-
La \(LNS\) è stata introdotta da Shaw (1998) per problemi di vehicle routing, in cui la riparazione era fatta con la constraint programming. La dimensione dell'intorno cresce molto rapidamente con il numero \(q\) di elementi tolti: per il TSP ci sono \(\binom{n-1}{q}\) modi di scegliere le città tolte, e molti modi di reinserirle. Un intorno del genere non si può elencare e valutare mossa per mossa, come in una ricerca locale: viene esplorato implicitamente, dal metodo di riparazione.
-
Il metodo di riparazione è un sotto-algoritmo: un'euristica costruttiva (cheapest insertion, FFD), o un algoritmo esatto per il sottoproblema lasciato dal metodo di distruzione. Più forte è la riparazione, migliore è il miglior vicino trovato; più grande è \(q\), più grande è l'intorno, e più costosa la sua esplorazione.
-
Il metodo di distruzione diversifica (di solito è casuale, e \(q\) controlla quanto lontano va la ricerca); il metodo di riparazione intensifica (ricostruisce la parte distrutta nel modo migliore possibile). Togliere elementi correlati (città vicine fra loro, oggetti degli stessi contenitori) rende la riparazione più efficace che togliere elementi non correlati, che possono solo essere rimessi dov'erano.
Esempio 32.9: \(LNS\) sull'istanza di riferimento del TSP
Dal giro nearest neighbour \((1,3,2,4,5)\) di lunghezza \(25\), con \(q=2\) e \(seed=1\). Il primo numero casuale \(0.0000\) toglie la città in posizione \(2+\lfloor 4\cdot 0.0000\rfloor=2\), la città \(3\); il giro parziale è \((1,2,4,5)\), e \(0.1315\) toglie la città in posizione \(2+\lfloor 3\cdot 0.1315\rfloor=2\), la città \(2\). Il giro parziale \((1,4,5)\) ha lunghezza \(2+7+9=18\). Cheapest insertion della città \(3\):
quindi la città \(3\) va fra \(5\) e \(1\): \((1,4,5,3)\). Cheapest insertion della città \(2\):
quindi la città \(2\) va fra \(4\) e \(5\): \((1,4,2,5,3)\), di lunghezza \(18\), accettato. È il giro ottimo, percorso nel verso opposto: un solo passo di distruzione e riparazione ha cambiato quattro lati del giro.
32.9.1 Large neighbourhood search per il BPP: riparazione euristica ed esatta¶
-
Per il BPP il metodo di distruzione naturale svuota contenitori: il contenitore meno carico, che è quello di cui vorremmo liberarci, e \(q-1\) altri contenitori scelti a caso. Il metodo di riparazione reimpacchetta gli oggetti tolti in contenitori nuovi, mentre gli altri contenitori restano come sono. Il nuovo impacchettamento è accettato se usa meno contenitori, o lo stesso numero di contenitori e un valore dell'obiettivo ausiliario \(\sum_b(\sum_{j\in P_b}w_j)^2\) non minore: sui plateau dell'obiettivo piatto, la ricerca si muove verso contenitori più pieni.
-
La riparazione risolve un sottoproblema di BPP, sui soli oggetti tolti, e può farlo in due modi: con FFD, oppure in modo esatto, con un branch-and-bound che prova ogni contenitore per ogni oggetto e conserva l'impacchettamento con il minor numero di contenitori. Il sottoproblema ha solo gli oggetti di \(q\) contenitori, quindi una riparazione esatta è sostenibile.
Algoritmo: Large neighbourhood search per il BPP
Esempio 32.10: \(LNS\) sull'istanza di riferimento del BPP
Partiamo dall'impacchettamento calcolato da First Fit, \(P_1=\{1,4\}\), \(P_2=\{2,5\}\), \(P_3=\{3\}\), \(P_4=\{6\}\), con carichi \((7,6,5,3)\), e usiamo \(q=2\), riparazione con FFD e \(seed=3\) (numeri casuali \(0.0000\), \(0.3946\), \(0.2668\), \(0.3760\)). A ogni iterazione si svuota il contenitore meno carico, insieme al contenitore in posizione \(1+\lfloor 3u\rfloor\) fra gli altri tre.
| it | carichi | svuotati | oggetti | FFD | \(nb'\) | \(\sum_b(\cdot)^2\) |
|---|---|---|---|---|---|---|
| \(1\) | \((7,6,5,3)\) | \(P_4,P_1\) | \(\{1,4,6\}\) | \(\{1,4\}, \{6\}\) | \(4\) | \(119\to 119\) |
| \(2\) | \((6,5,7,3)\) | \(P_4,P_2\) | \(\{3,6\}\) | \(\{3\}, \{6\}\) | \(4\) | \(119\to 119\) |
| \(3\) | \((6,7,5,3)\) | \(P_4,P_1\) | \(\{2,5,6\}\) | \(\{2,6\}, \{5\}\) | \(4\) | \(119\to 127\) |
| \(4\) | \((7,5,7,2)\) | \(P_4,P_2\) | \(\{3,5\}\) | \(\{3,5\}\) | \(3\) | \(127\to 147\) |
Le iterazioni \(1\) e \(2\) si limitano a rimescolare gli oggetti e mantengono gli stessi carichi (l'obiettivo ausiliario resta \(119\), e il nuovo impacchettamento è accettato perché non è peggiore); l'iterazione \(3\) costruisce il contenitore pieno \(\{2,6\}\), portando l'obiettivo ausiliario a \(127\); l'iterazione \(4\) svuota i contenitori \(\{5\}\) e \(\{3\}\), e FFD mette insieme gli oggetti \(3\) e \(5\): \(3\) contenitori, l'ottimo, e la ricerca si ferma poiché \(nb=\LB\).
- Su BPP24, partendo dall'impacchettamento FFD (\(10\) contenitori), con \(200\) iterazioni e \(seed=1,\dots,10\), il risultato dipende dalla riparazione:
| \(q\) | riparazione | contenitori alla fine (10 semi) | iterazioni per arrivare a \(9\) |
|---|---|---|---|
| \(2\) | FFD | \(10,10,10,10,10,10,10,10,10,10\) | mai |
| \(2\) | esatta | \(10,10,10,10,10,10,10,10,10,10\) | mai |
| \(3\) | FFD | \(10,10,10,10,10,10,10,10,10,10\) | mai |
| \(3\) | esatta | \(9,9,9,9,9,9,9,9,9,9\) | \(4,4,12,38,3,20,5,2,7,5\) |
| \(4\) | FFD | \(10,10,10,10,10,10,10,10,10,10\) | mai |
| \(4\) | esatta | \(9,9,9,9,9,9,9,9,9,9\) | \(2,3,9,12,4,5,1,3,10,2\) |
- Con la riparazione FFD, la \(LNS\) non migliora mai l'impacchettamento FFD: gli oggetti tolti da un impacchettamento FFD vengono reimpacchettati da FFD nello stesso modo. Con la riparazione esatta e \(q\ge 3\) raggiunge l'ottimo in ogni esecuzione, in poche iterazioni: trova tre contenitori i cui oggetti entrano in due, ed è ciò che FFD non vede. Con \(q=2\) anche la riparazione esatta fallisce, perché gli oggetti di due contenitori di un impacchettamento FFD non entrano mai in uno solo.
Un intorno grande si esplora risolvendo un sottoproblema: la parte della soluzione lasciata libera dal metodo di distruzione viene riottimizzata, mentre il resto è fissato. Più potente è il metodo che risolve il sottoproblema, più potente è l'intorno.
32.9.2 Adaptive large neighbourhood search¶
- Quale metodo di distruzione funzioni meglio dipende dall'istanza, e dalla fase della ricerca. La LNS adattiva (ALNS), introdotta da Ropke e Pisinger (2006), usa più metodi di distruzione (e di riparazione), ne sceglie uno a caso a ogni iterazione, e impara quali funzionano, assegnando a ogni metodo \(o\) un peso \(w_o\):
dove \(\rho\in[0,1]\) è il fattore di reazione e il punteggio \(\psi\) premia l'esito dell'iterazione in cui \(o\) è stato usato: \(\psi=3\) se la nuova soluzione è la migliore trovata finora, \(2\) se è migliore di quella corrente, \(1\) se è altrettanto buona, \(0\) se è peggiore.
Algoritmo: Adaptive large neighbourhood search per il TSP
-
WORSTREMOVAL toglie, \(q\) volte, la città la cui rimozione accorcia di più il giro: la città \(v\), fra \(a\) e \(b\), di massimo \(d_{av}+d_{vb}-d_{ab}\). È un metodo di distruzione deterministico e greedy: toglie le città che sembrano mal posizionate.
-
Su TSP20, dal giro nearest neighbour, con \(q=5\), \(200\) iterazioni e \(\rho=0.1\), la ALNS raggiunge l'ottimo in \(7\) esecuzioni su \(10\) (media \(299.4\)).
-
Alla fine il peso della rimozione casuale è fra \(0.77\) e \(0.98\), il peso della worst removal fra \(0.03\) e \(0.08\): il metodo ha imparato che, da un giro buono, togliere le città peggio posizionate e reinserirle con cheapest insertion ricostruisce quasi sempre un giro non migliore, e ha quasi smesso di usarla.
-
In queste esecuzioni la \(LNS\) semplice con rimozione casuale (\(q=5\)) fa leggermente meglio: l'adattività ripaga quando ci sono molti metodi, di qualità ignota, ed esecuzioni lunghe.
Avanti: 32.10 Metodi basati su popolazioni: algoritmi genetici e memetici